基于贪心边的MMAS改进算法及在TSP中的应用

方洁

摘要：最大最小蚁群算法通过对信息素更新和限制的改进，有效提高收敛速度，但难以避免出现停滞并陷入局部最优的困境。基于贪心边的MMAS改进算法规定一种新的搜索停滞状态，设定不同等级贪心边，并在停滞状态下利用搜索过程中寻找到的贪心边进行优先搜索。该算法使搜索能够尽早地集中在有效边进行，丢弃“无用”搜索，提高发现更优路径的可能性。利用TSP标准实例进行测试，结果表明改进算法的最优解更加接近实际最优解，具有更高的全局寻优能力和更快的收敛速度。

关键词：贪心边；优先级；搜索停滞；最大最小蚁群算法；旅行商问题

DOIDOI：10.11907/rjdk.173153

中图分类号：TP312

文献标识码：A 文章编号文章编号：1672-7800（2018）008-0097-05

英文摘要Abstract：Through the update of pheromone and restriction improvement，MMAS can improve the speed of convergence effectively.However，it is difficult to avoid stagnation and falling into local optima.The improved MMAS algorithm based on greedy-edge defines a new search stagnation state and sets different levels of greedy-edges.When the new search stagnation state occurs，greedy-edges will be chosen.The algorithm focuses the search on the effective edges as early as possible，and discards the useless path.，thus the possibility of finding better path is improved.Experiments on data in TSPLIB show that the improved algorithm can get the optimal solution which is closer to the actual optimal solution，and has higher global optimization ability and faster convergence speed.

英文關键词Key Words：greedy-edge； priority； search stagnation； MMAS； TSP

0 引言

蚁群算法是一种成功应用于多种NP-hard组合优化问题的方法，这种思想来源于真实蚁群的行为，特别是它们的觅食行为，蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。利用信息素浓度大小表征路径的远近，蚂蚁会以较大概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，形成一种正反馈作用，直至蚂蚁找到一条从巢穴到食物源的最短路径。

至今，蚁群算法已经成功应用于旅行商问题、车辆路径问题[1]、智能装载问题[2-3]等多个领域，取得了较好的实验效果。然而蚁群算法也存在一些缺陷，特别是过早收敛、容易陷入局部最优解等。针对这些缺点，许多学者在基本蚁群算法（Ant Colony System，ACS）[4]基础上提出了不同改进算法，如Ant-Q蚁群算法[5]仅对循环中最短路径上的信息量作更新，并仅让信息量大的路径以较大的概率被选中；最大最小蚂蚁系统（Max-Min Ant System，MMAS）[6]限定了信息素值的上下限，使各条路径上的信息素保持在某个区间范围内，从而避免算法过早收敛；李成兵等[7]提出的改进蚁群算法以轮盘赌的方式进行状态转移，并调整全局信息素的更新方式增强全局搜索能力；耿志强等[8]提出的基于混沌的MMAS算法利用混沌的遍历特性产生一组较优路径指导初始信息素的非均匀分布，运用混沌扰动的方法增强算法跳出局部最优的能力；王宝生等[9]提出基于边缘初始化和自适应全局信息素的改进蚁群算法，具有较好的搜索最优解的能力，不会过早收敛。这些算法都一定程度提高了全局搜索能力，但不能避免停滞现象的出现，同时最优解的精度也有待进一步提高。

本文在MMAS的基础上提出一种改进算法，对算法的搜索停滞状态进重新定义，设置贪心边及其优先级，分析不同贪心边参数性能，并在该停滞状态下优先在贪心边进行搜索。根据优先级的高低进行选择，更快、更集中地进行有效搜索。最后利用TSP标准实例进行实验测试，结果表明该算法取得的最优解更加接近实际最优解，求解精度有较大提高，同时加快了收敛速度。

1 最大最小蚁群算法MMAS

旅行商问题即TSP问题，指给定一个城市的集合以及城市之间的旅行代价，寻找经过每个城市一次且仅一次，最终回到起始城市旅行代价最小的路径。若将该问题构造成一个图，则TSP问题可以抽象为寻找图中最短哈密尔顿回路[10]。

为有效防止算法早熟和停滞，MMAS算法在ACS算法基础上主要进行了以下两方面的改进：

（1）信息素更新。

在迭代过程中采用最优方案，即每次迭代后仅对一只蚂蚁经过的路径增加信息素。ACS改进算法一般仅使用全局最佳方案（从第一次迭代至当前迭代，找到最好解决方案的蚂蚁），MMAS则主要使用迭代最佳方案（即从本次迭代中找到最好解决方案的蚂蚁）。在迭代最佳和全局最佳蚂蚁中作出适当选择可以提高搜索性能。当仅仅使用全局最佳蚂蚁，搜索会很快集中到最终结果，更好的方案可能会被限制，容易陷入被低质量解决方案限制的危险，而选择迭代最佳蚂蚁则会降低这种危险，因为迭代最优的结果每次都可能不同。因此大多数路径上的信息素都会增强，不会过早陷入局部最优。

通常，在MMAS中选择混合的方案，即选择迭代最佳蚂蚁作为信息素更新的默认值，选择全局最佳蚂蚁用于一些固定次数的迭代。实验证明搜索过程中增加全局最佳蚂蚁用于信息素更新的动态混合策略是一种最优策略。因此，信息素更新遵循公式（3），其中Δτbestij=1/f（sbest），f（sbest）为迭代最佳路径长度或全局最佳路径长度[6]。

2 基于贪心边的MMAS改进算法（MMAS_GE）

2.1 搜索停滞状态处理

2.1.1 搜索停滞状态判断

文献[11]描述的搜索停滞是指每次迭代中所有的蚂蚁遵从相同路径，不断创建同样的路径，以至于更好的路径不可能被找到。实际搜索过程中会出现迭代最优解持续保持不变的情况，这说明算法有可能已陷入某一局部最优解，继续执行可能导致搜索停滞。为了避免出现停滞状态，应提前采取相应措施使算法继续向前推进。

在搜索停滞状态中，每次迭代所有蚂蚁遵从相同的路径，MMAS_GE算法采取提前检测的方法，设定一个限定值KeepMax=[蚂蚁总数/2]，即一半及以上的蚂蚁若遵从相同路径且迭代最优解持续KeepMax代内保持不变时，判定该算法处于搜索停滞状态。

2.1.2 贪心边及其优先级设置

2.1.3 路径选择

当算法处于停滞状态时，不再依据式（1）进行路径选择，需要对选择规则进行调整。由于贪心边中优先级较高的边可能获得较短的哈密尔顿路径，因此路径的优化选择在优先级高的边中进行。此外，由于TSP的最优解中绝对不含任何交叉线路的情况[12]，MMAS_GE算法针对贪心边进一步筛选。

当出现所述停滞状态时，整个搜索过程考虑以下两点：

（1）搜索的起点。在优先级为1的边中随机选择一个城市节点作为搜索的起点。

（2）下一个搜索的城市节点。蚂蚁选择下一个城市时依据贪心边的优先级进行选定，优先选择优先级高的边所对应的城市结点。若依据降序在所有优先级为1～3的边中没有可选的城市结点，则在剩余未访问的边中选择启发信息最大的边所对应的城市结点。同时，在可供选择的贪心边中选择不交叉的线路，若该边与已走过路径交叉，则修改其优先级为0，继续搜索。

由于蚂蚁所走的路径为一个哈密尔顿回路，因此在选择下一个搜索的城市节点时，有可能出现路径待选一端没有满足条件的城市节点，但路径的起点端却存在满足条件的城市节点与其连接，这时需要将整段路径反转。举例说明如下：某只蚂蚁经过路径为（a1，a2，…，ai-1，ai），选择第i+1个访问城市时，查找从ai出发的优先级为1的边，若存在则筛选出不相交的边，并通过轮盘赌算法选择其中一个结点作为第i+1个节点；若不存在，并不是立即查找从ai出发优先级为2的边，而是查找路径另一端a1节点是否存在对应优先级为1的可选边，存在则将该路径反转，即路径为（ai，ai-1，…，a2，a1），第i+1个访问的城市节点为与a1相连的可选节点；若两端均不存在满足条件的城市节点与其连接，则在从ai出发的优先级为2的边中继续查找，以此类推。

2.2 MMAS_GE算法步骤

算法的具体实现过程如下：

（1）算法参数和信息素的初始化，设定N_IT_COUNT为最大迭代次数，stopflag为搜索停滞标志量，初始为0（未停滞）。初始化每条边的最小哈密尔顿长度为某一恒定较大值，且优先级为0。

（2）根据状态转移函数计算概率pkij（t），选择下一个城市节点，搜索过程中不断更新每条边的最小哈密尔顿长度。此外，计算本次迭代取得迭代最优解的蚂蚁数量。

（3）根据MMAS算法中的信息素更新原则进行更新后，跳到步骤（6）。

（4）进入迭代循环。每次迭代结束时进行搜索停滞状态的判定，若stopflag=0，跳到步骤（2）；若stopflag=1，计算满足条件的贪心边并设置优先级，跳到步骤（5）。

（5）繼续迭代，m只蚂蚁均优先在贪心边中进行初始搜索城市的选取，并根据优先级的高低进行后续城市结点的选择。搜索完成后，跳到步骤（3）。

（6）若迭代次数=N_IT_COUNT，输出全局最优路径，结束算法；否则转步骤（4）继续搜索，直至算法结束。

3 实验仿真与分析

3.1 参数λ性能分析

为了考察参数λ对于算法效果的影响，并确定贪心边的优先级，采用标准测试用例eil51和kroA100进行分析，参数设置如下：蚂蚁个数m=n（城市个数），α=1.0，β=2.0，ρ=0.98，Pbest=0.05，每组蚂蚁迭代n*100次，每个测试用例运行20次。

针对eil51和kroA100，分别取λ为-2、-1和0进行测试，根据目前所得实际最优路径（以下称最优解）进行比对，可得在3种参数情况下，最优解中贪心边命中率（即最优解中属于贪心边的个数/最优解总边数，如eil51最优解总边数为51）见表1所示。

由表1可知，只有当λ取值为0时，才能在贪心边中命中所有最优解的边。此外，经过测试，当λ取值为3时，每次实验的迭代及全局最优解中的边均为贪心边，使得搜索的可选范围很广，不能突出贪心边的优势，仍然不能有效地获得全局最优解。所以MMAS_GE算法选取λ取值分别为0、1、2三个等级来设定贪心边，既保证最优解中的边都能在贪心边中命中，又能有效利用贪心边的优势进行求解。

3.2 改进算法对最优解和收敛速度的影响

为了检验算法的正确性和有效性，从TSPLIB中选择3个TSP实例eil51、kroA100和d198，利用C++语言编写程序进行测试，并与最大最小蚁群算法MMAS进行比较。算法中主要参数设置同3.1节，每组蚂蚁迭代n*100次，对各种算法测试20次求平均值。所得结果如表2所示。

由表2可以看出，在同样参数情况下，MMAS_GE算法的平均值更接近最优解，且在城市规模较小的情况下能多次取得目前实际最优解。

此外，本文在MATLAB 7.0软件上模拟两种算法在eil51、kroA100和d198三个实例的运行情况，横坐标轴为迭代次数，纵坐标轴为每次迭代的全局最优路径长度。由图1～图3的进化曲线可以看出，eil51和kroA100两种算法的收敛速度接近，但MMAS_GE算法求解精度更高，且随着迭代次数的增加后期仍能不断搜索到更优解。从d198的收敛曲线可以看出它的收敛速度高于MMAS，求解精度也更高。

3.3 与其它MMAS改进算法对比

文献[8]提出的基于混沌的MMAS算法能在算法陷入停滞时利用Tent映射将信息素转化为混沌变量，并运用混沌扰动的方法跳出局部最优解，具有较高的全局寻优成功率和较快的收敛速度。因此，利用上述3个标准TSP实例将改进后的算法与该算法进行比较。参数设置如下：m=40，α=1.0，β=2.0，ρ=0.95，Pbest=0.05，最大迭代次数100 000，每个测试用例运行20次。实验结果如表3所示。

表3针对3个实例对比MMAS_GE、CMMAS和MMAS 3种算法，其中指标SR是文献[8]提出的性能分析指标，称为寻优成功率，表示成功运行次数SRN占总运行次数TRN的百分比。成功运行是指某次搜索达到期望值Optimal×（1+1.25%），其中Optimal为全局最优路径长度，即要求误差不超过1.25%。总运行次数TRN如前所述为20次。而本算法在分析时设定Optimal为截至目前该实例的实际最优解。

从表3可以看出，可以分别从寻优成功率、最优解、最差解和平均值进行分析：

（1）MMAS_GE算法的寻优成功率最高，对3个实例的寻优成功率均为100%，说明所有误差均在1.25%以内，并且在d198中成功率相对于CMMAS提高了5%，相对于MMAS提高了20%。

（2）MMAS_GE算法的最优解和最差解的误差最低。当城市规模小于等于100时，3种算法都能获得最优解，但最差解均有較大提高，如eil51和kroA100两个实例的最差解误差MMAS_GE相比CMMAS分别降低了144%和0.43%，相比MMAS则分别降低了1.21%和073%；当城市规模大于100时，MMAS_GE在最优解和最差解上均表现出较好的性能，如在d198的测试中，最优解最接近实际最优解，误差仅为0.05%，相比CMMAS和MMAS分别降低了0.06%和0.23%，而最差解误差也分别降低了0.24%和0.67%。

（3）MMAS_GE算法的平均值精度也均有大幅度提升，3个标准实例的精度相比MMAS算法分别提高了0.26%、0.31%和0.15%。d198的测试结果显示，MMAS_GE与CMMAS算法的性能不相上下，均能取得较优的平均值。

综上可知，当蚂蚁数量小于或等于城市数量时，MMAS_GE算法均能取得较好的性能，所以适当提前处理搜索停滞，减少“无用边”的搜索，可以缩小搜索范围，提高搜索精度。

4 结语

本文提出的MMAS_GE算法是一种改进的MMAS算法，在信息素的更新上采用MMAS算法更新规则，但对搜索停滞状态重新进行约定，并设定3种级别的贪心边在停滞状态下进行优先搜索。从测试结果可知，该算法能让搜索较早地集中在优先级较高的贪心边中进行，避免了无用搜索，从而提高精度，特别是最优解的精度。但对类似d198这种城市规模较大的实例来说，处理时间较长，这是需要进一步解决的问题，今后可以考虑将固定顺序多次出现的城市作为一个整体，进一步缩小城市整体规模，达到降低算法复杂性、提高算法性能的目的。

参考文献：

[1] 谢骊玲，宋彦斌，杨坦，等.求解车辆路径问题的改进MMAS算法[J].计算机技术与发展，2016，26（3）：27-30.

[2] 田冉，孙林夫，唐慧佳，等.基于最大最小蚁群算法的多卸载点车载装箱模型研究[J].重庆交通大学学报：自然科学版，2016，35（2）：156-162.

[3] 葛玮，徐卫红，程海水.基于最大最小蚁群算法的智能装载方法[J].山东农业大学学报：自然科学版，2014，45（3）：366-371.

[4] DORIGO M，GAMBADELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

[5] DORIGO M，GAMBADELLA L M .A study of some properties of Ant-Q[C].Proceedings of the 4th International Conference on Parallel Problem Solving from Nature，1996：656-665.

[6] STUTZLE T，HOOS H.Max-min ant system[J].Future Generation Computer Systems，2000，16（8）：889-914.

[7] 李成兵，郭瑞雪，李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用，2014，34（S1）：131-132+165.

[8] 耿志强，邱大洪，韩永明.基于混沌的MMAS算法及其在旅行商问题中的应用[J].计算机工程，2016，42（3）：192-197.

[9] 王宝生，屈宝存.蚁群算法在求解TSP问题中的改进研究[J].电子设计工程，2014，22（22）：14-18.

[10] 姚金涛，祝胜林，孔宇彦.具有寿命估算的最大-最小蚂蚁系统[J].计算机工程与应用，2011，47（24）：27-29+50.

[11] DORIGO M，MANIEZZO V，COLRNI A.The ant system：optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man and Cybernetics，1996，26（1）：29-41.

[12] 侯文静，马永杰，张燕，等.求解TSP的改进蚁群算法[J].计算机应用研究，2010，27（6）：2087-2089.

（责任编辑：江 艳）