自適應蟻群算法在TSP問題中的應用與研究

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

?

自適應蟻群算法在TSP問題中的應用與研究

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

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

關鍵詞：蟻群算法；自適應函數；全局優化；函數優化

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

1　基本蟻群算法

1.1蟻群算法原理

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

1.2蟻群算法的實現

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

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

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

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

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

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

式中Q----------常數。

2　自適應蟻群算法（Self-Adaptive Ant Colony Algorithm，SAACA）

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

2.1自適應城市選擇策略

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

其中，S按照公式（2.1），P∈（0，1），r是（0，1）中均勻分布的隨機數。當進化方向基本確定后，簡單的放大（或縮小）方法調整每一路徑上的信息量，該方法不僅能夠加快收斂速度，節省搜索時間，而且能夠克服停滯行為的過早出現，有利于發現更好的解這對于求解大規模優化問題是有益的。

2.2信息啟發因子α和期望啟發因子β的自適應調整

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

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

2.3路徑優化算子

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

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

圖1　_opt優化算法

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

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

通過判斷當前總群最優路徑在整個總群的比例來判斷算法是否陷入局部收斂。當算法進入局部收斂時，采用新的規則分配各個邊上的信息素。信息素的濃度不再是平均分配，而是與路徑長度成反比，進而打亂各個邊上的信息素濃度，增加搜索能力。

3　仿真實驗及分析

3.1實驗環境

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

3.2仿真分析

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

圖2　最優值曲線比較

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

表1　性能比較圖

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

3.4結果

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

4　結束語

蟻群算法發展至今，人們已經針對不同的具體問題提出了許多不同類型的改進蟻群算法模型，但這些改進的蟻群算法模型往往普適性不強，同時基本蟻群算法模型也不能直接應用 于解決所有的優化問題。另外，自然界中的真實蟻群還有許多其他的智能行為，用逆向思維和發散思維開發不同的螞群算法模型是一條新的發展思路。基于此今后可以從以下幾個方面對其模型進行改進：

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

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

（3）擺脫傳統模型框架，開發新的蟻群算法模型。

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

參考文獻：

［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，FOGEL 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］段海濱. 蟻群算法原理及其應用［M］. 北京: 科學出版社，2006.

［4］焦李成，杜海峰，劉芳，等. 免疫優化計算，學習與識別［M］.北京: 科學出版社， 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］. 華中科技大學學報: 自然科學版，2009（11）:26-30.

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

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

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

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

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

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

［14］廖飛雄，馬良. 自調節種群的演化算法求解旅行商問題［J］.系統仿真學報，2009（9）:235-235.

［15］徐金榮，李允，劉海濤，劉攀.一種求解TSP的混合遺傳蟻群算法［J］.計算機應用，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