摘 要：論述了蟻群算法的原理，通過雙橋?qū)嶒瀸ο伻核惴ǖ哪Ｐ瓦M行了討論，分析了蟻群算法的工作機制，與啟發(fā)式圖搜索、蒙特卡羅模擬、神經(jīng)網(wǎng)絡(luò)、進化計算和隨機學(xué)習(xí)自動機等算法進行了比較，并對蟻群算法今后的研究方向指出了自己的看法。

關(guān)鍵詞：蟻群算法 啟發(fā)式圖搜索 蒙特卡羅 神經(jīng)網(wǎng)絡(luò) 進化計算 隨機學(xué)習(xí)自動機

1 引言（Introduction）

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

2 蟻群算法原理與模型

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

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

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

3 蟻群算法與其它算法的關(guān)系

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

3.1 啟發(fā)式圖搜索（Heuristic Graph Search， HGS）

在蟻群算法中，每只螞蟻在問題的解空間中按啟發(fā)式圖進行搜索。螞蟻按概率決策準(zhǔn)則選擇下一個要到的節(jié)點。其中，概率決策準(zhǔn)使用啟發(fā)式評估函數(shù)來指導(dǎo)螞蟻選擇更有希望的節(jié)點。

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

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

3.3 神經(jīng)網(wǎng)絡(luò)（Neural Network， NN）

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

3.4 進化計算（Evolutionary Computation， EC）

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

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

3.5 隨機學(xué)習(xí)自動機（Stochastic Learning Automata， SLA）

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

4 結(jié)論（Conclusions）

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

參考文獻(xiàn)：

[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.