蟻群算法基本原理及綜述

摘 要：雖然蟻群算法出現時間并不長，但由于其自身具有較好的魯棒性，以及較強的正反饋機制，使得其在解決TSP問題中取得了較好的成果。在其他問題的解決中，由于其全局搜索性較差，極易出現局部收斂。文章通過對蟻群算法的基本原理與相關方法進行分析，以期對相關問題的改善提供借鑒與參考。

關鍵詞：蟻群算法；基本原理；分析

1 概述

鑒于傳統優化技術的使用需要建立在規范的數學基礎上，進而使得在求解過程中存在一定的限制。這就使得大量的現實問題不能解決。為進一步解決上述問題，上世紀80年代初興起的啟發式算法對上述現象進行了一種全新的嘗試。啟發式算法，即為一種常用求解方式，該方式可以在能接受的經費范圍內獲得最優解，然而卻無法保證所獲得的解存在可行性，同時還有可能無法描述所獲得的解的近似程度[1]。

在這一系列算法中，以遺傳算法（GA）、禁忌搜索算法（tabu search）、 模擬退火（Simulated Annealing）算法、粒子群算法（Particles Swarm Optimization）、蟻群算法（Ant Optimization）為代表，這些算法主要應用于傳統優化問題中難以建立數學模型的題目，也就是優化理論中NP-hard問題。另外，由于上述算法擁有一定的普及應用型，并且對目標函數與約束條件的限制相對寬松，因此已經普及到解決實際問題的各個方面中。

2 蟻群算法的基本原理

蟻群算法是意大利學者Dorigo Mden等人在上世紀九十年代，以螞蟻在自然界中協同工作尋找食物為模型，模擬螞蟻運動規律，并在運動過程中以信息素為牽引，控制螞蟻尋找最優路徑。由于信息素的加入，使得該算法具有了正反饋機制，具有良好的局部搜索能力。因此，蟻群算法已在多個領域得到了驗證，尤其是在車輛路徑以及車間調度方面。

蟻群算法來源于商旅問題。商旅問題就是指一位商人，從A地出發，經過多個城市，最后返回A地。在這一過程中全部的城市則必須被訪問一次，且僅一次，從而獲得路徑最短的距離。在蟻群算法構建中，螞蟻們將隨機決定下一個要訪問的城市。當t時刻位于城市i的螞蟻k選擇城市j為目標城市的概率為：

根據信息素更新方法不同，Dorigo M提出了三種不同的基本蟻群算法模型，分別稱之為螞蟻周期（Ant-Cycle）模型、螞蟻數量（Ant-Quantity）模型及螞蟻密度（Ant-Density）模型[2]。

但伴隨著算法的開展，信息素不斷增加，使得全部螞蟻都集中在某一路徑中，最后全部螞蟻所獲得的解全部相同，無法對空間開展深入搜索，極易出現局部收斂的現象。基于解決上述問題的目的，經過各方的研究，提出了蟻群系統，精英蟻群系統，最大最小蟻群系統等一系列算法。文章通過對多種群改進的蟻群算法、自適應蟻群算法以及與其他算法的融合這三方面的介紹，來說明蟻群算法在改進方面的一些研究成果。

（1）多種群改進的蟻群算法

針對傳統蟻群算法容易陷入局部最優解的現狀，進一步加大全局搜索，避免過早陷入局部最優解。多種群蟻群算法將蟻群隨機放入不同區域，每只螞蟻按照自身概率進行搜索，搜索一段時間后，信息素進行交換。這使得蟻群能對路徑做出更多選擇，以便挑選出最優解。

（2）自適應蟻群算法

傳統算法搜索到一定程度后會造成某條路徑上信息素越積越多且由于下一條路徑越短則該路徑被選中的概率越大，但是下一路徑較短，并不意味整條路徑是最短的，這會造成轉移概率基本不變，使得螞蟻總是選擇轉移系數最大的路徑，造成選擇的結果具有一定的確定性。而自適應蟻群算法，在搜索過程中采用確定性選擇和隨機選擇相結合的選擇策略，動態地對揮發因子進行變動，使得在初期搜索時，最優解路徑上的信息素濃度較高，揮發因子較小，造成蟻群容易聚集搜索。而到達一定搜索之后，信息素揮發因子變大，保證了全局的搜索。同時，設置信息素的濃度在一個合理區間內，使得信息素濃度不可能過大，也不可過小。

（3）與其他算法的融合

由于蟻群算法具有強大的正反饋機制，在這種反饋機制的引導下，使其具有了較強的局部搜索能力。

遺傳算法具有交叉和突變的屬性，使得遺傳算法具有強大的全局搜索能力，能夠全面對解進行搜索，但同時交叉和突變會對原有解產生較大的變化，不能對最優解進行繼承和發展，使得效率減低。由此可以看出，遺傳算法具有全局性，蟻群算法具有局部搜索性，兩者可以很好結合。

此外，粒子群算法的整體搜索能力也十分強大，其可以在顯示隨機性、全面性的基礎上，利用迭代次數來獲得次優解。再通過問題的次優解來對蟻群算法中信息素的分布進行調整，并且使用蟻群算法中的正反饋機制，利用其正反饋特點等優勢來獲得問題的精確解，進而全面提升求解的效率與精準度[3][4]。

3 結束語

經驗證[3][5][6][7]，以上三種算法在解決全局收斂性方面都取得了不錯的效果。前兩種算法，都是在傳統蟻群算法的基礎上，進行了部分修改，增加算法在選擇方面的不確定性，而第三種算法是借鑒了其他算法中全局搜索性較強的屬性，來彌補自身不足。這兩個方面將是以后研究的重要方面。

參考文獻

[1]Reeves CR （Ed）. Modern Heuristic Techniques for Combinatorial Problems[M]. Oxford：Blackwell Scientific Publications，1993.

[2]汪定偉，王俊偉，王洪峰，等.智能優化方法[M].北京：高等教育出版社，2007.

[3]張長春，蘇昕，易克初.粒子群算法和蟻群算法的結合及其在組合優化中的應用[J].空間電子技術，2007（2）.

[4]支成秀，梁正友.融合粒子群優化算法與蟻群算法的隨機搜索算法[J].廣西科學院學報，2006，22（4）：231-233.

[5]王俊良.蟻群算法與遺傳算法的融合及其應用研究[D].南京：南京郵電學院，2005.

[6]王穎，謝劍英.一種自適應蟻群算法及其仿真研究[J].系統仿真學報，2002（1）.

[7]胡乃平，王延智.多種群蟻群算法在多目標優化中的研究[J].科技信息，2012（17）.