蟻群優(yōu)化算法及其理論進展

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

關(guān)鍵詞:蟻群算法 離散域 連續(xù)域 收斂性

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

1 引言

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

2 蟻群算法理論研究

2.1 基本螞蟻算法

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

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

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

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

(1)

其中為啟發(fā)優(yōu)先系數(shù)且?？梢愿淖冃畔⑺嘏c啟發(fā)優(yōu)先系數(shù)的相對重要性。如果則最近的城市容易被選擇，這類似經(jīng)典的隨機貪婪算法。如果則只有信息素放大機制在獨自工作，這將導(dǎo)致算法迅速收斂于一個可能是非最優(yōu)的解。

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

在基本螞蟻算法中，通過應(yīng)用信息素更新來提高螞蟻構(gòu)建解的質(zhì)量，以全面提高算法性能。

(2)

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

2.2 改進螞蟻算法

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

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

(3)

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

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

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

。其中為常數(shù)，滿足

。這種方法的優(yōu)點是有利于發(fā)現(xiàn)更多的潛在最優(yōu)解，從而提高算法的搜索質(zhì)量。

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

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

2.3 連續(xù)域內(nèi)算法改進

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

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

3 收斂性研究

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

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

4 結(jié)語

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

參考文獻

[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動態(tài)任務(wù)分配研究[J]．計算機科學(xué)，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] 肖菁，李亮平．基于信息熵調(diào)整的自適應(yīng)蟻群算法[J]．計算機工程與設(shè)計，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] 倪世宏 秦軍立 蘇晨．一種求解連續(xù)空間優(yōu)化問題的動態(tài)蟻群算法[J]．電光與控制，2009，16(12):12～14．