張?zhí)烊穑瑓菍殠?kù)，周福強(qiáng)

沈陽(yáng)大學(xué)機(jī)械工程學(xué)院，沈陽(yáng) 110044

近幾年，國(guó)內(nèi)外科學(xué)技術(shù)水平與自動(dòng)化程度逐漸提升，移動(dòng)機(jī)器人的應(yīng)用日益廣泛。例如在倉(cāng)儲(chǔ)車(chē)間中機(jī)器人可以替代人工搬運(yùn)貨物，既能提升搬運(yùn)效率，又可以降低危險(xiǎn)事故的發(fā)生，同時(shí)為企業(yè)節(jié)省大量人工成本。在智慧醫(yī)療領(lǐng)域，移動(dòng)機(jī)器人也有著巨大的應(yīng)用價(jià)值，例如可以代替人工將食物從廚房運(yùn)送到病房、運(yùn)輸一些被污染的醫(yī)療廢品、運(yùn)輸清潔手推車(chē)等，可大幅度提升醫(yī)院的運(yùn)行效率[1-2]。而優(yōu)秀的路徑規(guī)劃能力是移動(dòng)機(jī)器人的重要指標(biāo)。路徑規(guī)劃是指移動(dòng)機(jī)器人從起點(diǎn)開(kāi)始規(guī)劃出一條到終點(diǎn)的最佳移動(dòng)路徑，且有能力避開(kāi)環(huán)境中存在的障礙物，不與其發(fā)生碰撞，防止危險(xiǎn)的發(fā)生[3]，該路徑的質(zhì)量直接影響到移動(dòng)機(jī)器人系統(tǒng)的工作穩(wěn)定性與運(yùn)行效率[3-5]。全局路徑規(guī)劃作為機(jī)器人領(lǐng)域的一個(gè)重要研究對(duì)象[6]，專家學(xué)者已進(jìn)行了大量科研工作，例如遺傳算法[7]、粒子群算法[8]、蟻群算法等優(yōu)化算法[9]等。遺傳算法是借鑒生物界的進(jìn)化規(guī)律所設(shè)計(jì)的算法，在求解很多復(fù)雜優(yōu)化問(wèn)題方面，具有出色的性能，例如組合優(yōu)化[10]、車(chē)間調(diào)度[11]等領(lǐng)域，同時(shí)在機(jī)器人移動(dòng)路徑規(guī)劃方面也有著廣泛的應(yīng)用[12]。粒子群算法受鳥(niǎo)類(lèi)尋找食物的過(guò)程啟發(fā)，具有收斂速度快的特點(diǎn)，可應(yīng)用于復(fù)雜的多目標(biāo)優(yōu)化[13]、裝配線平衡[14]、機(jī)器人路徑規(guī)劃[15]等方面。

Dorigo[16]模擬自然界中蟻群覓食過(guò)程中搜尋可行路徑的方式提出蟻群算法，其全局優(yōu)化能力較強(qiáng)，因此非常適合用于優(yōu)化sink移動(dòng)距離[17]、機(jī)器人全局路徑規(guī)劃[18]等問(wèn)題，然而在實(shí)際應(yīng)用中，基本蟻群算法易出現(xiàn)局部極小值、收斂速度慢等問(wèn)題，因而國(guó)內(nèi)外眾多學(xué)者以不同的方式對(duì)其進(jìn)行了優(yōu)化。文獻(xiàn)[19]提出一種16方向24鄰域的路徑搜索方式，并對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)，使得螞蟻有更多的移動(dòng)路徑可供選擇，在簡(jiǎn)單的柵格地圖可有效縮短路徑長(zhǎng)度，但是在相對(duì)復(fù)雜的環(huán)境中，此方法效果并不明顯。文獻(xiàn)[20]在概率轉(zhuǎn)移函數(shù)中引入了權(quán)重因子，同時(shí)改進(jìn)了信息的更新方式，其仿真結(jié)果表明改進(jìn)后的算法收斂速度有所提高，最優(yōu)路徑更短，但是其搜索結(jié)果并不穩(wěn)定。文獻(xiàn)[21]提出了改進(jìn)改進(jìn)免疫遺傳優(yōu)化蟻群算法，可依照具體情況來(lái)調(diào)整變異概率與方式，并且可自適應(yīng)更新個(gè)體免疫位長(zhǎng)度，然后將改進(jìn)后的變異算子與免疫算法引入到蟻群算法，提升了算法尋優(yōu)能力，但使得算法步驟過(guò)多，延長(zhǎng)運(yùn)行時(shí)間。文獻(xiàn)[22]將粒子群算法與蟻群算法相結(jié)合，用粒子群算法得到初始的信息素，降低前期螞蟻搜索路徑的時(shí)間，但在路徑尋優(yōu)能力上還有待改進(jìn)，且算法運(yùn)行后期容易陷入局部極小值。

針對(duì)上述改進(jìn)蟻群算法的缺陷，提出新的改進(jìn)蟻群算法，引入轉(zhuǎn)角啟發(fā)函數(shù)以提升路徑選擇指向性；對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)，提高搜索速度；提出信息素?fù)]發(fā)因子自適應(yīng)更新策略，提升算法搜索性能，加快收斂速度；引入遺傳算法的染色體交叉操作，提升尋優(yōu)能力；最后通過(guò)路徑平滑操作得到最優(yōu)的機(jī)器人移動(dòng)路徑。

1 環(huán)境建模

為精準(zhǔn)表述機(jī)器人路徑規(guī)劃過(guò)程，需對(duì)其二維環(huán)境地圖進(jìn)行建模，常規(guī)的環(huán)境建模法有柵格法、幾何信息法、視圖法等。而柵格法具有建圖簡(jiǎn)單、數(shù)據(jù)結(jié)構(gòu)清晰易于實(shí)現(xiàn)等優(yōu)點(diǎn)。因此選取柵格法對(duì)機(jī)器人工作環(huán)境進(jìn)行建模。柵格法可將平面地圖分解為一系列的柵格，便于分析地圖信息。白色柵格表示機(jī)器人可自由移動(dòng)的區(qū)域，黑色柵格表示障礙物區(qū)域，示例如圖1 所示。對(duì)障礙物進(jìn)行膨化處理，如圖2 所示，障礙物擴(kuò)展的尺寸是移動(dòng)機(jī)器人半徑與安全預(yù)留距離之和，因此移動(dòng)機(jī)器人可視為一個(gè)沒(méi)有體積的質(zhì)點(diǎn)，圖中r為機(jī)器人半徑。若不規(guī)則障礙物沒(méi)有占滿一個(gè)柵格時(shí)，仍視為占滿一個(gè)柵格。

圖1 環(huán)境建模示例Fig.1 Environment modeling example

圖2 障礙物膨化Fig.2 Obstacle puffing

機(jī)器人將按照如下規(guī)則進(jìn)行移動(dòng)：

（1）機(jī)器人只可以出現(xiàn)在白色柵格內(nèi)，不能穿越或經(jīng)過(guò)黑色柵格移動(dòng)，但機(jī)器人可在黑色柵格的四角通過(guò)。

（2）優(yōu)秀的機(jī)器人路徑規(guī)劃要以盡可能短的移動(dòng)路徑使得機(jī)器人從起點(diǎn)運(yùn)動(dòng)到目標(biāo)點(diǎn)，因此若機(jī)器人重復(fù)經(jīng)過(guò)同一柵格，則證明該路徑必定浪費(fèi)更多不必要的能量且并非是最短路徑，因此定義機(jī)器人不可重復(fù)經(jīng)過(guò)同一柵格。

（3）在單位時(shí)間里，機(jī)器人只能在兩個(gè)相鄰的柵格間移動(dòng)，因此在一個(gè)單位的下一時(shí)刻，機(jī)器人只能出現(xiàn)在所處當(dāng)前柵格附近的8 個(gè)柵格里。利用歐氏距離來(lái)度量移動(dòng)路徑的長(zhǎng)度，若機(jī)器人向上下左右4個(gè)方向移動(dòng)，則路徑長(zhǎng)度為1 個(gè)單位，若機(jī)器人向柵格的4 角移動(dòng)，則路徑長(zhǎng)度為1.4個(gè)單位。

2 基本蟻群算法

蟻群算法受螞蟻種群覓食行為的啟發(fā)，在此過(guò)程，種群中每只螞蟻都會(huì)在其移動(dòng)路徑中留下信息素以向種群傳達(dá)信息。移動(dòng)路徑越短，則信息素濃度較高，該路徑被螞蟻選中的概率較大，這就形成了螞蟻尋找最短路徑的正反饋機(jī)制?；鞠伻核惴ㄔ砣缦?。

螞蟻移動(dòng)時(shí)，依照信息素濃度與距離啟發(fā)函數(shù)來(lái)選擇路徑，螞蟻k從柵格i運(yùn)動(dòng)至柵格j的概率可表示為：α為信息素啟發(fā)因子，β為距離期望函數(shù)因子，二者分別影響著信息素與距離啟發(fā)函數(shù)的重要程度；Ak表示螞蟻下一步可到達(dá)目的地集合；τij(t)為t時(shí)刻移動(dòng)路線上的信息素濃度；ηij(t)表示距離啟發(fā)函數(shù)。

每只螞蟻在移動(dòng)時(shí)均會(huì)遺留一定量的信息素，因此算法不斷迭代時(shí)，路徑中信息素含量逐漸累積，同時(shí)也在不斷的揮發(fā)，當(dāng)全體種群均完成第一次迭代后，將依照式（4）～（6）刷新路徑上信息素含量：

ρ為信息素?fù)]發(fā)系數(shù)；Δτij表示兩節(jié)點(diǎn)上釋放信息素的和；表示兩節(jié)點(diǎn)上信息素增量；Lk表示螞蟻k經(jīng)過(guò)路徑長(zhǎng)度，Q為信息素增強(qiáng)系數(shù)。

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

利用基本蟻群算法對(duì)機(jī)器人路徑進(jìn)行規(guī)劃時(shí)，其算法的啟發(fā)函數(shù)僅僅考慮了局部的最短路徑，若以全局路徑的角度分析，并非是最優(yōu)的選擇。此外，基本蟻群算法的信息素?fù)]發(fā)因子數(shù)值從始至終是一成不變的，并沒(méi)有任何動(dòng)態(tài)的調(diào)整，因而算法極其容易陷入局部最優(yōu)解，導(dǎo)致無(wú)法找到全局最優(yōu)解，并消耗了大量的時(shí)間與能源。針對(duì)上述問(wèn)題，提出合理的優(yōu)化策略與改善方案：包括引入轉(zhuǎn)角啟發(fā)函數(shù)達(dá)到提升路徑選擇指向性，并縮短轉(zhuǎn)彎時(shí)間的效果；其次改進(jìn)啟發(fā)函數(shù)，可快速找到較優(yōu)路徑；此外提出信息素?fù)]發(fā)因子自適應(yīng)更新策略，以降低算法前期搜索的盲目性，并提高搜索后期的收斂速度；最后引入遺傳算法的染色體交叉操作，找到全局最優(yōu)解，并通過(guò)路徑平滑操作得到最優(yōu)的機(jī)器人移動(dòng)路徑。

3.1 設(shè)計(jì)轉(zhuǎn)角啟發(fā)函數(shù)

當(dāng)螞蟻在柵格移動(dòng)時(shí)，爬行的角度只能是0°、45°、90°、135°四種情形，為應(yīng)盡可能減少路徑轉(zhuǎn)折點(diǎn)，并提升路徑指向性，設(shè)計(jì)轉(zhuǎn)角啟發(fā)函數(shù)：

3.2 改進(jìn)啟發(fā)函數(shù)

在基本蟻群算法運(yùn)行的初始階段，螞蟻經(jīng)過(guò)的移動(dòng)路徑并不存在信息素，導(dǎo)致后續(xù)的螞蟻不能依照路徑中信息素的濃度高低來(lái)判定其較優(yōu)移動(dòng)方向，無(wú)法快速搜尋到可行路徑。針對(duì)這一問(wèn)題，對(duì)基本蟻群算法的距離啟發(fā)函數(shù)進(jìn)行優(yōu)化，利用當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間的距離和下一節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)距離之和的二次方來(lái)改進(jìn)啟發(fā)函數(shù)，可達(dá)到在算法運(yùn)行初期獲得朝向目標(biāo)點(diǎn)引導(dǎo)方向搜索的目的，優(yōu)化后啟發(fā)函數(shù)：

其中djD含義為節(jié)點(diǎn)j與目標(biāo)點(diǎn)的歐幾里得距離，改進(jìn)后的啟發(fā)函數(shù)可提高算法搜索路徑的目的性，并降低陷入局部極小值的概率。

3.3 信息素?fù)]發(fā)因子自適應(yīng)更新

基本蟻群算法信息素?fù)]發(fā)因子通常是不變的，這就導(dǎo)致螞蟻在探索路徑時(shí)信息素分配不合理。早期路徑中信息素含量過(guò)低，因此，增加了螞蟻搜索路徑的盲目性，而后期由于信息素積累過(guò)多，又縮小了路徑的可選擇范圍，導(dǎo)致算法陷入局部最優(yōu)。故不變的揮發(fā)因子對(duì)搜索最優(yōu)路徑并非是最具優(yōu)勢(shì)的。本文提出信息素?fù)]發(fā)因子自適應(yīng)更新策略如下：

其中T表示算法總迭代次數(shù)，t表示當(dāng)前迭代次數(shù)。

為盡可能搜索到更多的移動(dòng)路徑，在算法尋優(yōu)的初始階段，應(yīng)將信息素含量控制在較低水平，因此初始揮發(fā)因子ρ1的取值不應(yīng)過(guò)小，此時(shí)信息素濃度對(duì)螞蟻探索路徑的過(guò)程干預(yù)較小，螞蟻可搜索到更多的移動(dòng)路徑。隨著算法逐步迭代，揮發(fā)因子ρ數(shù)值逐漸降低，負(fù)反饋效果削弱，移動(dòng)路徑上信息素含量提高，信息素濃度對(duì)蟻群的導(dǎo)向作用增強(qiáng)，當(dāng)?shù)螖?shù)提升到一定次數(shù)時(shí)，蟻群將向信息素含量較高的路徑匯集。因此，改進(jìn)后的算法可以擴(kuò)大蟻群搜索范圍，且提高收斂速度，信息素?fù)]發(fā)因子變化曲線如圖3所示，其中初始揮發(fā)因子ρ1設(shè)置為0.9。

圖3 信息素?fù)]發(fā)因子變化曲線Fig.3 Change curve of pheromone volatilization factor

算法改進(jìn)后，螞蟻從節(jié)點(diǎn)i運(yùn)動(dòng)到節(jié)點(diǎn)j概率為：

3.4 路徑交叉

當(dāng)蟻群算法在迭代過(guò)程中，隨著移動(dòng)路徑上信息素的揮發(fā)與積累，最終收斂至最優(yōu)路徑，若算法多次迭代后，始終無(wú)法尋得更優(yōu)路徑，則算法陷入局部最優(yōu)。因此，本文將利用標(biāo)準(zhǔn)遺傳算法中染色體交叉操作，對(duì)蟻群算法在每次迭代后得到的移動(dòng)路徑進(jìn)行二次優(yōu)化，進(jìn)而使得蟻群算法跳出局部最優(yōu)解，以找到全局最優(yōu)，遺傳算法染色體交叉操作如下。

（1）從目前算法迭代得到的全部移動(dòng)路徑中，選擇當(dāng)前最優(yōu)路徑并復(fù)制全部路徑的1n個(gè)，作為種群的一部分，同時(shí)利用輪盤(pán)賭[23]方法，生成剩余()n-1 /n個(gè)初始種群。

（2）在初始種群中，隨機(jī)挑選兩條路徑作為染色體交叉操作的親代。

（3）找出親代路徑中全部相同的節(jié)點(diǎn)，隨機(jī)選取一組進(jìn)行路徑片段交叉操作，生成兩個(gè)子代路徑。

（4）在全部子代路徑中找出最優(yōu)路徑，若路徑長(zhǎng)度比當(dāng)前迭代最優(yōu)路徑或全局最優(yōu)路徑更短，則用其代替當(dāng)前迭代最優(yōu)路徑和全局最優(yōu)路徑。

3.5 路徑平滑

當(dāng)機(jī)器人移動(dòng)過(guò)程中，能源消耗與運(yùn)行時(shí)間也應(yīng)予以考慮，移動(dòng)路徑的節(jié)點(diǎn)越多，機(jī)器人的移動(dòng)時(shí)間就越長(zhǎng)，導(dǎo)致能源浪費(fèi)。利用基本蟻群算法規(guī)劃的移動(dòng)路徑存在一些冗余節(jié)點(diǎn)，因此需要對(duì)該路徑進(jìn)行路徑平滑操作，減少多余的節(jié)點(diǎn)，縮短移動(dòng)路徑長(zhǎng)度，提高路徑平滑度。所以本文基于Floyd 算法的思想設(shè)計(jì)路徑平滑方法，以減少路徑中不必要的轉(zhuǎn)彎節(jié)點(diǎn)，縮短移動(dòng)距離進(jìn)而節(jié)約工作時(shí)間，降低能耗。

具體操作步驟為，從起點(diǎn)開(kāi)始，往后依次選擇相鄰的3個(gè)路徑中的節(jié)點(diǎn)連接，將節(jié)點(diǎn)1與節(jié)點(diǎn)3連線，若之間沒(méi)有障礙物且第3個(gè)節(jié)點(diǎn)的位置處于第1個(gè)節(jié)點(diǎn)可移動(dòng)的范圍內(nèi)，則刪除節(jié)點(diǎn)1與節(jié)點(diǎn)3之間的節(jié)點(diǎn)2，所以機(jī)器人將直接從節(jié)點(diǎn)1移動(dòng)至節(jié)點(diǎn)2，縮短移動(dòng)距離，遍歷后續(xù)全部節(jié)點(diǎn)，繼續(xù)依照此方法，進(jìn)行路徑平滑操作，直至選取的節(jié)點(diǎn)為目標(biāo)點(diǎn)為止。

如圖4 所示，以該路徑平滑為例，若利用基本蟻群算法規(guī)劃的移動(dòng)路徑為(S,1,2,3,4,5,6,7,8,9,10,11,T)，顯而易見(jiàn)該移動(dòng)路徑中存在一些冗余的節(jié)點(diǎn)，則利用上述路徑平滑的方法對(duì)移動(dòng)路徑進(jìn)行優(yōu)化后，移動(dòng)路徑縮短為(S,1,2,3,4,6,8,10,T)，有效地減少了移動(dòng)路徑中的冗余節(jié)點(diǎn)，移動(dòng)路徑更加平滑。

圖4 路徑平滑優(yōu)化前后對(duì)比Fig.4 Comparison of path smooth before and after optimization

3.6 算法步驟

改進(jìn)后蟻群算法流程如圖5所示，步驟如下：

圖5 改進(jìn)蟻群算法流程Fig.5 Flow chart of improved ant colony algorithm

步驟1 利用柵格法構(gòu)建機(jī)器人工作的地圖模型。

步驟2 調(diào)試算法參數(shù)，設(shè)置起點(diǎn)與終點(diǎn)位置。

步驟3 螞蟻從起始點(diǎn)出發(fā)，搜尋最優(yōu)移動(dòng)路徑。

步驟4 依照引入轉(zhuǎn)角啟發(fā)函數(shù)的概率公式，得到螞蟻下一次運(yùn)動(dòng)節(jié)點(diǎn)。

步驟5 判斷每只螞蟻是否全部移動(dòng)至終點(diǎn)，若到達(dá)則算法運(yùn)行下一步操作；否則回到步驟4。

步驟6 依照優(yōu)化的后的信息素自適應(yīng)更新策略更新路徑中螞蟻留下的信息素含量。

步驟7 記錄每只螞蟻的路徑長(zhǎng)度，選出當(dāng)前迭代中最優(yōu)路徑，更新全局最優(yōu)路徑。

步驟8 選擇當(dāng)前迭代中對(duì)應(yīng)的路徑進(jìn)行路徑交叉操作，所得結(jié)果更新當(dāng)前最優(yōu)解與全局最優(yōu)解。

步驟9 判斷是否達(dá)到終止迭代條件，若達(dá)到則輸出全局最優(yōu)解并執(zhí)行路徑平滑操作；否則返回步驟3。

3.7 運(yùn)算復(fù)雜度

4 實(shí)驗(yàn)仿真與分析

為驗(yàn)證本文改進(jìn)蟻群算法的可行性、穩(wěn)定性、優(yōu)越性，通過(guò)仿真軟件MATLAB2018a，在2.20 GHz PC，8 GB RAM，Windows10，64位操作系統(tǒng)上運(yùn)行。

4.1 優(yōu)化引入?yún)?shù)

在實(shí)驗(yàn)中依照經(jīng)驗(yàn)，蟻群算法參數(shù)初始化為：M=100，T=400，α=1.5，β=10，Q=1，ρ1=0.9。對(duì)引入的參數(shù)n、ε進(jìn)行組合優(yōu)化，設(shè)定參數(shù)范圍為：n∈{4，5，6，7，8}，ε∈{1，2，3，4，5}，參數(shù)默認(rèn)為n=6，ε=2。每次實(shí)驗(yàn)僅改變一個(gè)參數(shù)，其他參數(shù)設(shè)為默認(rèn)值，實(shí)驗(yàn)在40×40復(fù)雜環(huán)境中，進(jìn)行如圖6所示數(shù)仿真實(shí)驗(yàn)20次取均值，實(shí)驗(yàn)結(jié)果如表1所示，n=5時(shí)路徑最優(yōu)，ε=3路徑最優(yōu)。故本文引入?yún)?shù)n、ε取值分別為5、3。

圖6 40×40復(fù)雜環(huán)境地圖Fig.6 40×40 complex environment map

表1 引入?yún)?shù)優(yōu)化結(jié)果Table 1 Optimization results of introduced parameters

4.2 算法性能測(cè)試

為驗(yàn)證本文改進(jìn)蟻群算法的尋優(yōu)能力，利用7個(gè)不同特質(zhì)的測(cè)試函數(shù)進(jìn)行函數(shù)尋優(yōu)對(duì)比測(cè)試，其中f1、f2、f3、f4是單模態(tài)函數(shù)，f5、f6、f7是多模態(tài)函數(shù)，如表2所示。與本文改進(jìn)蟻群算法（IACO）對(duì)比的是基本蟻群算法（ACO）與基于改進(jìn)搜索策略的蟻群算法[24]（UACO）。種群數(shù)量設(shè)為100，問(wèn)題維度設(shè)為30，最大迭代次數(shù)設(shè)為400，算法共有參數(shù)保持一致。上述3 種算法在各個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行30 次的結(jié)果，如表3所示。

表2 測(cè)試函數(shù)Table 2 Test functions

由表3 的測(cè)試實(shí)驗(yàn)結(jié)果可知，本文提出的IACO 算法針對(duì)單模測(cè)試函數(shù)與多模測(cè)試函數(shù)的尋優(yōu)效果在3個(gè)算法的對(duì)比中都是最優(yōu)的，并且對(duì)于函數(shù)f1、f2、f5都可以搜索得到理論的全局最優(yōu)值0，尋優(yōu)效果可達(dá)到100%，此外IACO在這3個(gè)函數(shù)尋優(yōu)過(guò)程中的標(biāo)準(zhǔn)差始終都為0，則證明IACO 算法具有良好的穩(wěn)定性與魯棒性。在測(cè)試函數(shù)f3中，ACO 算法與UACO 算法的尋優(yōu)表現(xiàn)均相對(duì)較差，而利用IACO算法對(duì)測(cè)試函數(shù)f3進(jìn)行尋優(yōu)時(shí)，其平均值比其他兩個(gè)算法高出了5 個(gè)數(shù)量級(jí)，說(shuō)明IACO算法的尋優(yōu)能力更強(qiáng)。對(duì)于函數(shù)f4、f6、f7而言，IACO算法在實(shí)驗(yàn)結(jié)果的4項(xiàng)指標(biāo)中，均優(yōu)于ACO算法與UACO 算法，表明IACO 算法的尋優(yōu)精度更高，尋優(yōu)能力更強(qiáng)。

表3 測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果Table 3 Test results

為更好地體現(xiàn)出IACO算法較強(qiáng)的尋優(yōu)能力，部分測(cè)試函數(shù)的收斂曲線如圖7所示。

圖7 函數(shù)的收斂曲線Fig.7 Convergence curves of functions

本文選取的測(cè)試函數(shù)中f1～f4是單峰函數(shù)，可用來(lái)檢測(cè)算法的收斂精度和收斂速度，而f5～f7是多峰函數(shù)，可用來(lái)檢測(cè)算法跳出局部極小值與全局搜索能力，同時(shí)也能測(cè)試算法的收斂精度和收斂速度。由7 圖可知，IACO 算法的適應(yīng)度值收斂曲線下降速度相比較于ACO 與UACO 更快，而且達(dá)到穩(wěn)定時(shí)的狀態(tài)所用迭代次數(shù)更少，并且穩(wěn)定時(shí)函數(shù)適應(yīng)度值更低，證明IACO算法具有更高的收斂精度與收斂速度。此外，在多峰函數(shù)f6與f7的收斂曲線中，IACO算法在迭代過(guò)程中出現(xiàn)多個(gè)拐點(diǎn)，并且其收斂精度也是3 個(gè)算法中最高的，因此IACO算法可以跳出局部極小值，具有良好的局部搜索能力同時(shí)也具有優(yōu)秀的全局搜索能力。

4.3 算法仿真與對(duì)比分析

為驗(yàn)證IACO算法在機(jī)器人路徑規(guī)劃中的有效性，將ACO 與UACO 作為對(duì)比算法，在3 種不同環(huán)境地圖中進(jìn)行仿真對(duì)比實(shí)驗(yàn)，3種算法參數(shù)設(shè)置如表4所示。

表4 算法參數(shù)設(shè)置Table 4 Algorithm parameters setting

4.3.1 20×20仿真環(huán)境

在20×20 的柵格地圖中進(jìn)行仿真實(shí)驗(yàn)，分別利用ACO、UACO算法和本文提出的IACO算法對(duì)機(jī)器人移動(dòng)路徑進(jìn)行規(guī)劃，3種算法路徑規(guī)劃圖與算法迭代收斂曲線圖如圖8、9所示。實(shí)驗(yàn)結(jié)果如表5所示。

圖8 20×20柵格地圖中基于3種蟻群算法最優(yōu)規(guī)劃路徑Fig.8 Optimal plan path based on three ant colony algorithms in 20×20 grid map

由表5 可知，應(yīng)用本文提出的IACO 算法得到的最短路徑長(zhǎng)度比應(yīng)用ACO算法和UACO算法得到的最短路徑長(zhǎng)度分別縮短了14.5%和9.8%。且應(yīng)用IACO算法的搜索效率相比于ACO 和UACO 分別提高了47.2%和41.7%。此外應(yīng)用IACO得到的最優(yōu)路徑拐點(diǎn)數(shù)量相比于ACO和UACO算法分別減少了58.8%和30%。因此，本文提出的IACO 算法在機(jī)器人路徑規(guī)劃中具有更強(qiáng)的尋優(yōu)能力。

表5 20×20柵格地圖中3種蟻群算法仿真結(jié)果對(duì)比Table 5 Comparison of simulation results of three ant colony algorithms in 20×20 grid map

4.3.2 30×30仿真環(huán)境

為驗(yàn)證復(fù)雜情況下本文提出的IACO 算法的機(jī)器人移動(dòng)路徑規(guī)劃能力，在30×30 的柵格地圖中，分別利用ACO、UACO算法和IACO算法進(jìn)行機(jī)器人路徑規(guī)劃仿真。由于地形相比較于20×20的地圖中更為復(fù)雜，為保持算法的可靠性，將螞蟻數(shù)量設(shè)置為100 只，算法最大迭代次數(shù)設(shè)置為150，其他參數(shù)不變。3 種算法路徑規(guī)劃圖與算法迭代收斂曲線如圖10與圖11所示。

圖9 20×20柵格地圖中3種蟻群算法迭代曲線Fig.9 Iteration curves of three ant colony algorithms in 20×20 grid map

圖10 30×30柵格地圖中基于3種蟻群算法最優(yōu)規(guī)劃路徑Fig.10 Optimal plan path based on three ant colony algorithms in 30×30 grid map

圖11 30×30柵格地圖中3種蟻群算法迭代曲線Fig.11 Iteration curves of three ant colony algorithms in 30×30 grid map

由圖10 與圖11 可知，ACO 算法搜索速度較慢，搜索最優(yōu)路徑較長(zhǎng)，并難以得到最優(yōu)解。UACO算法搜索前期具有一定的盲目性，且算法收斂較慢。而本文提出的IACO算法可在搜索前期較快的收斂，并且找到最短路徑。如表6 所示，應(yīng)用IACO 算法得到的最短路徑比ACO 算法和UACO 算法分別縮短了16.1%和2.6%，拐點(diǎn)數(shù)量減少了38.1%和23.5%。因此，IACO算法有著較高的搜索效率，路徑拐點(diǎn)數(shù)量較少，路徑更為平滑，有著強(qiáng)勁路徑規(guī)劃性能。

表6 30×30柵格地圖中3種蟻群算法仿真結(jié)果對(duì)比Table 6 Comparison of simulation results of three ant colony algorithms in 30×30 grid map

4.3.3 40×40仿真環(huán)境

為驗(yàn)證在環(huán)境空間較大且障礙物分布較為復(fù)雜情況下，ICAO算法的機(jī)器人路徑規(guī)劃能力，創(chuàng)建40×40柵格地圖，分別利用ACO、UACO 算法和IACO 算法進(jìn)行機(jī)器人路徑規(guī)劃仿真。由于40×40 地圖較大且障礙物分布情況更加復(fù)雜，為保持算法可靠性與穩(wěn)定性，將螞蟻數(shù)量設(shè)置為100只，算法最大迭代次數(shù)設(shè)置為400，其他參數(shù)不變。3種算法路徑規(guī)劃圖與算法迭代收斂曲線如圖12和圖13所示。

圖12 40×40柵格地圖中基于3種蟻群算法最優(yōu)規(guī)劃路徑圖Fig.12 Optimal plan path based on three ant colony algorithms in 40×40 grid map

圖13 40×40柵格地圖中3種蟻群算法迭代曲線Fig.13 Iteration curves of three ant colony algorithms in 40×40 grid map

由圖12 和圖13 可知，當(dāng)機(jī)器人工作環(huán)境較大且障礙物分布較為密集時(shí)，應(yīng)用ACO 算法與UACO 算法進(jìn)行機(jī)器人路徑規(guī)劃時(shí)均無(wú)法有效收斂至最短路徑，規(guī)劃的機(jī)器人移動(dòng)路徑較長(zhǎng)，而應(yīng)用IACO算法得到的機(jī)器人移動(dòng)路徑更短，且算法可以有效收斂。如表7 所示，應(yīng)用IACO 算法得到的最短路徑比ACO 算法和UACO算法分別縮短了23.2%和10.2%，拐點(diǎn)數(shù)量減少51.9%和31.6%，系統(tǒng)運(yùn)行時(shí)間分別減少了52.0%與40.1%。因此，IACO算法可在更短的時(shí)間內(nèi)找到最短的移動(dòng)路徑，且路徑更加平滑。

表7 40×40柵格地圖中3種蟻群算法仿真結(jié)果對(duì)比Table 7 Comparison of simulation results of three antcolony algorithms in 40×40 grid map

5 結(jié)論

為提高基本蟻群算法的收斂速度與尋優(yōu)能力，本文提出改進(jìn)蟻群算法，主要體現(xiàn)在以下5個(gè)方面：

（1）引入方向夾角啟發(fā)函數(shù)，增加了路徑選擇的指向性，可有效縮短機(jī)器人在轉(zhuǎn)彎過(guò)程中不必要時(shí)間。

（2）重新設(shè)計(jì)蟻群算法的啟發(fā)函數(shù)，有效地縮短了算法的運(yùn)行時(shí)間和最優(yōu)移動(dòng)路徑的距離。

（3）提出了信息素?fù)]發(fā)因子自適應(yīng)更新策略，提高了算法迭代速率。

（4）引入遺傳算法的交叉操作，對(duì)每次迭代后的路徑進(jìn)行了二次優(yōu)化，避免算法陷入局部極小值，使算法找到全局最優(yōu)解。

（5）對(duì)最終的最佳移動(dòng)路徑進(jìn)行平滑處理，減少路徑中不必要的節(jié)點(diǎn)，降低了移動(dòng)機(jī)器人的能量損耗，并縮短了工作時(shí)間。

由仿真對(duì)比結(jié)果可知，本文的改進(jìn)蟻群算法可有效提升收斂速度，尋優(yōu)能力更強(qiáng)，且規(guī)劃的路徑更為平滑，降低了機(jī)器人的能量損耗，在簡(jiǎn)單的環(huán)境與在復(fù)雜的環(huán)境均取得了良好的效果，驗(yàn)證了該算法的可行性和有效性。