螞蟻算法的應用與發展

葉 凡

(成都理工大學 管理科學學院，四川 成都 610059)

1 引言

螞蟻算法是一種用于解決搜索問題的優化方法。1992年，Dorigo在他的博士畢業論文中首次提出了此算法并用于解決了經典的離散組合問題商旅問題、二次分配問題。十多年來，螞蟻算法以及各種改進過的螞蟻算法，被廣泛的應用在實際生活的各個方面，應用范圍不斷擴大，在計算機技術應用、交通控制，圖表制作等都有螞蟻算法的影響。

2 螞蟻算法簡介

2.1 算法思想

螞蟻在路徑上前進時會根據前邊走過的螞蟻所留下的分泌物選擇其要走的路徑，我們把這種分泌物叫做信息素。其選擇一條路徑的概率與該路徑上信息素的強度成正比。因此，由大量螞蟻組成的群體的集體行為實際上構成一種學習信息的正反饋現象：某一條路徑走過的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個體間通過這種信息的交流尋求通向食物的最短路徑。

2.2 算法原理

下面介紹螞蟻算法的原理：第1步：初始化，NC=0，將m只螞蟻置于n個頂點上;第2步：將各螞蟻的初始出發點置于當前解集中;對每一個螞蟻k，按概率P選擇移至下一頂點j上;將頂點j置于當前解集;第3步：計算各螞蟻的目標函數值;記錄當前的最好解;第4步：按更新方程修改信息素軌跡強度;第5 步：對各邊弧(i，j)，Δτij=0，NC=NC+1;第 6 步：若搜索次數NC＜預定迭代次數且無退化行為(即找到的都是相同解)，則轉第二步;第7步：輸出目前的最好解。

2.3 基本螞蟻算法的優缺點

(1)優點：蟻群算法與其他啟發式算法相比，在求解性能上，具有很強的魯棒性和搜索較好解的能力，是一種基于種群的進化算法，具有本質并行性，易于并行實現，容易與多種啟發式算法結合，以改善算法性能。

(2)缺點：如果參數設置不當，導致求解速度很慢且所得解的質量特別差。計算量大，求解所需時間較長實際操作中很難讓所有螞蟻都選擇最優路線。

3 螞蟻算法的研究進展

3.1 改進的蟻群優化算法

螞蟻優化算法在提高螞蟻的搜索性能方面有著顯著的發展。但是在實際應用中，不同的搜索優化問題，基本螞蟻算法受到了許多條件的局限，并且這些束縛都要根據具體問題進行相應的處理，因此產生了許多改進的螞蟻算法以適應各領域的問題特點。

(1)基于優化排序的螞蟻系統

在螞蟻系統中加入遺傳算法排序的概念，當每只螞蟻都走完一條路徑后，根據路徑長度對螞蟻排序，根據該螞蟻的排名對激素軌跡量更新的貢獻進行加權。只考慮其中最好的W只螞蟻，并要避免很多螞蟻過分重視某些局部極優路徑的情況發生。

(2)最大-最小螞蟻算法。

該算法在蟻群算法的基礎上進行了改進，當在最佳路徑上時，此路徑的信息素的跡才會增加，通過信息素的跡被限定在一個范圍內，從而使得在當前找出的最好路徑的領域內螞蟻的搜索更集中。螞蟻算法的任務就是使問題不斷地向著最優化的方向進行。該算法的本質是對最優的解進行強化，并且對最差的解進行弱化，使最優路徑和最差路徑之間的差異化信息量變大，使螞蟻的搜索行為向最優路徑集中。

(3)多群螞蟻算法。

Middendorf和Martin提出多群螞蟻算法，利用若干個蟻群并行操作，每次迭代完成后，蟻群之間交換一次信息。螞蟻間進行交換信息的信息素有正信息素和負信息素兩種類型，進而提高了尋優過程的速度。MCAS在TSP和QAP問題的求解上有比AS更好的表現。

螞蟻算法的改進還可以與其他更多的智能算法進行結合，在許多問題上都能弱化自身單一的缺點，增強各自的優點來改進和完善算法的性能。

3.2 螞蟻算法在優化問題中的應用

蟻群優化算法已應用于許多組合優化問題，包括蛋白質折疊或路由車輛的二次分配問題，很多派生的方法已經應用于實變量動力學問題，隨機問題，多目標并行的實現。它也被用于產生貨郎擔問題的擬最優解。下面分別介紹了螞蟻算法在不同領域中的基本應用：

3.2.1 離散組合中的應用

除TSP早期最為經典以外，螞蟻算法早已應用到其他離散組合優化問題中：二次分配問題(QAP)指的是在n個地點分配n個設備使得分配代價最少，其實質也是TSP問題的一種。車間任務調度問題(job-shop)指的是一組M臺機器和一組T個任務，任務有一組制定的將在這些機器上執行的操作序列組成。還有許多問題，如指派問題、車輛路線問題(VRP)、有序排列問題(SOP)、圖著色問題(GCP)，電力系統故障檢測等。

3.2.2 連續空間中的應用

連續空間優化問題中的特點是隨著時間變化問題的解決方案也在變化。其中通信網絡問題是螞蟻算法解決連續空間優化問題中有代表性的一類問題。在國際上，Sehoonderwerd，White等人在路由有向和網絡路由問題中較早使用螞蟻算法.而Diearogy等人根據路由的自適應問題改進了螞蟻算法并更適用于此類問題的解決。在國內，也有了基于解決的QoS路由調度問題的螞蟻算法。

4 結束語

蟻群算法的本質是受自然界啟發的一種隨機優化算法，由于它具有很強的魯棒性和搜索較好解的能力使得在許多方面顯示出良好的計算性能。求解范圍由初始離散空間優化的組合擴大到約束多目標和連續的空間區域，并在社會學宏觀領域表現出強大的生命力。但是，不是所有的基本螞蟻算法都能解決優化問題，改進后的算法模型往往不是普遍適用，并且螞蟻在真實自然界中還有很多其他的智能行為可以研究。

［1]溫文波，杜維.蟻群算法綜述［J].石油化工自動化，2002(1).

［3]張賢達，保錚.通信信號處理［M].北京：國防工業出版社，2000.