馬小銘 靳伍銀

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

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

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

1? ?蟻群算法基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

η* = ■? ? ? ?（4）

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

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

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

P *kij = ■，s∈allowk

（6）

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

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

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

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

3? ?仿真實驗

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

3.1? ?實驗一

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

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

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

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

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

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

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

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

3.2? ?實驗二

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

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

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

（a）傳統(tǒng)蟻群算法

（b）本文算法

4? ?結(jié)? ?論

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

參考文獻

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

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

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

[4]? ? 鄧萬宇，鄭慶華，陳琳，等. 神經(jīng)網(wǎng)絡(luò)極速學(xué)習(xí)方法研究[J]. 計算機學(xué)報，2010，33（02）：279-287.

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

[6]? ? 俞燁，賀乃寶，高倩，等. 基于改進蟻群算法的移動機器人路徑規(guī)劃[J].? 物聯(lián)網(wǎng)技術(shù)，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]. 電子學(xué)報，2011，39（05）：1220-1224.

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

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

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

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