基于动态重组和协同交流策略的蚁群优化算法

刘一凡，游晓明+，刘 升

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

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

旅行商问题[1]（traveling salesman problem，TSP）是一类经典的组合优化问题，可以描述为：旅行商从一个城市出发，不重复地遍历完所有城市并最终回到起始城市，需要在所有满足以上条件的路径中找出最短路径的问题。国内外学者采用多种算法来研究此问题，目前主要有遗传算法[2]、模拟退火法[3]、粒子群算法[4]和蚁群算法[5]等。其中，蚁群算法具有较强的鲁棒性、良好的并行性和易与其他算法结合等特点，在求解TSP 问题中取得很好的效果，并被广泛应用于车辆调度、图像处理和多目标组合优化等诸多优化领域。

蚁群算法是一种新兴智能仿生优化算法，最初于20 世纪90 年代由意大利学者Dorigo 等人提出。1996 年，Dorigo 等人在蚂蚁系统（ant system，AS）[6]的基础上，采用信息素全局更新和局部更新两种信息素更新方式，提出蚁群系统（ant colony system，ACS）[7]算法，加快了算法收敛速度。2000年，Stutzle等人提出了最大最小蚂蚁系统（max-min ant system，MMAS）[8]，为每条路径上信息素浓度设定了上、下限阈值，避免信息素浓度无限累加而停滞，提高了算法的多样性。以上基本蚁群算法具有高效的搜索能力，但仍存在着易陷入局部最优、收敛速度慢等问题。

蚁群优化算法（ant colony optimization，ACO）是对基本蚁群算法进行改进的一系列优化算法，为了提高基本蚁群算法的性能，国内外学者主要在路径选择、信息素更新、添加局部优化算子和与其他算法结合等方面进行改进。文献[9]引入精英策略思想，提出一种基于排序加权的信息素更新策略，通过强化较优路径信息对蚂蚁的反馈作用，提高了算法收敛速度和求解质量。文献[10]从蚁群算法的理论研究、算法融合、多蚁群算法研究等方面对蚁群算法在移动机器人路径规划中的未来研究内容和研究热点进行展望。文献[11]依据聚类算法对环境复杂程度的准确判别自动改变寻优半径，达到充分利用机器人有限的计算能力，提高收敛速度的目的，但算法多样性仍有待提升。针对这一不足，文献[12]利用改进的头尾搜索机制，并引入奖惩因子、信息素最大最小阈值和遗传算法变异因子，提高了算法全局搜索能力和跳出局部最优的能力。以上单种群蚁群优化算法在解决中小规模TSP 问题方面得到了很大的改进，但在解决大规模TSP 问题时，其求解精度仍需要进一步提高。

为进一步提高算法的搜索能力和求解性能，许多算法采用了多种群策略。在文献[13]中，姜慧楠等人结合人工鱼群算法（artificial fish swarms algorithm，AFSA）前期收敛速度快和混合蛙跳算法（shuffled frog leaping algorithm，SFLA）局部搜索能力强的优势，提出一种人工鱼群-蛙跳混合优化算法（AFSA-SFLA），提高了种群的质量和算法的高效性。文献[14]中魏士伟提出了一种基于协同进化的遗传算法（co-evolution genetic algorithm，CEGA）用于解决遗传算法（genetic algorithm，GA）的缺陷，既保证了种群向最优解的方向移动，又保持了种群的多样性。此外，多种群策略在蚁群优化算法中也有许多体现，文献[15-17]利用蚁群算法与其他优化算法的良好结合特性，提出了一系列的融合蚁群算法，有效提升了蚁群算法的收敛速度和算法多样性，但对于大规模TSP 问题的求解精度和跳出局部最优的能力有待进一步改善。

为了在提升收敛速度的同时提高求解精度和稳定性，需要进一步平衡蚁群多样性和算法收敛性，为此，本文提出一种基于动态重组和协同交流策略的蚁群优化算法（ant colony optimization algorithm based on dynamic recombination and cooperative communication strategy，RCACO）。其主要改进思想是：（1）多种群策略。将蚁群划分为贪婪蚁群和探索蚁群，贪婪蚁群沿用ACS 的路径构建规则和信息素更新策略，主要负责寻找当前较优路径，提高算法的收敛速度，探索蚁群采用改进的路径构建规则和信息素更新策略，主要负责探索有潜力的非较优路径，增加算法的多样性。（2）动态重组策略。提出一种基于线索二叉树的新型重组算子，并采用不同的重组策略对解集进行动态重组，避免随机盲目重组的同时增加了算法的导向性，以提升算法的多样性和平均求解质量。（3）协同交流策略。提出一种基于相似度和潜力值的协同交流策略，让两类蚁群并行搜索那些有潜力成为最优解的路径，将所搜索到的优良路径作为共享信息进行种群间的交流，从而有效提高算法的收敛速度。（4）停止规避策略。为避免算法因次优路径上信息素浓度过高而陷入停滞，加入了停滞规避策略，保证了算法后续循环的有效性，从而增强算法的搜索性能，以帮助蚁群跳出局部最优，获得标准最优解。

1 相关工作

1.1 ACS 蚁群算法原理

1.1.1 路径构建

ACS 算法中每只蚂蚁从城市i到城市j的状态转移规则如下：

其中，q是一个在区间[0,1]上的随机数，q0(0 ≤q0≤1)是一个可调参数，τij表示i和j城市路径上的信息素总量，ηij表示i和j城市之间距离的倒数，allowed表示当前可选城市的集合。s是采用轮盘赌的方式选出的下一个城市，使得算法可以有偏向性地探索各条边，城市之间信息素浓度高和距离近的城市被选择的概率更大，但其他次优路径也有一定概率被选到，具体公式如下：

本文中的两类蚁群沿用了ACS 的状态转移规则，但两类算法分别采用不同的q0。贪婪蚁群采用较大的q0，对当前最优区域进行深度探索，加快收敛速度；探索蚁群采用较小的q0，对其他次优区域进行广度搜索，增加算法多样性。

1.1.2 信息素的更新

ACS 算法中的信息素更新策略分为局部信息素更新和全局信息素更新两部分。

局部信息素更新：当每只蚂蚁从城市i经过下一个城市j之后，算法会对这条路径进行局部信息素更新，公式为：

其中，τ0为每条边上的起始信息素浓度，ξ是局部信息素的蒸发率。局部信息素更新可以防止算法过早陷入局部最优，增加算法的多样性。

全局信息素更新：当所有蚂蚁都完成路径构建后，算法会对当前全局最优路径进行全局信息素更新，公式为：

其中，Δτij是信息素增量；Lgb是当前全局最优路径的长度；ρ是全局信息素的蒸发率。全局信息素更新会对全局最优蚂蚁走过的路径进行信息素奖励，可以起到正反馈的作用，增加算法的导向性和收敛速度。

1.2 线索二叉树

在二叉树的节点上加上线索的二叉树称为线索二叉树，线索二叉树中的线索能记录每个节点前驱和后继信息。为了区别线索指针和孩子指针，在每个节点中设置两个标志ltag 和rtag。

传统线索二叉树的节点结构如表1 所示。

Table 1 Node structure of traditional clew binary tree表1 传统线索二叉树的节点结构

表1 中：ltag=0 时，lchild 指向左儿子；ltag=1 时，lchild 指向前驱；rtag=0 时，rchild 指向右儿子；rtag=1时，rchild 指向后继。

2 改进策略

2.1 多种群信息素更新策略

传统的信息素更新策略会对全局最优蚂蚁走过的路径进行信息素奖励，可以起到正反馈的作用，提高算法的导向性和收敛速度，本文将其作为信息素更新1 应用于贪婪蚁群。但是，传统蚁群算法的正反馈策略会在较短的路径上留下更多的信息素，吸引更多的蚂蚁选择此路径，在迭代一定次数后，这些较短的路径上容易堆积大量信息素，即使最终这些路径并不是最优路径，也会使后续的蚁群都去选择这些次优路径，导致蚁群不能对解空间进一步进行广度搜索，进而出现停滞现象，陷入局部最优解。

为此，本文引入贡献度因子，借鉴精英策略和MMAS 的思想，提出一种改进的信息素更新策略，并将其作为信息素更新策略2 应用于探索蚁群。贡献度因子是指每条路径历史累计更新的次数，在所有蚂蚁完成路径构建后，对所有路径进行升序排序，取出本次迭代的前10%的蚂蚁，并按照路径长短进行不同程度的信息素更新，对于当前全局最优的路径会给予额外奖励。在依次对这些精英蚂蚁所经过的路径段进行更新后，该路径段贡献度+1，当贡献度到达一定次数后，这段路径就不予更新，以此达到控制路径上信息素阈值的效果。具体公式如下：

2.2 动态重组策略

2.2.1 改进线索二叉树

蚂蚁完成路径构建后得出一组城市序列，每2 个城市及连接它们的1 条路径构成一个最短子路径。输入两组城市序列A、B，将A中的每个城市节点及其最短子路径拿出来和B作对比，本文算法对传统线索二叉树结构进行改进以存储每个城市节点及其最短子路径的相关信息，如表2 所示。

线索二叉树构建完成后，对Scount 求和再除以城市个数，可得出A和B两组城市序列的相似度SAB，其取值范围为[0,1]，相似度在后文的协同交流阶段中控制两类蚁群交流的频率起作用。

例如有一个10 城市的TSP，其两个解向量的城市序列分别为A=[1 2 3 4 5 6 7 8 9 10]和B=[5 7 8 6 9 1 10 2 3 4]。以城市4 为例，其在A和B序列中的前驱节点都为3，后继节点都为5，说明3→4 和4→5 均是重复路径，以此类推，两个解向量具有4 个相同最短子路径:2→3，3→4，4→5，7→8，即SAB=0.4。

2.2.2 新型动态重组算子

为加强算法多样性和跳出局部最优的能力，在以往的遗传算法和与之结合的蚁群算法中大多会采用重组策略，可大致描述为：若两条路径节点序列中具有公共节点，则随机选其一公共节点进行交叉操作，产生两条新路径；若路径节点序列没有公共节点，则在该两条路径中分别随机剔除一条路段，通过交叉拼接得到两条新路径。这样的重组策略随机性强，虽然多样性会增加，但效率较低，往往得不到优于目前最优解的解。

为避免盲目随机重组，本文采用结合线索二叉树的新型重组算子对算法进行动态重组。首先由城市序列A和B构建出线索二叉树矩阵，为保留一定的随机性，增加多样性，在全部城市节点中随机选出一个节点作为新路径的第一个节点，接下来循环进行后续节点的选择，最后依次将选出的节点添加到新路径中，构成新的城市序列。具体操作如下：

Table 2 Node structure of improved cue binary tree表2 改进的线索二叉树的节点结构

动态重组算子会保留公共子路径，将非公共子路径按策略重组，提升算法的收敛速度，具体操作为：将选出的第一个城市节点作为当前节点node，若当前节点有后继节点Anode(Bnode)，说明原路径A和B都包含有这段最短子路径，则待选节点选其后继节点；若无后继节点，则优先选择距离当前节点之间路径距离近的、信息素浓度高的、贡献度值大的城市节点作为后续节点，还有概率直接选择原序列A或B中的下一节点，将其作为后续节点添加到新路径中。

该重组策略根据线索二叉树来保留公共路径，根据城市距离矩阵、信息素表和贡献度表共同影响进行导向性重组，实验发现重组后优于原路径的概率大大增加，而重组后没有改进的路径会被舍弃，这就有效提升了蚁群整体的求解质量。

2.2.3 动态重组策略

（1）种群内部动态重组

在每次迭代过程中，算法会对两类蚁群内部所产生的解单独进行动态重组。具体操作为：当种群内的m只蚁群全部构建完路径后，对全部路径进行升序排序，用Li表示本次迭代中排名为i的解(0

（2）种群之间动态重组

在改进蚁群算法中，贪婪蚁群和探索蚁群完成迭代后共得到2m个解，每个解包含路径长度和城市序列，将每个解按照路径长度进行升序排列，将整个蚁群分为N组，每组包含M只蚂蚁，即满足2m=N×M。具体分组情况如表3 所示。

这样划分后的每组解的质量相似，能保证种群中更多的差解得到进化，提升解集的平均质量。对于每组蚂蚁，用Lb表示组中最短路径的解，Lw表示组中最长路径的解，Lg表示所有蚂蚁当前全局最短路径的解，则有Lg≤Lb≤Lw。分别取Lb为A，Lw为B，利用上文中结合线索二叉树的新型重组算子生成新解Lnew，然后对各组蚂蚁中的Lb和Lw循环进行更新，公式如下：

Table 3 Grouping situation table表3 分组情况表

动态重组算子很大程度上改善了整体蚁群解集的平均质量，重组算子增加了算法的多样性和跳出局部最优的能力，有效提高了算法的收敛速度和求解精度。

2.3 协同交流策略

2.3.1 引入相似度的交流频率策略

当两类蚁群交流间隔过短时，会造成算法多样性下降，产生的结果会类似于一个种群，起不到分两个种群的作用；而当信息交流间隔过长时，会削弱两类蚁群之间互相学习和促进的作用，不利于提升收敛速度。

为此，本文采用引入相似度[18]的交流频率策略，对交流间隔进行自适应调整。在两类蚁群完成本次迭代后，进入协同交流阶段，首先分别用贪婪蚁群和探索蚁群得到的全局最优路径作为A和B，并构建线索二叉树，进而得到两条路径的相似度。当相似度过高时，两类蚁群趋于一致，多样性较差，不适合交流；当相似度过低时，两类蚁群的多样性较高，应进行信息交流。每隔K次迭代，根据式（11）判断是否交流，公式如下：

式中，L为判断是否可交流的逻辑值，SAB是两类种群最优解的相似度，S是相似度阈值。

2.3.2 引入潜力值的激励策略

传统蚁群算法通常只对最优的蚂蚁进行信息素更新，忽略了其他次优蚂蚁携带最优路径片段的潜力，从而容易陷入局部最优解。

为此，本文引入潜力值的概念，潜力值受贡献度和最小生成树的共同影响。首先，贪婪蚁群和探索蚁群各有一份贡献度表，将两份贡献度表整合成一张，某段路径的贡献度越高，代表这条路径被两类种群都选为最优路径片段的概率越高，即可认为这条路径段成为最优路径的潜力值就比较大，即潜力值和贡献度呈正比关系。此外，在TSP 问题中，标准最优路径与最小生成树中70%～80%的路径是吻合的，而最小生成树不是唯一的，因此多个最小生成树所重复包含的路径的潜力值也是比较大的。将潜力值因子结合到求解TSP 问题中去，对合并贡献度表中贡献度值较大的前n条路径以及生成最小生成树重合路径最多的前n条路径进行额外的信息素奖励，将会综合两类蚁群的优点，提升算法的收敛性能，其公式如下：

其中，Δτij是由式（5）得出的信息素增量，ρ是全局信息素的蒸发率。对潜力值高的路径进行额外更新可以使两类蚁群的信息得到交融，起到一定的正导向性，从而加快算法的收敛速度并提高收敛精度。

2.4 停滞规避策略

传统蚁群算法迭代一定次数后，可能在次优路径上积累大量信息素，进而出现停滞现象，而算法停滞后的循环都是在做无用功，为加强算法跳出局部最优的能力，应对停滞现象做出检测及相应处理措施。

本文的算法停滞检测分为两种：第一种是当本次迭代所有蚂蚁所构建的路径相似度过高，甚至趋于一条路径；第二种是在一定迭代次数内，仍未出现更优的解。具体检测判断公式如下：

其中，L1为判断是否停滞的逻辑值；Sall是所有蚂蚁的相似度均值；T和q1是可调参数。

本文对算法停滞的具体措施如下：当检测到算法中两类蚁群都停滞时，首先将两类蚁群中所有路径上的信息素置为初始值，然后筛选出两类蚁群都停滞时所产生最优路径的公共路径，最后加强公共路径上的信息素。公式如下：

其中，τ0为每条边上的起始信息素浓度，Δτij是两类蚁群分别由式（5）得出的信息素增量。加强公共路径的信息素会增强算法停滞后再次运行的导向性，并使得算法减少在公共路径上的搜索，将算法的侧重点放在非公共路径的城市序列的优化中。该策略有利于算法发现更优的路径，帮助算法在后续的循环中能有效跳出局部最优。

2.5 算法步骤和算法流程图

算法整体流程图如图1 所示。

Fig.1 Algorithm overall flow chart图1 算法整体流程图

算法步骤：

步骤1参数初始化。

步骤2将蚁群划分为贪婪蚁群和探索蚁群，并分别单独进行迭代，两类蚁群均采用式（1）、式（2）的城市转移规则以及式（3）的局部信息素更新策略。

步骤3当每类蚁群完成路径构建后，运用新型重组算子，根据式（9）对蚁群所产生的解集进行内部动态重组。

步骤4进入全局信息素更新阶段，贪婪蚁群采用式（4）、式（5）即ACS 中的全局信息素更新策略1，而探索蚁群采用式（6）～式（8）即改进的全局信息素更新策略2。

步骤5将两类蚁群所产生解集混合并分组，根据式（10）对两类蚁群之间进行动态重组，然后混洗蚁群。

步骤6进入协同交流阶段，计算两类蚁群的相似度，然后根据式（11）判断是否进行交流，若是，转步骤7，否则，转步骤8。

步骤7由各路径的贡献度和最小生成树计算潜力值，并根据式（12）进行各种群间的交流。

步骤8根据式（13）对算法是否停滞做出检测，若是，转步骤9，否则，转步骤10。

步骤9根据式（14）对算法停滞做出相应处理。

步骤10当NC≤NCmax时，NC=NC+1，跳转到步骤2；否则，转到步骤11。

步骤11输出最优解。

3 实验仿真

为了验证RCACO算法的有效性，使用MATLAB-2019a 对TSPLIB 标准库中的15 个不同规模的城市进行实验仿真，其中包括10 个中小规模城市实例和5个大规模城市实例。以上述TSP 实例为对象，分别对ACS、ACS+3opt 和不同优化方案下的RCACO 进行15 次实验，每轮迭代2 000 次，同时从收敛速度（迭代次数）、误差率（最优解）、稳定性（平均解）等几个方向进行实验分析。其中，误差率用来衡量每种ACO与测试集最优解之间的差距，计算公式如下：

其中，LACO为三种ACO 算法所找到的最优解，LBest为测试集的标准最优解。

3.1 参数设置

为保证实验合理性，ACS、ACS+3opt 和RCACO算法在各TSP 实例中的实验参数设置均如表4 所示。

Table 4 Setting of parameters表4 参数设置

表4 中，m为蚂蚁数量，蚂蚁数量越多，得到的最优解就越精确，但会产生不少重复解，增加时间复杂度；α为信息启发因子，α值越小，蚂蚁选择之前走过的路径可能性就越小，可以加强搜索路径的随机性，但容易陷入局部最优；β为期望启发因子，β值越大，蚁群就越容易选择局部较短路径，可以加快收敛速度，但是多样性较差；q0是式（1）中的参数，q0越大，贪婪性却强，收敛速度越快，但多样性越低；ρ是全局信息素蒸发率，ξ是局部信息素蒸发率，蒸发率过小时，会影响到算法的收敛速率，蒸发率过大时，会影响到最优值的搜索；S是式（11）中的相似度阈值，相似度均值超过S后不再进行交流；K是交流间隔，K值过大会降低交流策略的效果，K值过小会让两种蚁群趋于一致，失去设立多蚁群的意义。

经过多次实验，统计对比其结果发现，参数设置如表4 所示效果更好。

3.2 算法性能分析

为验证RCACO 算法中不同改进策略的作用，本文将不同的改进策略重新组合为不同的优化方案，并进行对比分析，优化方案编号如表5 所示。

Table 5 Optimization scheme number表5 优化方案编号

从进行仿真实验的15 个不同规模的TSP 实例中，分别选取小规模实例Eil51 和rat99、中规模实例ch130和KroA200、大规模实例tsp225 和a280，并采用表5 中的四种优化方案对每个TSP 实例都进行15 次实验，每次实验均迭代2 000 次。选取四种优化方案在各组TSP 实例中的最小值作为最优解，并根据实验数据计算出误差率和平均误差率，实验结果如表6 与图2 所示。

由以上实验结果可以看出，在小规模实例中，四

种优化方案均能得到标准最优解，而从图2 中的rat99的迭代情况来看，改进算法的收敛速度明显较快。在中大规模实例中，优化方案A 不论是收敛速度还是求解精度上都不是很理想，其平均误差率也高于改进算法。

Table 6 Performance comparison of optimization schemes表6 优化方案性能对比

Fig.2 Comparison of partial test set experiments图2 部分测试集实验对比

由优化方案B 的实验数据和迭代情况可以看出，在对信息素更新规则进行优化并加入协同交流策略后，在城市数小于200 时均能得到标准最优解，在城市数大于200 时也能明显降低迭代次数和误差率。说明协同交流策略能在提高算法收敛速度的同时，增加算法的多样性，改善求解精度。

由优化方案C 的实验数据和迭代情况可以看出，在方案B 的基础上加入动态重组策略后，收敛速度和求解精度得到了进一步提高，平均误差率也得到了明显下降。说明动态重组策略能够提高算法多样性和改善解的质量，但仍未能找到标准最优解。

由优化方案D 的实验数据和迭代情况可以看出，在方案C 的基础上加入停滞规避策略后，改进算法能在算法停滞后跳出局部最优，在选取的6 组不同规模的TSP 实例中均能在较少的迭代次数内找到标准最优解。说明停滞规避策略能够帮助算法跳出局部最优，提高全局最优解的搜索能力。

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

为了分析RCACO 在中小规模问题中的性能，将ACS、ACS+3opt 及RCACO 分别应用于不同城市规模的TSP 实例中，结果如表7 与图3 所示。

Table 7 Performance comparison of test sets for small and medium-sized cities表7 中小规模城市测试集的性能对比

Fig.3 Experimental comparison of small and medium-sized test sets图3 部分中小规模测试集实验对比

由表7 中实验数据可以看出，对于Oliver30、Eil51、Eil76、rat99、KroA100 等城市数量在100 及100以下的小规模TSP 问题中，三种算法都能得到标准最优解，但ACS 和ACS+3opt 收敛速度较慢，而RCACO在迭代次数小于100 的情况下就得到了标准最优解，有效提高了算法的收敛速度。对于ch130、ch150、KroB150、KroA200、KroB200 等城市数量在100 以上及200 以下 的中规 模TSP 问题，ACS 和ACS+3opt 均陷入局部最优，未能得到标准最优解，且误差率偏高。而RCACO 除KroB200 外均在1 000 代之内得到了标准最优解，KroB200 虽未得到最优解，但也有效地将误差率控制在0.1%以内，表明改进的算法能够在提高算法收敛速度的同时，提高解的精度及降低误差率。

图3 为Eil76、ch130、KroB150、KroA200 四组实验使用RCACO 算法得到解的路径和三种算法在四组实验中的性能对比。由图3 可以看出，RCACO 算法显著改进解的质量，并且相较经典算法，改进算法有更好的收敛速度表现。例如在ch130 实验中，改进算法曲线有最快的下降速度和最小的数据值，并且具有跳出局部最优的能力。

为了进一步分析改进算法在大规模问题中的性能表现，分别将三种算法运用到tsp225、gil262、a280、rand300、lin318 实验中，实验结果由表8 与图4 所示。

由表8 可以看出，在5 组大规模问题中，ACS 和ACS+3opt都未能取得标准最优解，且迭代次数较多，收敛速度都需要进一步优化，而RCACO 在tsp225 和a280 得到了标准最优解，在另外3 组不同规模城市的实验中，都能将最优解的误差率控制在1%以下，且迭代次数都比较少，表明改进算法能很好地改善解的质量，提高求解速度。

由图4 可以看出，改进算法的收敛速度较快，且具有较强的跳出局部最优的能力。例如在tsp225 的实验中，改进算法的曲线图下降速度明显优于传统蚁群算法，而且在算法多次迭代没有变化时，改进的算法可以对停滞现象做出处理，跳出局部最优，最终得到标准最优解。

图5 是参加实验的15 个TSP 实例的稳定性对比图，其中，平均误差率是指对每个TSP 实例进行15 次实验的误差率均值，也即平均解的误差率。其值越小，说明算法随机进行某次实验得到高质量解的概率越大，也即稳定性越强。在不同规模的TSP 实例中，两种传统蚁群算法的平均误差率各有高低，而RCACO 算法的平均误差率一直优于传统蚁群算法，且稳定在2%以内，这表明RCACO 算法能有效改善平均解的质量，增强算法的稳定性。

综合以上对实验结果的对比分析，可以明确看出：相比于传统蚁群算法而言，RCACO 算法无论是在中小规模还是大规模的TSP 实例中，其收敛速度都更快、收敛精度都更高、稳定性都更强，表明了改进算法能够有效平衡解的质量和收敛速度之间的矛盾，并进一步提升了算法的稳定性和跳出局部最优的能力。

Table 8 Performance comparison of test sets for large-scale cities表8 大规模城市测试集的性能对比

Fig.4 Experimental comparison of large-scale test sets图4 部分大规模测试集实验对比

Table 9 Comparison of RCACO and other improved algorithms表9 RCACO 与其他改进算法对比

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

3.4 与当今最新改进算法对比分析

为进一步检验算法的性能，本文将RCACO 算法与最新的改进蚁群算法及其他算法进行比较，结果如表9 所示。表中数据为各算法所得到的最优解及其与标准最优解之间的误差率。

根据表9 的对比结果可以看出：在小规模TSP 问题中，RCACO 算法求解的精度不逊色于其他算法；在中大规模的TSP 问题中，其他算法未能求出标准最优解的情况下，RCACO 算法依旧可以找到标准最优解。由此可见，RCACO 算法求解旅行商问题的性能更为高效。

4 结束语

针对传统蚁群算法收敛速度慢、易陷入局部最优等问题，本文提出了一种基于动态重组和协同交流策略的蚁群优化算法（RCACO）。算法将蚁群划分为贪婪蚁群和探索蚁群，两类蚁群分别执行不同的状态转移规则和信息素更新规则，共同向最优解靠近，有效平衡了算法的收敛速度和多样性。其次，本文提出了一种基于线索二叉树的新型重组算子，并采用不同的重组策略对解集进行动态重组，避免了传统的盲目随机重组，有效提升了算法的多样性和平均求解质量。此外，本文提出了一种基于相似度和潜力值的协同交流策略，让两类蚁群将潜力较大的优良路径片段作为共享信息进行种群间的交流，有效提高了算法的收敛速度。最后，算法还加入了停滞规避策略，保证了算法后续循环的有效性，大大增强了算法跳出局部最优的能力。

在标准TSP 实例上的仿真结果表明，改进的蚁群算法在收敛速度、求解精度和算法稳定性等方面均有显著提升。算法能在较少的迭代次数内找到中小规模TSP 问题的最优解，能较好改善大规模TSP 问题上解的平均质量，但对于超大规模TSP 问题求解精度仍需进一步提高。为提高超大规模TSP 问题中解的精度，今后将在优化多种群之间的博弈策略和信息素更新策略上作进一步研究。