陈 达，游晓明+，刘 升
1.上海工程技术大学 电子电气工程学院，上海 201620
2.上海工程技术大学 管理学院，上海 201620
旅行商问题（traveling salesman problem，TSP）是经典的组合优化问题，可以简单地描述成：旅行商从规定的几个城市中的某一起点出发，并通过所有给定的城市，且每个城市只经过一次，最后回到起点，从而找到一条最短闭合回路的路径问题。目前有很多可以解决TSP 问题的算法，蚁群算法因其良好的并行性和较好的鲁棒性成为了解决TSP问题最好的算法之一。
20 世纪90 年代初，意大利学者Dorigo 等人[1-2]受到蚂蚁觅食行为的启发提出了蚂蚁算法（ant system，AS），但算法有着收敛速度慢、容易陷入局部最优的缺点。于是在此基础上，Dorigo 等人在1997 年提出了全新的蚁群算法（ant colony system，ACS）[3]，相较于AS算法，该算法大大地提高了收敛速度和求解精度。同时期，由Stutzle 等人提出了最大最小蚂蚁系统（max-min ant system，MMAS）[4]，该算法为信息素设置了上下限阈值，避免了信息素浓度无限累加以致算法停滞，提高了算法的求解效率。以上就是经典的蚁群算法，它们都具有效率较高的求解能力，但仍就存在易于陷入局部最优、收敛速度慢等问题。
此后众多的专家学者针对这些问题提出了自己的改进，文献[5-7]提出了融合遗传-蚁群算法，一种引入代价算子的蚁群算法和一种自适应分组的蚁群算法，分别利用了遗传算法前期收敛速度快，引入代价算子控制搜索方向和让蚁群自适应分组的方式，很好地提高了算法的收敛速度，但存在着多样性较差，求解质量不高的问题。文献[8]与文献[9]分别使用了一种新的信息素二次更新机制和使用K-Means 聚类算法生成城市关联矩阵影响蚂蚁选择城市的概率的方法，从而增加了算法的多样性，但算法收敛速度略有不足。文献[10]提出了一种新的信息素更新方式，从而在加快算法收敛速度的同时扩大了搜索范围；
文献[11]使用了拥挤度与2-opt 算子，提高蚁群算法的收敛速度和全局搜索能力，从而很好地平衡了收敛速度和多样性之间的关系，但由实验结果可知，对于较大规模的城市的求解精度有待提高。
针对以上问题，提出一种引入特征迁移和匹配学习的双蚁型蚁群算法（dual ant colony algorithm based on backtracking migration and matching learning，BMACS），通过改进的动态分级策略，根据个体适应度的评价，将蚂蚁分为探索蚁和追踪蚁，探索蚁适应度好，通过较大权重的动态信息素更新增强自己的影响力，起到导向作用；
追踪蚁跟随探索蚁，每只探索蚁通过分配规则分到若干追踪蚁，随后追踪蚁在探索蚁附近搜索次优路径，扩大搜索范围。其次，提出一种局部迁移机制，通过局部特征迁移策略将探索蚁得到的解选出公共路径，并作为局部特征通过局部信息素奖励迁移到信息素矩阵中，进一步加快收敛速度；
通过变异学习策略，针对探索蚁的路径使用分配的追踪蚁进行变异学习操作，搜索探索蚁附近路径的探索，从而增加多样性，产生的新个体与原个体进行比较择优保留。最后匹配学习机制通过余弦相似度选出历史最优解，并与当前最优解进行匹配，保留之间公共路径的信息素，并对非公共路径的信息素进行平滑操作，帮助算法跳出局部最优。实验结果表明，本文算法在解决TSP问题时相比原算法有一定的提高，较好平衡了算法收敛速度与多样性之间的矛盾，并对较大规模的TSP问题求解也具有一定的提高。
1.1 路径构建
在ACS算法中，蚂蚁k当前位置在i处，遵循伪随机规则选择自己将要访问的城市j，其规则如式（1）：
其中，q是均匀分布在区间[0,1]上的随机变量；
q0是一个参数，其范围是[0,1]；
J是根据式（2）给出的一个变量。
其中，α为信息启发式因子；
β为期望启发式因子；
为蚂蚁下一步可以直接到达并且尚未访问过的城市的集合；
ηij为启发函数，其表达式为式（3）；
τij是城市i到城市j所在边信息素的大小。
1.2 信息素更新
局部信息素更新规则：蚂蚁k从当前城市i到下一城市j后，立即进行更新信息素，如式（4）所示：
其中，ρ是局部信息素蒸发系数，其范围是[0,1]；
τ0是信息素初始值，这里根据实验结果选取τ0的值为1/nC时，算法性能较好；
n是城市节点数，C是一个常数。
全局信息素更新规则：当所有蚂蚁都走完之后，选择本次迭代中的当前最短路径进行全局信息素更新，如式（5）所示：
其中，ξ为全局信息素蒸发系数，Lbs为全局最优的路径长度；
为全局最优的路径改变的信息素，按照式（6）计算。
2.1 改进的动态分级策略
传统蚁群算法蚂蚁的探索行为单一，且个体之间的协作沟通不足，为了解决这一问题，本节提出一种改进的动态分级策略，通过式（7）评价每只蚂蚁个体适应度的好坏，并将蚂蚁分成探索蚂蚁和追踪蚂蚁，随后将若干追踪蚂蚁通过2.1.3 小节的分配规则分给探索蚂蚁，随后探索蚂蚁执行局部特征迁移策略交流各自的优秀解或片段，增强其导向作用，追踪蚂蚁通过变异学习策略跟随探索蚂蚁所走的路径附近，追踪次优级的路径，并通过局部信息素的自适应更新反馈给探索蚂蚁，提高探索蚂蚁的局部搜索能力，若追踪蚂蚁在局部搜索的过程中找到更优的解则替换掉该路径，提高算法效率，两种蚂蚁的关系如图1所示。
图1 探索蚂蚁与追踪蚂蚁交流Fig.1 Communication between exploration and tracking ants
2.1.1 适应度评价算子
在TSP问题中，蚂蚁在跑完路径之后得到的长度相差较大，并不适合直接评判解的优劣，故本小节提出一种适应度评价方法，如式（7）所示：
其中，Lj是第j个个体的解，λj是个体j的适应度，N是种群数目。由上述公式可知，适应度越小，蚂蚁个体得到的路径长度越小，从而适应度越好。
2.1.2 动态分级算子
动态分级规则如式（8）、式（9），由公式可知两种蚂蚁的数量并不是固定不变的，探索蚂蚁和追踪蚂蚁可以按照算法的当前状态互相转变。在算法的前期，探索蚂蚁数量较多，这样可以增强算法的导向能力，加快算法的收敛；
在算法的中后期，追踪蚂蚁的数量变多，将会加大对次优级路径的探索，增加算法多样性，使得算法不容易陷入局部最优。
其中，λi是个体适应度的大小，由式（7）计算得出，式（9）将根据个体λi的大小将蚂蚁种群分为两类，在0 ＜λi≤m中的为探索蚂蚁，在m＜λi＜1 中的为追踪蚂蚁。由式（9）可以看出，两种群体的数量会根据个体适应度的大小动态变化；
m是两种蚂蚁的动态阈值界点，由式（8）计算得出，其中λmin是当前迭代最小的适应度，λmax是当前迭代最大的适应度，是当前迭代所有适应度的平均值，在算法前期，个体之间适应度的差异较大，因此m的值也较大，更多的蚂蚁被选为探索蚂蚁；
在算法的中后期，随着个体之间的适应度差异减小，m也相应变小，更多蚂蚁被选为追踪蚂蚁。C是常数，由实验给出，以eil51 为例，每组30次实验，由表1可知当C取3时算法的平均误差最小。
表1 C 的取值对精度的影响统计Table 1 Statistics on influence of value of C on accuracy
2.1.3 追踪蚂蚁的分配规则
本小节将对2.1.2小节分级后的追踪蚂蚁进行分配，每只探索蚂蚁分到数量不等的追踪蚂蚁帮助其局部搜索。在算法前期，每只蚂蚁得到的解的质量不等，未进行充分的发展，所有解都可以认为有相同的潜力，因此在前期将追踪蚂蚁均匀地分配给每只探索蚂蚁；
在算法的中后期，经过充分发展后，每只探索蚂蚁的潜力将通过其各自的适应度体现，在这一阶段将按照探索蚂蚁的适应度成比例地分配追踪蚂蚁，适应度好的探索蚂蚁会分到更多的追踪蚂蚁从而获得更大的搜索能力，充分发挥其潜力。如图2所示，式（10）是每只探索蚂蚁按比例得到追踪蚂蚁的公式。
图2 追踪蚁的分配Fig.2 Distribution process of tracking ants
2.2 局部特征迁移学习机制
2.2.1 局部特征迁移策略
蚂蚁在遍历完所有城市后会得到一个解，解是由一组城市编号组成的序列，而适应度较好的个体一般具有一些共同的序列片段，这些序列片段可以看作每个个体之间共同的局部特征，本小节利用局部特征迁移策略提取出适应度较好的蚂蚁个体解中一些共有的局部特征，并将这些特征迁移通过局部信息素更新将这些特征映射到信息素矩阵中，随着算法的不断迭代，被采集特征的样本变多，被提取局部特征更加可靠，从而使得信息素空间更加具有导向作用，进一步提高算法的正向反馈能力。
（1）迁移样本选择
为了让优秀的个体提高其影响力，本小节将选取每次迭代中适应度较好的解作为特征提取样本，而探索蚁具有较好的适应度，因此本文选择探索蚁作为迁移样本。所选取的特征迁移到每只探索蚁各自被分配到的追踪蚁的解中进行解的重组从而得到新解。
（2）特征提取
如图3所示，每只蚂蚁个体的解是由城市序列组成的数组，每次选取的特征是蚂蚁走过城市编号的排列，在当前迭代下，选取的局部特征是当前探索蚁个体所有解的交集，如式（11）所示。
图3 公共路径选取Fig.3 Common feature selection
其中，v(t)是当前探索蚁个体所有解的交集；
A1到是当前探索蚁的路径，是由城市编号组成的一组序列，当前蚂蚁走过相同的路径超过三个节点即可被称为公共路径。
（3）局部特征迁移
如图4 所示，将探索蚁的公共路径选择之后，算法通过局部信息素的更新对这些公共路径进行奖励，从而完成对局部特征的迁移，之后通过信息素矩阵的影响，加快算法的收敛速度。式（12）是针对公共路径信息素的浓度。
图4 特征迁移Fig.4 Feature migration process
其中，是公共路径边的信息素；
n是城市的节点数；
Lmin是当前最优路径的长度。
2.2.2 变异学习策略
算法完成特征迁移后提高了收敛速度，但也增大了陷入局部最优的可能性，为了平衡特征迁移机制，本小节提出一种变异学习机制，帮助追踪蚁在探索蚁路径的次优路径进行局部搜索。如图5所示，在追踪蚁完成分配后，追踪蚁平均分布在探索蚁的路径上，随后针对每一段路径进行变异学习，完成对探索蚁次优路径的探索，从而提高算法的多样性。若新个体比原有个体适应度好，则代替旧个体进行局部信息素更新。
图5 变异学习Fig.5 Mutation learning process
变异学习规则对于符合要求的解在某个维度d(1 ≤d≤n)上面生成一个介于0 到1 之间的随机数，该随机数即为此解X的子序列X[d,d+l]突变的概率，其中d为1到n之间的一个随机数，l是由TSP城市的规模决定的，且l在[0,n-d]之间，对于选好之后X的子序列，将其序列进行翻转学习。在变异学习完成后，产生的新个体计算适应度并与原有个体比较，保留适应度较好的个体，提高算法效率。
2.2.3 信息素更新规则
（1）局部信息素更新
BMACS算法局部信息素更新如式（13）～（15）所示：
式（13）中λi是当前蚂蚁的适应度，λmax是当前迭代适应度的最大值；
式（14）中Lgb是当前迭代最优路径的长度；
式（15）中τa-l是被选中的片段更新的信息素，且只在该片段进行更新，La-l是当前蚂蚁找到的路径长度；
ρ是局部信息素蒸发系数。
（2）全局信息素更新
BMACS 全局信息素更新如式（5）、式（6）所示，在完成最优解的更新之后，将对自适应回溯策略的公共区域奖励信息素，奖励的大小如式（6）所示将按照当前迭代的最优解进行奖励。
2.3 匹配学习机制
传统的蚁群算法容易陷入局部最优，一般而言，当蚁群算法的信息素矩阵在某一条路径上的路径的信息素浓度过高时会减少对其他路径的探索，从而陷入局部最优；
根据这一特点，当算法陷入局部最优时，通过对信息素矩阵重组，改变信息素的分布就能增加算法跳出局部最优的可能性。重组信息素的方法有很多，其中最简单的是初始化信息素，但这种方法的缺点是不能记录蚂蚁寻解的经验，降低了算法的搜索效率；
本节中，为了尽量保留蚂蚁的经验，提出一种匹配学习机制，在该机制中，算法将会记录每次迭代的最优解，并通过相似度评价选择历史最优解，并与当前最优解进行匹配学习，保留公共路径信息素的同时，平滑非公共路径的信息素，最大程度上保留蚂蚁的优秀经验。
2.3.1 余弦相似度
余弦相似度是通过向量的余弦值判断个体之间差异的度量，本文中，用余弦相似度来度量当前最优解与历史最优解之间的相似度，从而选择一个相似度最高的历史最优解进行匹配学习。本文选择信息熵和公共路径节点与总结点的比值作为当前最优解的两个特征组成解的向量，如式（16）所示：
其中，T是余弦相似度；
x和y分别是历史最优解和当代最优解的二维向量，此二维向量(E,V)由信息熵E和公共路径节点与总结点的比值V组成，分别由式（17）、式（18）得到。
其中，E(x)是种群的信息熵；
L(x)是蚂蚁x解的倒数；
V是公共路径与城市节点的比值；
n是城市节点数；
v是公共路径，由式（11）得到。
2.3.2 信息素重组
通过余弦相似度匹配到学习的历史最优解后，保留当前最优解与历史最优解之间的信息素，而后对非公共路径节点的信息素进行信息素的平滑操作，平滑的大小如式（19）所示：
其中，Ph是非公共路径的信息素；
Phmin是信息素中的最小值；
Phmax是信息素中的最大值；
通过信息素中最大值和最小值的平均值对非公共路径的信息素进行平滑。
2.4 BMACS算法伪代码展示
算法1解决TSP问题的BMACS算法
2.5 BMACS算法与其他算法复杂度对比分析
表2展示了不同智能算法的复杂度[12]，本文算法BMACS分别与离散蝙蝠算法（discrete bat algorithm，DBA）、自适应模拟退火蚁群算法（adaptive simulated annealing ant colony algorithm，SA-MMAS）、烟花算法（fireworks algorithm，FWA）、混沌烟花算法(chaotic fireworks algorithm，CFWA）和ACS 算法进行对比分析，结果表明，BMACS 算法的复杂度与其他智能算法的复杂度相同，并未增加算法的时间复杂度。
表2 不同算法复杂度对比Table 2 Comparison of complexity of different algorithms
为了验证BMACS的算法性能，本文选取TSPLIP中14 个TSP 实例样本对算法进行测试，每个实例进行30 次实验，迭代2 000 次。本文实验测试环境为Windows 10 操作系统，利用MATLAB2019a 进行仿真，并与传统算法与其他的智能算法进行对比。
3.1 算法参数的确定
本节针对BMACS 算法的5 个参数使用正交实验确定最佳的参数组合，如表3所示。使用城市实例eil76，建立五因素四水平的正交实验，如表4 所示。每组的参数分别做20次实验并做平均，如表5所示。BMACS 的最佳参数组合是：α=2，β=4，ρ=0.2，ξ=0.2，q0=0.9。
表3 BMACS的实验因素和水平Table 3 Experimental factors and levels of BMACS
表4 正交实验方案及BMACS实验结果Table 4 Orthogonal test scheme and test results of BMACS
表5 BMACS测试结果分析Table 5 Analysis of test results of BMACS
3.2 BMACS算法的对比分析
本节使用14 个TSP 实例，将BMACS 算法与ACS 算法和ACS-3opt 算法进行对比，实验结果如表6所示。误差率的计算公式如式（20）所示：
由表6可知，BMACS算法在14个实例中在平均解、最优解、误差率等各项指标的对比中均优于ACS-3opt、ACS 算法；
在eil51、eil76 和rat99 这些小规模的城市中3 个算法均能够找到最优解，但BMACS 算法找到最优解的收敛迭代次数要小于ACS-3opt、ACS算法，这表明BMACS 算法有更快的收敛速度；
在kroA100、kroB100、ch130、kroA150、kroB150、kroA200、kroB200、tsp225 这些中等规模的城市中，BMACS 算法在kroA100、kroB100中找到了最优解，在其他的实例中误差也均小于0.5%，这表明算法在中规模的城市中与另外两个经典的算法相比较求解精度也较高；
在大规模的城市中，求解a280 的误差率在0.31%，在lin318、fl417 这两个实例的求解误差率也均在1%左右，这表明在大规模的城市中，BMACS算法也有着较高的求解精度。
由表6 的对比可知，经过特征迁移机制的影响，BMACS 算法很好地平衡了收敛速度和多样性之间的关系，使得算法在中小规模实例中的求解性能均优于ACS-3opt、ACS算法，在大规模的城市实例中虽然没有找到最优解，但求解的误差也较小，这说明BMACS 算法的局部特征迁移学习策略也发挥着较好的效果。图6 所示的是BMACS 算法找到最优解城市的路径。
表6 ACS、ACS+3opt、BMACS在不同测试集的性能对比Table 6 Performance comparison of ACS、ACS+3opt、BMACS in different test sets
图6 最优路径图Fig.6 Optimum path maps
3.2.1 BMACS算法多样性和收敛性分析
为了更好地验证BMACS算法性能，本小节将算法与ACS 和ACS-3opt 在收敛性和多样性两方面进行对比。本小节选取实例rat99、kroB150、kroA200做出各自的多样性图和收敛图，结果如图7～图9所示。
图7～图9中的（a）、（b）是BMACS和ACS-3opt的多样性图，随着城市数量的增多，两种算法的标准差波动差距随之变大，这说明算法的多样性也更为丰富，这是通过动态分级策略中的追踪蚁与变异学习机制的影响使得种群的多样性得到改善。由各图的（c）可以知道三种算法在收敛性上的表现，由收敛图可以很明显看到，BMACS在各种中大规模的城市中均能够快速收敛并且求解精度也高于ACS-3opt、ACS 算法。这是由于在算法的前期，通过局部特征迁移策略将优秀个体的解与其他个体充分交流，让其他个体吸收较好的片段，使得其快速收敛；
在算法运行的中后期，算法极易陷入局部最优，匹配学习机制使得当前最优解通过相似度匹配历史最合适的最优解，保留公共路径的信息素，平滑非公共路径的信息素，增加了算法后期的多样性，使得算法在后期更容易跳出局部最优。
图7 rat99测试集的对比Fig.7 Comparison of rat99 test set
图8 kroA150测试集的对比Fig.8 Comparison of kroA150 test set
图9 kroA200测试集的对比Fig.9 Comparison of kroA200 test set
3.2.2 BMACS算法与其他算法的对比分析
本小节将BMACS算法分别与随机插入烟花算法（random insertion of fireworks algorithm，RBIFWA）[12]、自适应升温模拟退火算法（adaptive temperature rise simulated annealing algorithm，SGSAA）[13]、基于SAC模型改进的遗传算法（improved genetic algorithm for solving TSP problem based on SAC model，GA-SAC）[14]、基于信息素初始分配和动态更新的蚁群算法（ant colony algorithm based on initial pheromone assignment and dynamic update，IADUACO）[15]、蚁群算法与3-OPT相结合的算法（ant colony algorithm combined with 3-OPT，PACO-3OPT）[16]、基于信息熵的动态异构蚁群算法（dynamic heterogeneous ant colony algorithm based on information entropy，EDHACO）[17]、基于皮尔逊相关系数的多种群蚁群算法（multiple swarm ant colony algorithm based on Pearson correlation coefficient，PCCACO）[18]、蜘蛛猴优化算法（spider monkey optimization algorithm，DSMO）[19]与水波优化算法（water wave optimization algorithm，WWO）[20]进行对比，实验结果表明相比其他算法，BMACS算法的精度更高，实验结果如表7所示。
表7 BMACS算法与其他算法的对比Table 7 Comparison between BMACS algorithm and other algorithms
3.3 算法机制的有效性分析
3.3.1 BMACS个体分布及其影响
为了研究两种个体在不同时期的影响力，本小节使用城市例子rat99列出了两种个体在不同时期的分布图表。图10中的两段折线图分别是探索蚁与追踪蚁在不同迭代次数下的分布。
图10 个体分布图Fig.10 Individual distribution map
由图10 可知，由于动态分级策略，探索蚁、追踪蚁的数量随着迭代次数的变化而动态改变，探索蚁及其影响力随着迭代次数的增大而减小，追踪蚁及其影响力随着迭代次数的增大而增大。
在算法前期，图中200代左右，探索蚁数量多，对其他个体产生的影响大，通过信息素更新产生了导向作用，使得算法能够在前期很快收敛到某个较好的路径。同时，追踪蚁发挥作用，搜索探索蚁周围的次优级路径。平衡精英个体，增加前期的多样性，避免算法陷入局部最优。
在算法中期，图中1 000代、1 400代左右，追踪蚁数量增多，加大了对探索蚁周围的搜索，增加了算法的多样性。
在算法后期，图中的1 800代、2 000代，追踪蚁产生的影响最大，此时信息素已经积累到了精度较高的路径。通过追踪蚁的搜索，并通过局部信息素更新，算法增加其他路径片段区域内的信息素浓度，避免算法陷入局部最优。
3.3.2 特征迁移策略的有效性分析
局部特征迁移策略作用于对蚂蚁种群中的比较优秀的个体，本文选取探索蚁作为局部特征迁移的作用对象，加快算法的收敛速度。为了验证其有效性，选取kroA100 做了三组实验，验证其在单独作用时迭代速度比经典的ACS算法快。由表8所知，在局部迁移机制单独作用下的算法与原算法相比精度与迭代速度均有所提高。随着迭代次数的增加，算法的精度越高，对于最优解的路径依赖就越强，个体之间的差异性越小，因此局部特征迁移策略增强了传统蚁群算法的正向反馈。
表8 性能对比Table 8 Performance comparison
3.3.3 变异学习策略的有效性分析
变异学习策略的作用对象是追踪蚁，变异对象由随机数与各自的适应度对比大小选出，被筛选出的蚂蚁会进行多维度的变异操作形成一个全新的个体，增加算法的多样性。选取eil51 对不同迭代次数下单独作用的变异学习与原算法对比多样性，结果如图11所示。
图11 eil51实例上变异学习与原算法对比Fig.11 Comparison between variant learning and original algorithm on eil51
3.3.4 匹配学习机制的有效性分析
匹配学习机制可以使得算法在陷入局部最优时增加算法多样性，保持最优个体的优势，从而帮助其提高跳出局部最优的可能性，因此在解决较大规模的TSP问题时自适应回溯机制可以帮助ACS算法提高寻解精度。本小节用lin318、fl417这两个大规模的实例各自做30 次实验，对加了自适应回溯机制的ACS 算法与经典ACS 算法进行对比，验证其有效性。由表9所知，匹配学习机制帮助ACS算法找到了更好的解，从而验证了机制可以增加算法跳出局部最优的可能性。
表9 匹配学习机制的对比分析Table 9 Contrastive analysis of matching learning mechanism
针对传统蚁群算法收敛速度慢、易于陷入局部最优等缺点，本文提出了一种引入特征迁移与匹配学习的双蚁型蚁群算法。首先，通过动态分级将蚂蚁分为探索蚁和追踪蚁，提高了蚂蚁之间的协作能力；
其次，通过特征迁移策略提高了算法的收敛速度，通过变异学习策略提高算法的多样性；
最后，提出匹配学习机制帮助算法跳出局部最优。
实验仿真结果表明，相较于经典的蚁群算法，本文算法加快了收敛速度，提高了多样性。在解决中小规模的TSP问题时，本文算法能够很快地找到最优解；
在解决大规模TSP问题中，本文算法虽然没有快速收敛到最优解，但依旧能保证解的多样性，在求解精度上，误差也较低。下一步的研究方向是利用聚类思想来解决大规模的TSP问题。