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

【關(guān)鍵詞】TSP問(wèn)題；蟻群算法；遺傳算法；仿真分析

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

1、基本蟻群算法TSP仿真分析及改進(jìn)

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

對(duì)于蟻群算法的流程，首先應(yīng)該明確蟻群算法公式及符號(hào)定義

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

β：?jiǎn)l(fā)信息影響程度的表達(dá)因子，相當(dāng)于能見度；

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

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

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

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

Pkij（t）：在t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率，i為當(dāng)前螞蟻所在的城市，j為螞蟻尚未訪問(wèn)過(guò)的城市；

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

（1-1）

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

tabuK：螞蟻k的禁忌表，記錄螞蟻己經(jīng)訪問(wèn)的城市而禁止再走這些城市。

城市i和城市j之間路徑的信息素量，經(jīng)過(guò)n個(gè)時(shí)刻，信息素調(diào)整如公式（1-2）所示：

（1-2）

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

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

Lk：表示第k只螞蟻在當(dāng)前迭代中所經(jīng)過(guò)的路徑長(zhǎng)度；

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

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

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

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

2、結(jié)論

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

參考文獻(xiàn)

[1]江迎春.改進(jìn)的蟻群算法在TSP問(wèn)題上的應(yīng)用[D].中南民族大學(xué)，2009.

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

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

[4]王勝訓(xùn).蟻群算法的改進(jìn)及TSP仿真研究[D].西安電子科技大學(xué)，2014.

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