自適應(yīng)蟻群算法在TSP問題中的應(yīng)用與研究

賈麗媛，周翠紅（湖南城市學(xué)院，湖南 益陽 413000）

?

自適應(yīng)蟻群算法在TSP問題中的應(yīng)用與研究

賈麗媛，周翠紅
（湖南城市學(xué)院，湖南 益陽 413000）

摘 要：傳統(tǒng)算法在構(gòu)造解的過程中，利用隨機選擇策略，這種選擇策略使得進化速度較慢，正反饋原理旨在強化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象。這是造成蟻群算法的不足之處的根本原因．因而我們從選擇策略方面進行修改，我們采用確定性選擇和隨機選擇相結(jié)合的選擇策略，并且在搜索過程中動態(tài)地調(diào)整作確定性選擇的概率當進化到一定代數(shù)后，進化方向已經(jīng)基本確定，這時對路徑上信息量作動態(tài)凋整?？s小最好和最差路徑上的信息量的差距，并且適當加大隨機選擇的概率，以小于 l對解空間的更完全搜索，從而可有效地克服基本蟻群算法的不足，此算法屬于自適應(yīng)算法。

關(guān)鍵詞：蟻群算法；自適應(yīng)函數(shù)；全局優(yōu)化；函數(shù)優(yōu)化

在二十世紀九十年代初期，意大利M.Dorigo，V.Maniezzo，A.Colorni［1］等人首先提出了一種新的啟發(fā)式優(yōu)化算法，又叫蟻群系統(tǒng)（Ant Colony System），這種算法是目前國內(nèi)外啟發(fā)式算法中的研究熱點和前沿課題，被成功地運用于旅行商問題的求解，蟻群算法在求解復(fù)雜優(yōu)化問題方面具有很大的優(yōu)越性和廣闊的前景。但是，根據(jù)觀察實驗發(fā)現(xiàn)，蟻群中的多個螞蟻的運動是隨機的，在擴散范圍較大時，在較短時間內(nèi)很難找出一條較好的路徑，在算法實現(xiàn)的過程中容易出現(xiàn)停滯現(xiàn)象和收斂速度慢現(xiàn)象。在這種弊端的情況下，學(xué)者們提出了一種自適應(yīng)蟻群算法，通過自適應(yīng)地調(diào)整運行過程中的揮發(fā)因子來改變路徑中信息素濃度，從而有效地克服傳統(tǒng)蟻群算法中容易陷入局部最優(yōu)解和收斂速度慢的現(xiàn)象。

1　基本蟻群算法

1.1蟻群算法原理

人工蟻群算法是受到人們對自然界中真實的蟻群集體行為的研究成果的啟發(fā)而提的，是一種基于種群的模擬進化算法，屬于隨機搜索算法。由意大利學(xué)者M.Dorigo等人首先提出M.Dorigo等人首次提出該方法時，充分利用了蟻群搜索食物的過程與著名的旅行商問題（TSP）之間的相似性，通過人工模擬螞蟻搜索食物的過程（通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑）來求解TSP。蟻群是如何完成這些復(fù)雜的任務(wù)的呢？經(jīng)過人們大量研究發(fā)現(xiàn)，螞蟻個體之間是通過一種稱之為外激素（pheromone）的物質(zhì)進行信息傳遞從而能相互協(xié)作，完成復(fù)雜的任務(wù)。蟻群之所以表現(xiàn)出復(fù)雜有秩序的行為，個體之間的信息交流與相互協(xié)作起著重要的作用螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下該種物質(zhì)。

1.2蟻群算法的實現(xiàn)

設(shè)將M只螞蟻放入到N個隨機選擇的城市，每只螞蟻每一步的行動是根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市或者一個循環(huán)，螞蟻選擇下一個城市的主要依據(jù)是：τij（t）（t時刻連接城市i和j的路徑上殘留信息的濃度），由算法本身提供的信息，ηij（由城市i轉(zhuǎn)移到城市j的起始信息），該起始信息是由要解決的問題給出的.ηij=1/dij為城市i到城市j的先驗值，于是，t時刻位于城市i的螞蟻k選擇城市j為目標城市的概率是［2］：式（2.1）

α——殘留信息的相對重要程度。

β——期望值的相對重要程度。

為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題，在每個螞蟻完成對所有n個城市的訪問后（即一個循環(huán)），必須對殘留信息進行更新處理，對舊的信息進行削弱，同時，必須將最新的螞蟻訪問路徑的信息加入τi ，j［3］，

ρ為殘留信息的保留部分，1-ρ為殘留信息被削弱的部分，為了防止信息的無限累積，ρ必須小于1。為螞蟻k在時間段t到（t+n）時間內(nèi)的訪問過程中。在i到j(luò)的路徑上留下的殘留信息濃度。

與實際蟻群不同，搜索蟻群算法具有記憶功能，每個螞蟻個體可以記憶自己所走過的城市.隨著時間的推移，以前留下的信息素逐漸消逝，用參數(shù)1-ρ表示信息消逝程度，經(jīng)過n個城市的搜索，螞蟻完成一次循環(huán)，各路徑上信息量要作調(diào)整：

式中Q----------常數(shù)。

2　自適應(yīng)蟻群算法（Self-Adaptive Ant Colony Algorithm，SAACA）

通過對蟻群算法的分析和研究發(fā)現(xiàn)：一般的蟻群算法的選擇策略使得進化速度較慢，正反饋原理旨在強化性能較好的解，卻容易出現(xiàn)停滯現(xiàn)象。因而提出自適應(yīng)蟻群算法，從選擇策略方面進行修改，采用確定性選擇和隨機選擇相結(jié)合的選擇策略，在搜索過程中動態(tài)地調(diào)整作確定性選擇的概率當進化到一定代數(shù)后，進化方向已經(jīng)基本確定，這時對路徑上信息量作動態(tài)凋整?？s小最好和最差路徑上的信息量的差距，并且適當加大隨機選擇的概率，以小于l對解空間的更完全搜索，從而有效地克服基本蟻群算法的不足。

2.1自適應(yīng)城市選擇策略

該算法按照下式3.1確定螞蟻由所在轉(zhuǎn)移到下一個城市S［5］

其中，S按照公式（2.1），P∈（0，1），r是（0，1）中均勻分布的隨機數(shù)。當進化方向基本確定后，簡單的放大（或縮?。┓椒ㄕ{(diào)整每一路徑上的信息量，該方法不僅能夠加快收斂速度，節(jié)省搜索時間，而且能夠克服停滯行為的過早出現(xiàn)，有利于發(fā)現(xiàn)更好的解這對于求解大規(guī)模優(yōu)化問題是有益的。

2.2信息啟發(fā)因子α和期望啟發(fā)因子β的自適應(yīng)調(diào)整

當α=0 時，算法就是傳統(tǒng)的貪心算法，而當β=0 時，算法就是純粹的正反饋的啟發(fā)式算法.剛開始時螞蟻對鏈路的情況不了解，鏈路上的信息素對螞蟻的尋路影響不大，隨著迭代次數(shù)的增加，鏈路上的信息素對螞蟻的尋路越來越重要，到最后使優(yōu)勝者鏈路被選擇的概率越來越大，從而優(yōu)勝者鏈路的收斂速度越來越快，到最后找到最優(yōu)路徑.所以α，β 值分別按式（3.2）、式（3.3）進行自適應(yīng)調(diào)整：

其中 MINLENGTH為當前最佳路徑的長度，num為當前運行代數(shù)。

2.3路徑優(yōu)化算子

總所周知，在TSP問題中，如果路徑中存在交叉路徑，則該路徑必定不為最優(yōu)路徑。

通過采用2_opt［6］算法能夠輕松解決該問題，如圖1所示。

圖1　_opt優(yōu)化算法

通過采用路徑優(yōu)化算子，能使算法擁有更好的收斂能力。

2.4局部收斂時 信息素重新分配

通過判斷當前總?cè)鹤顑?yōu)路徑在整個總?cè)旱谋壤齺砼袛嗨惴ㄊ欠裣萑刖植渴諗俊．斔惴ㄟM入局部收斂時，采用新的規(guī)則分配各個邊上的信息素。信息素的濃度不再是平均分配，而是與路徑長度成反比，進而打亂各個邊上的信息素濃度，增加搜索能力。

3　仿真實驗及分析

3.1實驗環(huán)境

運行環(huán)境為: Visual Studio 2010 采用 C#語言編寫程序。

3.2仿真分析

為了檢驗改進的蟻群算法的求解性能，從通用TSPLIB 算例庫中選取多個實例進行測試.在Chc51算例中，參數(shù)設(shè)置為m=500，Max τ =1；p= 0.6 ，Min τ =0.000001；4；針對Chc51實例SAACA 與IDIA［14］、ACLA［15］算法最優(yōu)值曲線對比如圖2 所示:

圖2　最優(yōu)值曲線比較

表1是SAACA 與算法ACA［12］、CSA［13］、IDIA［14］和 ACLA［15］算法的一些性能比較，其性能指標包括：MTL（Maximal value of Tour Length）為測試結(jié)果中的最長路徑值，MITL（Minimal valueof Tour Length）為最短路徑值，METL（Mean valueof Tour Length）為路徑均值，平均百分誤差為:

表1　性能比較圖

從圖1不難發(fā)現(xiàn)，本文提出的自適應(yīng)蟻群算法SAACA運用于TSP問題中，它的最優(yōu)值都比IDIA［14］、ACLA［15］好，同時收斂速度都比IDIA和ACLA快。從表1可以看出，將SAACA算法運用于四種TSP問題中，除KroD100問題外，其尋優(yōu)解的最短時間都比ACA［12］、CSA［13］、IDIA［14］和ACLA［15］短。除KroD100問題外，最優(yōu)解的獲得次數(shù)都比ACA［12］、CSA［13］、IDIA［14］和ACLA［15］算法多。對于MTL，MITL，METL和平均百分誤差等性能指示而言，SAACA都比其他四種算法都好。

3.4結(jié)果

改進后的蟻群算法具有比傳統(tǒng)蟻群算法和MMAS蟻群算法更強的搜索全局最優(yōu)解的能力，并具有更好的穩(wěn)定性和收斂性。對傳統(tǒng)蟻群算法容易出現(xiàn)早熟和停滯現(xiàn)象的缺陷，提出了一種動態(tài)更新信息素的蟻群算法。實驗表明，改進的蟻群算法具有比傳統(tǒng)蟻群算法和 MMAS蟻群算法更強的搜索全局最優(yōu)解的能力，并具有更好的穩(wěn)定性和收斂性。

4　結(jié)束語

蟻群算法發(fā)展至今，人們已經(jīng)針對不同的具體問題提出了許多不同類型的改進蟻群算法模型，但這些改進的蟻群算法模型往往普適性不強，同時基本蟻群算法模型也不能直接應(yīng)用 于解決所有的優(yōu)化問題。另外，自然界中的真實蟻群還有許多其他的智能行為，用逆向思維和發(fā)散思維開發(fā)不同的螞群算法模型是一條新的發(fā)展思路?；诖私窈罂梢詮囊韵聨讉€方面對其模型進行改進：

（1）設(shè)計一種通用的蟻群算法普適性模型。

（2）進一步研究自然蟻群行為，提出更加智能化的蟻群混合行為模型。

（3）擺脫傳統(tǒng)模型框架，開發(fā)新的蟻群算法模型。

因此，關(guān)于蟻群算法理論及其應(yīng)用的研究必將是一個長期的研究課題。相信隨著人們對仿生智能系統(tǒng)理論及應(yīng)用研究的不斷深入，蟻群算法這一新興的仿生優(yōu)化算法必將展現(xiàn)出更加廣闊、更加引人注目的發(fā)展前景。

參考文獻：

［1］Garey M R，Graham R L，Johnson D S. Some NP -completegeomet ric problems［C］// 8th ACM Symposium on the Theory ofComputing. New York: Association for Computing Machinery，1976: 10-22.

［2］Michal E Z，F(xiàn)OGEL D B. How to solve it: ModernHeuristick［M］. BerlinHeidelberg: Springer2Verlag， 2000.

［3］Stutzl E，Hoos H H. Max-min ant system［J］. Future Generation Computer Systems，2000，16（8）: 889-914.

［3］段海濱. 蟻群算法原理及其應(yīng)用［M］. 北京: 科學(xué)出版社，2006.

［4］焦李成，杜海峰，劉芳，等. 免疫優(yōu)化計算，學(xué)習與識別［M］.北京: 科學(xué)出版社， 2007.

［5］Kirkpat R S，Gelatt J R，Vecchi M P. Optimization by simulatedannealing［J］. Journal of statistical，1983，34（516）: 975-986.

［6］Shi Y，Eberhart C. Particle Swarm Optimization: development，applications and resources［C］//Proc Congress on Evolutionary Computation 2001. Piscataway: IEEE Press， 2001: 81-86.

［7］劉波，劉蒙生. 采用基于模擬退火算法的蟻群算法求解旅行商問題［J］. 華中科技大學(xué)學(xué)報: 自然科學(xué)版，2009（11）:26-30.

［8］劉勇，馬欣，申志兵. 基于改進蟻群算法的應(yīng)急救援最優(yōu)路徑選擇［J］. 工業(yè)安全與環(huán)保， 2009（11）: 56-57.

［9］張曉玲，黃力. 融入遺傳算子的蟻群算法求解TSP問題［J］. 廣西民族大學(xué)學(xué)報: 自然科學(xué)版，2009（3）: 81-86.

［10］吳建輝，章兢，劉朝華. 基于蟻群算法和免疫算法融合的TSP問題求解［J］. 湖南大學(xué)學(xué)報: 自然科學(xué)版，2009（10）:81-87.

［11］峰峰，王仁明，伍佳.求解TSP問題的一種改進蟻群算法［J］.自動化技術(shù)與應(yīng)用，2010（7）: 1-3.

［12］萬曉鳳，胡偉，方武義，鄭博嘉.基于改進蟻群算法的機器人路徑規(guī)劃研究［J］.計算機工程與應(yīng)用，2014（18）:123-125.

［13］劉好斌，胡小兵，趙吉東. 動態(tài)調(diào)整路徑選擇的蟻群優(yōu)化算法［J］.計算機工程，2010（17）: 201-203.

［14］廖飛雄，馬良. 自調(diào)節(jié)種群的演化算法求解旅行商問題［J］.系統(tǒng)仿真學(xué)報，2009（9）:235-235.

［15］徐金榮，李允，劉海濤，劉攀.一種求解TSP的混合遺傳蟻群算法［J］.計算機應(yīng)用，2008（8）:223-234.

（責任編輯：廖建勇）

中圖分類號：TP301.6

文獻標識碼：A

doi:10.3969/j.issn.1672-7304.2016.01.061

文章編號：1672–7304（2016）01–0129–04

作者簡介：賈麗媛（1972-），女，湖南益陽人，教授，研究方向：算法與人工智能。

Adaptive Ant Colony Algorithm Research and Application in TSP Problems

JIA Li-yuan， ZHOU Cui-hong
（Hunan City University，Yiyang Hunan 413000 ）

Abstract:Traditional algorithm in the structure solution process， by the random selection strategy， the selection strategy of making a slow evolution， positive feedback priprinciple aimed at strengthening the performance of a better solution， but prone to stagnation. This is caused by the root causes of the shortcomings of ant colony algorithm. So we from a strategy to modify， we adopt deterministic selection and random selection combining selection strategy， and in the search process dynamically adjust for deterministic choice probability when the evolution to a certain algebra， evolutionary direction has been basically established， then on the amount of information on the path as dynamic full wither. Narrowing the gap between the best and worst path on the amount of information， and appropriate to increase the probability of randomly selected， to less than 1 of the solution space more complete search， which caneffectively overcome the deficiency of the basic ant colony algorithm， this algorithm is adaptive algorithm..

Keywords:Ant colony algorithm； adaptive function； global optimization； function optimization