蟻群算法研究及前景

王焱偉

摘要：蟻群算法（ACA）是一種優(yōu)秀的啟發(fā)類分布進(jìn)化算法，對處理組合優(yōu)化類問題具有極佳的效果。分布式與正反饋機(jī)制使得弱小的個體能夠與種群聯(lián)系起來，從而解決復(fù)雜的問題。本文簡單介紹了算法的原理，描述以及參數(shù)的影響。文末列舉了該算法在實(shí)際生活中的應(yīng)用及其前景。

關(guān)鍵詞： 蟻群算法；參數(shù)；TSP

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）35-0270-03

The Study and Prospect of Ant Colony Algorithm

WANG Yan-wei

（North China University of Technology， Beijing 100144， China）

Abstract：Ant colony algorithm （ACA） is a new kind of heuristic bionic algorithm， which has excellent performance in solving combinatorial optimization problems. Distributed and positive feedback mechanism makes small and weak individual can be connected with the colony， so as to solve complex problems. This paper simply introduces the principle， description of the algorithm and the influence of the parameters. At the end of this paper， the application and prospect of the algorithm in real life are enumerated.

Key words：Ant colony algorithm；parameters；TSP

1 引言

仿生學(xué)的飛速發(fā)展，生物的行為模式給了人類研究學(xué)者很大的啟發(fā)，他們便由此提出了解決像NP類復(fù)雜問題的新穎方法。蟻群算法（ACA）是一個成功的例子。它是一種基于螞蟻覓食行為的仿生進(jìn)化算法，M .Dorigo 等人在1991年首次提出了這個算法。蟻群中的螞蟻在覓食過程中會在其經(jīng)過的路徑上釋放“信息素”，螞蟻并行的探索路徑，依靠信息素作為反饋信息選擇路徑，異步取得最優(yōu)解，該算法的核心就在于并行分布與反饋[1-2]。蟻群算法對解決TSP，QAP，SJP等問題具有良好的效果，現(xiàn)在其應(yīng)用已經(jīng)擴(kuò)展到各個行業(yè)的各方各面。

2 蟻群算法原理

由于蟻群算法是受螞蟻覓食行為啟發(fā)而想到的一種仿生進(jìn)化算法。為了更簡單地理解這個算法，為此我們首先來觀察螞蟻覓食的過程到底是怎樣的。

螞蟻在覓食時，總能找到最短的路線，這是因?yàn)楫?dāng)首只螞蟻首先到達(dá)路口時（無信息素），我們假設(shè)其等概率選擇其間某一條路徑，然后螞蟻會在其經(jīng)過的路徑上釋放“信息素”，而信息素會被蟻群中的其它螞蟻感知到，后來到達(dá)路口的螞蟻會根據(jù)信息素濃度選擇路徑，濃度越高，螞蟻?zhàn)哌@條路徑的可能性越大。在一定時間內(nèi)，宏觀上來看，距離更短的路徑會被更多的螞蟻經(jīng)過，使得這條路徑信息素濃度更高[8]。并且隨著時間推移，其他路徑上的信息素會逐漸揮發(fā)（或者說螞蟻們的記憶減弱），信息素的差異會越來越明顯，最終蟻群一定會找到那條最優(yōu)路徑。即使突然出現(xiàn)了障礙物，蟻群也會在短時間內(nèi)找到最優(yōu)路徑。在尋優(yōu)過程中，螞蟻們并行尋路，雖然個體能力不足，但它們通過信息素作為反饋信號與種群進(jìn)行間接地交流，然后找到了最優(yōu)路徑。

人工蟻群與自然蟻群具有很高的相似性，二者的覓食模式是相同的，但是人工蟻群在選擇路徑時，并不會像自然螞蟻那樣僅僅根據(jù)信息素盲目的選擇，它會根據(jù)已知數(shù)據(jù)有意識的做出更好的選擇，例如我們在TSP問題中，我們是知道點(diǎn)與點(diǎn)之間的路徑長度以及訪問過的節(jié)點(diǎn)的，人工蟻群會根據(jù)路徑長度與信息素濃度二者綜合考量來選擇路徑。

3 基本蟻群算法描述

景，由仿真實(shí)驗(yàn)來確定。在不同的實(shí)際應(yīng)用場景下，參數(shù)的選擇會極大地影響算法的性能。自蟻群算法出現(xiàn)以來，大量的ACO類算法被提出，例如AS，ACS，MMAS算法，并且與其他算法相融合的算法也稱層出不窮，但依然缺乏一種普適算法。

4 蟻群算法參數(shù)詳解

4.1 螞蟻數(shù)量m

蟻群算法是一種啟發(fā)式仿生進(jìn)化算法，通過多只螞蟻組成的種群來獲得最優(yōu)路徑。這個過程中，螞蟻分布式的探路，但是間接地與種群交流協(xié)作才是至關(guān)重要的。顯然，m越大，子集越大，蟻群算法的全局搜索能力和算法的穩(wěn)定性得以提高，但當(dāng)m過大時，單只螞蟻釋放的信息素對總體的影響微乎其微，信息正反饋?zhàn)饔脮幌魅?，搜索時間加長。反之，m 越小，子集越小，個體的影響過于突出，很明顯正反饋?zhàn)饔猛怀?，然而收斂速度過快的快，極易陷入局部最優(yōu)解。螞蟻數(shù)量的多少對于蟻群算法搜索的循環(huán)次數(shù)大致上是線性關(guān)系的，文獻(xiàn)[5]提出：當(dāng)螞蟻數(shù)量處于0.6倍城市數(shù)量和0.9倍城市數(shù)量之間時，在短時間內(nèi)可以得到一個相對優(yōu)秀的解。m值的選擇依靠于實(shí)際情況，對于不同的問題，一般通過仿真實(shí)驗(yàn)得到適應(yīng)的參數(shù)。

4.2 信息素?fù)]發(fā)因子ρ

前文中提到人工蟻群具有一定的記憶能力，仿照人類記憶的特點(diǎn)，隨著時間發(fā)展，記憶應(yīng)該被減弱。在算法中設(shè)置了ρ來代表信息素的揮發(fā)程度。收斂速度慢，局部最優(yōu)解是蟻群算法不可避免的兩大缺點(diǎn)。而ρ的選擇對這些缺點(diǎn)的影響極其巨大。如果ρ過大的話，以前路徑上的信息素?fù)]發(fā)過快，本次循環(huán)中能見度占主導(dǎo)地位，正反饋加強(qiáng)，收斂速度加快，卻容易得到局部最優(yōu)解，降低了全局的搜索能力。反之，ρ過小的話，正反饋相對較弱，收斂速度緩慢，耗時過長，相對的也增加了全局搜索能力。參考文獻(xiàn)[4]的研究，我們了解到當(dāng)ρ取值接近0.5時，蟻群算法的收斂速度與全局搜索能力較好。

4.3 信息啟發(fā)因子α和期望啟發(fā)因子β

5 應(yīng)用及前景

蟻群算法自提出以來已經(jīng)解決了很多實(shí)際的問題。例如在網(wǎng)絡(luò)中數(shù)據(jù)的傳遞，路由器就相當(dāng)于城鎮(zhèn)，各個路由器的連接存儲在路由表中，而需要傳遞的數(shù)據(jù)就相當(dāng)于螞蟻，如何更快更準(zhǔn)確的找到最優(yōu)的路徑，這和TSP問題是很相似的。蟻群算法在該領(lǐng)域的可行性在文獻(xiàn)[6]中已經(jīng)得到證實(shí)，其得到的路徑長度和呼叫拒絕率均優(yōu)于最小節(jié)點(diǎn)負(fù)載優(yōu)先的方法。還有生產(chǎn)調(diào)度類問題，比較著名的QAP和JSP，蟻群算法都具有良好的性能。而在電力系統(tǒng)優(yōu)化問題中，機(jī)組最優(yōu)投入問題是尋求一個周期內(nèi)各個負(fù)荷水平下機(jī)組的最優(yōu)組合方式及開停機(jī)計劃，使運(yùn)行費(fèi)用最小。利用路徑信息，決策信息，以及電網(wǎng)狀態(tài)信息等相關(guān)參數(shù)，將機(jī)組最優(yōu)投入問題類比為一個TSP問題[7]， 從而可方便地利用蟻群算法來求解.在連續(xù)函數(shù)優(yōu)化，機(jī)器人路徑規(guī)劃，光譜解析等各個領(lǐng)域，蟻群算法都表現(xiàn)出了極佳的性能，該算法的前景可以說是一片光明。

但是對于該算法的認(rèn)識還遠(yuǎn)遠(yuǎn)不足，我們還有很長的路要走。就目前而言，大量的研究還是基于對蟻群算法的仿真和優(yōu)化，研究的深度還遠(yuǎn)遠(yuǎn)不夠。隨機(jī)優(yōu)化和動態(tài)優(yōu)化，新的分析方法和模型，參量的合理選擇將會是本算法將來重要的研究方面。即使蟻群算法在一些領(lǐng)域中表現(xiàn)優(yōu)秀，但它仍然不具有普適性，如何擴(kuò)大其應(yīng)用范圍，增強(qiáng)其穩(wěn)定性與速度必也是研究學(xué)者不得不考慮的一大難題。

6 結(jié)語

蟻群算法是一種新型的仿生進(jìn)化模擬算法，大量的實(shí)驗(yàn)研究已經(jīng)表明其在組合優(yōu)化問題中的巨大優(yōu)勢，具有廣闊的發(fā)展前景。而且蟻群算法魯棒性強(qiáng)，并且易與其他算法相結(jié)合。雖然現(xiàn)在應(yīng)用依然局限在實(shí)際問題上，但隨著仿生學(xué)的發(fā)展和研究的進(jìn)步，相信會形成一套科學(xué)的理論體系和研究方法，這會是一個長期的過程，我們的研究還需不斷加深。

參考文獻(xiàn)：

[1] Colorni A， Dorigo M ，Maniezzo V， et al .Distributedoptimization by ant colonies[A].Proceedings of the 1stEuropean Conference on Artificial Life[C] .1991.134-142.

[2] DorigoM.Optimization， learning and natural algorithms[D] .Department of Electronics， PolitecnicodiMilano，Italy， 1992.

[3] Walter J， Gutjahr.AGraph_based Ant System and its convergence[J].Future Generation Computer System， 2000（16）：837-888.

[4]詹士昌，徐婕. 蟻群算法中有關(guān)參數(shù)的最優(yōu)選擇[J].科技同報，2003，19（5）：381-386.

[5]蔣玲艷，張軍，鐘樹鴻.蟻群算法的參數(shù)分析[J].計算機(jī)工程與應(yīng)用，2007，43（20）：31-36

[6]李連源，劉澤民，周正.“基于ACS的動態(tài)分布式路由算法，”北京郵電大學(xué)學(xué)報， 2000，23（2）.

[7] Sisw o rahardjo N S， El-Keib A A. Unit commitmentusing the a nt colony sear chalgorithm[A] . Proc of the2002 I ntConf on Pow erSy stem Technology[C]. Kunming， 2002. 2-6.

[8]溫文波.蟻群算法概述[J].石油化工自動化，2001（1）：19-22.