改進的蟻群算法在機器人路徑規劃上的應用

張曉莉，楊亞新，謝永成

西安科技大學 通信與信息工程學院，西安710000

1 引言

蟻群算法[1]（ACO）是一種啟發式智能群體仿生優化算法[2]，該算法是Dorigo等最早提出的一種基于種群的模擬進化算法，其目的就是蟻群在蟻巢和食物源之間尋找一條最短的可行路徑[3]，這與機器人路徑規劃的目的不謀而合[4]，兩者存在著本質上的聯系。因此，把蟻群算法運用到路徑規劃問題上具有合理性。此外，移動機器人路徑規劃也是機器人研究中的重要問題[5]。由于蟻群算法存在的運行時間長，易陷入局部最優等問題[6]，限制了它在求解最短路徑問題上的應用。對此，一些學者提出了一些改進算法來緩解上述問題[7]。

文獻[8]對傳統A*算法加以改進，提出正反向搜索交替機制的方法，運行速度和擴展節點規模兩個方面的性能有了明顯的改善，搜索效率較高并且具有較好的實時性，但是A*算法難以保證得到的解為最優解。文獻[9]提出將單向A*搜索算法應用于蟻群算法啟發函數中，并考慮前期螞蟻易陷入局部最優問題，引入自適應調整啟發函數來提高解的質量，但是單向A*算法存在的搜索效率和穩定性低的問題沒有得到很好的解決。文獻[10]對蟻群算法中針對信息素正反饋的原理強化性能較好的解而出現的停滯現象，提出動態修改增加信息素的方法，采用時變函數Q(t)來調整常數項信息素強度Q，并提出錦標賽競爭法的信息素更新策略，找到最為優秀的螞蟻，修改其所走過路徑對應邊的信息素，避免算法陷入局部最優且提高算法搜索效率，卻只考慮了每條路徑的重要程度，沒有考慮到路徑上每個路段的權重。文獻[11]提出一種基于自適應調整信息素的改進蟻群算法，根據人工螞蟻所獲得解的情況，動態調整路徑上的信息素，從而使得算法跳離局部最優解，該改進方法雖然在一定程度上提高了解的質量，但是改進方法單一并未能考慮較優路徑重要路段上的信息素強度，使得算法搜索效率不高。

在對以上改進算法研究分析的基礎上，考慮到蟻群算法具有自組織性、較強的魯棒性、尋優能力強且易于和其他算法相結合等優點。提出將改進后的雙向A*算法應用于蟻群算法中，在改進雙向搜索方向機制的啟發函數中繼續加入比例系數引導因子和衡量搜索空間大小的閾值，不僅使算法容易跳出局部最優解，而且可以加大螞蟻后期搜索的目的性。并針對算法模型改進引入路段權重因子，找到適合的函數模型來強化重要路段信息素增量，有效提高搜索速度和解的質量。

2 蟻群算法原理

蟻群算法通過信息素引導整個搜索過程[12]，該算法的核心在于模擬自然界螞蟻的覓食行為，即螞蟻從巢穴出發利用前一批次的螞蟻釋放的信息素選取到達目標點的最優路徑[13]。螞蟻在尋找食物的過程中，會在其走過的路線上留下一種被稱為信息素的物質，其他螞蟻能夠感知到這種物質并以此作為它們的前進方向[14]。

在人工蟻群算法中，設m 為螞蟻總數，螞蟻從某個節點轉移到另一個節點是由路徑上的信息素量決定的，在t 時刻，螞蟻k 從節點i 轉移到節點j 的狀態轉移概率為：

其中，dk={c-tabuk} 為螞蟻k 下一步可選城市集合，tabuk為禁忌表，用來記錄螞蟻走過的節點；α 表示路徑上信息素對螞蟻選擇的重要程度；β 為期望啟發因子；τij(t)為節點i 與節點j 之間的信息素量；ηij(t)為啟發函數，一般取做節點i 與節點j 之間歐式距離的倒數，即：

所有螞蟻都完成一次覓食以后，需要對信息素進行更新。更新公式為：

其中，ρ 為信息素揮發系數，表示信息素會隨著時間的推移而慢慢蒸發，信息素增量Δτij可表示為：

例如式（5）是最常用的蟻周模型：

其中，Q 為常數，Lk為螞蟻k 在本次循環中所走過的路徑長度。

移動機器人路徑規劃是指按照一定的性能指標規劃出一條從起始位置到目標位置的可通行路徑[16]。將改進后的蟻群算法應用于移動機器人在未知環境中搜索目標和尋求最短路徑問題上[17]。

3 改進的蟻群算法路徑規劃方法

3.1 添加雙向搜索方向機制和比例系數引導因子的啟發函數

經典蟻群算法中的啟發函數是通過相鄰柵格距離構造的，所得的數值差別很小，而且沒有考慮到從起點到目標點的方向性問題，可能導致在搜索過程中螞蟻會選擇與終點方向相背的區域行走或者走回路，從而導致算法的搜索效率很低并且尋得的路徑長度增大。針對這個問題，本文提出基于頭尾雙向搜索的A*算法對蟻群算法的啟發函數進行改進。

基于頭尾雙向搜索的A*算法是在傳統A*算法的基礎上進行改進的方法。改進后的A*算法中h*(n)將原來的當前節點到目標點的曼哈頓距離改為當前節點與另一搜索方向上的當前節點間的曼哈頓距離，即：

其中，g(n)表示初始節點s 到可選節點n 的代價，h*(n)表示當前可選節點n 與另一搜索方向上的當前節點d之間的曼哈頓距離。

雙向搜索方向分別存放了從初始節點出發和目標節點出發的當前節點信息，將原始算法的兩個隊列擴大為四個隊列，分別為從初始節點開始搜索的SOPEN、SCLOSED 隊列，從目標節點開始搜索的EOPEN、ECLOSED 隊列。每個子節點要從上、下、左、右、左上、左下、右上、右下8個方向上進行遍歷，搜索出有最小f(n)的擴展節點并放入CLOSED 隊列，直到某個擴展節點的啟發函數h*(n)值為零時，算法結束。

將雙向搜索機制和單向搜索在三種環境模型下進行仿真，圖1（a）和圖1（b）分別為在環境模型1下的搜索路徑和擴散節點區域；圖2（a）和圖2（b）分別為在環境模型2下的搜索路徑和擴散節點區域；圖3（a）和圖3（b）分別為在環境模型3下的搜索路徑和擴散節點區域。

圖1（a）環境模型1單向搜索算法

圖1（b）環境模型1雙向搜索算法

圖2（a）環境模型2單向搜索算法

圖2（b）環境模型2雙向搜索算法

圖3（a）環境模型3單向搜索算法

圖3（b）環境模型3雙向搜索算法

對三種環境模型下算法的運行時間和擴展節點兩項性能指標進行分析，得出表1所示結果。

表1 算法性能對比

由以上分析得出，雙向搜索算法相較于單向搜索運行時間更短，節點擴散個數也更少。

將改進后的A*算法估價函數值用于構造蟻群算法的啟發函數。改進后為如下公式：

在添加雙向搜索的啟發函數后，不僅考慮了源節點與目標節點的方向性問題，而且因為搜索是頭尾雙向并行進行的，相比單向搜索更易找到最優解。其運行速度和擴展節點規模兩個方面的性能也有了明顯的改善，從而有效提高搜索速率。

但是目標點方向信息對啟發函數的影響主要體現在后期螞蟻尋優路徑過程中。對于在前期過早引入目標點會導致初始時期搜索空間太小，算法容易陷入局部最優的問題，提出了在前期通過設置閾值范圍，不引入目標點對啟發函數的影響。用初始階段起始節點s 和當前節點i 之間的距離dsi作為衡量搜索空間大小的標準。在后期也即是閾值范圍外，引入雙向搜索目標點，并添加比例系數引導因子k 。 k 的取值又與當前螞蟻的迭代次數和螞蟻數量呈動態變化，路徑越靠近最優解，k 的取值就越大，相應的啟發函數值就越大，螞蟻在最優路徑上收斂越快，更容易快速找到最優解。

將前期和后期蟻群算法存在的問題考慮到其中，公式（8）中的啟發函數改進后為：

其中，Dsd為起始節點s 和從目標點搜索到的當前節點d 的距離；Dij為當前節點i 和下一步可選節點j 的距離。 μ 為極小鄰域值，由Dsd的長度具體決定。k 為比例系數引導因子，它隨著當前螞蟻數量mk和迭代次數Nc的增加而產生動態變化，k 的函數設定如下：

其中，m 為螞蟻總量，Ncmax為設定的最大迭代次數。

3.2 加入信息素權重的算法模型

由于蟻周模型具有更好的全局搜索能力，蟻周模型成為目前使用最多的模型，公式如式（5）所示，某只螞蟻走過的路徑上更新同路徑長度相對應的信息素量，但是由于每條路徑上不同部分的重要程度不同，如圖4 所示，螞蟻k 走過的路徑由5小段1-3-4-5-7組成，其中4段是最優路徑的一部分，很顯然，4段比其他幾個路段具有更重要的地位，因此對于路段4的信息素增量需要設置更大一些，而傳統的蟻周模型在每小段路徑上更新的信息素都相等。

圖4 螞蟻k 走過路徑和最優路徑

為加快算法的收斂速度，在蟻周模型的基礎上進行改進。根據一次迭代中螞蟻選擇的次數來衡量路徑上每一部分的重要程度，進而確定路徑k 上節點i 與節點j 之間的重要程度。引入路段權重因子μij，改進后的公式如下：

通過查閱資料發現神經網絡激活函數Softplus函數適合這個算法模型路段權重因子μij的改進。Softplus函數表達式為f(x)=ln(1+ex)，Softplus 函數是一個單調遞增的函數，其函數圖像如圖5所示。圖5中Relu函數表達式為y={x,x≥00,x ＜0 。

圖5 Softplus函數

本文提出的算法模型改進點綜合考慮了每條路徑的長度以及路徑上的每個路段的重要程度，每個路段的重要程度和被選擇的次數有關，被選擇次數越多，其重要程度越高，信息素增量就設置越多，這就強化了重要程度高的路徑，因此就加快了算法的收斂速度。

4 算法仿真與分析

為了驗證改進后的蟻群算法的可行性，在MATLAB R2014a 平臺環境下進行仿真實驗，其中，螞蟻個數為50，α=1，β=7，信息素蒸發系數ρ=0.95，信息素增加強度系數Q=1，分別在兩種實驗環境下對文獻[9]蟻群算法路徑規劃方法和文獻[10]動態調節信息素增量路徑規劃方法中的改進算法與本文改進后的蟻群算法進行分析對比，得出如圖6～9所示的實驗結果。

圖6 實驗1三種蟻群算法最短路徑長度對比圖

圖7 實驗1三種蟻群算法迭代次數對比圖

圖8 實驗2三種蟻群算法最短路徑長度對比圖

圖9 實驗2三種蟻群算法迭代次數對比圖

在實驗環境1中的仿真對比圖如圖6和圖7所示。

在實驗環境2中的仿真對比圖如圖8和圖9所示。

同時本文對兩次實驗進行了文獻[9]中蟻群算法路徑規劃方法與文獻[10]中動態調節信息素增量改進的蟻群算法以及本文提出的改進方法在最優路徑長度和迭代次數兩項指標的對比。如表2 和表3 所示，本文改進算法對比文獻[9]中算法在效率上提升了63.64%，文獻[10]中算法對比文獻[9]搜索效率上最大提升了54.55%。在路徑規劃結果上，本文改進算法最大減少了32.72%，文獻[10]中算法最大減少了31.39%。

表2 實驗1路徑長度與迭代次數仿真結果對比情況

表3 實驗2路徑長度與迭代次數仿真結果對比情況

此外，在第二種實驗下文獻[9]算法在搜索前期陷入了局部最優狀態，導致可行方向背離目標點。雖然最后跳出了局部最優解，但是使得算法搜索效率降低。文獻[10]中算法雖然能夠跳出局部最優解且算法搜索速度相比文獻[9]中算法有很大的提升，但是對比本文改進算法增加了4.06%的最優路徑長度，迭代次數也增加了14.28%。綜上所述，本文改進算法在前期能夠保證跳出局部最優解，且找到最佳路徑的前提下，顯著縮短了算法運行時間，提高算法的搜索效率和解的質量。

5 結語

本文選用神經網絡激活函數建立數學模型來改變重要路段信息素增量并添加雙向搜索方向機制和比例系數引導因子調整啟發函數，考慮了蟻群算法存在如前期易陷入局部極小值、收斂速度慢的缺點。并在兩種實驗環境下進行三種算法仿真對比分析，從仿真結果可以看出，本文算法在跳出局部最優解以及搜索效率上有所提高。但是，由于改進后的算法采用柵格法環境建模，所得出的路徑并不一定是最優的，所以算法的有效性還有待進一步的改善。