蚁群算法的改进及其在TSP 问题中的 应用

蚁群算法的改进及其在TSP问题中的应用雷德明吴智铭上海交通大学自动化研究所200030上海摘要：在过去的10多年，蚁群算法（ACO）的研究和应用取得了很大的进展，大量结果证明了算法的有效性和在某些领域的优势。算法的基本缺陷：搜索时间过长和容易陷入局部解也得到了一定程度的解决，提出了一些有效的方法。但问题并未完全消除。本文首先分析了ACO中产生停滞现象的原因，然后给出了一种解决方案，通过直接交换部分边上的信息素和合理设定每条边的信息素挥发率，来克服算法停滞现象。仿真结果表明上述方法是可行和有效的。关键词：蚁群算法信息素旅行商问题TheImprovementofAntColonyOptimizationAlgorithmanditsApplicationtoTSPproblemLeiDemingWuZhiming(ShanghaiJiaotongUniversity,InstituteofAutomation,20030,Shanghai)Abstract:TheresearchesandapplicationsonACOalgorithmhavemadegreatprogressesinthepastmorethantenyears.Anumberofresultsprovethevalidityofthealgorithmanditsadvantagesinsomefields.Itsbasicshortcomings,whicharelongsearchingtimeandeasilyjumpingintolocaloptimalsolution,alsohavebeenovercomepartiallyandsomeeffectivemethodsareintroduced.However,theproblemsaren’tcompletelysolved.Thispaperfirstanalyzesthegroundsproducingstagnationandthenintroducesanewsolutionforexcludingstagnation,whichincludesthedirectexchangeofpheromoneonsomeedgesanddynamicallysettingevaporationrateforeachedge.Thesimulationresultsdemonstratethattheaboveapproachisreasonableandefficient.Keyword:AntColonyOptimizationalgorithmpheromoneTSPproblem1．引论蚁群算法（ACO）是受自然界中蚂蚁搜索食物行为启发而提出的一种智能优化算法。单个蚂蚁是脆弱的，但整个蚁群的群居生活却能完成许多单个个体无法承担的工作，蚂蚁间借助于信息素这种化学物质进行信息的交流和传递，并表现出正反馈现象：某段路径上经过的蚂蚁越多，该路径被重复选择的概率就越高。正反馈机制和通讯机制是蚁群算法的两个重要基础。正反馈作用能加快算法的搜索，也会导致算法出现停滞现象，而通讯机制能使个体相互协作，有利于算法搜索到更优解。目前，该算法在组合优化包括TSP,QAP等、车辆路径问题、电力系统中故障点的估计以及通讯网络等诸多领域得到应用。蚁群算法是一种本质并行的算法，和其它智能算法不同，其搜索时间比较长，新解的产生不是直接在已有解的基础上通过变换如GA的交叉算子而得到的，和其他算法一样，该算法也容易陷于局部最优解，使搜索停滞。本文给出了一种改进方案，通过直接交换部分边上的信息素和合理设定每条边的信息素挥发速度，来避免算法出现停滞现象。仿真结果表明新方法是可行和有效的。2．蚁群算法基本原理和遗传算法不同，关于蚁群算法的介绍往往要结合具体问题进行，通常选择的问题是TSP问题。该问题可以描述如下：设有个城市集，任意两个城市之间的距离为，求一条经过每个城市仅一次的路径，使得最小表示t时刻位于城市的蚂蚁的个数，为蚂蚁的总数。表示t时刻边上的信息素量，＝(为常数)。随着时间的推移，新的信息素加进来，旧的信息素要挥发，表示信息素的挥发快慢。当所有蚂蚁完成一次周游后，各条边上的信息素按下式调整：（1）(2)表示本次周游中路径上的信息素增量，初始时刻，＝0。表示第只蚂蚁在周游过程中释放在边上的信息素。（3）为常数，表示本次周游第只蚂蚁所形成的回路的长度。蚂蚁在周游时，向那个城市转移由转移概率决定。（4）其中＝表示蚂蚁当前能选择的城市集合，为禁忌表，它记录蚂蚁已路过的城市，用来说明人工蚂蚁的记忆性。是某种启发信息。在TSP问题中，。体现了信息素和启发信息对蚂蚁决策的影响。蚁群算法基本的运行过程是这样的：只蚂蚁同时从某个城市出发，根据（4）选择下一次旅行的城市，已去过的城市放入中，一次循环完成后，由公式（1），（2），（3）更新每条边上的信息素，反复重复上述过程，直到终止条件成立。蚁群算法研究包括算法的应用和算法的改进，利用蚁群算法解决实际优化问题是整个研究的主流，每年都要发表许多这类论文。关于算法的改进。可以从以下3个方面对算法进行。1.将算法和其它搜索方法结合，提高算法的搜索效率，例如：在算法中引入逆转变异方式，通过随机变异，增大搜索所需的信息量，克服了搜索慢的缺点。2－opt和ACO的混合也明显地改进了算法的计算效率。2.自适应调整参数等。FabioAbbattista等提出由GA优化AS的参数，将两种算法的优势结合在一起。而在文献[3]中，不再保持固定，而是随着搜索的进行动态地调整。文献[4]提出了自适应改变值的方法。3．设计，和等新的计算公式。SeungGwanLee等给出了一种信息素全局更新规则，根据该规则，高级个体经过的边要增加信息素，而低级个体路过的边要减少信息素。所谓高级个体是那些获得较优解的个体，两类个体各占一半。的公式也很多。和GA相比，蚁群算法相对简单，能加以改进的地方比较少，但现有的改进还不尽如人意，需进一步研究新方法和措施。3．蚁群算法的改进对ACO来说，之间的相对大小会直接影响城市到城市的转移概率，从而直接影响可行解的质量。在搜索早期，信息素的分布是分散的，随着搜索进行，信息素慢慢地集中到部分边上，搜索方向也随之基本确定。当某些边上地信息素强度明显高于其它边，导致在构造可行解时，总是使用少数几条边，就会使解的结构过于相似，搜索也会停顿下来，算法陷入局部最优解。虽然不同的智能算法出现停滞现象的原因各不相同，但结果是相同的，即所求的解越来越相似，避免这种现象的方法也是一致的，那就是增加解的多样性。并且有些增加多样性的手段也是通用的。例如：结合智能算法和局部搜索方法，就是一种常见的方法。当分别用GA和ACO求解TSP问题时，2－opt，3－opt等就曾分别和两种算法结合，并且效果明显。如何在ACO中增加解的多样性呢？关键是形成和保持一个合理的信息素分布，让较多的边能以较高概率用于构造可行解，也就是在“探索”和“利用”之间建立一个平衡点，既充分利用正反馈机制加快搜索，又尽可能地扩大算法的搜索区域，使用更多的边形成新解。通过加入新搜索方式，根据新解改变之间的相对大小和信息素分布，可以让算法逃离局部最优解。本文引入另一种通过直接交换部分边上的信息素避免搜索停滞的方法。其具体过程如下：对于个城市的TSP问题，每个城市设定交换概率，产生（0，1）上均匀分布随机数，如果，则在城市（起点）与其它城市可以形成的条边中，随机选出一定数量的边，然后两两互换相应边上的信息素。若，则不作上述处理。交换概率（<0.15）不能过大，过大会抑止正反馈作用。通过直接互换部分边上的信息素，改变了的分布，从而使人工蚂蚁在确定转移城市时有较多的选择，避免算法过早地陷入局部解。信息素的挥发率也会影响信息素分布。如何确定的大小，是应用ACO的关键。通常，被设置成常数，由经验或实验而定，且每条边的挥发率相同。实际上，在以城市为起点与其它城市形成的条边中，不一定每次每条边上的信息素都要挥发，例如：在搜索开始后很长一段时间内，让所有边上的信息素都不减少，能加快搜索。各个边之间也要有差别。一般情况下，较大的边用于构造可行解的概率较高，为了防止部分边上的信息素浓度过大，相应地，这些边上的信息素应挥发快一些。而为了避免最优路径上的某些边由于信息素强度过低而失去选择机会，这些边的值应该较大。的计算公式如下：（5）（6）表示t时刻边上信息素挥发率。是早期搜索时间，，但两者的差别不能太大。介于个的平均值与最大值之间。当所有蚂蚁完成一次周游后，先根据对各边的信息素强度进行调整，然后互换部分边上的信息素，改变现有的信息素分布。算法的具体步骤如下Begin初始化，，，，＝0，对任意边。while(){只蚂蚁从初始城市出发，根据（4）将所有城市周游一次。计算可行解，若新解优于旧解，则替换，否则，保留旧解2-opt等局部优化（option）利用包括最优回路在内的少量解更新，，根据交换概率选择城市，对选中的城市，在以该城市为起点的条边随机确定部分边，两两互换这些边上的信息素。,＝0,对任意边.}输出最终结果End4．仿真实验本文选用文献[7]中列出的两个TSP问题：50－city和75－city问题。这两个问题目前已知的最优长度为426.14和542.3。分别用基本蚁群算法BACO、没有信息素交换的ImprovedACO1和有信息素交换的ImprovedACO2对两问题进行求解，每个程序各运行20次，计算结果如表一所示。ImprovedACO2所获得的最优回路如图一、图二所示。表一：三种算法的计算结果算法50-city问题75-city问题平均值最好结果最差结果平均值最好结果最差结果BACOImprovedACO1ImprovedACO2434.2430.4442.8552.3549.9556.8428.7427.3429.9546.8545.3547.83427.5427.3427.8544.6543.0547.0图一50-cityTSP问题的最优回路(长度为427.3)图275-cityTSP问题的最优回路(长度为543.0)从表一可以发现，改进后ACO明显优于改进前的蚁群算法，而信息素的直接交换也改善了算法的求解质量，使解的平均值与最优结果之间的误差都在0.5%之内。验证了改进措施的有效性。5．结论如何抑止搜索停滞现象是设计大多数智能优化算法必须解决的问题，一些通用的方法可用来解决该问题，也应该存在专门解决某类算法停滞问题的途径。本文提出了避免ACO算法陷入局部最优解的专门方法：直接交换部分边上的信息素和动态地给每条边设置挥发率，这两种措施改善了算法搜索性能，提高了算法的计算效率。参考文献1．SeungGwanLee,TaeUngJungandTaechoongChungAneffectivedynamicalweightedruleforAntColonysystemalgorithmProceedingsofIEEEconferenceonEvolutionaryComputation2001v2:1393-13962．FabioAbbattista,NicolaAbbattistaandLauraCaponettiAnEvolutionaryandCooperativeagentsforoptimizationProceedingsofIEEEconferenceonEvolutionaryComputation1995v2:668-6713．覃刚力杨家