蚁群算法及其在TSP问题中的应用研究

摘要：TSP问题是一类典型的NP完全问题，蚁群算法是求解该问题的方法之一。该文在研究蚁群算法的基本优化原理的基础上，建立了求解TSP 问题的数学模型，设计了一个求解TSP问题的蚁群算法程序，并通过仿真实验验证了算法的有效性，分析了蚂蚁规模、周游次数等因素对蚁群算法搜索结果所产生的影响。

关键词：TSP；蚁群算法；NP完全问题

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）13-3117-03

旅行商问题（Traveling Salesman Problem，简称TSP）是一个具有广泛应用背景和重要理论价值的组合优化问题，它已被证明属于NP难题[1]。目前对于求解该类问题的研究主要有两个方向：一是传统的数学规划方法，这种算法可以得到全局最优解，但复杂性往往难以接受，因而不适应于大规模复杂问题的求解。二是近年来发展起来的各种仿生进化算法如遗传算法、蚁群算法等，此类算法能够在多项式时间内找到全局最优解或近似全局最优解[2]。蚁群算法（Ant Colony Algorithm， 简称ACA）是受自然界中蚂蚁集体寻食过程的启发而提出来的一种新的智能优化算法，它具有高度的本质并行性、正反馈选择、分布式计算、鲁棒性等优点，蚁群算法最早成功地应用于解决TSP问题。

本文在研究蚁群算法的基本优化原理的基础上，编写了一个基于VC的求解TSP问题的蚁群算法程序，并且通过多次实验测试，验证了算法的有效性，分析了蚂蚁规模、周游次数等因素对蚁群算法的搜索结果和效率所产生的影响。

1 TSP问题建模

2 基于蚁群算法的TSP问题求解

2.2蚁群算法的基本原理

蚁群算法是一种源于自然生物界的新型仿生优化算法，它于20世纪90年代初由意大利学者M.Dorigo，V.Maniezzo首次提出[3]，蚁群算法的特点是模拟自然界中蚂蚁寻食的群体行为。研究表明，蚂蚁会在走过的路上留下信息素，信息素会随时间的推移逐渐挥发消失，蚂蚁就是通过信息素进行信息交流。蚂蚁趋向于朝信息素积累较多的路径移动，信息素浓度越高的路径，选择它的蚂蚁就越多，则该路径上留下的信息素浓度就越大，而高浓度的信息素反过来又会吸引更多的蚂蚁，从而形成一种正反馈。通过这种正反馈机制，蚂蚁最终可以发现最短的路径，并且最后所有的蚂蚁都会趋向于选择这条最短路径[4]。这就是蚁群算法的基本原理。

2.2求解TSP问题的蚁群算法设计

2.3算法步骤

4 结束语

本文探讨了蚁群算法的基本优化原理，设计并实现了求解TSP问题的蚁群算法程序，通过实验验证了算法的有效性，同时，经过多次实验测试结果，分析了对蚁群行为和算法的解产生影响的各个因素。

蚁群算法作为一种新的仿生进化算法，它在解决许多复杂组合优化问题方面显示出了明显的优势，但也存在着诸如搜索时间较长等不足之处，因此，对算法的改进、收敛性分析及理论依据等方面还有待进一步深入研究。

参考文献：

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

[2] 周康，强小利，同小军，等.求解TSP算法[J].计算机工程与应用，2007（29）：43-47.

[3] DORIGO M， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems，1996，26（1）：1-26.

[4] 李志伟.基于群集智能的蚁群优化算法研究[J].计算机工程与设计，2003，24（8）：27-29.

[5] Dorigo M， Bonabeau E， Theraulaz G. Ant algorithms and stigmergy[J]. Future Generation Computer Systems Journal， 2000，16 （8）： 851-857.