蟻群算法基本原理及綜述

陳少杰+麻莉娜

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

關(guān)鍵詞：蟻群算法；基本原理；分析

1 概述

鑒于傳統(tǒng)優(yōu)化技術(shù)的使用需要建立在規(guī)范的數(shù)學(xué)基礎(chǔ)上，進(jìn)而使得在求解過程中存在一定的限制。這就使得大量的現(xiàn)實(shí)問題不能解決。為進(jìn)一步解決上述問題，上世紀(jì)80年代初興起的啟發(fā)式算法對(duì)上述現(xiàn)象進(jìn)行了一種全新的嘗試。啟發(fā)式算法，即為一種常用求解方式，該方式可以在能接受的經(jīng)費(fèi)范圍內(nèi)獲得最優(yōu)解，然而卻無法保證所獲得的解存在可行性，同時(shí)還有可能無法描述所獲得的解的近似程度[1]。

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

2 蟻群算法的基本原理

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

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

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

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

（1）多種群改進(jìn)的蟻群算法

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

（2）自適應(yīng)蟻群算法

傳統(tǒng)算法搜索到一定程度后會(huì)造成某條路徑上信息素越積越多且由于下一條路徑越短則該路徑被選中的概率越大，但是下一路徑較短，并不意味整條路徑是最短的，這會(huì)造成轉(zhuǎn)移概率基本不變，使得螞蟻總是選擇轉(zhuǎn)移系數(shù)最大的路徑，造成選擇的結(jié)果具有一定的確定性。而自適應(yīng)蟻群算法，在搜索過程中采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，動(dòng)態(tài)地對(duì)揮發(fā)因子進(jìn)行變動(dòng)，使得在初期搜索時(shí)，最優(yōu)解路徑上的信息素濃度較高，揮發(fā)因子較小，造成蟻群容易聚集搜索。而到達(dá)一定搜索之后，信息素?fù)]發(fā)因子變大，保證了全局的搜索。同時(shí)，設(shè)置信息素的濃度在一個(gè)合理區(qū)間內(nèi)，使得信息素濃度不可能過大，也不可過小。

（3）與其他算法的融合

由于蟻群算法具有強(qiáng)大的正反饋機(jī)制，在這種反饋機(jī)制的引導(dǎo)下，使其具有了較強(qiáng)的局部搜索能力。

遺傳算法具有交叉和突變的屬性，使得遺傳算法具有強(qiáng)大的全局搜索能力，能夠全面對(duì)解進(jìn)行搜索，但同時(shí)交叉和突變會(huì)對(duì)原有解產(chǎn)生較大的變化，不能對(duì)最優(yōu)解進(jìn)行繼承和發(fā)展，使得效率減低。由此可以看出，遺傳算法具有全局性，蟻群算法具有局部搜索性，兩者可以很好結(jié)合。

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

[3]張長(zhǎng)春，蘇昕，易克初.粒子群算法和蟻群算法的結(jié)合及其在組合優(yōu)化中的應(yīng)用[J].空間電子技術(shù)，2007（2）.

[4]支成秀，梁正友.融合粒子群優(yōu)化算法與蟻群算法的隨機(jī)搜索算法[J].廣西科學(xué)院學(xué)報(bào)，2006，22（4）：231-233.

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

[6]王穎，謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2002（1）.

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