基于改進(jìn)蟻群算法的多目標(biāo)路徑規(guī)劃研究

馬小銘 靳伍銀

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

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

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

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

1? ?蟻群算法基本原理

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

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

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

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

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

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

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

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

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

2? ?基于蟻群算法的改進(jìn)

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

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

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

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

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

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

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

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

η* = ■? ? ? ?（4）

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

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

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

P *kij = ■，s∈allowk

（6）

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

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

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

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

3? ?仿真實(shí)驗(yàn)

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

3.1? ?實(shí)驗(yàn)一

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

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

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

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

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

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

2）當(dāng)環(huán)境因子取值過大時(shí)，對(duì)死鎖點(diǎn)的排斥過大，其方法等效于死鎖點(diǎn)的填充。縮小了全局路徑搜索的范圍。

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

3.2? ?實(shí)驗(yàn)二

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

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

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

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

（b）本文算法

4? ?結(jié)? ?論

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

參考文獻(xiàn)

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

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

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

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

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

[6]? ? 俞燁，賀乃寶，高倩，等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(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]? 柳長安，鄢小虎，劉春陽，等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J]. 電子學(xué)報(bào)，2011，39（05）：1220-1224.

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

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

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

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