蟻群優化算法及其理論進展

摘 要:蟻群優化算法作為一種新的智能計算模式，近年來在理論研究上取得了豐碩成果。本文主要闡述蟻群優化算法的研究成果，論述了算法在離散域、連續域問題上的理論進展，然后對收斂性研究做了介紹。最后，闡述了蟻群優化算法的發展趨勢。

關鍵詞:蟻群算法 離散域 連續域 收斂性

中圖分類號:TP301.6文獻標識碼:A 文章編號:1674-098x(2012)04(a)-0032-02

1 引言

意大利學者Dorigo[1]等人根據真實螞蟻覓食行為，提出了蟻群優化算法的(ACO)最早形式—螞蟻系統(AS)，并應用在TSP旅行商問題中。該算法采用分布式并行計算機制，易與其他方法結合，具有較強的魯棒性。AS算法提出之后，其應用范圍逐漸廣泛，已經由單一的TSP領域滲透到了多個應用領域[2]，算法本身也不斷完善和改進，形成了一系列改進ACO算法。

2 蟻群算法理論研究

2.1 基本螞蟻算法

與真實螞蟻覓食行為類似，基本蟻群算法主要包括路徑選擇和信息素更新兩個步驟。以蟻群算法求解TSP問題為例[1]:TSP問題可表述成，旅行商走完n個城市有多種走法，每周游完所有城市可得長度為i的路徑，它們構成解的集合

。而每個解是依次走過n個城市的路徑距離構成的集合，可表示為。

設是在第g次周游中城市i上的螞蟻數。在算法周游過程中，每只螞蟻根據概率轉換規則生成一個有n步過程的行動路線，整個算法的周游過程以g為刻度，。其中是預先設定的算法最大周游次數，當所有螞蟻移動一次后，周游次數計數器加1。經過次周游，基本可找到一條最短路徑。設，NP為算法中總螞蟻數。

基本步驟為:算法開始時，每條路徑上初始信息素設置為常數，并對每只螞蟻設置隨機起始城市。螞蟻移動過程中，從城市i選擇移動到城市j主要是根據概率啟發公式(1)來完成，每次選擇的城市都是從可選城市列表中取出。

(1)

其中為啟發優先系數且。可以改變信息素與啟發優先系數的相對重要性。如果則最近的城市容易被選擇，這類似經典的隨機貪婪算法。如果則只有信息素放大機制在獨自工作，這將導致算法迅速收斂于一個可能是非最優的解。

為滿足一只螞蟻可以旅行n個不同城市，賦給每只螞蟻一個數據結構，稱禁忌表(tabu表)即tabu表與的集合為整個城市集合。tabu表存儲本次周游中已經走過的城市，禁止本只螞蟻在本次周游中再次訪問已訪問的城市。本周游結束后，tabu表置空，釋放螞蟻再次循環。假設是在g+1次周游時信息素值。

在基本螞蟻算法中，通過應用信息素更新來提高螞蟻構建解的質量，以全面提高算法性能。

(2)

而其中ρ是揮發系數，即信息素隨著時間的推移是逐漸揮發的;是第k只螞蟻在g到g+1次周游過程中放置在路徑上的信息素增量。

2.2 改進螞蟻算法

不可避免蟻群算法也有其明顯的缺陷，測試結果證明，基本AS算法要次于其它已經存在的優化算法，如計算量較大，需要較長的搜索時間，易陷入局部最優解等。為此，許多學者開發了一系列改進ACO算法。

對AS較早的改進是EAS[3]算法，其對信息素的更新規則進行了改進，信息素更新形式為:

(3)

在EAS算法中，定義為用于更新的解的集合，由每代生成的解(稱為)和目前找到的最好的解(稱為)組成。為解Ψ的權值，當，解的權值定義為，只有解的權值比較大，為。稱為品質函數，

。為解的集合Φ中的兩個不同的解。

ACS算法[4]與原始AS有多方面不同:在時，ACS與AS的轉化規則是一致的。當時，其轉換規則就來源于與問題相關的知識。q是均勻分布在之間的隨機變量，是一個可調參數;ACS算法把信息素更新分為全局更新和局部更新。全局更新僅應用中，ACS只更新屬于最好路徑的各條邊的信息素值;在局部搜索中，每次構造解后，對信息素應用如下方式進行信息素更新。

。其中為常數，滿足

。這種方法的優點是有利于發現更多的潛在最優解，從而提高算法的搜索質量。

MMAS算法[5]是ACO系列中最成功的改進之一，特征如下:算法開始時，通常多使用局部更新規則。算法運行時，更多使用全局更新規則。在MMAS中只有每次迭代后一只螞蟻的信息素更新，這只螞蟻可以是當前迭代中最好的解或截止當前的最好解解;為避免搜索停滯，對信息素設置一定的范圍，初始信息素設置為，可以在開始時較快的搜索到較好解。

此外，一些學者針對基本蟻群算法在求解大規模旅行商問題進易陷入停滯的問題，提出一種基于信息熵調整的自適應蟻群算法。該算法通過優化過程中種群的信息熵來衡量演化的程度，自適應地調整路徑選擇策略和信息素更新策略[6]。隨著人們對ACO研究的不斷深入，Dorigo等人對各種版本的蟻群算法進行總結，提出了蟻群優化元啟發式(ACO-MH)這一求解復雜問題的通用框架[7]，ACO-MH為ACO的理論研究和算法設計提供了技術上的保障。

2.3 連續域內算法改進

在離散優化問題中，蟻群算法的信息量留存，增減和最優解的選取，都通過離散的點狀分布方式進行的。因此，連續蟻群算法與離散蟻群算法至少應有信息量留存方式，蟻群在解空間中的尋優方式和行進策略等方面的不同。

Bilchev等最早將蟻群算法運用于連續優化問題，把整個搜索空間分成多個搜索域，使用遺傳算法對解空間進行全局搜索，并利用蟻群算法對所得結果進行局部搜索。但是算法在運行過程中出現螞蟻對同一個區域進行多次搜索的情況，算法效率較低。倪世宏等[8]在實現了連續蟻群算法的基礎上，針對容易陷入局部最優解的問題，對連續蟻群算法的全局轉移概率進行改進，提出一種動態蟻群算法，根據動態全局轉移概率分配螞蟻個數，進行不同階段的搜索。但在如何將蟻群優化思想有效地應用到連續空間優化中還沒有形成一致的看法。許多算法就結果的魯棒性、算法的推廣性來說，都有待進一步驗證。

3 收斂性研究

蟻群算法理論發展的“瓶頸”問題之一是算法的收斂性，研究算法的收斂性不僅可以深入理解算法機理，還可以對改進算法、編寫算法程序有重要意義。

在ACO的收斂性方面，Gutjahr作了開創性的上作，提出了基于圖的螞蟻系統元啟發式模型，證明了改進算法可與模擬退火算法獲得相似的結果，該模型在一定的條件下能以任意接近1的概率收斂到最優解。Stützle等對一類ACO算法的收斂性進行了證明，其結論可直接用到實驗證明最成功的兩個ACO算法—MMAS和ACS上。

4 結語

自蟻群算法創立以來，已有十多年的發展歷程，其良好的尋優性能越來越受到人們的關注。目前對算法的研究己由解決一維離散優化問題發展到多維離散優化問題，由離散域拓展到連續域研究。蟻群算法作為一類用于解決優化問題的隨機搜索過程。其收斂性研究依然是今后一個非常重要的研究方向，這對深入理解算法機理，改進蟻群算法具有重要意義。此外，蟻群算法同其它仿生學智能算法的融合目前也有了一定的研究成果，這也將是蟻群算法的發展方向之一。

參考文獻

[1] Colorni A，Dorigo M，Manlezzo V．Distributed optimization by ant colonies [C]∥Proceedings-European Conference on Artificial Life，ECAL1991． Paris:Elsevier Publishing，1991:134～142．

[2] 張晉，曹耀欽.基于混合遺傳蟻群算法的多Agent動態任務分配研究[J]．計算機科學，2011，38(10):268～270.

[3] Dorigo M．Optimization， learning and natural algorithms [D]． PhD thesis， Dipartimento di Elettronica， Politecnico di Milano，Italy，1992．

[4] Dorigo M，Gambardella LM．Ant colony system:a cooperative learning approach to the traveling salesman problem [J]．IEEE Transactions on Evolutionary Computation，1997，1(1):53～66．

[5] Stützle T，Hoos HH．MAX-MIN ant system[J]．Future Generation Computer Systems Journal．2000，16(8):889～914．

[6] 肖菁，李亮平．基于信息熵調整的自適應蟻群算法[J]．計算機工程與設計，2010，(22):4873～4876．

[7] Dorigo M， Caro GD， Gambardella LM．Ant algorithms for discrete optimization [J]．Artificial Life， 1999，5(2):137～172．

[8] 倪世宏 秦軍立 蘇晨．一種求解連續空間優化問題的動態蟻群算法[J]．電光與控制，2009，16(12):12～14．