求解TSP的改进信息素二次更新与局部优化蚁群算法

许凯波, 鲁海燕，程毕芸，黄 洋

(江南大学 理学院，江苏 无锡 214122)

求解TSP的改进信息素二次更新与局部优化蚁群算法

许凯波, 鲁海燕*，程毕芸，黄 洋

(江南大学 理学院，江苏 无锡 214122)

(*通信作者电子邮箱luhaiyan@jiangnan.edu.cn)

针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷，提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新，以提高构成潜在最优解的子路径被选择的概率，从而加快算法的收敛。然后，在搜索过程中，当蚁群陷入局部最优时，使用随机插入法对局部最优解中城市的排序进行调整，以增强算法跳出局部最优解的能力。将改进算法应用于若干经典的旅行售货商问题(TSP)进行仿真实验，实验结果表明，对于小规模的TSP, IPDULACO可以在较少的迭代次数内获得已知最优解；对于较大规模的TSP, IPDULACO可以在较少的迭代次数内获得更精确的解。因此，IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度，可以高效求解TSP。

旅行售货商问题；蚁群算法；信息素二次更新；局部优化

0 引言

旅行售货商问题(Traveling Salesman Problem, TSP)是经典的组合优化问题[1]，现实生活中的许多问题都可以归结为TSP，如邮路问题、装配线上的螺母问题和产品的生产安排问题等。因此，TSP的有效求解在降低运输成本、提高生产效率等方面具有重要意义。由于TSP是NP难(Non-deterministic Polynomial hard, NP-hard)问题[2]，随着问题规模的扩大，问题解的数量呈指数式增长，目前尚无求解该问题的有效算法。一般地，求解TSP的算法大体可以分为两类：精确算法和启发式算法。对于小规模的TSP，用精确算法即可获得最优解；对于中大规模的TSP，精确算法由于求解时间和空间消耗过大而完全不可行，一般用启发式算法来求解。精确算法主要有分枝定界法[3]、线性规划法[4]和动态规划法[5]等。启发式算法包括：最邻近算法[6]、贪婪算法[7]、遗传算法(Genetic Algorithm, GA)[8]、模拟退火(Simulated Annealing, SA)[9]算法、禁忌搜索(Tabu Search, TS)[10]算法、粒子群(Particle Swarm Optimization, PSO)[11]算法、蚁群(Ant Colony Optimization, ACO)[12]算法等。

蚁群算法[13-14]是根据蚂蚁群体在觅食过程中所体现出的智能行为提出的。该算法具有正反馈、分布式、并行式、自组织等优点，经过众多学者的不断探索研究，蚁群算法已经被成功地用于解决许多实际问题，譬如数据挖掘、参数辨识、图像处理、图形着色、分析化学、TSP等。但是，蚁群算法也存在迭代次数多、收敛速度慢以及容易陷入局部最优等缺陷。针对以上缺陷，国内外学者也提出了很多的改进策略。比如：Dorigo等[12]提出了蚂蚁系统，该算法使用最优选择与随机选择结合的路径选择方式，以及局部更新和全局更新的信息素更新策略，来提高算法的全局搜索能力，但最优解的精度有待提高；Stutzle等[15]提出了最大最小蚁群系统(Max-Min Ant System, MMAS)，通过对路径上的信息素进行上下界的限制避免算法陷入局部最优；郑松等[16]提出了动态调整选择策略的改进蚁群算法，通过适当刺激蚂蚁尝试具有较弱信息素的解，以提高所得解的全局性，但迭代次数较多，收敛速度较慢；吴华锋等[17]提出了基于自然选择策略的蚁群算法求解TSP，通过随机进化因子的随机性增强算法跳出局部最优解的概率，以及信息素二次更新规则加快算法的收敛。本文将对文献[17]提出的信息素二次更新规则作进一步研究，分析其存在的不足，提出一种改进的信息素二次更新策略，进一步提高算法的收敛速度；此外，在算法中引入一种局部优化策略，当最优解连续若干次迭代后没有改善时，使用随机插入法对局部最优解中城市的排序进行调整，以增强算法跳出局部最优解的能力。结合以上两种改进策略提出一种求解TSP的改进信息素二次更新局部优化蚁群算法(Ant Colony Optimization algorithm based on Improved Pheromones Double Updating and Local optimization, IPDULACO)。通过对TSP的仿真实验，验证了改进算法的有效性。

1 研究基础

首先给定一个赋权图G(V,E)，其中V={1,2,…,n}为顶点(城市)的集合，E={(i,j,dij)|i,j∈n,dij∈R+}为赋权边(两个城市之间的距离)的集合，假设：

(1)

则经典TSP的数学模型[18]为：

(2)

(3)

其中：|S|为图S的顶点数。式(1)和式(3)限定经过所有顶点一次且仅一次，式(2)为TSP的目标函数，即求一条距离最短的哈密顿回路。

2 改进的蚁群算法

2.1 基本ACO算法

2.1.1 蚁群算法基本思想

蚂蚁在寻找食物时，综合考虑路径长度和路径上信息素两个方面进行路径选择(蚂蚁会在其走过的路径释放信息素，其他蚂蚁能够感知这种信息素并优先选择信息素浓度较高的路径)。开始时，路径上的信息素浓度较低，蚂蚁主要根据路径长度进行选择，而且会以较大的概率选择较短的路径。随着时间的推移，各路径上的信息素逐渐积累增多；且越短的路径，走过的蚂蚁越多，路径上残留的信息素越多，选择走该路径的蚂蚁也越多，如此形成一个正反馈。最终，蚂蚁找到一条从巢穴到食物源的最优路径。

2.1.2 求解TSP的蚁群算法

(4)

其中：α为信息素重要程度因子；β为启发函数重要程度因子；cityk(k=1,2,…,m)为蚂蚁k已经访问过的城市集合，其随时间动态更新。经过n个时刻，所有蚂蚁都寻找到一条回路，一次循环结束。同时，蚂蚁释放在各个城市间连接路径上的信息素也在逐渐消失，因此，当所有蚂蚁完成一次循环后，按式(5)和式(6)调整各个城市间连接路径上的信息素浓度：

(5)

(6)

2.2 改进的蚁群算法求解TSP

2.2.1 信息素更新策略

在基本蚁群算法中，蚂蚁在选择路径时主要取决于节点间的距离，即距离越短，该路径被选择的概率越大，距离越长，该路径被选择的概率越小。因为全局最优路径中的某些子路径(子路径为任意两城市连接构成的路径)可能较长，所以该子路径被选择的概率较小，导致蚂蚁错过构成潜在全局最优解的子路径。为了弥补这个缺陷，文献[17]提出路径贡献度(ContributionDegreeofSub-Path,CDSP)的概念，定义为每次迭代蚁群找到的最优解中，子路径与本次迭代最优路径的比值，如式(7)所示。并提出一种信息素更新策略：当按式(5)和式(6)完成路径信息素的首次更新后，对每次迭代最优路径上的各子路径按式(7)所示进行路径贡献度判断，按式(8)和式(9)所示再次更新信息素，即增加路径贡献度大于给定的路径贡献阈值的子路径上的信息素，从而提高该子路径被选择的概率。

CSCDij=D(i,j)/Lb(t)

(7)

(8)

(9)

CSCDij=D(i,j)/Lgb(t)

(10)

其中：Lb(t)是第t次迭代后蚁群找到的此次迭代的最优解；τij(t+1)是第t次迭代后路径(i,j)上的信息素总量。

文献[17]提出的信息素更新策略确实可以提高构成潜在全局最优解的子路径被选择的概率。但是考虑到每次迭代得到的最优解基本不相同，每次信息素二次更新的子路径也基本不同，导致构成潜在全局最优解的子路径信息素增量不明显，被选择的概率也没有有效提高。但是，相比每次迭代的最优解，每次迭代的当前全局最优解在每次迭代后不相同的概率较小，通常每经过一定次数的迭代后改变一次，这样在一定的迭代次数内，信息素二次更新的子路径一样，信息素增量明显，更有利于提高构成潜在全局最优解的子路径被选择的概率。而且，当前全局最优解所含子路径构成最优解的可能性更大，所以更应该对该条路径中满足条件的子路径进行信息素的二次更新，而不是每次迭代得到的最优路径。

基于以上分析，本文提出一种改进的信息素更新策略。首先，和基本蚁群算法一样，在每次迭代后，按式(5)和式(6)所示更新各个城市间连接路径上的信息素。然后，按式(10)对每次迭代后的当前全局最优路径中的子路径进行路径贡献度判断，而不是对每次迭代的最优路径，并对路径贡献度大于给定的路径贡献阈值的子路径按式(8)～(9)所示进行信息素的再次更新，其中Lgb(t)指t次迭代后蚁群搜索到的当前全局最优解，q0是路径贡献度阈值，通过实验验证，取q0=0.01时算法性能最优。

改进的信息素更新策略可以提高构成潜在最优解的子路径被选择的概率，加快算法的收敛；同时，为了提高算法跳出局部最优的能力，在算法中加入一种局部优化策略，以提高搜索的随机性和多样性。

2.2.2 局部优化策略

基本蚁群算法的信息素更新方式具有正反馈性。正反馈有利于算法的快速收敛，但优化后期较优路径上的信息素积累会较多，影响种群的多样性，算法容易陷入局部最优而停滞，最终导致求解质量的下降。因此，本文在算法中引入一种局部优化策略：每当算法陷入局部最优时，使用随机插入法对该局部最优解中城市的排序进行调整，以提高种群的多样性，增强算法跳出局部最优的能力。局部优化策略的具体方法如下：

设局部最优解(即当前全局最优解)为a1,a2,a3,a4,…,ai,ai+1,…,an-1,an,a1，其中ai为城市编号。对其进行局部优化：随机产生子路径集合((a1,a3),(ai,an))，这里以两条子路径(a1,a3)和(ai,an)为例，本文在仿真实验中设置子路径数等于城市个数。接着按子路径在集合中的顺序，在局部最优解中依次连接。先找到城市a1和城市a3的位置，将城市a3插入到城市a1后面，此时城市排列变为a1,a3,a2,a4,…,ai,ai+1,…,an-1,an,a1；再找到城市ai和城市an的位置，将城市an插入到城市ai的后面，最终得到城市排列(a1,a3,a2,a4,…,ai,an,ai+1,…,an-1,a1)。计算此时的适应度，判断解的质量是否提高，若解的质量提高，则更新全局最优解；否则不更新。继续随机产生子路径集合，按子路径在集合中的顺序在当前全局最优解上依次连接，如此迭代多次，本文在仿真实验中设置迭代30次。

2.2.3 改进ACO算法流程

本文改进ACO算法求解旅行商问题的简要流程如图1所示，基本步骤如下：

步骤1 算法开始，设置算法所需的参数，如蚂蚁数量，算法迭代次数N，算法最大迭代次数Nmax等。

步骤2 将蚂蚁随机放在不同的城市上，作为起始点。

步骤3 每只蚂蚁构建解空间，计算适应度值。

步骤4 按照式(5)和式(6)对各个城市间连接路径上的信息素进行实时更新。

步骤5 按照式(10)计算路径贡献度，按照式(8)判断确定路径贡献度大于路径贡献阈值的子路径并计算信息素二次增量，按照式(9)再次更新满足条件的子路径上的信息素。

步骤6 判断算法是否陷入局部最优，判断方法：比较本次迭代得到的全局最优解与上一次迭代得到的全局最优解，观察最优解是否得到改善，如果连续5次最优解都没有得到改善，则判定算法陷入局部最优，执行局部优化策略；否则进入步骤7。

步骤7 判断是否达到迭代的最大次数。若达到，则程序停止，输出最优解；若未达到，返回步骤2。

图1 本文改进算法流程

3 仿真实验与结果分析

为了验证改进算法的性能，本文选取了TSPLIB测试库中的部分案例(数据更新到2013年7月，网址为：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95)，使用Matlab编程，在CPU为i5- 430M、RAM为2GB的计算机上进行测试实验，并对不同算法的求解结果进行分析和比较，实验结果验证了本文改进算法的有效性。实验中选取了蚁群算法常用的一种参数取值的组合：m=n，α=1，β=5，ρ=0.1，Q=20，Nmax=100。

表1给出了五种算法分别在Oliver30、Eil51、Eil101和Ts225上进行20次独立实验的结果。其中，五种算法分别为：基本蚁群算法，基于文献[17]信息素二次更新策略的蚁群(ACObasedonPheromonesDoubleUpdating,PDUACO)算法，基于改进信息素二次更新策略的蚁群(ACObasedonImprovedPheromonesDoubleUpdating,IPDUACO)算法、基于局部优化策略的蚁群(ACObasedonLocalOptimization,LACO)算法以及本文提出的算法(IPDULACO)。

从表1可以看出，基于文献[17]信息素二次更新策略的蚁群算法(PDUACO)和基于改进信息素二次更新策略的蚁群算法(IPDUACO)都获得了Oliver30实例的已知最优解，但在其他3个实例上，基于改进信息素二次更新策略的蚁群算法(IPDUACO)求得的最优解更接近已知最优解，其中在Eil51实例上相比PDUACO提高了2.22%，且所有实例获得的平均值也更好，说明改进信息素二次更新策略使算法的性能得到了提高。此外，在4个TSP实例上，基于局部优化策略的蚁群算法(LACO)获得的最优解和平均值都优于基本蚁群算法，说明加入局部优化策略后算法的全局寻优能力得到了提高。同时加入两种改进策略的基本蚁群算法(即本文提出的改进算法IPDULACO)在4个TSP实例上求得的最优解的精度得到了进一步提高，其在Eil51实例上与已知最优解的偏差(偏差表示所得最优解与已知最优解之间的偏离程度)缩小到0.8%，可见本文所提的两种改进策略的有效性。

表1 不同算法求解结果比较

图2给出了ACO、PDUACO、IPDUACO和IPDULACO四种算法优化Oliver30问题的收敛曲线。从图2中可以看出：本文改进算法(IPDULACO)在18代收敛到最优解，基于改进信息素二次更新策略的蚁群算法(IPDUACO)也在50代收敛到最优解，而基于文献[17]信息素二次更新策略的蚁群算法(PDUACO)在65代才收敛，且收敛到的最优解为426.60(Oliver30已知最优解为423.74)。ACO算法虽然在10代收敛，但收敛到的最优解质量最差。由此可见，在收敛到已知最优解的前提下，本文改进算法的收敛速度更快。

图2 四种算法求解Oliver30的收敛曲线

图3给出了ACO和IPDULACO优化Ts225问题的收敛曲线，ACO在95代收敛，而本文改进算法(IPDULACO)在82代即收敛，再次说明了本文改进算法具有更快的收敛速度，且收敛到的最优值为130 955.48，精度也更高(ACO收敛到的最优值为131 434.97)。

图3 ACO和IPDULACO求解Ts225收敛曲线

为了进一步验证本文改进算法(IPDULACO)的性能，首先将IPDULACO的实验结果与求解TSP的4种改进ACO算法的实验结果进行了纵向比较，然后又与求解TSP的2种粒子群算法和遗传算法进行了纵向比较。表2给出了蚁群(ACO)算法[19]、蚁群算法驱动的遗传算法(AntColonyGeneticAlgorithm,ACGA)[19]、基于启发式遗传信息的蚁群遗传算法(HeuristicGeneticInformationbasedAntColonyGeneticAlgorithm,HGIACGA)[19]、新型蚁群算法(NewACO,NACO)[20]和本文改进算法(IPDULACO)在三组TSP分别运行10次的平均求解性能，其中偏差表示所得最优解与已知最优解之间的偏离程度。表2中ACO、ACGA、HGIACGA、NACO算法的结果来自文献[20]。从表2可以看出，IPDULACO的求解性能优于其他4种算法，偏差最小，说明IPDULACO具有较强跳出局部最优的能力，而且平均值也最低，表明IPDULACO也具有较好的稳定性。

表2 ACO、ACGA、HGIACGA、NACO和IPDULACO性能对比

表3给出了IPDULACO、离散粒子群(DiscretePSO,DPSO)算法[21]、自适应离散粒子群(Self-AdaptiveDPSO,SADPSO)算法[21]、遗传算法(GA)在3组TSP上的实验结果。其中DPSO、SADPSO算法的结果来自文献[21]，GA的参数设置为：最大迭代次数Maxgen=n，交叉概率Pc=0.9，变异概率Pm=0.05。除了在Burma14问题上，本文改进算法的平均值高于SADPSO外，其他两个问题本文改进算法获得的最优值和平均值都优于所对比的3种算法。图4为本文改进算法求得Eil51问题的最优路径图。

表3 DPSO、SADPSO、GA和IPDULACO性能对比

图4 IPDULACO求得Eil51最优路径

在与现有的几种算法纵向比较后，又将本文改进算法与其他几种常见的TSP求解算法进行了横向比较，结果如表4所示。其中包括：改进贪婪算法(IMprovedGReedyAlgorithm,IMGRA)[22]、自适应离散粒子群算法(Self-AdaptiveDiscreteParticleSwarm,SADPSO)[21]、文献[16]提出的动态调整选择策略的改进蚁群算法(AntColonyAlgorithmwithDynamicTransition, 简记为A16)和文献[23]提出的基于粒子群参数优化的改进蚁群算法(ImprovedAntColonyOptimizationAlgorithmbasedonParticleSwarmOptimization, 简记为A23)。

表4 不同算法求解Eil51性能比较

从表4可以看出：5种算法求解Eil51问题，IPDULACO获得的最优解最接近已知最优解，平均值除了比SADPSO略高外，比其他2种算法都低(IMGRA求解的平均值除外)，进一步说明了IPDULACO具有较强的全局搜索能力。

再用本文改进算法(IPDULACO)求解文献[24]中的TSP，并和文献[24]改进蚁群算法(ImprovedAntColonyOptimizationAlgorithm, 简记为A24)求得的最优解进行比较。14个城市的坐标分别为A(8，2)、B(0，4)、C(-1，6)、D(2，-1)、E(4，2)、F(6，0.5)、G(3，0)、H(10，3.7)、I(2.5，1.8)、J(-5，1)、K(7，0)、L(9，4)、M(11，3)、N(13，2)。实验中取蚁群算法常用的一种参数取值的组合：m=n，α=1，β=5，ρ=0.1，Q=20，Nmax=100。图5为两种算法所得最优路径对比。

图5 不同算法所得最优路径对比

图5(a)为文献[24]提出的改进蚁群算法求得的最优路径，最优路径为：A→I→B→C→J→D→G→E→F→K→N→M→H→L→A，最优路径长度为45.784 4；图5(b)为IPDULACO求得的最优路径，最优路径为：A→F→G→I→B→C→J→D→E→K→N→M→H→L→A，最优路径长度为45.562 0，显然IPDULACO的求解性能更优，提高了0.222 4，进一步说明IPDULACO具有较强的跳出局部最优的能力。

4 结语

本文针对蚁群算法收敛速度慢、容易陷入局部最优解的缺陷，提出一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。对每次迭代后当前全局最优路径中路径贡献度大于给定的路径贡献阈值的子路径进行信息素的二次更新，增大构成潜在最优解的子路径被选择的概率，提高算法的收敛速度；同时，在算法中引入一种局部优化策略来提高算法跳出局部最优解的能力。在TSP上的仿真实验也表明，改进的蚁群算法可以在迭代次数较少的情况下获得小规模TSP的已知最优解；对于较大规模TSP,改进算法可以在迭代次数较少的情况下获得更精确的解。如何选取路径贡献度阈值以提高算法的鲁棒性，以及如何提高求解大规模TSP实例最优解的精度还需在今后作进一步研究。

)

[1]WILLIAMJC.迷茫的旅行商:一个无处不在的计算机算法问题[M].随春宁,译.北京:人民邮电出版社,2013:178-183.(WILLIAMJC.InPursuitoftheTravelingSalesman:MathematicsattheLimitsofComputation[M].SUICN,translated.Beijing:Posts&TelecomPress, 2013: 178-183.)

[2]GAREYMR,JOHNSONDS.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[M].NewYork:W.H.FreemanandCompany, 1979: 56-59.

[3]PADBERGMW,RINALDIG.Optimizationofa532-citysymmetricgenetictravelingsalesmanproblemsbybranchandcut[J].OperationResearchLetters, 1987, 6(1): 1-7.

[4]HELDM,KARPRM.Adynamicprogrammingapproachtosequencingproblems[J].JournaloftheSocietyforIndustrialandAppliedMathematics, 1962, 10(1): 196-210.

[5]APPLEGATED,BIXBYR,CHVATALV,etal.FindingcutsintheTSP(apreliminaryreport),TR95- 05 [R].Piscataway,NJ:CenterforDiscreteMathematics&TheoreticalComputerScience, 1995.

[6]JÜNGERM,REINELTG,RINALDIG.Thetravelingsalesmanproblems[J].HandbooksinOperationsResearch&ManagementScience, 1995, 7(5): 225-230.

[7]BENTLEYJL.Fastalgorithmsforgeometrictravelingsalesmanproblem[J].ORSAJournalonComputing, 1992, 4(4): 387-411.

[8]AHMEDZH.Geneticalgorithmforthetravelingsalesmanproblemusingsequentialconstructivecrossoveroperator[J].InternationalJournalofBiometricsandBioinformatics, 2010, 3(6): 96-105.

[9]SONGCH,LEEK,LEEWD.ExtendedsimulatedannealingforaugmentedTSPandmulti-salesmanTSP[C]//Proceedingsofthe2003InternationalJointConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 2003: 2340-2343.

[10]GENDREAUM,LAPORTEG,SEMETF.Atabusearchheuristicfortheundirectedselectivetravelingsalesmanproblem[J].EuropeanJournalofOperationalResearch, 1998, 106(2/3): 539-545.

[11]CLEARM.Discreteparticleswarmoptimization,illustratedbythetravelingsalesmanproblem[M]//NewOptimizationTechniquesinEngineering.Berlin:Springer, 2004: 219-239.

[12]DORIGOM,GAMBARDELLALM.Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[J].IEEETransactionsonEvolutionaryComputation, 1997, 1(1): 53-66.

[13]COLORNIA,DORIGOM,MANIEZZOV.Distributedoptimizationbyantcolonies[C]//Proceedingsofthe1991EuropeanConferenceOnArtificialLife.Amsterdam:Elsevier, 1991: 134-142.

[14]DORIGOM,MANIEZZOV,COLORNIA.Theantsystem:optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystems,Man,andCybernetics, 1996, 26(1): 29-41.

[15]STUTZLET,HOOSH.Improvementsontheantsystem:introducingMAX-MINantsystem[C]//Proceedingsofthe1998InternationalConferenceonArtificialNeuralNetworksandGeneticAlgorithms.Berlin:Springer, 1998: 245-249.

[16] 郑松,侯迪波,周泽魁.动态调整选择策略的改进蚁群算法[J].控制与决策,2008,23(2):225-228.(ZHENGS,HOUDB,ZHOUZK.Antcolonyalgorithmwithdynamictransitionprobability[J].ControlandDecision, 2008, 23(2): 225-228.)

[17] 吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013,34(4):165-170.(WUHF,CHENXQ,MAOQH,etal.ImprovedantcolonyalgorithmbasedonnaturalselectionstrategyforsolvingTSPproblem[J].JournalonCommunications, 2013, 34(4): 165-170.)

[18] 程毕芸,鲁海燕,徐向平,等.求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J].计算机应用,2016,36(1):138-142,149.(CHENGBY,LUHY,XUXP,etal.Improvedlocal-search-basedchaoticdiscreteparticleswarmoptimizationalgorithmforsolvingtravelingsalesmanproblem[J].JournalofComputerApplications, 2016, 36(1): 138-142, 149.)

[19] 徐金荣,李允,刘海涛,等.一种求解TSP的混合遗传蚁群算法[J].计算机应用,2008,28(8):2084-2087.(XUJR,LIY,LIUHT,etal.Hybridgeneticantcolonyalgorithmfortravelingsalesmanproblem[J].JournalofComputerApplications, 2008, 28(8): 2084-2087.)

[20] 张弛,涂立,王加阳.新型蚁群算法在TSP问题中的应用[J].中南大学学报(自然科学版),2015,46(8):2944-2949.(ZHANGC,TUL,WANGJY.Applicationofself-adaptiveantcolonyoptimizationinTSP[J].JournalofCentralSouthUniversity(ScienceandTechnology), 2015, 46(8): 2944-2949.)

[21] 张长胜,孙吉贵,欧阳丹彤.一种自适应离散粒子群算法及其应用研究[J].电子学报,2009,37(2):299-304.(ZHANGCS,SUNJG,OUYANGDT.Aself-adaptivediscreteparticleswarmoptimizationalgorithm[J].ActaElectronicaSinica, 2009, 37(2): 299-304.)

[22] 饶卫振,金淳,陆林涛.考虑边位置信息的求解ETSP问题改进贪婪算法[J].计算机学报,2013,36(4):836-850.(RAOWZ,JINC,LULT.Animprovedgreedyalgorithmwithinformationofedges’locationforsolvingtheeuclideantravelingsalesmanproblem[J].ChineseJournalofComputers, 2013, 36(4): 836-850)

[23] 李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878.(LIQ,ZHANGC,CHENP,etal.Improvedantcolonyoptimizationalgorithmbasedonparticleswarmoptimization[J].ControlandDecision, 2013, 28(6): 873-878.)

[24] 李成兵,郭瑞雪,李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用,2014,34(S1):131-132,165.(LICB,GUORX,LIM.ApplicationofImprovedantcolonyalgorithmintravelingsalesmanproblem[J].JournalofComputerApplications, 2014, 34(S1): 131-132, 165.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(11371174),theFundamentalResearchFundsfortheCentralUniversities(1142050205135260,JUSRP51317B).

XU Kaibo, born in 1992, M. S. candidate. His research interests include optimization and control.

LU Haiyan, born in 1970, Ph. D., associate professor. Her research interests include combinatorial optimization, intelligent algorithm.

CHENG Biyun, born in 1992, M. S. candidate. Her research interests include optimization and control.

HUANG Yang, born in 1991, M. S. candidate. His research interests include optimization and control.

Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP

XU Kaibo, LU Haiyan*, CHENG Biyun, HUANG Yang

(SchoolofScience,JiangnanUniversity,WuxiJiangsu214122,China)

Concerning the drawbacks of the Ant Colony Optimization (ACO) algorithm such as low convergence rate and being easy to fall into local optimum solutions, an ACO algorithm based on Improved Pheromones Double Updating and Local Optimization (IPDULACO) was proposed. Double updating was performed on the pheromones of subpaths whose path contribution degrees to the current global optimal solution obtained by colony were bigger than the prescribed path contribution threshold. The selected probability of the subpaths which were used to constitute the potential optimal solution was increased and the convergence rate of the proposed algorithm was accelerated. Then, when the ant colony fell into the local optimal solution in the search process, the random insertion method was utilized to change the city sequences of the current local optimal solution in order to enhance the algorithm’s ability of jumping out of local optimal solution. The improved algorithm was applied to several classical Traveling Salesman Problem (TSP) instances in the simulation experiments. The experimental results show that, for small-size TSP instances, the IPDULACO can obtain the known optimal solution in less number of iterations. For relatively large-size TSP instances, the IPDULACO can obtain the optimal solution with higher accuracy in less number of iterations. Therefore, the IPDULACO has the stronger ability of searching for the global optimal solution and faster convergence rate, and it can be used for solving TSP effectively.

Traveling Salesman Problem (TSP); Ant Colony Optimization (ACO) algorithm; pheromones double updating; local optimization

2016- 12- 06;

2017- 03- 01。

国家自然科学基金资助项目(11371174)；中央高校基本科研业务费专项资金资助项目(1142050205135260,JUSRP51317B)。

许凯波(1992—)，男，山西晋城人，硕士研究生，CCF会员，主要研究方向：最优化与控制； 鲁海燕(1970—)，女，山东淄博人，副教授，博士，主要研究方向：组合最优化、智能算法； 程毕芸(1992—)，女，安徽马鞍山人，硕士研究生，CCF会员，主要研究方向：最优化与控制；黄洋(1991—)，男，河南信阳人，硕士研究生，CCF会员，主要研究方向：最优化与控制。

1001- 9081(2017)06- 1686- 06

10.11772/j.issn.1001- 9081.2017.06.1686

TP301.6

A