离散社会群体优化算法求解旅行商问题

刘亚军，陈得宝，邹 锋，王苏霞,吴乐会

(淮北师范大学物理与电子信息学院，安徽淮北 235000)

[通讯作者]陈得宝(1975- )，男，教授，硕士生导师，博士，从事智能计算、模式识别研究。

社会群体优化算法(SGO)是Suresh Satapathy等于2016年提出的一种新型优化算法[1]，源自社会群体学习知识提高能力的过程。此算法操作简单，易于实现，故在一些问题优化中取得了良好的效果[2]。与其他算法相比，SGO算法在两个学习阶段都以群体最好的个体作为学习向导，算法的收敛速度较快。因此，在优化领域，SGO算法在连续域问题求解上取得了不错的效果。SGO算法作为一种新型优化算法，在离散域问题上的应用较少。为了使SGO算法在离散问题的解决中也取得不错的效果，本文研究离散后的SGO算法在TSP中的应用，并分析了仿真后的结果。

本文主要对SGO算法进行离散化处理，并用于求解TSP问题。首先介绍TSP问题模型和基本SGO算法，接着将基本SGO算法的运算规则进行离散化处理，最后通过TSP问题的仿真实验。结果表明，社会群体优化算法在解决TSP问题中具有良好的性能。

1 TSP模型和基本SGO算法

1.1 TSP问题模型

旅行商问题(Traveling Salesman Problem，TSP)是一个典型的NP完全问题[3]。TSP问题目的：从某一个城市出发，找到一条通过所有城市再回到起点的最短路径，每座城市必须且只能访问一次。TSP已经被证明是NP完全问题，且在车辆调度、物流管理等方面具有广泛的应用[4]。研究人员对此提出多种优化算法来解决TSP问题,都取得了不错的效果。如遗传算法(GA)[5]、粒子群优化算法(PSO)[6]、蚁群算法(ACO)[7]等。……