尤海龍，魯照權(quán)

（合肥工業(yè)大學(xué) 智能制造研究院，合肥 230009）

0 引言

蟻群算法是由意大利學(xué)者Dorigo M等于1991年在法國巴黎召開的第一屆歐洲人工生命會(huì)議（European Conference on Artificial Lif，ECAL）上最早提出的[1]。蟻群算法遵循螞蟻搜尋食物的過程，螞蟻在尋找食物的路程中留下信息素，隨著時(shí)間的累計(jì)，最短路徑上的信息素濃度高于其他路徑，這使得后來的螞蟻有更大的概率選擇該條路徑，是一個(gè)正反饋過程。蟻群算法的優(yōu)點(diǎn)包括分布式并行計(jì)算機(jī)制、易與其他方法相結(jié)合、具有較強(qiáng)的魯棒性等[2]。隨著智能機(jī)器人的興起，蟻群算法也被大量使用在機(jī)器人路徑尋優(yōu)中。由于機(jī)器人行走的實(shí)時(shí)性，使得要在盡可能短的時(shí)間內(nèi)尋找到最優(yōu)路徑，蟻群算法收斂速度慢的問題顯得尤為突出。針對(duì)此問題，國內(nèi)外很多學(xué)者對(duì)蟻群算法做出了多次改進(jìn)。改進(jìn)的方法主要有改變信息素更新策略，僅更新最優(yōu)路徑上的信息素[3]。在全局信息素的基礎(chǔ)上加入局部信息素更新[4]避免局部最優(yōu)。將蟻群算法與其他算法相結(jié)合，如與遺傳算法相結(jié)合[5]加入交叉算子和變異算子，增加了解的全局性；與免疫算法相結(jié)合，加入免疫算子，加快了算法的收斂性[6]。對(duì)蟻群算法中的參數(shù)進(jìn)行改進(jìn)，使其成為自適應(yīng)參數(shù)[7]。

文中首先引入一般蟻群算法的數(shù)學(xué)模型，對(duì)蟻群算法的各個(gè)參數(shù)所起的作用進(jìn)行介紹，之后根據(jù)其作用提出相應(yīng)的自適應(yīng)模型。接著使用MATLAB對(duì)傳統(tǒng)蟻群算法與改進(jìn)后的蟻群算法進(jìn)行對(duì)比，通過實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)蟻群算法相對(duì)于傳統(tǒng)蟻群算法收斂速度有了顯著提高。最后，進(jìn)行進(jìn)一步總結(jié)與分析。

1 傳統(tǒng)蟻群算法

螞蟻k（k=1,2,3...,m）在移動(dòng)過程中，選擇從初始點(diǎn)下一步可以到達(dá)的節(jié)點(diǎn)，根據(jù)每個(gè)節(jié)點(diǎn)路徑上的信息素求出前往每個(gè)節(jié)點(diǎn)的概率，并使用輪盤賭法[8]選取下一步的初始點(diǎn)。以表示螞蟻從i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)的概率：

其中τij（t）表示弧（i，j）上信息素的濃度，ηij（i，j）表示與弧（i，j）相關(guān)聯(lián)的啟發(fā)式信息；tabuk為禁忌表，用來記錄螞蟻已走過的節(jié)點(diǎn)，避免螞蟻“回頭”；N為能夠選擇的所有節(jié)點(diǎn)；α為信息素啟發(fā)因子，反映了τij（t）在蟻群搜索中的重要性；β為期望啟發(fā)因子，反映了下一節(jié)點(diǎn)的位置在蟻群搜索中的重要性，且β越大，狀態(tài)轉(zhuǎn)移概率越接近貪心規(guī)則[9]。

一般情況下， ηij（i，j）按式(2)計(jì)算：

dij表示i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)的距離。由式(2)可知，dij越小，則ηij（i，j）越大，也就越大，被螞蟻選擇的概率就越大。在螞蟻k到達(dá)目的地后，要對(duì)路徑上殘留信息素進(jìn)行更新，這種更新類似人類的記憶功能，在新的信息素增加的同時(shí)，舊的信息素也在不斷揮發(fā)，被“忘記”。根據(jù)此原理，τij(t+1)時(shí)刻信息素的濃度相對(duì)于τij(t)時(shí)刻信息素的更新按照式(3)、式(4)處理：

ρ表示信息素?fù)]發(fā)系數(shù)， 則（1-ρ）表示信息素殘留因子，為了防止路徑上信息素?zé)o限積累，ρ的取值范圍為ρ∈[0，1]；Δτij(t)表示本次循環(huán)中路徑(i，j)上的信息素增量，初始時(shí)刻表示第 k只螞蟻在本次循環(huán)中留在路徑（i，j）上的信息量，由式(5)求得：

Lk為第k只螞蟻在本次循環(huán)中所走過的路徑長度，Q為信息素強(qiáng)度。

2 改進(jìn)蟻群算法

與傳統(tǒng)蟻群算法相比，文中在兩個(gè)方面對(duì)蟻群算法進(jìn)行了改進(jìn)：1）將α（信息啟發(fā)因子）和β（期望啟發(fā)因子）改為動(dòng)態(tài)自適應(yīng)參數(shù)，隨著迭代次數(shù)的改變相應(yīng)的做出變化。2）將ρ（信息素?fù)]發(fā)系數(shù)）設(shè)置為閾值函數(shù)。

2.1 α和β的自適應(yīng)變化

傳統(tǒng)蟻群算法中α和β通常取值為[1，9]中某個(gè)固定值。α過大，會(huì)使路徑上信息素影響權(quán)值過大，使得螞蟻易進(jìn)入局部最優(yōu)解。α過小，則螞蟻行走的隨機(jī)性又太強(qiáng)，收斂速度太慢。β的取值影響與α相似[10]。α和β過大或者過小都容易導(dǎo)致蟻群算法的搜索陷入局部最優(yōu)或者陷入隨機(jī)而無法找到最優(yōu)解[11]。取最短路徑下的運(yùn)行時(shí)間為研究對(duì)象，對(duì)α和β的最佳取值進(jìn)行研究。蟻群算法中的其他參數(shù)分別取值為：迭代總數(shù)K=50，每代出動(dòng)螞蟻總數(shù)M=80，信息素?fù)]發(fā)系數(shù)ρ=0.7。多次改變?chǔ)梁挺碌娜≈?，得到路徑長度、運(yùn)算時(shí)間與迭代次數(shù)的變化如表1和表2所示。觀察變化趨勢(shì)，可以得出在求取最短路徑的問題上，α和β的最佳取值范圍分別為[2～4]和[7～9]。

通過分析和多次仿真實(shí)驗(yàn)可知，在迭代初期，各條路徑信息素濃度差別不大，此時(shí)與弧相關(guān)聯(lián)的啟發(fā)式信息η為影響螞蟻選擇路徑的主要因素，因此α的值應(yīng)較小，β的值應(yīng)較大。隨著迭代的不斷進(jìn)行，最短路徑上的信息素濃度逐漸高于其他路徑，此時(shí)信息素濃度在路徑選擇中占據(jù)主導(dǎo)地位，α的值應(yīng)相應(yīng)增加，β的值則較小。到了迭代的后期，部分路徑上信息素濃度已遠(yuǎn)高于其他路徑，為了防止由于信息素積累陷入局部最優(yōu)，此時(shí)應(yīng)減小信息素濃度在路徑選擇中所占的比重，即α再次變小，β的值則相應(yīng)增加[12]。同時(shí)，適當(dāng)增大α和β的取值范圍，可使蟻群尋得路徑解空間范圍變大，有助于尋找全局最優(yōu)解[13]。因此本文中α取值為[1～4]，β取值為[6～9]。

表1 α取值對(duì)性能的影響

表2 β取值對(duì)性能的影響

通過以上分析可知，α和β隨著迭代次數(shù)的改變呈現(xiàn)階梯型變化，為了能夠更平滑的完成權(quán)重系數(shù)的改變，本文分別對(duì)α和β的取值采用正弦函數(shù)和余弦函數(shù)的方式，如式(6)、式(7)所示：

式中，k表示當(dāng)前迭代次數(shù)，K表示迭代總次數(shù)；本文取式(6)中A=3、B=1、ε=1而式(7)中C=3、D=6、θ=1。也可按需求適當(dāng)調(diào)整。

2.2 ρ信息素?fù)]發(fā)系數(shù)函數(shù)

在信息素的積累過程中，信息素?fù)]發(fā)系數(shù)占有重要作用。若ρ過大，會(huì)降低算法的全局搜索能力；若ρ過小，則收斂速度會(huì)降低[14]。將蟻群算法中的其他參數(shù)分別取值為：迭代總數(shù)K=50，每代出動(dòng)螞蟻總數(shù)M=80，α=1，β=7。ρ的取值變化與算法性能的關(guān)系如表3所示。

表3 ρ的取值與算法性能的關(guān)系

根據(jù)分析可知，算法開始時(shí)路徑上信息素濃度較低，此時(shí)ρ應(yīng)相應(yīng)取大，使得螞蟻可以更快的找到較優(yōu)路徑，加快算法收斂速度；隨著路徑上信息素濃度的不斷積累，為了避免陷入局部最優(yōu)丟失算法的全局搜索能力，ρ的取值應(yīng)相應(yīng)減小。為了使算法的全局搜索能力和收斂速度在動(dòng)態(tài)平衡中得到最大程度的優(yōu)化，本文選用閾值函數(shù)對(duì)ρ進(jìn)行動(dòng)態(tài)調(diào)整，使其隨著迭代次數(shù)的改變而改變，ρ的取值為[0.5,0.9]，取式(8)：

式中ψ為常數(shù)項(xiàng)，λ為改變因子，k為當(dāng)前迭代次數(shù)，K為總迭代次數(shù)。選擇合適的值，使ρ的取值在[0.5,0.9]中隨著迭代的進(jìn)行而動(dòng)態(tài)減小。本文中ψ=1.82，λ=1。

3 實(shí)驗(yàn)

3.1 二維地圖的建立及相關(guān)參數(shù)設(shè)置

為了驗(yàn)證本文中算法的有效性，使用matlab2014創(chuàng)建二維靜態(tài)柵格地圖如圖1所示。圖中黑色柵格表示障礙物，白色柵格表示可選擇的節(jié)點(diǎn)。

圖1 柵格法靜態(tài)二維地圖

柵格的編號(hào)首先通過序號(hào)法從第一行依次編號(hào)，如第一行和第二行的障礙物的序號(hào)為N={2，14，15，19，20}。螞蟻所取的節(jié)點(diǎn)為每個(gè)柵格的中心，可通過式(9)換算為直角坐標(biāo)系坐標(biāo)：

其中N為序列號(hào)，M是地圖中柵格的列數(shù)，mod( )為求余函數(shù)，ceil( )為取整函數(shù)。

3.2 算法步驟

1）使用柵格法建立機(jī)器人尋找最優(yōu)路徑的地圖。

2）輸入初始的信息素矩陣，選擇初始點(diǎn)和終點(diǎn)并且設(shè)置各種參數(shù)。算法的相關(guān)參數(shù)設(shè)置為：迭代總次數(shù)K=100，每代螞蟻總數(shù)M=80，信息素強(qiáng)度系數(shù)Q=1。改進(jìn)前α、β與ρ分別取1、7和0.7，改進(jìn)后根據(jù)式(6)、式(7)、式(8)設(shè)置。文獻(xiàn)[15]中的ρ按式(9)設(shè)置。

ξ∈(0,1)為揮發(fā)因子調(diào)節(jié)系數(shù)；ρmin為ρ的最小值。

3）選擇從初始點(diǎn)下一步可以到達(dá)的節(jié)點(diǎn)，根據(jù)每個(gè)節(jié)點(diǎn)的信息素求出前往每個(gè)節(jié)點(diǎn)的概率，并利用式(1)的輪盤賭法選取下一步初始點(diǎn)。

4）更新路徑及路徑長度。

5）重復(fù)步驟3）、4），直到螞蟻到達(dá)終點(diǎn)或因進(jìn)入陷阱而死亡。

6）重復(fù)步驟3）、4）、5），直到這一代的M只螞蟻全部遍歷。

7）根據(jù)式(3)、式(4)更新信息素矩陣。

8）重復(fù)步驟3）～7），直到第K代螞蟻迭代結(jié)束。

3.3 算法實(shí)現(xiàn)與比較

建立一個(gè)20×20的二維靜態(tài)地圖，多次改變障礙物位置，統(tǒng)計(jì)傳統(tǒng)蟻群算法和本文改進(jìn)后蟻群算法找到最優(yōu)路徑所需的迭代次數(shù)。如圖2所示，某次實(shí)驗(yàn)下傳統(tǒng)蟻法。

圖2 蟻群算法下的最優(yōu)路徑

文獻(xiàn)[15]蟻群算法和本文改進(jìn)后的蟻群算法找到的最優(yōu)路徑相同。在此前提下，三種蟻群算法所需的迭代次數(shù)則分布如圖3、圖4、圖5所示。

圖3 改進(jìn)前的迭代次數(shù)

圖4 文獻(xiàn)[15]的迭代次數(shù)

圖5 本文的迭代次數(shù)

改變障礙物位置，迭代總次數(shù)選為各算法求得最優(yōu)路徑所需迭代數(shù)的次數(shù)五倍以保證結(jié)果穩(wěn)定。進(jìn)行多次實(shí)驗(yàn)，在所得最優(yōu)路徑相同的前提下，三種蟻群算法的迭代次數(shù)及運(yùn)算時(shí)間如圖6、圖7所示。

圖6 各算法迭代數(shù)

圖7 各算法運(yùn)算時(shí)間

由圖可知，本文改進(jìn)后的蟻群算法在得到相同最優(yōu)解的前提下，能夠有效的減少迭代次數(shù)。由于求得最優(yōu)

【】【】解所需迭代次數(shù)的減小，使得算法在設(shè)定總迭代數(shù)時(shí)可以大幅減小，從而使得算法的總運(yùn)行時(shí)間相應(yīng)減小，實(shí)現(xiàn)了蟻群算法的快速尋路。

4 結(jié)論

蟻群算法作為機(jī)器人路徑避障中的重要方法，如何解決其收斂速度慢的問題以應(yīng)對(duì)實(shí)時(shí)路況一直是蟻群算法研究的重要方向。本文提出的改進(jìn)蟻群算法，是對(duì)蟻群算法的三個(gè)主要參數(shù)做了改進(jìn)，使得它們?cè)谒惴ǖ牟煌^程中所做出的影響發(fā)生最合適的變化，在避免陷入局部最優(yōu)的同時(shí)加快了收斂速度，并經(jīng)過仿真實(shí)驗(yàn)完成了驗(yàn)證。

[1]T Stützle,M López-Ibáez.Parameter Adaptation in Ant Colony Optimization[M].Springer Be-rlin Heidelberg,2011,6(1):23-8.

[2]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱工業(yè)大學(xué)出版社.2004,28(1):42-45.

[3]HH Hoos,MAX-MIN Ant system[M].Elsevier Science Publishers B. V.,2000,16(9):889-914.

[4]孟祥萍,片兆宇.基于方向信息素協(xié)調(diào)的蟻群算法[J].控制與決策.2013(5):782-786.

[5]李冬妮,賈曉宇.基于蟻群算法和遺傳規(guī)劃的跨單元調(diào)度方法[J].北京理工大學(xué)學(xué)報(bào),2017,37(7):704-7102.

[6]周文明.基于智能算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[D].南京理工大學(xué).2016.

[7]ZM Lai，GD Guo.Ant Colony Optimization Based on Self-Adaption Threshold for Path Planning[J].Computer Systems &Applications,2014.

[8]郁磊.matlab智能算法30個(gè)案例分析[M].北京航空航天大學(xué)出版社.2015.

[9]DP Du,YR Zu Greedy. Strategy Based Self-adaption Ant Colony Algorithm for 0/1 Knapsack Problem[M].Springer Netherlands.2015,331:663-670.

[10]魏星,李燕.蟻群算法中參數(shù)優(yōu)化及其仿真研究[J].制造業(yè)自動(dòng)化,2015(10):33-35.

[11]王越,葉秋冬.蟻群算法在求解最短路徑問題上的改進(jìn)策略[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(13):35-38.

[12]T Zhu,G Dong.Research for the Path Planning of the Agricultural Robot Based on the Improved Ant Colony Algorithm[J].Journal of Agricultural Mechanization Research,2016.

[13]DE JACKSON,M HOLCMBE,FLW RA-TNIEKS.Trail geometry gives polarity to ant foraging networks[J].Nature,2004,432(7019):907-909.

[14]鐘娟,趙彥強(qiáng),孫富康,等.基于混合蟻群算法的物流配送路徑問題[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,32(5):686-688.

[15]申鉉京,劉陽陽,等.求解TSP問題的快速蟻群算法[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版）2013,43(1):147-151.