结合局部优化的蚁群优化算法的研究与实现

结合局部优化的蚁群优化算法的研究与实现

刘景巍

刘景巍LIUJing-wei曰张迪ZHANGDi曰唐向辉TANGXiang-hui曰曲大鹏QUDa-peng

（辽宁大学信息学院，沈阳110036）

（CollegeofInformation，LiaoningUniversity，Shenyang110036，China）

摘要：蚁群算法是一种成功的启发式算法，但在解决TSP问题时存在着收敛速度慢和易陷入局部最优解的问题。本文针对这两个问题，提出了定期交流和模范带头学习模型，前者是在蚂蚁每走过一定城市后，进行学习交流，选出所走路径相对较短的蚂蚁进行信息素影响，从而加快总体的收敛速度；后者是当所有蚂蚁都旅行一圈后，选出最优秀的蚂蚁，在其走过的路径上释放大量信息素，对下一周期蚂蚁的旅行进行引导，避免陷入局部最优解。实验结果表明新算法在求解质量上比传统蚁群算法有了明显提高。本文也通过实验分析了蚂蚁数量等参数对算法性能的影响。

Abstract:Antcolonyalgorithmisasuccessfulheuristicalgorithm,butithastwodisadvantagesinsolvingTravelingSalesmanProblem(TSP),thatisslowconvergenceandeasytofallintolocaloptimaion.Inthispaper,theauthorsproposearegularexchangemodelandanexemplarymodeloflearning.Theformeristhateachantwalkingincertaincities,learningexchanges,thepathchosenbytherelativelyshortwalkpheromoneantinfluence,thusspeedinguptheoverallspeedofconvergence;thelatteristhatwhenalltheantsaretravelingaroundafterselectionofthemostoutstandingants,releaselargeamountsofpheromoneonitspathtraversedforthenextcycleofantstravelingtoboot,toavoidfallingintolocaloptima.Aftercomparisonwiththeconventionalantcolonyalgorithmfoundthatthenewalgorithmhasbeensignificantlyimprovedinthesolutionquality.Thepaperanalyzestheinfluenceoftheparameters,suchasantpopulation,onthealgorithmperformance.

关键词：蚁群算法；TSP问题；优化算法

Keywords:antcolonyalgorithm；TSPproblem；optimizationalgorithm

中图分类号院TP18文献标识码院A文章编号院1006-4311（2014）29-0227-03

0引言

蚁群算法（ACO）[1-2]是意大利学者Dorigo于1992年在他的博士论文中提出的，其灵感来源于蚂蚁觅食的过程。蚁群算法是一种仿生智能算法，早期主要应用于求解旅行商问题。经过多年的发展与研究，蚁群算法应用领域越来越广泛，如网络路由、分配，调度、机器学习问题等。虽然蚁群算法具有很多的优点，但由于相对较新，难免还存在一些缺陷，如收敛速度慢，易陷入局部最优解等。针对这些缺陷，人们提出了多种改进策略，包括：最大最小蚁群（MMAS）算法[3]、相遇蚁群算法[4]、云模型算法[5]和多态蚁群算法[6]等。

1基本蚁群算法介绍

蚁群算法是一种仿生算法，主要用于模拟自然界中蚂蚁寻找食物的过程。蚂蚁在寻找食物的过程中，会在它所经过的路径上散发出一种叫做“信息素”的物质。所有蚂蚁均能够感知到这种物质，蚂蚁可以通过辨别这种物质的浓度来指导觅食的方向，从而在大量蚂蚁共同寻找食物的过程中形成信息正反馈的现象。蚁群算法具有如下特性：淤自组织性。蚁群算法在开始的初期，个体蚂蚁均无序地寻找解，但经过一段时间后，蚁群通过信息素的交互作用，会自发地向最优解收敛，这个从无序到有序的过程，不受蚁群系统外任何因素的影响。

并行性。蚁群算法在同一个时刻，存在多只蚂蚁共同寻找最优解，它们共享信息素矩阵。不仅增强了算法的可靠性，更提高了算法全局搜索能力。

正反馈机制。通过信息素的引导使得蚂蚁向优质路径聚集，引导系统向最优解不断靠拢。正反馈是蚁群算法的最重要特性之一，它的存在使得算法能寻找到最优解。榆鲁棒性。蚁群算法有较强的鲁棒性，相对于其它算法来说，它对初始路线的要求不高。即蚁群算法的最后结果并不是依赖最初选择的路线。其次，蚁群算法在搜索过程中是自我调整的。另外，蚁群算法的参数较少，设置方便，使得蚁群算法能够更好的应用到其他的组合优化问题上。

2算法研究

2.1TSP问题描述TSP问题（TravelingSalesmanProblem）又称旅行商问题，是当今数学领域中一个著名组合问题。假设现在有N个节点，要寻找这样一条环路，每一个节点都要经过且只经过一次，并且总路径长度最短，即最短的哈密顿回路。

2.2对传统蚁群算法的缺陷分析

算法的运算量大，运算需要的时间很长。于算法对于参数的设置十分敏感，不同的参数对于运算结果的影响很大。

蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中，由于初始信息素匮乏，一般需要较长的搜索时间；另外蚁群算法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，陷入局部最优。

3优化算法实现与分析

3.1优化算法实现

3.1.1定期交流、模范带头学习模型定期交流模型：假定共有N个城市，M只蚂蚁。当每m（m<M）只蚂蚁通过n（n<N）个城市时，选取行走路径较短的a（a<m）只蚂蚁进行信息素影响，进行阶段性小组学习交流。不断重复这个过程直到N个城市全部旅行完。由于每只蚂蚁通过的n个城市并不完全相同，故蚂蚁间可以通过这种交流互相引导接下来旅途的前进方向，从而加快蚁群的收敛速度。实验证明，这种局部优化的思想非常有利于寻找局部最优解。

模范带头模型：当所有蚂蚁都旅行一圈后，选出最优秀的蚂蚁，在其走过的路径上释放大量信息素，覆盖先前定期交流时释放的信息素。通过这种模范蚂蚁的引领，在对下一周期蚂蚁的旅行进行引导的同时，还能够使蚂蚁避免陷入通过定期交流模型寻找到的局部最优解，实现整体的优化。

3.1.2算法的流程图

3.2实验结果分析

3.2.1实验数据分析

本节以TSP问题的eil51路径为例，将测试结果与ACA算法进行比较，实验中所使用的参数均通过实验确定。

通过结果可以看出，优化算法开始时（1-10次）收敛速度很快，随着迭代次数的增加，收敛速度减慢，一段时间后虽会陷入局部最优解（例如第3组数据，30-80次时均收敛到489），但不久后便会跳出（90次时便跳出局部最优解489），继续收敛。1000次后，均收敛到440以下，可以看出，优化算法具有较强的稳定性。

从图2可看出，优化算法与原算法相比，开始时收敛速度都很快，约迭代300次左右时收敛速度明显减慢，但优化算法相对于ACA算法减慢速度有了明显改善，平均收敛于435以下，而ACA算法则平均收敛于440以上。结合表2可发现，只对局部地区（点较稠密的地带）较优路径信息素更新和每次最优蚂蚁遍历的路径进行信息素加强的方法，有效地加快了路径优化的收敛速度，避免陷入局部最优解。当收敛到1000次左右时，改进算法无论从平均质量上还是稳定性上都有了明显改善，高稳定性的保证，使得此程序将更适合实际应用。另外，根据实验发现约在迭代2000次左右即可出现目前针于eil51路径发现的最优解426，而原算法至少要迭代上万次才可能出现。

优化蚁群算法是在全局范围内查找路径相对较短的一些点提前释放信息素，可以对未遍历这些点的蚂蚁起到一个引导作用。同时，可以在一定范围内找到路径较优的局部解，而且这些局部解很可能是全局最优路径的一部分。另外，通过全局大量释放信息素，也可以防止蚁群算法受到局部最优解的影响。优化蚁群算法会在较疏的点上放置较多蚂蚁，在较密点上放置少量蚂蚁，这样是为了防止局部稠密点上信息素浓度过高影响全局最优解的查找。

在求解方式上，优化的蚁群算法和ACA算法在求解方式上有不同的地方，以上均有描述。优化的蚁群算法在目的上就是紧紧抓住小距离路径（路径长度比较小的那一小段路径），因为这一小段的距离比较小的路径很可能是最优解的一部分，即使不是最优解的一部分，也对整体蚁群求解具有指导性作用（通过过多释放信息素）。最理想的情况就是，找到的几个最短路径全都是最优解的一部分，在计算结束的时候，多个小路径大体上已经组成了最后的最优解。

在结果比较上，蚁群算法在eil51上展现出了其优越性，在最后得到的结果上看，优化的算法可以在循环较少的次数上得到令人满意的结果。在运算的过程中，我们可能会发现，本算法因为在单次循环的计算量相对较大，所以需要控制蚂蚁的数量来尽可能减少运算量（我们已经在实验中发现这个想法是正确的）。

3.2.2蚁群算法中蚂蚁个数的研究

在对蚂蚁系统初始化时，需要确定蚂蚁的数目和每只蚂蚁的出发城市。蚂蚁数目的确定对算法起着比较大的影响，一般来说，蚂蚁数目越多，算法的全局搜索能力越强，但随着蚂蚁的数目增多，计算量将成指数级增长。

根据实验发现，当蚂蚁数量较少时，实验的结果很大，当蚂蚁数量增加时，实验的结果会逐渐减少，当蚂蚁的数量达到某一数值时，继续增加蚂蚁的数量不会对结果产生较大的影响。而且，不管是理论和实验，蚂蚁数量的增加会增加整个系统的“负担”，即运算的速度明显减慢。所以，适当地找到最合适的蚂蚁的数量不仅可以得到我们希望的结果，而且可以极大的增加运算速度，减少运算的时间，提高整个系统的运行效率。

图3为本文算法在蚂蚁个数不同的情况下通过eil51测试的结果，可以看出，在线的右方结果基本没有变化，验证了本算法通过适当地减少蚂蚁数量加快整体的运行速度和效率的想法。

3.2.3参数分析

由于目前还没有一种有效的数学分析方法使不同情况下的蚂蚁系统都能生成最优的参数设置，而国内外有关蚂蚁系统的文献大都只笼统地提出一种参数配置，但在实验中我们发现对于不同规模的问题同样的参数所得的结果优劣差别很大。因此，本文通过大量仿真实验有针对性地对参数进行了测试，研究参数对算法的影响。实验结果如表3。

从以上关于蚁群系统的参数分析上可以发现，当琢<茁时，可以得到一个令人满意的结果，也就是说，如果适当调整参数，可以优化整个蚁群系统，从侧面也反映出了蚁群算法对参数敏感的特性，因此我们需要根据具体情况调整参数进而得到我们需要的结果。

4总结

针对蚁群算法在求解TSP问题时，收敛速度慢、易于停滞等现象，本文提出了定期交流、模范带头学习模型。该算法提出了信息素局部和总体相结合的释放方法，用于更好的平衡求解效率与求解质量之间的矛盾。同时，具体研究分析了蚂蚁数量以及参数对算法的影响并根据分析结果做了适当改进。实验表明，优化算法能够较快获得最优解。

参考文献：

[1]DorigoM,ManiezzoV,ColorniA.Antsystem:Optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystems,ManandCyberneticsPartB,1996,26(1):29-41.

[2]DorigoM,GambardellaLM.Antcolonysystem:Acooperativelearningapproachtothetravelingsalesmanproblem[J].IEEETransonEvolutionaryComputation,1997,1(1):53-66.

[3]StuzleT,HoosHH.MAX-MINantsystemandlocalsearchforthetravellingsalesmanproblem.In:Proc.ofthe4thIEEEInt’lConf.onEvolutionaryComputation(ICEC’97).NewYork:IEEEPress,1997：309-314.

[4]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报，2001，24（12）：1328-1333.

[5]LiZY,WangY,OlivierKKS,ChenJ,LiKL.Thecloudbasedframeworkforantcolonyoptimization.In:Proc.ofthe1stACM/SIGEVOSummitonGeneticandEvolutionaryComputation.Shanghai:ACM，2009，279-286.

[6]徐精明，曹先彬，王煦法.多态蚁群算法[J].中国科学技术大学学报，2005，35（1）：59-65.