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

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

(淮北师范大学物理与电子信息学院，安徽淮北 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]等。本文采用TSPLIB中的TSP数据作为此次实验数据及优化结果的对比数据。

1.2 基本SGO算法

SGO算法是一种基于社会群体学习和提升自身解决问题能力的新型优化算法。在现实生活中，很多工作或者难题的处理需要多方面因素的参与。当学习者欠缺此方面的能力时，须向周围或拥有此项能力的个体学习，以便达到相应的目的。SGO算法是基于此种思想提出的，其实现过程主要包含三个步骤：种群初始化、提高阶段学习、获得阶段学习。

1.2.1 种群初始化

随机初始化种群P，如式(1)所示。

Xi,j=xmin+r*(1,D)*(xmax-xmin).

(1)

其中，i=1,2,…,N，j=1,2,…,D，N为种群的规模，D为变量的维数；r∈[0,1]；xmax与xmin分别为变量的上限与下限；P为进化种群，X为个体位置。

1.2.2 提高阶段学习

SGO算法在此阶段采用的学习策略如式(2)所示。

Xnewi,j=c*Xoldi,j+r*(gbestj-Xoldi,j).

(2)

其中，c为自我反省参数，c∈[0,1]。文献[1]实验结果表明，当c为0.2时,算法效果较好；gbestj为当前最优个体的第j维变量。Xnewi,j与Xoldi,j分别为第i个个体更新前后的第j维变量。

1.2.3 获得阶段学习

在获得阶段，每个个体从种群中随机选择一个个体作为学习对象，并结合当前代群体的最优个体信息进行学习，具体学习方法如式(3)(4)所示。

Iff(Xi)isbetterthanf(Xk)：

Xnewi,j=Xoldi,j+r1*(Xi,j-Xk,j)+r2*(gbestj-Xi,j).

(3)

Else

Xnewi,j=Xoldi,j+r1*(Xk,j-Xi,j)+r2*(gbestj-Xi,j).

(4)

其中，Xi,j与Xk,j分别为个体i和个体k的第j维变量；Xnewi,j与Xoldi,j分别为第i个个体更新前后的第j维变量；gbestj为当前代最优个体的第j维变量。

2 离散SGO算法

SGO算法最初是用来优化连续域函数问题的，而在实际工程应用中有很多组合优化问题属于离散域范畴。基于这个前提，本文在基本SGO算法的基础上发展了离散SGO算法来求解离散化问题。离散化问题的典型代表是TSP问题，本文以提出的离散SGO算法来解决TSP问题，提出的离散SGO算法易于实现。操作步骤：首先，使用随机初始化策略产生一个具有NP个学习者的种群；其次，获取此种群中的最优个体作为教师；然后，在提高阶段和获得阶段分别采用交叉、变异操作来生成新学习者，以此提高种群的多样性；最后，通过对原学习者和新学习者的比较进行种群更新。

2.1 个体初始化和教师的确定

在此阶段TSP问题中，采用随机初始化方法生成学习者群体。假设群体的大小为NP，求解的TSP问题的城市规模为N，则初始化后会生成一个NP×N的矩阵。矩阵中的第i行对应着第i个学习者个体，学习者个体的每一列代表一个城市，从第1列到第N列代表着对应城市遍访顺序。第i个学习者个体的初始化公式如下：

Xi=randperm(N).

(5)

其中，randperm(N)表示产生一个包含数值1到N的随机排列的N维向量。

在基本SGO算法中，种群中个体向当代本群的最好个体(即教师)学习知识，提高自身的能力，学习者的更新是根据教师来实现的。Teacher为种群中的最好学习者个体，其表达式如下所示：

Teacher=Best(X1,X2,…,Xi).

(6)

其中，X1,X2,…,Xi为种群中学习者个体。

2.2 离散SGO算法的提高阶段

在基本SGO算法的提高阶段，学习者是根据式(2)更新知识的，但这适用于优化连续域问题，而TSP问题属于离散化范畴。因此，应重新定义学习者的更新方法来求解TSP问题。在提高阶段的更新公式如下所示：

TXi=Xi⊗Teacher.

(7)

其中，⊗表示交叉操作。

交叉操作的具体步骤可以概述如下：

假设以种群中任意两个学习者个体A和B为例：

然后，随机从A、B中选择两段基因位，并交换两段基因位中相对应的元素，得到：

由于在AA、BB中出现了遍历重复，根据位置合法性检测，逐一交换，得到newA、newB：

以上交叉操作完成后，接着执行变异操作来产生新的学习者，更新公式如下：

newXi=ΘTXi.

(8)

其中，Θ表示变异操作。

在本文中，种群中采用的是翻转变异，其具体操作步骤如下：在城市序列中随机选择两基因位，再将这两基因位内的子序列按反序插入原位置。如序列newA的两基因位为2和6，则经翻转后，得到新学习者newAA如下：

与基本SGO算法一样，在提高阶段这两部分操作完成后，种群会产生新的学习者，新的学习者的学习能力可能比原先的学习者的能力强。若是这样，种群中学习能力强的学习者将会取代能力差的个体，其更新可以描述为：如果f(newXi)

2.3 离散SGO算法的获得阶段

在基本SGO算法的获得阶段，种群中学习者Xi是根据当前从种群中随机选择的学习者Xj之间的差异及当前种群最好学习者的信息进行知识更新的。在离散SGO算法中，此操作可以被定义如下：

TXi=Xi⊗Xj.

(9)

TXi=Xi⊗Teacher.

(10)

其中，⊗表示交叉操作，与提高阶段的交叉操作一样；Teacher=Best(X1,X2,…,Xi)。

同提高阶段一样，当交叉操作完成后，接着进行变异操作来产生新的学习者。获得阶段的变异采用的也是翻转变异，其操作流程与提高阶段相同，表达式如下：

newXi=ΘTXi.

(11)

其中，Θ表示变异操作。

与基本SGO算法一样，在获得阶段这两部分操作完成后，种群会产生新的学习者。学习能力强的学习者将会取代能力差的个体，其更新可以描述如下：如果f(newXi)

3 求解TSP的离散SGO算法

为了验证离散SGO算法的有效性与正确性，选用6个TSP标准测试问题进行实验仿真测试，并与其他4个算法进行比较，得出相应的结果。

3.1 参数设置

为了检验算法的有效性，选取在TSPLIB库中不同城市样例。选取的比较算法在合适的参数下方能达到较为理想的结果。本文选取的4个比较算法是分别是ACO[8]、ABC[9]、GA和PSO算法。GA、PSO与SGO算法的参数设置如下：

SGO：pc=2，pm=0.1；

GA：pc=0.8，pm=0.4；

PSO：pm=0.3，个体经验保留概率为0.25，全局经验保留概率为0.55。

本文所有算法的种群规模均设置成40，迭代次数设置为1000。为了测试结果的真实性，每个算法独立运行20次。

3.2 仿真结果比较

各算法仿真结果如表1所示。KOS表示在TSPLIB中已知的最好解，加粗的数字表示各个算法对不同城市个数的TSP问题独立运行20次时所得到的平均最优结果。

表1 试验结果的比较

从表1可以看出，对于burma14问题，PSO、GA与SGO算法在独立运行20次后的平均值均能达到已知最优解30.87；对于Oliver30问题，ACO、SGO的最优解均是423.74，比已知最优解相差0.24，相比较其他3种算法效果要好；对于chn31问题，SGO算法的最优结果达到了已知最优结果15381，而其他4种算法最优解均不能达到已知最优解15381；对于dantzig42问题，SGO算法最优解692.03，要比已知最优解699好，ABC算法同样达到了已知最优解；对于st70和kroA100问题，SGO算法虽都未能达到已知最优解，但是较其他3种算法结果要好，更接近已知最优解。从表1中数据可以看出，SGO算法在求解TSP问题上有明显的优势。

为了证明SGO算法的有效性，本文以chn31为例进行简单证明。图1为SGO算法在chn31下最优路径回路图，图2为SGO算法在chn31下的迭代收敛曲线图。对于SGO算法，随着迭代的进行，算法收敛速度较快(仅迭代了180代左右就实现了最优)，从而搜索路径更优(该算法得到的最短路径长度为15381)。由图2可以看出，在大致迭代180代后，各代的最短路径和平均距离保持一致。

图1 SGO算法chn31最优路径图

图2 SGO算法chn31迭代收敛曲线

4 结语

为了更好地求解TSP问题，本文将基本SGO算法进行了离散化处理。在算法的提高阶段和获得阶段分别引入了交叉与变异操作，增加了算法的多样性，减小了算法整体陷入局部最优的可能性。对6个不同的TSP问题进行了仿真试验，结果证明SGO算法应用在TSP问题上的有效性。但从实验数据可知，随着城市规模的增大，离散SGO算法的性能也随之降低。因此,如何改进SGO算法来解决大城市规模问题将是一个新的研究方向。

[参考文献]

[1]Satapathy S, Naik A. Social group optimization (SGO): a new population evolutionary optimization technique[J].Complex & Intelligent Systems, 2016(3):1-31.

[2]Naik A,Satapathy S C,Ashour A S,et al.Social group optimization for global optimization of multimodal functions and data clustering problems[J].Neural Computing & Applications,2016:1-17.

[3]Lawler E L.The traveling salesman problem:a guided tour of combinatorial optimization[M].Wiley,1985:535-536.

[4]Wang Y.The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem[J].Computers & Industrial Engineering,2014(70):124-133.

[5]Liu Y H.Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem[J].Applied Mathematics and Computation,2010(1):125-137.

[6]程毕芸,鲁海燕,黄洋,等.求解TSP的自适应优秀系数粒子群优化算法[J].计算机应用,2017(3):750-754.

[7]Chen S M,Chien C Y.Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J].Expert Systems with Applications,2011(12):14439-14450．

[8]Liu Yin,Ma Liang.Fuzzy artificial bee colony algorithm for solving traveling salesman problem[J].Application Research of Computers,2013(9):2694-2696.

[9]胡中华,赵敏.基于人工蜂群算法的TSP仿真[J].北京理工大学学报,2009(11):978-982.