蟻群算法的原理、模型及與其它算法的關系

摘 要：論述了蟻群算法的原理，通過雙橋實驗對蟻群算法的模型進行了討論，分析了蟻群算法的工作機制，與啟發式圖搜索、蒙特卡羅模擬、神經網絡、進化計算和隨機學習自動機等算法進行了比較，并對蟻群算法今后的研究方向指出了自己的看法。

關鍵詞：蟻群算法 啟發式圖搜索 蒙特卡羅 神經網絡 進化計算 隨機學習自動機

1 引言（Introduction）

20世紀90年代初，意大利學者M.Dorigo等人提出了一種新型的模擬進化算法——蟻群算法（ant colony algorithm， ACA）[1， 2]，該算法首先用于求解著名的解旅行商問題（traveling salesman problem， TSP），實驗結果表明蟻群算法具有較強的魯棒性和發現較好解的能力，但同時也存在一些缺陷，如收斂速度慢、易出現停滯現象等。針對該算法的不足，一些學者提出了改進的蟻群算法如蟻群系統 （ant colony system， ACS） [3]、最大-最小螞蟻系統（max-min ant system， MMAS）[4，5]和基于排序的螞蟻系統（rank-based version of ant system， ASrank）[6]等。這些改進算法在性能上有了極大的提高，很大程度上消除了搜索中的停滯現象，使蟻群算法更適合求解高維NP-Hard問題。繼成功求解TSP問題之后，許多學者利用蟻群算法求解其它組合優化問題[2，7-11]如二次指派問題（quadratic assignment problem， QAP）、車間作業調度問題（job-shop scheduling problem， JSP）、車輛路徑問題（vehicle routing problem， VRP）、圖著色問題（graph coloring problem， GCP）、通訊網絡路由問題（network routing problem， NRP）、背包問題（knapsack problem， KP）、交通分配問題（transportation allocation problem， TAP）、最小生成樹（minimum spanning tree， MST）問題、機器人路徑規劃問題和大規模集成電路（VLSI）設計問題等等。近年來，一些學者提出了蟻群優化元啟發式（ant colony optimization meta heuristic， ACO-MH），ACO-MH給蟻群算法提供了一個統一的框架，為蟻群算法的設計工作提供了技術上的保障，并為蟻群算法的理論研究打下了堅實的基礎。

2 蟻群算法原理與模型

象螞蟻這類群居動物，雖然個體的行為極其簡單，但由這些簡單個體所組成的蟻群卻表現出極其復雜的行為特征，能夠完成復雜的任務；不僅如此，螞蟻還能夠適應環境的變化，如圖1所示，在蟻群運動路線上出現障礙物時，螞蟻能夠很快地重新找到最優路徑。蟻群是如何完成這些復雜任務的呢？人們經過大量研究發現，螞蟻個體之間是通過一種稱之為外激素（pheromone）的物質進行信息交流、相互協作來完成復雜的任務。螞蟻在運動過程中，能夠在它所經過的路徑上留下該種物質，而且螞蟻能夠感知這種物質的存在及其強度，并以此指導自己的運動方向。螞蟻傾向于朝著該物質強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個體之間正是通過這種信息的交流達到發現最優路徑的目的。M.Dorigo等人充分利用了蟻群搜索食物的過程與著名的旅行商問題之間的相似性，通過人工模擬螞蟻搜索食物的過程（即：通過螞蟻個體之間的信息交流與相互協作最終找到從蟻穴到食物源的最短路徑）來求解TSP問題。（圖1）

蟻群覓食行為實際上是一種分布式的協同優化機制。單只螞蟻雖然能夠找到從蟻巢到食物源的路徑，但找到最短路徑的概率非常小。只有當多只螞蟻組成蟻群時，其集體行為才突現出螞蟻的智能——發現最短路徑的能力。在尋找最短路徑的過程中，蟻群使用了一種間接的通信方式，即通過向所經過的路徑上釋放一定量的外激素，其它螞蟻通過感知這種物質的強弱來選擇下一步要走的路徑。

在蟻群的覓食行為中，另一個重要的方面是自催化機制（正反饋機制）和解的隱式評估。自催化機制和解的隱式評估的組合，極大地提高了問題的求解效率，即對于越短的路徑，螞蟻將會越早走完，從而使更多的螞蟻將會選擇該路徑。自催化機制在基于群體的算法中非常有效，如在遺傳算法中，通過選擇和復制機制來實現。因為它獎勵好的個體，可以指導搜索方向。當然在使用自催化機制時，要努力避免早熟現象。在人工蟻群算法中，使用外激素的蒸發和隨即狀態轉移來彌補自催化機制的缺陷。

3 蟻群算法與其它算法的關系

作為一種新型的模擬進化算法，蟻群算法與啟發式圖搜索、蒙特卡羅算法、神經網絡、進化計算和隨機學習自動機有許多相似之處，同時也存在著差別。下面是蟻群算法與這些算法的比較。

3.1 啟發式圖搜索（Heuristic Graph Search， HGS）

在蟻群算法中，每只螞蟻在問題的解空間中按啟發式圖進行搜索。螞蟻按概率決策準則選擇下一個要到的節點。其中，概率決策準使用啟發式評估函數來指導螞蟻選擇更有希望的節點。

3.2 蒙特卡羅（Mente Carlo， MC）模擬

可以將蟻群算法解釋為并行的重復蒙特卡羅系統。蒙特卡羅系統是通用的隨機模擬系統，即通過利用隨機狀態采樣和轉移準則，對問題進行重復的采樣實驗。實驗所得的結果對問題的統計知識和感興趣變量的估計值進行更新。反過來，可以重復地使用知識以減少感興趣變量的不一致性，從而指導模擬過程向感興趣的狀態空間轉移。與此相似，在蟻群算法中，螞蟻利用隨機決策機制在問題的解空間中逐步發現問題的可行解。每只螞蟻自適應地修改問題的局部統計信息（即蟻群留下的外激素），通過stigmergy機制指導螞蟻沿著有希望的解空間向最優解靠近，從而節約了算法的搜索時間，避免資源的浪費。

3.3 神經網絡（Neural Network， NN）

由許多并發、局部交互的單元（人工螞蟻）組成的蟻群，可以看成是一種“連接”系統?！斑B接”系統最具代表性的例子是神經網絡。從結構上看，蟻群算法與通常的神經網絡具有類似的并行機制。螞蟻訪問的每一個狀態i對應于神經網絡中的神經元i，與問題相關的狀態i的鄰域結構與神經元i中的突觸連接相對應。螞蟻本身可看成輸入信號，并發傳播通過神經網絡并修改突觸與神經元之間的連接強度。信號經過隨機轉換函數的局部反傳，使用的突觸越多，兩個神經元之間的連接越強。蟻群算法中的學習規則可解釋為一種后天性的規則，即質量較好的解包含連接信號的強度高于質量較差的解。

3.4 進化計算（Evolutionary Computation， EC）

蟻群算法與進化計算之間有許多相似之處。首先，兩種算法都采用群體表示問題的解；其次，新群體通過包含在群體中與問題相關的知識來生成。兩者的主要差異是在進化計算中，所有問題的知識都包含在當前群體中；而在蟻群算法中，代表過去所學的知識保存在信息素的跡中。

與蟻群算法最相似的EC算法是Baluja等人提出的基于群體的增量學習（pupulation based incremental learning， PBIL）算法。在PBIL中維持一個實數向量，該向量與遺傳算法中的種群具有相似的作用。從該向量開始，隨機生成一個二進制串種群，并按某一概率將種群中的每個二進制串的第i位設置為1，其中的概率值為向量第i位的函數。一旦生成解的群體，將對群體中的解進行評估，評估結果用來增加/減少生成向量的各相應分量對應的概率值，以使將來好（壞）解將能以較高（低）的概率產生。顯然，在蟻群算法中，外激素的跡與生成向量具有相同的功能，外激素跡的更新與PBIL中生成向量的更新相對應。蟻群算法與PBIL的主要差別在于PBIL算法中所有概率向量的分量度的計算獨立進行，致使PBIL算法只適用于問題中解的每一個元素是相互分離的。

3.5 隨機學習自動機（Stochastic Learning Automata， SLA）

SLA是最古老的機器學習方法之一。自動機可定義為一組可能的操作和一個相關的概率向量，一組連續的輸入和一個學習算法用來學習輸入-輸出之間的關系。自動機與一個正反饋的環境相關聯，同時還定義了一組環境對行為的懲罰信號。SLA與蟻群算法的相似性為：在蟻群算法中，每條弧/鏈路上的信息素的跡可看成并發的隨機學習過程，螞蟻扮演環境信號的角色，其中外激素的更新規則相當于自動機的學習規則。兩者的主要差別在于蟻群算法中的環境信號是一種隨機的、通過概率轉移規則的偏差，學習過程沿著搜索空間中最感興趣的部分進行，即整個環境扮演了一個關鍵的角色，以此來學習好的解空間。

4 結論（Conclusions）

蟻群算法在各領域的應用說明該算法有著廣泛的適應性。但由于該算法出現較晚，對算法的許多特性，如收斂性，參數設定等都來自大量實驗統計結果，同時，對算法的理論研究、并行性研究的文獻也較少，而并行性正好是提高算法收斂速度的有效途徑。現在，蟻群優化思想在啟發式方法范疇內已逐漸成為一個獨立的分支，在有關國際會議上多次作為專題加以討論。1998年在比利時布魯塞爾大學召開了第一屆蟻群優化國際研討會，2000年、2002年仍在原地召開第二、三屆會議（Ants’ 2000，Ant’ 2002）。盡管蟻群算法的嚴格理論基礎尚未奠定，國內外的有關研究仍停留在實驗探索階段，但從當前的應用效果來看，這種模仿自然生物的新型系統尋優思想無疑具有十分光明的前景，更多深入細致的工作還有待于進一步展開。

參考文獻：

[1]A. Colorni， M. Dorigo， and V. Maniezzo. Distributed optimization by ant colonies[P]. In Proceedings of the First European Conference on Artificial Life， pages 134-142 Elsevier， 1992.

[2]M. Dorigo， V. Maniezzo and A. Colorni. The ant system： Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics Part B， 26（1）： 29-41， 1996.

[3]M. Dorigo and L.M.Gambardella. Ant Colony System： A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computations， 1（1）： 53-66，1997.

[4]T. Stützle and H.H. Hoos. Improvements on the Ant System： Introducing the MAX-MIN Ant System[J]. In R.F. Albrecht G. D. Smith， N.C. Steele， editor， Artificial Neural Networks and Genetic Algorithms， pages 245-249.Springer Verlag，Wien New York， 1998.

[5]T. Stützle and H.H. Hoos. The MAX-MIN Ant System and Local Search for Traveling Salesman Problem[P]. In T. Baeck， Z. Michalewicz， and X. Yao， editors， Proceedings of the IEEE International Conference on Evolutionary Computation （ICEC’97）， pages 309-314，1997.

[6]B. Bullnheimer， R.F. Hartl， and C. Strauss. A New Rank Based Version of the Ant System — A Computational Study[J]. Central European Journal for Operations Research and Economics.

[7]L. M. Gambardella， E. D. Taillard， and M. Dorigo. Ant colonies for the QAP[J]. Journal of the Operational Research Society （JORS）， 50 （2）： 167-1176，1999.

[8]A. Colorni， M. Dorigo， V. Maniezzo， and M. Trubian. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research， Statistics and Computer Science （JORBEL）， 34：39-53， 1994.

[9]B. Bullnheimer， R. F. Hartl， and C. Strauss. Applying the ant system to the vehicle routing problem[J]. IN I. H. Osman S. Vo， S. Martello and C. Roucairol， editors， Meta-Heuristics： Advances and Trends in Local Search Paradigms for Optimization， pages 109-120. Kluwer Academics， 1998.

[10]D. Costa and A. Hertz. Ants can color graphs[J]. Journal of the Operational Research Society， 48： 295-305， 1997.

[11]Lu Guoying， Liu Zemin. Qos Multicast Routing Based on Ant Algorithm in Internet[J]， The Journal of China Universities of Posts ant Telecommunication. Vol.7， No. 4， Dec. 2000.