改進蟻群算法在機器人路徑規(guī)劃中的應(yīng)用

何雅穎，范昕煒

中國計量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州310018

機器人路徑規(guī)劃是指根據(jù)已知障礙環(huán)境，自行規(guī)劃出一條從起始點到達終止點無碰撞的最優(yōu)路徑[1]。其中傳統(tǒng)方法包括柵格法、A*算法[2]、人工勢場算法[3]等。隨著智能群算法的發(fā)展，遺傳算法[4]、粒子群算法[5]、蟻群算法等也開始應(yīng)用于路徑規(guī)劃中。

蟻群算法（Ant Colony Optimization，ACO）是由意大利學(xué)者Dorigo等[6]提出的一種仿生螞蟻覓食的智能群算法，具有正反饋、并行性、強魯棒性和較好適應(yīng)性的特點，但同時也具有易陷入局部最優(yōu)、收斂速度較慢和易陷入死鎖等問題。其中信息素對算法結(jié)果具有重要影響，不少學(xué)者通過信息素不同的設(shè)置方式來優(yōu)化算法。文獻[7]提出非均勻信息素分布劃定起點到終點兩個點為頂點的矩形區(qū)域為有利區(qū)域，提高該區(qū)域的初始值。該方法能有效防止螞蟻在初期向目標點反方向搜索，但是區(qū)域內(nèi)信息素并沒有差別，改進效果有限。文獻[8]提出雙層蟻群算法，先通過外層算法求取最優(yōu)解延伸其解空間，后利用內(nèi)層算法進行局部尋優(yōu)，如果在此空間內(nèi)找到更優(yōu)路徑則執(zhí)行信息素二次更新。該方法雖然提高了最優(yōu)解的可能性，但是僅限于有限空間探索，算法可能陷入局部最優(yōu)。文獻[9]引入了最優(yōu)解與最差解改進信息素更新規(guī)則，增強當前最優(yōu)路徑的信息素，減弱最差路徑的信息素。該方法有效加快了收斂速度，但同時也減少了種群的多樣性，不利于最優(yōu)解的獲取。文獻[10]提出在算法搜索過程中加入人工勢場局部搜索尋優(yōu)算法，將人工勢場中力因素轉(zhuǎn)換為局部擴散信息素，算法有效減少了交叉路徑與螞蟻“迷失”數(shù)量，提高了蟻群對障礙物的預(yù)避障能力，但算法結(jié)構(gòu)設(shè)計較為復(fù)雜，環(huán)境適應(yīng)能力有待提高。文獻[11]將遺傳算法與蟻群算法相融合，提出利用遺傳算法生成初始路徑，將較優(yōu)路徑作為蟻群算法初始信息素的參考信息，減少初期算法盲目性，后利用蟻群算法對初始路徑進一步優(yōu)化。該改進算法能避免局部最優(yōu)，但算法運行時間較長。

綜上所述，信息素的設(shè)置能有效提高收斂速度，但同時也有可能降低算法尋優(yōu)能力，不利于獲取最優(yōu)解。為平衡尋求最優(yōu)解與算法收斂速度，提出改進的蟻群算法，其中包括：對初始信息素進行非均勻分配，提高收斂速度；提出局部分塊優(yōu)化策略優(yōu)化子區(qū)域路徑提高求解質(zhì)量；利用信息素增強因子保留更優(yōu)解，避免陷入局部最優(yōu)；引入反向?qū)W習(xí)對信息素進行優(yōu)化，改進狀態(tài)選擇概率，提高算法全局尋優(yōu)能力。

1 相關(guān)知識

1.1 蟻群算法

1.1.1轉(zhuǎn)移概率

在t時刻螞蟻m從節(jié)點i到節(jié)點j由式（1）計算轉(zhuǎn)移概率并根據(jù)輪盤賭法則對下一路徑點進行選擇。

式中，τij(t)為路徑(i,j)間的信息素含量，α為信息素啟發(fā)因子，ηij(t)為期望啟發(fā)項，通過式（2）計算可得；d(i,j)為路徑(i,j)間的歐式距離，β為期望啟發(fā)式因子。α和β分別代表信息素、期望啟發(fā)項的重要程度。allowedm表示螞蟻m所有下一可行節(jié)點集合。

1.1.2信息素更新

每只螞蟻在行走過程中都會留下一定量的信息素，隨著迭代次數(shù)的增加，信息素不斷地增加，同時也在不斷揮發(fā)。所有螞蟻完成一次迭代后，會對殘留信息素進行更新，根據(jù)式（3）、（4）更新信息素。

式（3）中ρ為揮發(fā)系數(shù)，Δτij為本次迭代中路徑(i,j)的信息素增量，W為螞蟻總數(shù)，為本次迭代中第m只螞蟻在路徑(i,j)留下的信息素。式（4）中值的計算采用的更新方式為蟻周模型，除此之外還有蟻量模型和蟻密模型。式中Q是一個常數(shù)，表示信息素強度值，Lm表示第m只螞蟻在本次迭代中所走路徑總長度。

1.2 反向?qū)W習(xí)

反向?qū)W習(xí)的概念于2005年由Tizhoosh[12]提出，后被成功用于算法的進化，解決優(yōu)化問題。以下為反向解定義。

定義1假設(shè)x是一維空間的一個實數(shù)，x∈[a,b]，因此x反向解為[13]：

定義2假設(shè)P=(x1,x2,…,xD)為D維空間中一點，其中xi∈[ai,bi],?i∈{1,2,…,D},則其反向解為Pˉ=

2 改進蟻群算法

2.1 非均勻初始信息素分布

蟻群算法中，螞蟻主要根據(jù)柵格間信息素的差異尋求最優(yōu)路徑，而在傳統(tǒng)的蟻群算法中，初始信息素采用的是均勻分布，因此每只螞蟻的狀態(tài)轉(zhuǎn)移概率只取決于期望啟發(fā)項，而柵格間期望啟發(fā)項差異較小，因此初期算法由于缺少信息素引導(dǎo)具有盲目性，且搜索速度較慢，最終影響解的質(zhì)量與收斂速度[14]。因此對初始化信息素進行非均勻分布處理，提高柵格間信息素的差異能有效提高搜索效率。為避免改進后的初始信息素過度或者錯誤引導(dǎo)后續(xù)螞蟻探索最優(yōu)解，信息素的非均勻分布僅針對區(qū)域進行差異處理而非單個柵格點，即只提高有利區(qū)域內(nèi)的初始信息素，降低算法陷入局部最優(yōu)的可能。由于最優(yōu)路徑多集中于起點S至目標點E的連線附近區(qū)域，其區(qū)域范圍受障礙物影響，以起點S和目標點E連線作x軸，以連線中點作為原點建立坐標系，以起點至終點距離dSE為長軸，全局優(yōu)選區(qū)域距離ddiff為短軸建立橢圓，其計算公式如式（8）。在該橢圓內(nèi)的區(qū)域為全局優(yōu)選區(qū)域R，并提高優(yōu)選區(qū)域R內(nèi)的路徑點初始信息素，而不在該范圍內(nèi)的路徑點則保持原初始信息素值τ0。非均勻初始信息素分布規(guī)則如式（7）所示：

式（7）中τ0為信息素初始值，C為全局優(yōu)選區(qū)域信息素增量。式（8）中ddiff與地圖障礙物有關(guān)，ξ為環(huán)境障礙物占比，ξ越高，則ddiff越大，全局優(yōu)選區(qū)域范圍更廣；r和c分別表示矩陣地圖的行數(shù)與列數(shù)。

2.2 改進信息素更新規(guī)則

信息素的更新包括對原有路徑上信息素的揮發(fā)與新增路徑信息素的積累，因此提出局部信息素分塊優(yōu)化策略對信息素的更新規(guī)則進行了改進。

在傳統(tǒng)蟻群算法中，所有的螞蟻完成當前迭代后將對螞蟻路徑進行更新。路徑的好壞評價取決于全局路徑的長度，而忽略了對局部區(qū)域路徑的評價。圖1中實線路徑與虛線路徑分別代表歷史最優(yōu)路徑和當前迭代最優(yōu)路徑，橫坐標x∈[0,5]時，當前迭代最優(yōu)路徑更短；而在x∈[5,20]時，歷史最優(yōu)路徑更短，因此提出局部信息素分塊優(yōu)化策略。算法初期并不知道路徑將會經(jīng)過哪些路徑點，無法利用具體坐標作為分割依據(jù)，因此將矩陣地圖按x坐標以一定間隔步長n縱向切割均勻劃分為多個區(qū)域，n越小容易造成路徑曲折較多，不利于尋求最佳路徑，n較大則達不到分塊優(yōu)化的效果。如圖1所示矩陣地圖被以步長n=5劃為4個區(qū)域，有多個點都經(jīng)過同一切分線時，以最后經(jīng)過點作為終止點。隨后引入精英螞蟻[15]的策略，當所有螞蟻完成當前迭代后，對各區(qū)域內(nèi)的最優(yōu)局部路徑信息素進行更新。全局最優(yōu)路徑本質(zhì)上是由各個局部最優(yōu)路徑組合而成的，對局部最優(yōu)路徑信息素的更新旨在引導(dǎo)后續(xù)螞蟻行駛至該區(qū)域內(nèi)的路徑選擇，一旦螞蟻行駛至該區(qū)域最優(yōu)路徑附近則能通過此策略更大概率選擇最優(yōu)路徑點。但局部區(qū)域路徑優(yōu)劣如果僅從區(qū)域內(nèi)路徑長度考慮，很容易導(dǎo)致區(qū)域內(nèi)水平方向的路徑被認為是最優(yōu)而非更接近終點的路徑，因此路徑長度考慮其路徑段與起點和終點的總距離，如式（9）所示。同時由于非均勻初始化信息素的改進，對局部路徑長度的選擇也更有利。

圖1 信息素分塊優(yōu)化Fig.1 Pheromone block optimization

因為局部更新只是針對局部區(qū)域，缺乏全局信息素引導(dǎo)，所以對每個區(qū)域內(nèi)最優(yōu)路徑更新后，再對螞蟻的全局信息素進行更新。鑒于此前已經(jīng)對局部最優(yōu)路徑進行了更新，為了避免信息素重復(fù)疊加，只對全局最優(yōu)路徑信息素進行更新。局部最優(yōu)路徑更新規(guī)則與全局最優(yōu)路徑更新規(guī)則相同，如式（9）和式（10）所示。

式中，當計算局部最優(yōu)路徑信息素時，Lbest為各個區(qū)域內(nèi)最優(yōu)路徑長度，Ldist為各局部區(qū)域內(nèi)最優(yōu)路徑段長度，Lds為路徑段第一個路徑點到起點距離，Lde為路徑段最后一個路徑點到終點距離。在計算全局最優(yōu)路徑信息素時，Lds和Lds都為0，則Lbest為全局最優(yōu)路徑長度。

如果只對最優(yōu)路徑進行更新，隨著迭代次數(shù)增加，最優(yōu)路徑上的信息素累積越來越多，高濃度的信息素含量會導(dǎo)致即使迭代后期出現(xiàn)了比歷史更優(yōu)路徑，這條新路徑上釋放的信息素仍然遠遠少于現(xiàn)有最優(yōu)路徑上的信息素，容易陷入局部最優(yōu)且可能在迭代收斂時丟失該解[16]。針對該問題，在信息素更新規(guī)則中引入信息素增強因子r，當出現(xiàn)比歷史更優(yōu)的路徑時，通過增強因子提高此路徑上的信息素，如式（11）所示。增強因子r隨著當前迭代次數(shù)Nc的改變而發(fā)生改變，初期r值較小，避免信息素過量疊加防止算法陷入局部最優(yōu)，后期值較大，加快收斂，如式（12）。

式中，Nmax為迭代總數(shù)，Lbest為當前局部區(qū)域或全局最優(yōu)路徑，L為歷史最優(yōu)路徑。

2.3 改進狀態(tài)轉(zhuǎn)移概率

反向?qū)W習(xí)的主要思想在于對一個可行解，同時評估其反向解，對比后選擇較優(yōu)解。蟻群算法的正反饋機制不適用于完全解[17]，因此反向?qū)W習(xí)更適用于擴展蟻群算法解空間而非評估反向解，通過反向?qū)W習(xí)增加解空間覆蓋率達到提高求解質(zhì)量的效果。文獻[12]提出基于反向?qū)W習(xí)的蟻群系統(tǒng)用于解決TSP問題，文獻[16]提出反向蟻群優(yōu)化算法解決故障診斷監(jiān)控參數(shù)優(yōu)化問題。

參考以上文獻，引入反向信息素改進蟻群算法狀態(tài)轉(zhuǎn)移概率，用于路徑規(guī)劃尋求最優(yōu)解。根據(jù)反向?qū)W習(xí)的定義，反向信息素計算如下式：

此時的信息素τij為局部和全局更新完畢后的信息素，分布優(yōu)化策略已結(jié)束，因此式（13）中Lgbest為全局最優(yōu)路徑長度。第一次迭代過程中不會產(chǎn)生Lgbest，因此第一次迭代時的值為初始信息素。其中確定反向信息素的值為初始信息素τij(0)和最優(yōu)路徑長度Lgbest，因為信息素的積累由初始信息素和最優(yōu)路徑長度共同決定。

當螞蟻m在t時刻進行路徑點選擇時，其轉(zhuǎn)移概率為：

式中，λc為反向概率，λc∈(0,1)，λ為隨機數(shù)；當λ<λc時，使用反向信息素計算選擇概率，當λ>λc時，選擇概率為原公式計算值。d(j,e)為下一節(jié)點j到終點e的歐氏距離。

3 改進蟻群算法的應(yīng)用步驟

步驟1建立矩陣柵格地圖，設(shè)置起始位置起點S與目標點E；初始化參數(shù)，包括信息素啟發(fā)因子α，期望啟發(fā)式因子β，揮發(fā)系數(shù)ρ，螞蟻總數(shù)W，迭代總數(shù)Nmax，信息素強度值Q，反向概率λc，信息素初始值τ0與初始信息素增量C。

步驟2初始信息素非均勻處理。通過式（8）確定ddiff，計算全局優(yōu)選區(qū)域R的范圍，并根據(jù)式（7）對初始信息素非均勻處理得出τij(0)。

步驟3路徑點選擇。將W只螞蟻放置于起點處，初始化禁忌表、路徑點、路徑長度，并將起點加入禁忌表中。根據(jù)式（14）和（15）計算每一只螞蟻下一路徑點選擇概率，通過輪盤賭選擇下一個節(jié)點，并將該節(jié)點加入禁忌表中。

步驟4判斷螞蟻是否到達了終點，如果沒有，則返回到步驟3直至到達目標點為止。否則執(zhí)行步驟5。

步驟5局部信息素分塊更新。當所有螞蟻完成當前迭代后，對所有地圖進行分塊處理，并分別計算每個區(qū)域的最佳局部路徑，按式（9）、（10）和（11）分別對每個區(qū)域進行信息素更新，此時Lbest為每個區(qū)域最優(yōu)局部解。當出現(xiàn)更優(yōu)解時，按照式（12）計算增強因子并代入式（11）中進行計算，L為每個區(qū)域歷史最優(yōu)路徑。

步驟6全局信息素更新。在局部區(qū)域信息素更新完畢后，按式（9）、（10）和（11）對全局信息素進行更新。此時Lbest為全局最優(yōu)解。當出現(xiàn)更優(yōu)解時，按照式（11）計算增強因子并代入式（11）中進行計算，L為全局歷史最優(yōu)路徑。

步驟7反向信息素更新。按照式（13）對反向信息素進行更新，式中Lbest為全局最優(yōu)解。

步驟8判斷是否達到最大迭代數(shù)。如果達到最大迭代數(shù)則輸出當前最優(yōu)全局路徑，如果沒有，則清空禁忌表，并將迭代次數(shù)加1，重復(fù)步驟3到步驟7，直到達到最大迭代數(shù)。

4 模擬實驗和分析

為驗證改進蟻群算法的有效性，在MATLAB 2018b上進行仿真實驗，操作系統(tǒng)為Win10（64 bit）操作系統(tǒng)，CoreTMi5-10210U處理器，16 GB運行內(nèi)存。仿真實驗采用兩組對比實驗，分別為20×20、30×30的柵格地圖，并在相同地圖下將本文改進蟻群算法與傳統(tǒng)蟻群算法、文獻[8]算法結(jié)果進行對比分析。

4.1 參數(shù)選取

蟻群算法參數(shù)多利用經(jīng)驗值取值，并利用多次對比結(jié)果選取最佳參數(shù)，但算法參數(shù)還涉及局部分塊優(yōu)化的步長n，因此基于以上參數(shù)，取分割步長n=1,2,…,c（c為地圖的列數(shù)）在隨機20×20、30×30地圖上進行實驗。其余仿真參數(shù)設(shè)置為：α=1,β=7,ρ=0.2,W=50,Nmax=

從20×20仿真結(jié)果圖2（a）來看，n∈[4,6]時，即將地圖分為4~5個區(qū)域效果較好，當n較小時，迭代次數(shù)比不分塊更高，算法信息素分布分散，難收斂，無法找到較優(yōu)值，因此路徑長度也比不分塊更長。隨著n的增加，雖然迭代收斂次數(shù)有時能較快收斂，但是算法也容易陷入局部最優(yōu)。從30×30的仿真結(jié)果圖2（b）也可以看出這一點，當n∈[4,7]時，對應(yīng)將地圖分為4~5效果較好，n過長或過短都將影響收斂與最終結(jié)果，造成收斂速度與局部最優(yōu)解的矛盾。基于此，對20×20和30×30都分為4塊，20×20地圖取n=5，30×30地圖取n=6。

圖2 n取值對結(jié)果的影響Fig.2 Influence of n value on results

4.2 20×20地圖實驗仿真

在20×20柵格地圖下，分別對傳統(tǒng)蟻群算法、文獻[8]、本文改進算法進行仿真，路徑仿真分別如圖3和圖4所示。最終實驗數(shù)據(jù)如表1所示：傳統(tǒng)算法路徑規(guī)劃長度為32.866，文獻[8]規(guī)劃長度為33.452，本文改進算法規(guī)劃長度為28.038。本文算法較另外兩種算法路徑規(guī)劃長度更短，拐點更少，對比傳統(tǒng)算法與文獻[8]算法，路徑長度分別縮短了14.6%和16.2%，拐點分別減少66.6%和75.0%。傳統(tǒng)蟻群算法收斂次數(shù)為21次，文獻[8]為5次，本文改進算法收斂次數(shù)為12次。雖然文獻[8]收斂次數(shù)為5，但是其求解質(zhì)量明顯低于本文改進算法，這也說明本文在算法收斂速度與求解全局最優(yōu)解上平衡得更好。傳統(tǒng)蟻群算法在迭代后期丟失最優(yōu)解，最后收斂為局部最優(yōu)值，而由于本文引入了增強因子r避免了這一問題，保留了最優(yōu)解，避免了陷入局部最優(yōu)。

圖3 20×20環(huán)境下四種算法仿真結(jié)果Fig.3 Simulation results of four algorithms in 20×20 environment

圖4 各算法路徑收斂曲線Fig.4 Convergence curve of each algorithm path

表1 20×20環(huán)境下各個算法結(jié)果對比Table 1 Comparison of results of various algorithms in 20×20 environment

為進一步驗證各個改進環(huán)節(jié)的有效性，分別對每個環(huán)節(jié)改進和本文整體改進在20×20柵格地圖下進行獨立實驗，實驗結(jié)果如表2所示。初始化與分塊策略這一改進環(huán)節(jié)對比傳統(tǒng)蟻群算法有效減少了迭代次數(shù)，同時找到了更優(yōu)解。反向?qū)W習(xí)信息素的引入對比傳統(tǒng)算法也有效提高了算法的全局尋優(yōu)能力，避免陷入了局部最優(yōu)，但也由于缺乏信息素引導(dǎo)，導(dǎo)致迭代次數(shù)較多。而本文的改進方法綜合以上步驟，結(jié)合了收斂速度的提升與全局尋優(yōu)能力上的改進，能在較少的迭代次數(shù)內(nèi)找到更優(yōu)解，同時曲線更平滑，路徑拐點數(shù)更少。

表2 20×20環(huán)境下各改進環(huán)節(jié)結(jié)果對比Table 2 Comparison of results of improvement steps in 20×20 environment

4.3 30×30地圖實驗仿真

在30×30復(fù)雜環(huán)境下，實驗仿真結(jié)果如圖5和圖6所示。隨著地圖的復(fù)雜度增加，三種算法收斂迭代次數(shù)都有所增加，傳統(tǒng)蟻群算法收斂曲線波動較大，算法穩(wěn)定性較差，且依然陷入了局部最優(yōu)。文獻[8]雖然對比傳統(tǒng)算法結(jié)果更優(yōu)，但由于該算法僅針對于最優(yōu)解拓展出來的小區(qū)域進行局部優(yōu)化，缺少全局探索，因此也陷入局部最優(yōu)。最終實驗數(shù)據(jù)如表3所示，綜合指標來看，本文改進算法在復(fù)雜環(huán)境下也有不錯效果。最優(yōu)路徑長度上來看，本文改進算法路徑長度對比傳統(tǒng)蟻群算法和文獻[8]分別縮短了14.1%和7.9%，拐點個數(shù)減少63.3%和60.0%，迭代次數(shù)減少23.0%和39.3%。在30×30地圖上也對各個步驟的改進進行了驗證，如表4，其結(jié)果與20×20地圖結(jié)果類似，再一次驗證了本文算法的有效性與優(yōu)越性。

圖5 30×30環(huán)境下四種算法仿真結(jié)果Fig.5 Simulation results of four algorithms in 30×30 environment

圖6 各算法路徑收斂曲線Fig.6 Convergence curve of each algorithm path

表3 30×30環(huán)境下各個算法結(jié)果對比Table 3 Comparison of results of various algorithms in 30×30 environment

表4 30×30環(huán)境下各改進環(huán)節(jié)結(jié)果對比Table 4 Comparison of results of improvement steps in 30×30 environment

5 結(jié)束語

本文針對傳統(tǒng)蟻群算法存在易陷入局部最優(yōu)、收斂速度慢等不足，提出改進蟻群算法。首先根據(jù)地圖的障礙物占比以及矩陣地圖大小構(gòu)建全局優(yōu)選區(qū)域，對初始信息素進行差異化處理，提高區(qū)域內(nèi)信息素初始濃度而非具體柵格點信息素濃度，避免陷入局部最優(yōu)的同時提高了收斂速度；利用局部信息素分塊優(yōu)化策略對矩陣地圖進行分塊處理，分別對各個子區(qū)域進行尋優(yōu)并更新最優(yōu)路徑信息素，后對全局路徑進行尋優(yōu)，更新最優(yōu)路徑信息素。為避免只更新最優(yōu)路徑信息素，丟失更優(yōu)解，在信息素更新公式中引入增強因子，保留更優(yōu)解，避免收斂于次優(yōu)解。最后應(yīng)用反向?qū)W習(xí)優(yōu)化信息素，改進狀態(tài)選擇概率，拓展了解空間，提高了全局搜索能力。實驗結(jié)果表明，改進后的算法明顯提高了收斂速度，尋優(yōu)能力更強。對初始化非均勻分布的處理、信息素更新規(guī)則的改進以及反向?qū)W習(xí)在蟻群路徑規(guī)劃上的應(yīng)用對比傳統(tǒng)算法均有明顯的改進，進一步驗證了算法的有效性與優(yōu)越性。