米永強

摘要：蟻群算法是一種求解組合優(yōu)化問題較好的方法。在蟻群算法的基本原理基礎上，以旅行商問題為例，介紹了該算法求解TSP的數學模型及具體步驟，并通過仿真實驗與粒子群優(yōu)化算法等方法比較分析，表明了該算法在求解組合優(yōu)化問題方面具有良好的性能。

關鍵詞：蟻群算法；組合優(yōu)化；旅行商問題；粒子群優(yōu)化算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）07-1505-03

1 概述

旅行商問題（Traveling Salesman Problem ，TSP）是一類典型的NP難問題，有著重要的應用前景。其大致描述為：旅行商從某城市出發(fā)，要走遍n個城市，且每個城市只許走一次，最后又回到原出發(fā)的城市，該如何選擇一條旅行路線使其旅行的總距離最小。

意大利學者M.Dorigo[1]等人在20世紀90年代初受到自然界真實蟻群集體行為的啟發(fā)提出了一種新型優(yōu)化算法—蟻群算法（ant colony algorithm，ACA），并將該算法率先應用于求解旅行商問題（TSP），取得了很好的效果?；谙伻核惴ň哂休^強的魯棒性且易與粒子群優(yōu)化算法、模擬退火算法等其他算法結合的優(yōu)點，其引起了許多研究者的注意，并將其應用于通信、交通、電力等領域，從而解決了一些復雜的組合優(yōu)化問題。

2 蟻群算法求解TSP問題

2.1 蟻群算法的基本原理

生物學家通過觀察及研究發(fā)現，螞蟻覓食是一種群體性行為，而并不是單只螞蟻尋找食物源。螞蟻在尋找食物源的過程中會在其經過的路線上釋放一種信息素，并且螞蟻在運動中能夠感知其他螞蟻釋放的這種物質濃度。而螞蟻選擇路線的概率取決于該路線的信息素濃度，濃度越高的路徑意味著選中的概率就越大，從而該路線上的信息素濃度也會被加強，螞蟻群體正是靠著這種內部機制找到了從巢穴通往食物源的最短路線。蟻群算法從該模型中受到啟發(fā)而提出并用于求解優(yōu)化問題。

2.2 基于蟻群算法求解TSP的數學模型

從表1中可以看出這四種優(yōu)化算法在最大迭代次數上限 500 的情況下得到的最優(yōu)值和迭代次數各不相同，比較發(fā)現ACA得到的最優(yōu)值425.649較好且僅需迭代88次。雖然PSO得到的最優(yōu)值接近于ACA得到的，但是找到最優(yōu)值時迭代次數卻遠大于ACA，可見，在迭代次數上ACA具有較快的收斂速度。由此，可知ACA在求解Oliver30的TSP問題上更有優(yōu)勢。

在TSP城市規(guī)模增大的情況下，ACA在算法精度及算法的收斂速度方面是否仍具有優(yōu)勢，從通用TSPLB中選取了Eil51 及CH130這兩個TSP 問題，結果如表2所示。

從表2結果看出在解決大規(guī)模TSP問題中ACA得到的最優(yōu)值沒有SA得到的好，但在迭代次數上卻有明顯優(yōu)勢。綜合考慮，ACA不僅能節(jié)約迭代次數而且可以保證算法在規(guī)定的迭代次數內找到最優(yōu)值，相比其他算法減少了算法的迭代次數，并在一定程度上提高了算法的精度。

4 結束語

本文以旅行商問題為例探討了蟻群算法的基本原理，數學模型及其求解TSP的步驟，最后通過數值實驗并與粒子群優(yōu)化算法及其它算法進行了比較分析得出了該算法在求解TSP問題中性能良好。

作為一種新型優(yōu)化算法—蟻群算法，因其魯棒性強，易于與其它智能優(yōu)化算法結合的優(yōu)點[7]，其在諸多組合優(yōu)化問題及應用領域具有優(yōu)越性，但其理論與遺傳算法、禁忌搜索算法等理論相比還尚未成熟。因此，有待于進一步對該算法的改進、收斂性及理論依據等方面研究。

參考文獻：

[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] 黃友銳.智能優(yōu)化算法及其應用[M].北京：國防工業(yè)出版社，2008：93-97.