融合猫群算法的动态分组蚁群算法*

张德惠，游晓明，刘 升

1.上海工程技术大学 电子电气学院，上海 201620

2.上海工程技术大学 管理学院，上海 201620

1 引言

旅行商问题（traveling salesman problem，TSP）是一类经典的组合优化问题，是指一位旅行者从某一起点出发，通过所有给定的需求点，且每个需求点只经过一次，最后回到起点的最短路径问题。

蚁群算法（ant colony optimization，ACO）[1-2]最初由意大利学者Dorigo 等在1996 年根据蚂蚁觅食机制而提出的用来解决旅行商和分布式优化问题的一种算法。例如，人们利用蚁群算法来解决路径规划[3]、车间调度以及网络路径负载均衡[4]等问题。其中蚁群算法在解决TSP 问题的实验中能够提供较好的解决方案，但在解决大规模问题时会出现陷入局部最优和收敛速度慢等问题。后来，Dorigo 又提出了蚁群系统（ant colony system，ACS）[5]，将局部信息素更新与全局信息素更新相结合，提高算法的收敛速度。2000 年，Stutzle 等提出了最大最小蚁群算法（minmax ant system，MMAS）[6]，通过限制信息素的范围来改善算法中过早停滞的问题。以上是经典的蚂蚁算法，它们具有高效的搜索能力，但仍存在着容易陷入局部最优、收敛速度慢等问题。文献[7]使用了一种改进信息素二次更新与局部优化策略，实验结果证明这些算法增强了全局搜索能力，多样性更好，但是收敛速度却有待提高。李俊等人[8]提出融入2-opt 邻域搜索策略，增强算法对TSP 问题解的构造能力,从而提高解的质量。文献[9]利用信息素全局更新和局部更新动态结合的方法，使当前最优路径上的信息素能够动态地调配，帮助算法跳出局部最优，避免算法停滞。张立毅等人[10]将细菌觅食算法和蚁群算法相结合以改进蚁群算法收敛速度慢和易陷入局部最优的不足。为了平衡多样性和收敛速度，文献[11]定义一种新的方向信息素来刻画寻优过程中的全局信息，从而保证在最优路径的基础上提高解的全局性，并加快算法的收敛。此外，由于新的探索率因子的提出及全局选择策略的修正，使得信息素较弱的路径得以选择，进而扩大了搜索的范围，提高了算法的鲁棒性。文献[12]提出了一种用猫群算法来解决TSP 问题，利用猫群的跟踪搜寻两种特殊模式，使其兼顾了较好的全局搜索性质和不易陷入局部最优解的两种优势。以上改进的蚁群算法中，在大规模的TSP 问题中仍然存在收敛速度慢且容易陷入局部最优等问题。

为此，本文提出了一种融合猫群算法的动态分组蚁群算法。猫群算法中利用猫的搜索和跟踪两种特性来平衡算法的多样性和收敛速度，故本文利用猫群算法中的分工思想引入动态分组机制，将参与实验的蚂蚁分为搜索蚂蚁和跟踪蚂蚁，带着不同的任务去执行各自的路径构建以及信息素更新算子。通过定义动态分组算子使前期搜索蚂蚁多，增加解的多样性；后期跟踪蚂蚁多，加快收敛速度，进一步结合信息素扩散机制避免算法陷入局部最优，最后利用3-opt 算子优化解的质量。实验结果表明，改进后的算法的多样性及收敛速度均优于传统蚁群算法以及其他智能算法。

2 相关研究

2.1 蚁群算法原理及研究现状

20 世纪90 年代初期科学家通过实验发现，蚂蚁在进行觅食时，会在走过的路径上留下一种对同类有吸引性的化学物质——信息素，蚂蚁会根据信息素浓度的大小来选择下一条路径，浓度越高被选中的几率越大。同时由于信息素的挥发特性，较差路径上的信息素会越来越少，从而最优路径也就能慢慢地被选择出来。目前已经出现了各种对蚁群算法的改进，例如：对算法参数进行优化，对信息素更新规则或路径构建规则进行改进[13]，使用其他智能算法优化蚁群算法[14-15]等。虽然这些改进算法在一定程度上改善了算法的性能，但是仍然存在多样性不足，收敛速度慢等问题。而本文改进算法与其他改进算法不同的是，引入猫群算法的思想对蚂蚁进行了分工，加强了蚂蚁之间的协作能力，使算法能够更好地平衡多样性与收敛速度。与其他改进算法相同的是，对拥有不同任务的蚂蚁的路径构建规则以及信息素更新规则进行了改进，使其达到相应的效果。

2.2 蚁群系统解决TSP 问题

2.2.1 路径构建规则

在ACS 算法中，蚂蚁k当前位置在i处，按照伪随机比例规则来选择下一个将要访问的城市j，其规则如式（1）：

其中，q是均匀分布在区间[0,1]上的一个随机变量；q0是一个参数，其范围是[0,1]；J是根据式（2）给出的概率分布产生出来的一个变量。

其中，α为信息启发式因子；β为期望启发式因子；为蚂蚁下一步可以直接到达并且尚未访问过的城市的集合；ηij为启发函数，其表达式为式（3）：

2.2.2 信息素更新规则

局部信息素更新规则：蚂蚁在进行一次路径选择时，即从当前城市i到下一个城市j后，立即更新信息素，其公式如式（4）：

其中，ρ为局部信息素蒸发系数，其范围为(0,1)；τ0为信息素初始值，经实验发现τ0取1/nC时，算法能拥有较好的性能；n为城市数目，C是由最近邻方法得到的路径长度。

全局信息素更新规则：所有蚂蚁进行一次迭代后更新信息素，且只有在全局最优路径上的蚂蚁可以更新，这样加快了算法的收敛速度，其公式如式（5）：

其中，ξ为全局信息素蒸发系数；Cbs为全局最优路径的长度；为全局最优路径上增加的信息素，按式（6）计算。

2.3 猫群算法

猫群算法[16]（cat swarm optimization，CSO）是由台湾学者Chu 等人在2006 年提出的一种新型群体智能算法。后来有很多对于猫群算法的改进与应用[17-18]。猫群算法将猫群分成跟踪和搜索两种模式。每只猫即对应问题的一个解。每只猫的属性由猫的速度、猫的适应值、猫处于跟踪或搜索模式的标志值组成。每只猫处于初始位置，然后通过每只猫的标志值来判断猫处于搜索模式还是跟踪模式。若猫处于跟踪模式，则执行跟踪算子；若猫处于搜索模式，则执行搜索算子。最后使得猫处于一个新的位置，并保留最优猫直至算法满足结束条件。

猫群算法基本步骤如下：

（1）初始化猫群；

（2）根据分组率将猫群随机划分为跟踪和搜索两种模式；

（3）根据猫的标志值对猫执行相应的算子，进行位置更新；

（4）计算每只猫的适应度，记录并保留适应度最优的猫；

（5）若满足结束条件则终止算法，否则再返回步骤（2）。

3 改进算法

3.1 猫群算法的引入

传统的蚁群算法是各个蚂蚁单独行动且每只蚂蚁都执行相同的操作，蚂蚁之间的协作不足，可能会导致滞后、算法陷入局部最优以及减少找到最优解的可能性等问题。而猫群算法采用猫的跟踪搜索两种特殊模式使其兼顾了较好的全局搜索性质和不易陷入局部最优解的两种优势。但是猫群算法自身也存在着很多的局限性，猫群算法中的猫执行的不同模式是根据分组率随机划分的，而该分组率是定值，算法从始至终处于两种模式的猫的数量是一定的，在算法前期也会有部分猫执行跟踪模式，这部分猫缺乏全局搜索性质，算法多样性较差；在算法后期仍然有部分猫处于搜索模式，在无目标搜索，导致收敛速度下降。故3.2 节中引入动态分组机制，使猫群算法中的分组率动态变化，增加蚂蚁之间的协作交流，最大化地平衡多样性与收敛速度。本文算法将m只蚂蚁分成搜索蚂蚁和跟踪蚂蚁两类：搜索蚂蚁主要负责增加多样性；跟踪蚂蚁主要负责在加快收敛速度的同时能避免陷入局部最优解。在一定迭代数后，重新分配跟踪蚂蚁与搜索蚂蚁，增加蚂蚁之间的交流，利于寻找更优解。

3.2 动态分组机制

CACS（dynamic grouping ant colony algorithm combined with cat swarm optimization）在种群初始化时，让每只蚂蚁能分配在不同的初始城市（蚂蚁数若大于城市数时，则使蚂蚁能够均匀分布在不同的城市），使构建的解的多样性更加丰富。本文引入动态分组算子ε动态地将m只蚂蚁分为搜索蚂蚁m(1-ε)只和跟踪蚂蚁mε只。其划分规则为：将每次迭代后蚂蚁所走的路径进行升序排序，排序后的路径所对应的前mε只蚂蚁变成跟踪蚂蚁，其余为搜索蚂蚁。ε公式为式（7），由式（7）可看出，每只蚂蚁在每一代都有可能会改变自己的职责，或者为跟踪蚂蚁或者为搜索蚂蚁，将前几名路径的蚂蚁变为跟踪蚂蚁，结合3.4 节的信息素扩散机制，突出较优路径的重要性以及较优路径附近的较优子路径的作用，避免陷入局部最优；而跟踪蚂蚁和搜索蚂蚁的数量却是间隔一定代数才会变化，这是为了避免跟踪蚂蚁在前期过多，导致信息素过量累积，降低算法的性能。

其中，iter为当前迭代数；max_iter为最大迭代数。蚂蚁选择下一个城市的概率规则为：跟踪蚂蚁按照式（2）进行路径构建，搜索蚂蚁按照式（8）进行路径构建。

其中，μ为环境适应度因子阈值，是(0,1)之间的常数；随着迭代的继续，某些路径上的信息素会逐渐增加，使算法具有导向性，故设f为环境适应度因子，随着迭代数的增加，ε越来越大，f越来越小。因此在算法的前期，搜索蚂蚁的数量多且搜索蚂蚁选择×rand的概率也大，丰富了解的多样性；后期时，跟踪蚂蚁数量多，搜索蚂蚁数量少并且按照传统ACS 的路径选择的概率变大，算法具有导向性逐渐收敛。

3.3 CACS 信息素更新规则

CACS 算法采用的是局部信息素更新和全局信息素更新相结合的信息素更新机制，本文对局部信息素更新规则进行了变异，见式（10），信息素增加的部分是对跟踪蚂蚁的额外奖励，该奖励源自于信息素扩散机制，将在3.4 节详细介绍。全局信息素更新规则为式（5）。局部信息素更新侧重开发较差路径中的较优子路径，提高多样性，降低陷入局部最优的可能；全局信息素更新侧重加快算法的收敛速度。

其中，ρ为局部信息素蒸发速率；为第t次迭代跟踪蚂蚁在附近边释放的可以扩散的信息素扩散到边(i,j)的信息素量，其公式见式（11）。

3.4 自适应信息素扩散机制

由于传统蚁群算法蚂蚁间协作不足，存在陷入局部最优的缺陷，故CACS 提出信息素自适应扩散机制来加强蚂蚁间的协作。在跟踪蚂蚁进行路径构建时，当其从城市i转移到城市j时，不仅会释放一定浓度的信息素在边(i,j)上，还会额外释放一定浓度的信息素在城市i上，然后以城市i为圆心，以dij为半径向四周其他子路径进行信息素的自适应扩散。该信息素一方面直接影响后代经过边(i,j)上的蚂蚁，另一方面还会影响当代附近蚂蚁的行为。

Fig.1 Pheromone diffusion range图1 信息素扩散范围

为防止信息素过度累积，降低算法的性能，令只有跟踪蚂蚁能产生可以扩散的信息素。如图1，以i为圆心dij为半径的圆为信息素扩散区域，当跟踪蚂蚁从城市i转移到城市j时，会额外产生能扩散的信息素，令此信息素集中在城市i点，则此时i处信息素最大，记为τmax，则其信息素以i为圆心，以dij为半径向四周扩散。若此时存在城市g到城市i的距离dig＜dij时，则蚂蚁k在第t次迭代时在城市i上的信息素扩散到边(i,g)上的信息素量为式（12）。dig越小时，扩散到边(i,g)的信息素越多，越能使该较优子路径发挥作用，且选用dij作为挥发半径达到自适应的效果。在传统蚁群算法的中后期，算法会逐渐收敛，蚂蚁所探索到的路径逐渐收敛在一些路径之间，使获得的解的多样性下降，算法容易陷入局部最优。而信息素扩散机制一方面能使陷入局部最优解中的子路径以及该局部最优解路径附近的较优子路径上的信息素浓度增加，加大了后代蚂蚁选择该较优子路径的概率，保持着解的多样性，避免算法陷入局部最优；另一方面，在算法后期，信息素扩散机制给较优子路径增加了信息素，使更多的蚂蚁以更大的可能性选择这些优质的子路径，而该子路径很大可能是最优解的一部分，故信息素扩散机制也适当地提高了算法的收敛速度。

其中，C2为信息素扩散因子，是(0,1)之间的一个常数；Q为蚂蚁k释放的信息素总量，是一个常数。

3.5 3-opt算子

为了使蚁群算法每次迭代过程中产生的解能够得到优化，采用3-opt算子进行优化。

3-opt算法的基本流程如下：

（1）随机生成一条初始路径T。

（2）在路径T上随机选择三点断开，形成三条路径，每条路径都有起点和终点。

（3）随机交换三条路径的起点和终点，形成一条新的路径T′。

（4）比较T与T′，留下较优路径。

（5）重复（3）和（4），直至所有交换的可能都比较结束。

3.6 算法描述

步骤1参数初始化。

步骤2将m只蚂蚁均匀地放置在不同的初始城市，m只蚂蚁全定义为搜索蚂蚁。

步骤3搜索蚂蚁和跟踪蚂蚁分别按照式（2）和式（8）选择下一个需要访问的城市,每选择一次，蚂蚁结合信息素扩散机制（见式（10））进行局部信息素更新。

步骤4m只蚂蚁完成一次完整的路径构建后，将产生的m个解进行升序排序，根据动态分组机制（见式（7））划分出跟踪蚂蚁和搜索蚂蚁。

步骤5将当前最优解用3-opt进行优化得到更优解，将此更优解路径根据式（5）进行全局信息素更新。

步骤6重复步骤3～步骤5 直到达到最大迭代数，结束。

3.7 时间复杂度分析

算法1 解决TSP 问题的CACS 算法框架

从算法1 的算法流程中可以看出，跟踪蚂蚁与搜索蚂蚁是独立运行的，因此CACS 的时间复杂度是O(nc×m1×(n-1)+nc×m2×(n-1))，其中m1为每代跟踪蚂蚁的数量，m2为每代搜索蚂蚁的数量，设总蚂蚁数为m，则CACS 时间复杂度为O(nc×m×n)，ACS 的最大时间复杂度也为O(nc×m×n)。由此，本文的改进算法并没有增加时间复杂度。

4 实验仿真与结果分析

4.1 仿真环境与参数设置

为验证改进后的算法性能，本文实验测试环境为：Windows 10 操作系统，利用Matlab2016a 对TSP标准数据库中的多组不同规模的城市进行仿真。对于实验参数的设置，在ACS 实验的基础上，经过多次实验参数的调节与数据统计发现，在ACS、ACS+3opt、CACS 这三种对比算法中所使用的参数值设置如表1 时，实验效果最好。在三种对比实验中，参数均设一致进行对比有较强的说服力且对于设计实验时也方便。

Table 1 Parameters setting表1 参数设置

4.2 CACS 个体分布情况分析

图2 为算法在eil51 算例上随着迭代数的变化搜索蚂蚁与跟踪蚂蚁的分布情况，其中横轴为迭代数，纵轴为数量。搜索蚂蚁与跟踪蚂蚁一共50 只，图中第一列Scount为搜索蚂蚁的数量，第二列Spath为搜索蚂蚁在该迭代数下所产生的不同的路径数量，第三列Gcount为跟踪蚂蚁的数量，第四列Gpath为跟踪蚂蚁在该迭代数下所产生的不同的路径数量。从图2 中可看出，由于动态分组机制，搜索蚂蚁与跟踪蚂蚁的数量随着迭代数的变化而变化，搜索蚂蚁越来越少，跟踪蚂蚁越来越多。前期搜索蚂蚁数量多，本文对搜索蚂蚁的路径构建机制进行了改善，使算法的多样性更加丰富；中期搜索蚂蚁与跟踪蚂蚁数量相当，与前期分析相同，搜索蚂蚁能够保持多样性，而跟踪蚂蚁执行信息素扩散机制在加快收敛速度的同时起到了保持多样性，从而避免陷入局部最优的作用。从图2 中可看到，算法从前期的200 代和400代，到中期的1 000 代和1 200 代时，Gcount和Gpath的数量变化渐渐有了差距，说明跟踪蚂蚁所产生的解正在慢慢收敛，而Scount与Spath的数量变化差距正在逐渐变小，说明虽然搜索蚂蚁的数量越来越少，但是算法的多样性并没有下降；后期跟踪蚂蚁数量多。从图2 中也可看出，产生的不同路径的数量也并没有下降太多，这是由于信息素扩散机制使局部最优路径附近的子路径加大了被选择的概率，能够跳出局部最优，从而多样性没有过度下降。从图2 中可看出，算法从中期的1 000 代和1 200 代到后期的1 800 代和2 000 代时，Gcount与Gpath的数量差距随着迭代数的增加越来越大，而Gpath的值依旧很高，说明在后期算法的收敛速度在加快，但是由于信息素扩散机制使多样性依然较好，从而使算法能够跳出局部最优。

Fig.2 Ants distribution at different time图2 不同时期蚂蚁分布图

4.3 与传统蚁群算法对比分析

对于小规模城市，现在大部分算法都能很好地找到最优解且多样性也较丰富，故本文选取kroA150、d198、a280 三种中大规模的城市结果进行对比分析。在ACS、ACS+3opt、CACS 三种算法中分别进行了15 次实验，每次实验进行2 000 次迭代，统计实验数据得到图3～图5 实验结果图。

从图3～图5 中的（a）、（b）图可以看出，CACS 算法由于动态分组机制使前期搜索蚂蚁数量较多，再搭配搜索蚂蚁中被改善过的路径构建规则，从而使CACS 算法的多样性大大增加。从kroA150 到d198再到a280，随着城市规模的不断增大，从图中也可看出，多样性波动的差距也越来越大，表明多样性的丰富度也在增加，能以更大的可能性找到更优的解。从多样性的图中还可看出，CACS 算法在后期依然保持着多样性，由于后期跟踪蚂蚁数量多，而跟踪蚂蚁利用信息素扩散机制避免算法陷入局部最优，从而继续保持着算法的多样性。而对于算法的收敛性，跟踪蚂蚁利用局部信息素扩散机制和全局信息素更新的共同作用，加快了算法的收敛速度。从图3～图5 的（c）图可以看出，CACS 的收敛性优于ACS 和ACS+3opt，且解的质量也更好。

为了更好地验证CACS 的性能，本文从TSP 测试集中选取了13 个不同规模的城市进行实验，并与ACS 和ACS+3opt算法进行对比，结果如表2。从表2中eil51、eil76、rat99 等小规模城市的实验结果可知，CACS 能够快速地找到最优解，且最差解与平均解均优于ACS 和ACS+3opt。对于kroA100、kroA150、kroA200、kroB100、kroB150、kroB200、ch130 以 及d198 的中规模实验结果中，kroA100 和kroB150 均找到了最优解，其余城市虽然没有找到最优，但是误差值均在1%以内，也说明了本文算法性能优于另外两种算法。对于a280、lin318 等大规模城市的测试虽然没有找到标准最优解，但测试结果显示CACS 还是优于原始ACS 且误差值保持在1%左右。综合以上：CACS 整体上改善了算法的多样性与收敛速度，寻优能力大大超过了ACS 和ACS+3opt。

Fig.3 kroA150 comparison of experimental results图3 kroA150 实验结果对比

Fig.4 d198 cmparison of experimental results图4 d198 实验结果对比

Fig.5 a280 comparison of experimental results图5 a280 实验结果对比

Table 2 Performance comparison of ACS、ACS+3opt、CACS in different test sets表2 ACS、ACS+3opt、CACS 在不同测试集的性能对比

图6 给出了参加实验的13 个城市的平均误差率，结合表2 中的平均解可看出：本文算法得到的平均解以及平均误差率均优于另外两种算法。随着城市规模的不断增加，三种算法的平均误差率的差距也处于增大的趋势中，这表明CACS 算法比ACS 和ACS+3opt 更加稳定，且城市规模越大这种稳定性越明显。

Fig.6 Comparison of algorithm stability图6 算法稳定性对比

图7 给出参加实验的13 个不同规模城市中达到标准最优解的路径图。

4.4 与改进蚁群算法以及其他算法进行对比

本文改进的算法还与其他改进的蚁群算法以及其他智能算法进行比较来验证其性能。表3 中改进单种群蚁群算法（ant colony algorithm for heuristic dynamic pheromone update strategy，D-ACS）数据来自于文献[19]，面向旅行商问题改进的蚁群算法（improved ant colony algorithm，IACA）数据来自于文献[20]，改进粒子群算法（improved random greedy particle swarm optimization based on Hamming distance,IMRGHPSO）数据来自于文献[21]，遗传算法（genetic algorithm，GA）和人工蜂群算法（artificial bee colony algorithm，ABC）数据来自于文献[22]。从表3 中可看出，CACS 算法所得的解的质量明显优于IMRGHPSO、GA 以及ABC 这三种智能算法；与单蚁群的改进算法D-ACS以及面向旅行商问题改进的蚁群算法IACA 相比较，解的精度也较优。

Table 3 Comparison of CACS with other algorithms on TSP instances表3 CACS 与其他算法在TSP 案例上的比较

Fig.7 The optimum path图7 最优路径

综合3.2 节与3.3 节的实验对比分析，本文所提出的融合猫群算法的动态分组蚁群算法与传统蚁群法、改进蚁群算法以及其他智能算法相比均具有一定的优势，解的质量以及收敛速度均有一定程度的提高。

4.5 算法性能分析

在算法的前期，传统蚁群算法由于信息素的差距不大，其对于路径选择的干扰不大，故多样性较丰富；本文算法提出的动态分组机制使搜索蚂蚁的数量多于跟踪蚂蚁，因此算法产生的解基本上来源于搜索蚂蚁，而本文对搜索蚂蚁的路径构建规则进行了改善。根据式（8）可知，环境适应度因子f是根据迭代数的改变而改变的，迭代开始时，f值较大，搜索蚂蚁基本上按照×rand路径构建规则选择下一个城市，由于rand的随机性，算法在前期多样性表现得很好。

在算法的中期，传统蚁群算法由于路径之间的信息素逐渐产生差距，其对于蚂蚁路径的构建已经能起到大部分的作用了，会使算法的多样性降低，可能会导致算法停滞；本文改进算法在中期搜索蚂蚁与跟踪蚂蚁数量相当，此时f较小，搜索蚂蚁对于路径构建的选择会有部分使用×rand，而rand的随机性使一部分搜索蚂蚁增加了随机选择路径的可能性，这部分蚂蚁能够保持着算法的多样性，而跟踪蚂蚁由于信息素扩散机制，使可能陷入局部最优的路径或其他较优路径附近的较优子路径得到更多的信息素，加大了较优子路径被选择的概率，减少了算法趋于停滞的可能性。

在算法的后期，传统蚁群算法由于路径之间的信息素差距较大，其对蚂蚁的路径构建完全干扰，使算法更容易陷入局部最优；本文算法在此时跟踪蚂蚁的数量多于搜索蚂蚁，因此算法产生的解基本上来源于跟踪蚂蚁，虽然此时搜索蚂蚁依然存在，其对于路径的选择跟传统蚁群算法一样，但是搜索蚂蚁过少，对于算法的整体几乎没有影响。对于跟踪蚂蚁，由于其使用信息素扩散机制使局部最优路径附近的较优子路径的信息素得到增加，加大了较优子路径被选择的概率，有利于算法跳出局部最优，从而也保持着算法的多样性。并且由于跟踪蚂蚁的信息素扩散机制使较优子路径上的信息素逐渐累积，而这些子路径很可能是最优解的一部分，信息素扩散机制使更多的蚂蚁以更大的可能性去选择这些较优子路径，会使算法逐渐向收敛趋势发展。再加上信息素全局更新机制对每次迭代产生的优解路径进行信息素更新也会加快收敛速度，故算法整体上在后期收敛速度会被加快。

故本文改进算法在整体上平衡了多样性与收敛速度，使获得的解的质量更优。

5 结束语

针对传统蚁群所存在的容易陷入局部最优以及收敛速度慢等问题，本文提出了一种融合猫群算法的动态分组蚁群算法，引入动态分组机制将蚂蚁分为搜索蚂蚁和跟踪蚂蚁。搜索蚂蚁改善了路径构建规则，使算法多样性得以丰富；跟踪蚂蚁改善了信息素更新规则，保持了算法的多样性，避免算法陷入局部最优，最后使用信息素全局更新机制加快了算法的收敛速度。

仿真结果表明，本文算法不仅提高了多样性，也在一定程度上加快了收敛速度。在中小规模的TSP问题上，该算法能快速地找到最优解，在大规模的TSP 问题上虽然不能快速地找到最优解，但还是能保证解的多样性和解的相对质量。下一步的研究方向是利用多种群来继续研究大规模城市的路径优化问题。