基于蟻群算法在TSP問題中的仿真分析

【摘要】在移動機器人路徑規(guī)劃TSP問題中選取蟻群算法和遺傳算法的matlab仿真作為研究重點，根據算法的特點分析了蟻群算法的主要參數(shù)例如啟發(fā)信息影響程度的表達因子；信息素揮發(fā)系數(shù)，蟻群中的螞蟻數(shù)量等對TSP問題規(guī)劃最優(yōu)解和效率的影響，同時對比遺傳算法對TSP問題的仿真分析，得出蟻群算法的效率優(yōu)勢和遺傳算法的穩(wěn)定性優(yōu)勢，為進一步的兩種算法優(yōu)勢互補融合研究做鋪墊。

【關鍵詞】TSP問題；蟻群算法；遺傳算法；仿真分析

目前，關于蟻群算法在TSP問題中的應用及改進已經相對成熟，文獻[1]通過引入模糊集合的概念提出改進路徑更新效果的蟻群算法（FACO），該方法通過模糊評價充分合理利用信息素，能有效提高求得最優(yōu)解的幾率，是一種有效的改進算法。文獻[2]通過在最大最小蟻群算法基礎上，通過遺傳算法特點對蟻群算法參數(shù)設置進行優(yōu)化，有效提高算法求解信息素的速度。文獻[3]通過提出相遇策略以及分組并列運行方式改進蟻群算法以及在二維和三維環(huán)境進行建模仿真，驗證了蟻群改進算法的可靠和有效性。文獻[4]通過提出擴大局部搜索空間策略和信息素更新機制提出蟻群自適應優(yōu)化算法求解TSP問題的方法，提高算法收斂速度和精度。同時探討了將混沌擾動引入信息素更新的求解過程，可以用更優(yōu)解取代當前最優(yōu)值。

1、基本蟻群算法TSP仿真分析及改進

基本蟻群算法求解TSP問題的實質在于引入螞蟻行走的思想求解最優(yōu)路徑問題，螞蟻隨機挑選路徑并產生信息素，信息素越大代表路徑長度越短從而反饋引導螞蟻選擇路徑最短的路線，蟻群算法有比較好的自組織性，通過整體反饋尋優(yōu)可以應用于很多實際組合優(yōu)化問題。

對于蟻群算法的流程，首先應該明確蟻群算法公式及符號定義

在蟻群算法描述之前，引入如下變量記號：m：蟻群中的螞蟻數(shù)量；

β：啟發(fā)信息影響程度的表達因子，相當于能見度；

ρ：信息素揮發(fā)系數(shù)，ρ<1；

dij：邊（i，j）代表城市距離；

ηij：邊（i，j）的啟發(fā)因子，取ηij=I/dij，這個值固定，一般不隨螞蟻系統(tǒng)而改變；

τij：邊（i，j）的信息素值表示；

Pkij（t）：在t時刻螞蟻k從城市i轉移到城市j的概率，i為當前螞蟻所在的城市，j為螞蟻尚未訪問過的城市；

其中，螞蟻系統(tǒng)使用隨機比例規(guī)則進行狀態(tài)轉移，用公式（1-1）表示：

（1-1）

allowedK：在本次循環(huán)中螞蟻k未曾訪問的城市集合；

tabuK：螞蟻k的禁忌表，記錄螞蟻己經訪問的城市而禁止再走這些城市。

城市i和城市j之間路徑的信息素量，經過n個時刻，信息素調整如公式（1-2）所示：

（1-2）

其中信息素調整原則我們采用蟻周（ant-cycle system）模型，利用的是螞蟻的全局信息素調整方式，效果最為優(yōu)越，蟻周模型中：

其中Q：表示螞蟻釋放在所經過路徑上（一個過程或一次迭代）的信息素總量，為正常數(shù)；

Lk：表示第k只螞蟻在當前迭代中所經過的路徑長度；

△τijk：表示螞蟻k釋放在路徑（i，j）上的信息素；△τij：表示所有螞蟻釋放在路徑（i，j）上的信息素總和。

本文進行如下蟻群算法TSP仿真實現(xiàn)，選取參數(shù)信息素啟發(fā)因子 a=1，路徑啟發(fā)因子β=2，局部信息素揮發(fā)系數(shù)ρ1=0.2，全局信息素揮發(fā)系數(shù)ρ2=0.1，螞蟻數(shù)量為m=100，最大迭代次數(shù)NCmax=500實際仿真結果如下：

同時我們輸出蟻群個體適應度最優(yōu)隨著迭代次數(shù)的變化曲線，在迭代50次以后適應度值達到相對穩(wěn)定狀態(tài)，表示路徑選擇基本穩(wěn)定在小范圍波動，從而達到輸出路徑的效果[5]。驗證了蟻群算法的有效性。

同時可以對基本蟻群算法作出改進，即采用最大最小螞蟻系統(tǒng)對將信息素在每條路徑上的值限定于[τmin，τmax]范圍內，如若超出范圍則被強制置為上限或下限。這樣可以有效控制路徑上的信息素差值多大導致的算法過早收斂，同時有利于蟻群的集中搜索[6]。仿真結果如圖3：

2、結論

利用蟻群算法對TSP問題的求解，驗證了蟻群算法在路徑規(guī)劃問題中的有效性，同時對蟻群算法的參數(shù)設置對仿真結果的影響進行探討，蟻群算法的參數(shù)較多，如何設置需要根據對算法具體要求合理配置。綜上分析，蟻群算法在求解TSP問題時具有比較強的速度優(yōu)勢，而遺傳算法具有比較高的可靠性和獨立性，因此我們通過以上仿真分析的結論，可以為進一步的融合算法深入研究打好基礎。

參考文獻

[1]江迎春.改進的蟻群算法在TSP問題上的應用[D].中南民族大學，2009.

[2]馮月華.基于遺傳算法的蟻群算法參數(shù)優(yōu)化研究[J].貴陽學院學報：自然科學版，2014，（1）.

[3]馬金財.基于蟻群算法的機器人路徑規(guī)劃問題研究[D].昆明理工大學，2014.

[4]王勝訓.蟻群算法的改進及TSP仿真研究[D].西安電子科技大學，2014.

[5]周磊.改進蟻群算法在機器人路徑規(guī)劃中的應用研究[D].華東理工大學，2013.