基于改進蟻群算法的多目標路徑規(guī)劃研究

馬小銘 靳伍銀

摘? ?要：傳統蟻群算法因在復雜環(huán)境中容易產生死鎖，導致部分螞蟻失效，造成效率低下，迭代次數增多。為此，提出了一種利用環(huán)境信息引入環(huán)境因子來調整啟發(fā)函數的方法從而降低死鎖情況的發(fā)生，增加了有效螞蟻的數量，從整體上提高了蟻群的搜索速度，擴大了搜索范圍。同時，傳統蟻群算法在路徑規(guī)劃中僅在理想地域內尋求最短路徑，而多因素環(huán)境中最短路徑往往并非最優(yōu)解。為解決此問題通過在不同環(huán)境中對轉移概率進行加權優(yōu)化在追求路徑最短的基礎上提出多目標路徑規(guī)劃，豐富了蟻群算法的實用性和現實意義。最后經仿真實驗對優(yōu)化算法進行驗證，證明了上述優(yōu)化的可行性。

關鍵詞：蟻群算法;避障;多目標;柵格法;路徑規(guī)劃

中圖分類號：TP242? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A

Mulit-objcctive Path Planning Based

on Improved and Colony Algorithm

MA Xiao-ming ，JIN Wu-yin

（School of Mechanical and Electronical Engineering，Lanzhou University of Technology，Lanzhou，Gansu 730050，China）

Abstract：Traditional ant colony algorithm is prone to cause failure by deadlocks in complex environments. A novel method is proposed to solve the problem，which adjusts the heuristic function by introducing environmental factors according to environmental information，increased the number of ants effectively，improved the search speed of ant colony，and expanded the search range. Aiming at the limitation of traditional ant colony algorithm in pursuit of shortest path in the ideal region in path planning，and the shortest path in the multi-factor environment is often not the optimal solution，the multi-objective path planning is proposed based on the weighted optimization of transition probability in different environments on the basis of the shortest path，which enriches the practicality and practical significance of the ant colony algorithm. Finally，the simulation experiment of optimization algorithm proves the feasibility of the method.

Key words：ant colony algorithm;obstacle avoidance;multi-objective;grid method;path planning

路徑規(guī)劃是指在有障礙物的工作環(huán)境中尋找一條從起點到終點的避開所有障礙物的運動路徑。它是智能移動機器人領域的重點研究方向之一，是其行為決策的關鍵技術[1]。路徑規(guī)劃結果的優(yōu)劣，將直觀地對機器人運動過程的流暢性及結果造成影響[2]。而全局路徑規(guī)劃是在已知全局環(huán)境信息的情況下，事前規(guī)劃一條規(guī)避障礙的最優(yōu)路徑。常見的移動機器人全局路徑規(guī)劃算法主要有Q-learning算法[3]、神經網絡法[4]、遺傳算法[5]、蟻群算法等[6]。相比其他算法蟻群算法采用正反饋機制引導整個系統向最優(yōu)解的方向進化，具有較強的魯棒性[7]，更加廣泛應用于解決旅行商問題（TSP）、車輛路徑問題（VRP）[8]等方面，因此蟻群算法也越來越受到研究者的關注[9]。然而蟻群算法仍存在易死鎖和易陷入局部最優(yōu)等缺陷。

介紹了傳統蟻群算法的背景原理以及系統模型，然后針對傳統算法中的不足與缺陷通過利用環(huán)境信息引入環(huán)境因子來調整啟發(fā)因子降低死鎖次數，提高螞蟻的有效率和搜索速度。同時，在柵格法環(huán)境建模過程中增添加權路徑并對轉移概率進行優(yōu)化，實現多目標路徑規(guī)劃。最后對優(yōu)化后的蟻群算法與傳統蟻群算法進行實驗仿真對比，驗證了本優(yōu)化算法的有效性。

1? ?蟻群算法基本原理

自1960年提出仿生學后，人們模仿生物體內功能機理提出許多新的仿生算法。1990年初期，受螞蟻覓食過程的啟發(fā)，Dorigo M首次提出蟻群算法[10]。該算法模仿螞蟻在覓食過程中釋放一種特殊的可揮發(fā)分泌物來引導其他的螞蟻的行為。經過一段時間，距離較短的路徑上保留的分泌物會多余其他路徑。此后所有螞蟻都會沿分泌物較濃的路徑覓食。

蟻群算法中螞蟻根據各節(jié)點的信息素和啟發(fā)信息來選擇下一節(jié)點[11]。螞蟻k從i點轉移j點的轉移概率為P? kij，計算公式如下：

P kij = ■，s∈allowk? ? ?（1）

式中：allowk表示螞蟻k下一步允許選擇的節(jié)點的集合;τij（t）為t時刻節(jié)點i到節(jié)點j之間的信息素;啟發(fā)函數ηij（t） = 1/dij，其中dij為節(jié)點i與節(jié)點j之間的距離，由此可知節(jié)點間的距離越近，轉移概率越大;α和β兩個參數分別反映了螞蟻選擇路徑過程中信息素濃度和啟發(fā)信息的相對重要性。

螞蟻經過ij釋放信息素的同時，信息素也具有揮發(fā)的特性。當所有螞蟻完成一次循環(huán)后，每條路徑上的信息素濃度也將更新，規(guī)則如式（2）所示：

τ（t + 1）=（1 - ρ）τij + ΔτijΔτij = ■Δτ kij，0 < ρ < 1? ? （2）

式中，ρ為揮發(fā)系數，ρ值越大，信息素揮發(fā)越快，避免信息素的無限累加。Δτij表示所有螞蟻在ij路徑上釋放的信息素濃度;Δτkij表示第k只螞蟻在路徑ij上釋放的信息素濃度，如公式（3）所示：

Δτ kij=Q/Lk? 第k只螞蟻從節(jié)點i到節(jié)點j0? ? ? ?其他 （3）

其中，Q為常數，表示螞蟻一次循環(huán)釋放信息素的總量;Lk為第k只螞蟻在本次循環(huán)中所走的路徑長度。

2? ?基于蟻群算法的改進

2.1? ?環(huán)境介紹

柵格法作為路徑規(guī)劃常見的環(huán)境建模方法[12]，實質上是將工作環(huán)境進行單元分割，即其用大小相等的方塊表示出來。同時將所有方塊按照實際需要分為可行區(qū)域（白色區(qū)域）和障礙物（黑色區(qū)域）。為了研究多目標蟻群算法本文將引入帶有權重的可行區(qū)域（灰色區(qū)域）。該部分模擬道路中常見的擁堵、施工、收費等情況，在行進過程中應盡量避開該區(qū)域。環(huán)境搭建則應用矩陣將每一個元素轉化為對應顏色的方格，如圖1所示。

2.2? ?啟發(fā)信息優(yōu)化調整

傳統蟻群算法在初始階段，每個節(jié)點的信息素都是相同的，螞蟻在路徑選擇中主要依賴于啟發(fā)信息的差異。依據啟發(fā)函數公式可知螞蟻傾向于選擇距離較近的節(jié)點。該方法沒有利用全局地圖障礙物信息，只依據距離長短布局啟發(fā)信息，以致在障礙物多，地圖復雜的情況下，螞蟻陷入某一節(jié)點并且無下一節(jié)點可選擇即發(fā)生死鎖現象，隨后的螞蟻依照之前螞蟻保留的信息素將會導致越來越多的螞蟻死鎖。

經多次試驗證明，在遇到凹形或邊界出現L形等障礙最容易引發(fā)螞蟻的鎖死。常見的改進方法是將障礙物進行填充處理，消除凹形或邊界的L形障礙物。這種方法以修改環(huán)境為代價來提高螞蟻有效率，當環(huán)境改變時需要重新建立環(huán)境模型。文獻[13]通過在不同迭代次數動態(tài)自適應調整α、β的值來降低死鎖發(fā)生率。該方法僅從全局優(yōu)化的角度出發(fā)，沒有對容易發(fā)生死鎖的環(huán)境細節(jié)考慮。本文在傳統啟發(fā)信息算法中引入環(huán)境因子Ej來增強對環(huán)境的閱讀，有效避免死鎖，提高有效螞蟻的數量。

如圖2所示，某節(jié)點前往下一節(jié)點共有8個方向可供選擇，選擇過程主要依據節(jié)點上的信息素及其啟發(fā)信息，未考慮節(jié)點周邊障礙物數量及其分步。因此，本文有效利用全局環(huán)境信息，對節(jié)點周圍障礙物進行統計分析。經試驗表明當節(jié)點周邊出現5個以上的障礙物時，則視該節(jié)點容易引發(fā)死鎖狀態(tài)。因此對啟發(fā)函數進行以下調整。

引入環(huán)境因子Ej，對啟發(fā)函數按式（4）和（5）進行調整。當障礙物的點少于5個時，則Ej = 1。當障礙物的點在5個及以上時，Ej > 1更有利于算法的調整。同時，當發(fā)生死鎖現象，將該只螞蟻之前路徑遺留的信息素清空，防止對后續(xù)螞蟻產生干擾。

該方法目的是在算法初期通過啟發(fā)函數標記易死鎖的點，避免尋找路徑的過程中陷入死鎖狀態(tài)，提高了有效搜索次數。隨著迭代次數的增加，無效路徑上的信息素逐漸揮發(fā)，有效路徑上已經積累了部分信息素。此時信息素在路徑搜索中占據主導地位，因此該優(yōu)化既有效的避免死鎖又提高了收斂速度。

η* = ■? ? ? ?（4）

Ej = 1? ?節(jié)點j周圍障礙物個數<5>1? ?節(jié)點j周圍障礙物個數≥5 （5）

2.3? ?轉移概率優(yōu)化

傳統蟻群算法主要追求從起點至終點的最短路徑，但是在現實生活中路徑規(guī)劃問題不再是單一目標下的優(yōu)化問題，而轉化成了多目標優(yōu)化問題[14]。多目標優(yōu)化通常需要在兩個及兩個以上的目標條件約束下尋求最優(yōu)解。轉移概率主要是依據信息素和啟發(fā)信息計算從該節(jié)點往相鄰可行每一個節(jié)點的概率。然后采用輪盤賭算法[15]，來確定下一個節(jié)點。該方法根據每個節(jié)點的概率計算累計概率，然后隨機產生一個0～1的數，該數落入的累積概率對應的節(jié)點就是下一個被選的節(jié)點。如圖3所示，當隨機數落在P1至P1 + P2端，即選擇P2所對應的節(jié)點。本文將通過對轉移概率的優(yōu)化，實現在盡可能避開加權路段的同時追求一條最短路徑。改進后的概率轉移公式如（6）所示。

P *kij = ■，s∈allowk

（6）

式中D（x，y）為節(jié)點在柵格矩陣中對應的元素。如果是普通路徑則按照柵格環(huán)境搭建規(guī)則得知D（x，y） = 1，如果該路徑是擁堵或收費路段則D（x，y） >1。因此D（x，y）與P *kij成反比，表明螞蟻更加傾向沿普通路徑行走。

為描述多目標路徑規(guī)劃的有效性，權衡最短路徑與盡可能較少的經過加權路徑之間的關系。本文采用線性加權和法建立新的評價函數，該方法按照各目標的重要性賦予它相應的權系數，然后對其線性組合求解最優(yōu)路徑。如公式（7）所示：

Lbest = D（x，y）（Lp + Lw1 + Lw2 …）? ? ? ? ?（7）

式中，Lbest為所得路徑總長，值越小越接近路徑規(guī)劃的最優(yōu)解;Lp為普通路徑;Lwi（i = 1、2、3……）為加權路徑。

3? ?仿真實驗

為了驗證上述蟻群優(yōu)化算法具有可行性和有效性，通過兩次仿真實驗與傳統蟻群算法進行了對比。驗證了本算法的優(yōu)越點。實驗中部分參數如表1所示。

3.1? ?實驗一

該實驗在20 × 20的柵格中進行，環(huán)境中障礙物數量多，分布復雜，多采用螞蟻容易死鎖的凹形障礙物。主要驗證環(huán)境中優(yōu)化后的蟻群算法螞蟻死鎖數量下降，提高了蟻群搜索速度。實驗結果如圖4-10所示。

為驗證改進后蟻群算法的優(yōu)化效果，以及獲取Ej的最優(yōu)值。實驗依次對傳統算法、文獻[13]和不同Ej值的優(yōu)化算法進行對比。圖4-9為各類算法運行10組后所得到的最優(yōu)路徑規(guī)劃圖以及對應的迭代次數與規(guī)劃路徑長度關系圖。由實驗數據可知改進后的蟻群算法與其他算法相比在規(guī)劃路徑中差異較小，但是優(yōu)化后的算法經過前期的路徑探索，較早獲得最優(yōu)路徑并且趨于穩(wěn)定。圖9（a）和圖9（b）經過約20次迭代達到最優(yōu)路徑并趨于穩(wěn)定。圖9（c）和圖9（d）則在約40次迭代達到最優(yōu)值并趨于穩(wěn)定。圖9（e）雖收斂早，但未達到最優(yōu)值。由圖5可知傳統算法前期探索時間長，在達到最優(yōu)路徑后穩(wěn)定性差，經過多次浮動迭代至90次才達到最優(yōu)路徑。圖7所反映文獻[13]在獲取最優(yōu)路徑后，未能在最優(yōu)路徑處收斂。

圖10比較了10組實驗中螞蟻發(fā)生死鎖個數的平均值以及波動幅度。由圖可知本文算法在不同參數下均有效降低了死鎖數量的發(fā)生。由公式（8）計算可知，死鎖發(fā)生率降低了約78%。

降低率=■×100%? （8）

綜合收斂速度變化曲線以及死鎖數量的誤差分析可得，當Ej = 2 - 4時收斂曲線平穩(wěn)收斂于最優(yōu)路徑，死鎖發(fā)生數維持在較低水平，誤差范圍相比其他參數波動較小。因此，優(yōu)化效果整體優(yōu)于其他參數?？偨Y原因主要有一下兩點：

1）當環(huán)境因子取值過小時，由于輪盤賭算法的隨機性，對于容易死鎖節(jié)點的抑制效果不明顯。不能有效避開該節(jié)點，造成誤差波動幅度較大。

2）當環(huán)境因子取值過大時，對死鎖點的排斥過大，其方法等效于死鎖點的填充?？s小了全局路徑搜索的范圍。

該實驗表明本文算法降低了死鎖現象的發(fā)生，提高了蟻群中有效螞蟻的數量。同時，消除死鎖螞蟻路徑中留下了信息素避免了無效路徑中信息素對其他螞蟻的干擾，加快了最優(yōu)路徑搜索速度?；谏鲜鼋Y論，優(yōu)化后的蟻群算法增強了蟻群的整體性能，因而路徑搜索速度及收斂速度都有所增強。

3.2? ?實驗二

該實驗將某地區(qū)局部道路圖映射在50 × 50的柵格當中。為驗證優(yōu)化后的蟻群算法能實現多目標路徑規(guī)劃，在地圖中將帶有權重的路徑用黃色表示。實驗意圖規(guī)劃一條從起點至終點的最短路徑，同時能最大限度的規(guī)避加權路徑。實驗結果如圖11所示：

圖11（a）中螞蟻受啟發(fā)函數，沿近似對角方向按階梯形式到達終點，未能對加權路段有效回避。而圖7（b）中經優(yōu)化后的算法在加權路段具有自主規(guī)避性能。

由此得出，優(yōu)化后的算法能最大限度避開加權路徑而且與傳統蟻群算法相比路徑長度相同。實驗結果表明優(yōu)化后的蟻群算法在多目標路徑規(guī)劃中具有良好的效果。

（a）傳統蟻群算法

（b）本文算法

4? ?結? ?論

基于蟻群算法提出了新的優(yōu)化方案，充分利用環(huán)境信息優(yōu)化啟發(fā)函數，引入環(huán)境因子調節(jié)節(jié)點中的啟發(fā)信息解決傳統算法中死鎖個數多，收斂速度慢的缺點。其次，優(yōu)化轉移概率，在環(huán)境建模中新添加權路徑，著力解決多目標路徑規(guī)劃問題。最后，通過仿真實驗將本算法與傳統蟻群算法進行了比對，證實了本算法的優(yōu)點。

參考文獻

[1]? ? 史恩秀，陳敏敏，李俊，等. 基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J]. 農業(yè)機械學報，2014，45（06）：53-57.

[2]? ? 霍鳳財，遲金，黃梓健，等. 移動機器人路徑規(guī)劃算法綜述[J]. 吉林大學學報（信息科學版），2018，36（06）：639-647.

[3]? ? 王帥. 煤礦井下基于Q-learning算法的移動機器人路徑規(guī)劃[J]. 現代電子技術，2008，31（24）：106-108.

[4]? ? 鄧萬宇，鄭慶華，陳琳，等. 神經網絡極速學習方法研究[J]. 計算機學報，2010，33（02）：279-287.

[5]? ? 鞠成恩，趙曉俠，王明興，等. 基于遺傳算法的目標追蹤過程中路徑規(guī)劃研究[J]. 傳感器與微統，2018，37（06）：112-114.

[6]? ? 俞燁，賀乃寶，高倩，等. 基于改進蟻群算法的移動機器人路徑規(guī)劃[J].? 物聯網技術，2017，7（3）：46-49.

[7]? ? LI J，DONG T，LI Y. Research on task allocation in multiple logistics robots based on an improved ant colony algorithm[C].International Conference on Robotics & Automation Engineering. IEEE，2016.

[8]? ? PAN T，PAN H，GAO J. An improved ant colony algorithm based on vehicle routing problem[C]. Control Conference. IEEE，2015.

[9]? ? GAN R，GUO Q，Chang H，et al. Improved ant colony optimization algorithm for the traveling salesman problems[J].? Journal of Systems Engineering and Electronics，2010，21（2）：329-333.

[10]? DORIGO M，MANIEZZO V，COLORNI A. Ant system：optimization by a colony of cooperating agents [J].? IEEE Transactions on Systems，Man，and Cybernetics，Part B （Cybernetics），2002，26（1）：29-41.

[11]? 柳長安，鄢小虎，劉春陽，等. 基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J]. 電子學報，2011，39（05）：1220-1224.

[12]? 劉建華，楊建國，劉華平. 基于勢場蟻群算法的移動機器人全局路徑規(guī)劃方法[J/OL].農業(yè)機械學報，2015，46（9）：18-27.

[13]? 裴振兵，陳雪波. 改進蟻群算法及其在機器人避障中的應用[J]. 智能系統學報，2015，10（01）：90-96.

[14]? 喻環(huán). 改進蟻群算法在機器人路徑規(guī)劃上的應用研究[D].合肥：安徽大學，2017.

[15]? 馬振. 改進蟻群算法及其在TSP中的應用研究[D].青島理工大學，2016.