張?zhí)烊?，吳寶庫，周福?/p>

沈陽大學機械工程學院，沈陽 110044

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

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

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

1 環(huán)境建模

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

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

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

機器人將按照如下規(guī)則進行移動：

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

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

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

2 基本蟻群算法

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

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

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

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

3 改進蟻群算法

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

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

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

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

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

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

3.3 信息素揮發(fā)因子自適應更新

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

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

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

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

算法改進后，螞蟻從節(jié)點i運動到節(jié)點j概率為：

3.4 路徑交叉

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

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

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

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

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

3.5 路徑平滑

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

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

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

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

3.6 算法步驟

改進后蟻群算法流程如圖5所示，步驟如下：

圖5 改進蟻群算法流程Fig.5 Flow chart of improved ant colony algorithm

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

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

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

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

步驟5 判斷每只螞蟻是否全部移動至終點，若到達則算法運行下一步操作；否則回到步驟4。

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

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

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

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

3.7 運算復雜度

4 實驗仿真與分析

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

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

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

圖6 40×40復雜環(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 算法性能測試

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

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

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

表3 測試函數(shù)實驗結(jié)果Table 3 Test results

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

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

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

4.3 算法仿真與對比分析

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

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

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

在20×20 的柵格地圖中進行仿真實驗，分別利用ACO、UACO算法和本文提出的IACO算法對機器人移動路徑進行規(guī)劃，3種算法路徑規(guī)劃圖與算法迭代收斂曲線圖如圖8、9所示。實驗結(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 可知，應用本文提出的IACO 算法得到的最短路徑長度比應用ACO算法和UACO算法得到的最短路徑長度分別縮短了14.5%和9.8%。且應用IACO算法的搜索效率相比于ACO 和UACO 分別提高了47.2%和41.7%。此外應用IACO得到的最優(yōu)路徑拐點數(shù)量相比于ACO和UACO算法分別減少了58.8%和30%。因此，本文提出的IACO 算法在機器人路徑規(guī)劃中具有更強的尋優(yōu)能力。

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

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

為驗證復雜情況下本文提出的IACO 算法的機器人移動路徑規(guī)劃能力，在30×30 的柵格地圖中，分別利用ACO、UACO算法和IACO算法進行機器人路徑規(guī)劃仿真。由于地形相比較于20×20的地圖中更為復雜，為保持算法的可靠性，將螞蟻數(shù)量設置為100 只，算法最大迭代次數(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)路徑較長，并難以得到最優(yōu)解。UACO算法搜索前期具有一定的盲目性，且算法收斂較慢。而本文提出的IACO算法可在搜索前期較快的收斂，并且找到最短路徑。如表6 所示，應用IACO 算法得到的最短路徑比ACO 算法和UACO 算法分別縮短了16.1%和2.6%，拐點數(shù)量減少了38.1%和23.5%。因此，IACO算法有著較高的搜索效率，路徑拐點數(shù)量較少，路徑更為平滑，有著強勁路徑規(guī)劃性能。

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

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

為驗證在環(huán)境空間較大且障礙物分布較為復雜情況下，ICAO算法的機器人路徑規(guī)劃能力，創(chuàng)建40×40柵格地圖，分別利用ACO、UACO 算法和IACO 算法進行機器人路徑規(guī)劃仿真。由于40×40 地圖較大且障礙物分布情況更加復雜，為保持算法可靠性與穩(wěn)定性，將螞蟻數(shù)量設置為100只，算法最大迭代次數(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 可知，當機器人工作環(huán)境較大且障礙物分布較為密集時，應用ACO 算法與UACO 算法進行機器人路徑規(guī)劃時均無法有效收斂至最短路徑，規(guī)劃的機器人移動路徑較長，而應用IACO算法得到的機器人移動路徑更短，且算法可以有效收斂。如表7 所示，應用IACO 算法得到的最短路徑比ACO 算法和UACO算法分別縮短了23.2%和10.2%，拐點數(shù)量減少51.9%和31.6%，系統(tǒng)運行時間分別減少了52.0%與40.1%。因此，IACO算法可在更短的時間內(nèi)找到最短的移動路徑，且路徑更加平滑。

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

5 結(jié)論

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

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

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

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

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

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

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