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

?

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

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

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

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

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

1　基本蟻群算法

1.1蟻群算法原理

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

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

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

α——?dú)埩粜畔⒌南鄬?duì)重要程度。

β——期望值的相對(duì)重要程度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4局部收斂時(shí) 信息素重新分配

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

3　仿真實(shí)驗(yàn)及分析

3.1實(shí)驗(yàn)環(huán)境

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

3.2仿真分析

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

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

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

表1　性能比較圖

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

3.4結(jié)果

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

4　結(jié)束語

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

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

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

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

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

參考文獻(xiàn)：

［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)化計(jì)算，學(xué)習(xí)與識(shí)別［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é)報(bào): 自然科學(xué)版，2009（11）:26-30.

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

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

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

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

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

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

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

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

（責(zé)任編輯：廖建勇）

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.3969/j.issn.1672-7304.2016.01.061

文章編號(hào)：1672–7304（2016）01–0129–04

作者簡(jiǎn)介：賈麗媛（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