蚁群算法及其在求解旅行商问题中的应用

米永强

摘要：蚁群算法是一种求解组合优化问题较好的方法。在蚁群算法的基本原理基础上，以旅行商问題为例，介绍了该算法求解TSP的数学模型及具体步骤，并通过仿真实验与粒子群优化算法等方法比较分析，表明了该算法在求解组合优化问题方面具有良好的性能。

关键词：蚁群算法；组合优化；旅行商问题；粒子群优化算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）07-1505-03

1 概述

旅行商问题（Traveling Salesman Problem ，TSP）是一类典型的NP难问题，有着重要的应用前景。其大致描述为：旅行商从某城市出发，要走遍n个城市，且每个城市只许走一次，最后又回到原出发的城市，该如何选择一条旅行路线使其旅行的总距离最小。

意大利学者M.Dorigo[1]等人在20世纪90年代初受到自然界真实蚁群集体行为的启发提出了一种新型优化算法—蚁群算法（ant colony algorithm，ACA），并将该算法率先应用于求解旅行商问题（TSP），取得了很好的效果。基于蚁群算法具有较强的鲁棒性且易与粒子群优化算法、模拟退火算法等其他算法结合的优点，其引起了许多研究者的注意，并将其应用于通信、交通、电力等领域，从而解决了一些复杂的组合优化问题。

2 蚁群算法求解TSP问题

2.1 蚁群算法的基本原理

生物学家通过观察及研究发现，蚂蚁觅食是一种群体性行为，而并不是单只蚂蚁寻找食物源。蚂蚁在寻找食物源的过程中会在其经过的路线上释放一种信息素，并且蚂蚁在运动中能够感知其他蚂蚁释放的这种物质浓度。而蚂蚁选择路线的概率取决于该路线的信息素浓度，浓度越高的路径意味着选中的概率就越大，从而该路线上的信息素浓度也会被加强，蚂蚁群体正是靠着这种内部机制找到了从巢穴通往食物源的最短路线。蚁群算法从该模型中受到启发而提出并用于求解优化问题。

2.2 基于蚁群算法求解TSP的数学模型

从表1中可以看出这四种优化算法在最大迭代次数上限 500 的情况下得到的最优值和迭代次数各不相同，比较发现ACA得到的最优值425.649较好且仅需迭代88次。虽然PSO得到的最优值接近于ACA得到的，但是找到最优值时迭代次数却远大于ACA，可见，在迭代次数上ACA具有较快的收敛速度。由此，可知ACA在求解Oliver30的TSP问题上更有优势。

在TSP城市规模增大的情况下，ACA在算法精度及算法的收敛速度方面是否仍具有优势，从通用TSPLB中选取了Eil51 及CH130这两个TSP 问题，结果如表2所示。

从表2结果看出在解决大规模TSP问题中ACA得到的最优值没有SA得到的好，但在迭代次数上却有明显优势。综合考虑，ACA不仅能节约迭代次数而且可以保证算法在规定的迭代次数内找到最优值，相比其他算法减少了算法的迭代次数，并在一定程度上提高了算法的精度。

4 结束语

本文以旅行商问题为例探讨了蚁群算法的基本原理，数学模型及其求解TSP的步骤，最后通过数值实验并与粒子群优化算法及其它算法进行了比较分析得出了该算法在求解TSP问题中性能良好。

作为一种新型优化算法—蚁群算法，因其鲁棒性强，易于与其它智能优化算法结合的优点[7]，其在诸多组合优化问题及应用领域具有优越性，但其理论与遗传算法、禁忌搜索算法等理论相比还尚未成熟。因此，有待于进一步对该算法的改进、收敛性及理论依据等方面研究。

参考文献：

[1] A. Colorni，M.Dorigo，V.Maniezzo，et al.Distributed Optimization by Ant Colonies[C].Proceedings of the 1European Conference on Artificial Life. 1991： 134-142.

[2] 郭平，嫣文静.求解TSP问题的蚁群算法综述[J].计算机科学，2007，34（10）：181-184.

[3] 史峰，王辉.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社，2011： 205-215.

[4] M.Dorigo，V.Maniezzo，A.Colorni.Ant System： Optimization by a colony of cooperating agents[J].IEEE Trans on SMC.1996，26（1）：29-41.

[5] 储理才.基于MATLAB的遗传算法程序设计及TSP问题求解[J].集美大学学报，2001，6（01）：14-19.

[6] 冯剑，岳琪.模拟退火算法求解TSP问题[J].森林工程，2008，24（01）：94-96.

[7] 黄友锐.智能优化算法及其应用[M].北京：国防工业出版社，2008：93-97.