基于雙向蟻群算法的路徑規(guī)劃研究

申鉉京,施英杰,黃永平,王玉

(1.吉林大學 計算機科學與技術(shù)學院,吉林 長春 130012;2.吉林大學 軟件學院,吉林 長春 130012)

蟻群算法[1]是經(jīng)典的仿生學優(yōu)化算法之一,與Dijstra[2]、Bellman-Ford[3]以及A*算法[4]等尋路算法相比,在尋求最短路徑上始終具有更加優(yōu)越的效果。

此外,在解決路徑問題時,與其他的優(yōu)化算法如模擬退火算法[5]及遺傳算法[6]更具優(yōu)勢。然而,該算法的收斂速度緩慢,陷入局部最優(yōu)解難以跳出始終都是困擾著蟻群算法效率的一大問題[7]。

針對上述問題,相關(guān)學者提出了不同的解決方案[8-9]。針對收斂速度問題,文獻[10]在每個路口加入了東南西北4個指針,從而使蟻群在路口時能夠優(yōu)先選擇指向終點的路徑來提高蟻群算法的效率。然而,該方法所選擇的環(huán)境為真實道路環(huán)境(十字路口等),且僅涉及4個方向,因此將其用于解決機器人路徑規(guī)劃時可能造成陷入局部最優(yōu)解等問題。在文獻[11]中,作者通過利用雙向搜索的思想,首先通過A*算法初始化一條次優(yōu)路徑,加強次優(yōu)路徑上的初始信息素的值在初期給螞蟻一個引導作用防止螞蟻進行盲目搜索。然后通過改變算法的信息素更新策略提高了算法的搜索精度,但依舊無法解決搜索全局最優(yōu)解困難的問題。此外,由于A*預(yù)處理的存在,導致該方法的解集合可能更小。在文獻[12]中,作者引入自適應(yīng)信息素揮發(fā)系數(shù),使信息素揮發(fā)系數(shù)隨著迭代次數(shù)發(fā)生改變,從而加快了搜索的速度,但在搜索精度方面仍有些許的不足,如在算法前中期無法找到最優(yōu)解,那本次算法就無法獲得全局最優(yōu)解。文獻[13]在信息素更新過程中對最優(yōu)路徑進行信息素獎勵,對最差路徑進行信息素懲罰,從而提高了算法的搜索速度和收斂能力。但不足之處在于某些情況優(yōu)先選擇離終點較近的節(jié)點可能會使螞蟻走過更長的路徑到達終點,且在長的路徑上設(shè)立了信息素懲罰,在路徑搜索時會減小某些同時存在于長路徑和最短路徑上的節(jié)點被選擇的概率,會對搜索精度和收斂速度造成影響。

相關(guān)學者也提出了許多方法致力于解決算法容易陷入局部最優(yōu)解以及搜索精度不足等問題。如在在文獻[14]中,作者在啟發(fā)信息中加入了對下一可行節(jié)點到目標節(jié)點的距離,同時在信息素更新過程中,對最優(yōu)路徑進行獎勵而對最差路徑進行懲罰減少其路徑上的信息素,在路徑搜索中有著較為明顯的效果提升,但對長路徑的信息素懲罰項以及對螞蟻的死鎖處理依舊存在導致其節(jié)點選擇時容易使螞蟻錯過最短路徑。文獻[15]中,作者通過控制蟻群的種群相似度來調(diào)節(jié)解的多樣性,并對蟻群算法的信息素更新策略進行調(diào)整,有效降低了算法所獲得的最短路徑的長度。在文獻[16]中,作者通過禁忌柵格來避免路徑死鎖問題,加快了算法的搜索速度,同時采用正反方向螞蟻,讓螞蟻根據(jù)2種不同的搜索策略來進行搜索,有效地提高了算法的收斂速度和搜索精度,然而其采用的折返搜索策略,雖在一定程度上提高了搜索效率,但也增大了算法的搜索時間。在文獻[17]中,作者在蟻群的啟發(fā)函數(shù)中加入了當前節(jié)點、待選節(jié)點以及終點之間的距離關(guān)系,并采取信息素擴散方法使某個節(jié)點上的信息素向附近節(jié)點擴散,從而有效地提高了算法的搜索精度,但同時因為信息素擴散,可能會導致某些差的路徑上信息素過大,從而對算法的效率和收斂速度造成影響。文獻[18]中,作者通過修改啟發(fā)式、螞蟻轉(zhuǎn)移概率及信息素更新公式來提高算法的效率,在最短路徑和收斂速度方面都有著不錯的提升。

同時也有學者將蟻群算法與其他算法進行融合來解決其收斂速度緩慢以及搜索精度不足的問題[19]。如文獻[20]中作者將蟻群算法與螢火蟲算法進行融合用來解決車輛路徑選擇問題,作者在蟻群算法中加入信息素搖動,通過避免信息素在開放區(qū)域上停滯而逃脫局部最優(yōu)。在文獻[21]中,作者在勢場蟻群算法的基礎(chǔ)上提出了基于勢場跳轉(zhuǎn)的蟻群算法,將跳點搜索算法引入到魚群算法中,引入了勢場合力遞減系數(shù)從而減小蟻群陷入局部最優(yōu)的問題,并對勢場蟻群算法的初始信息素濃度、信息素更新策略和啟發(fā)信息做了一定的改進,使算法的搜索速度有著明顯的提升。

在其他領(lǐng)域也存在對于路徑規(guī)劃問題良好解決辦法。文獻[22]考慮到除路徑長度以外的環(huán)境因素對最優(yōu)路徑選擇所產(chǎn)生的影響,選擇的最優(yōu)路徑評價指標不止局限于長度,還包括行走需要的時間、費用以及損耗等問題,并通過實驗證明了實時環(huán)境下基于多目標的路徑選擇模型更具有實用價值。該思想同樣可應(yīng)用于機器人路徑規(guī)劃。因此,在最優(yōu)路徑長度相近的情況下,縮小平均轉(zhuǎn)角可以有效減少機器人行走所需要的時間。

通過上述分析,本文提出一種改進蟻群算法用于解決傳統(tǒng)蟻群算法收斂緩慢以及搜索精度不足等問題,其基本思想為：讓螞蟻根據(jù)編號分別從不同的起始位置出發(fā)向起點或終點進行路徑搜索,在搜索到對應(yīng)的路徑后根據(jù)新的信息素更新規(guī)則對全局信息素進行更新。

1)讓螞蟻從地圖上非起點和目標節(jié)點的可行節(jié)點出發(fā),向起點或目標節(jié)點去進行搜索,通過讓螞蟻從不同的起點出發(fā)來增加解的多樣性以獲得全局最優(yōu)解。

2)設(shè)立新的全局信息素更新規(guī)則,對每次迭代中尋找到的最優(yōu)路徑進行獎勵而不對最差路徑進行懲罰以增加走過最優(yōu)路徑的螞蟻對下一輪迭代螞蟻的引導作用。

3)提出了自適應(yīng)角度參數(shù)并將其使用在螞蟻轉(zhuǎn)移概率中以提高算法的收斂速度,并與新的信息素更新規(guī)則共同作用來降低搜索到的路徑的總旋轉(zhuǎn)角度,使機器人在路徑上的旋轉(zhuǎn)角度有所下降

最后在Matlab仿真實驗中證實了該方法是有效可行的,且尋優(yōu)效率相對其他算法要高。

1 蟻群算法概述

蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法,是由Dorigo[15]提出的一種仿生學群體智能優(yōu)化算法,其靈感來源于螞蟻在覓食過程表現(xiàn)出的群體智能行為,即在螞蟻覓食過程中,單只螞蟻的行為比較簡單,但是蟻群整體卻可以體現(xiàn)一些智能的行為。

1.1 蟻群算法轉(zhuǎn)移概率

螞蟻在覓食時會在自己走過的路徑上留下信息素,而蟻群內(nèi)的螞蟻對信息素具有感知能力,它們會沿著不同路徑中信息素濃度高的路徑行走,每只走過該路徑的螞蟻都會在路徑上留下信息素,這樣經(jīng)過一段時間后,蟻群就會沿著最短的路徑到達食物源。蟻群算法的轉(zhuǎn)移概率公式為：

(1)

式中：k為當前螞蟻的編號;α是信息素啟發(fā)式因子,代表信息素濃度對轉(zhuǎn)移概率的影響。α的值越大,螞蟻就更傾向于選擇其他螞蟻選擇過的路徑,搜索的隨機性減弱,同時降低了解的多樣性,扼殺了一些地圖中找到全局最優(yōu)解的概率。α越小,蟻群的搜索范圍也就越小,容易陷入局部最優(yōu)。τij為i、j路徑上的信息素濃度。

信息素濃度β為期望啟發(fā)因子使算法成為正反饋搜索,該值過大,容易導致螞蟻選擇局部最優(yōu)路徑,雖然收斂速度加快,但無法獲得全局最優(yōu)路徑。η為啟發(fā)函數(shù),其值為i、j兩點之間距離的倒數(shù),啟發(fā)函數(shù)的表達式為：

(2)

1.2 信息素的揮發(fā)

蟻群在某個節(jié)點根據(jù)其遷移概率選擇下一個需要選擇的節(jié)點,并在走過的路徑上留下信息素。為了防止隨著迭代次數(shù)增加,路徑上的信息素濃度過多,遮蓋掉路徑上的啟發(fā)信息,需要在迭代過程中對路徑上的信息素進行一定的更新,更新策略為：

τij=(1-ρ)·τij+ρ·Δτij(t)

(3)

式中：ρ是信息素揮發(fā)系數(shù),(1-ρ)是信息素的殘留系數(shù),如果ρ值過小,會導致路徑上信息素殘留過多,無法有效區(qū)別最短路徑和較長路徑之間的差距,如果該值過大,在無效路徑被排除的同時有可能將有效路徑上的信息素也大幅度地消除,增加了算法所需要的時間。Δτ是該條路徑上信息素的增量,其值為：

(4)

式中Q為蟻群算法的信息素強度系數(shù)。

2 基于角度參數(shù)的雙向蟻群算法

蟻群算法存在著容易陷入局部最優(yōu)解、迭代速度慢以及搜索不到最優(yōu)解等一系列問題,同時在解決靜態(tài)環(huán)境的機器人路徑規(guī)劃中并沒有考慮到機器人轉(zhuǎn)動的問題。因此,本文在蟻群算法的基礎(chǔ)上提出改進算法用于解決機器人路徑規(guī)劃的問題。本文算法將蟻群的出發(fā)位置進行改變以增大螞蟻的搜索空間來解決蟻群算法初期搜索盲目以及搜索精度不足等問題,使算法在地圖中獲取更加多樣化的解集合,提高了獲得全局最優(yōu)解的概率。同時對蟻群的信息素更新規(guī)則進行了改進,增加走過較短路徑的螞蟻的信息素對下輪迭代的作用以解決蟻群算法容易陷入局部最優(yōu)解無法跳出。提出了角度參數(shù)并將其加入到螞蟻轉(zhuǎn)移概率中,使其能夠在蟻群算法的尋路過程中通過角度參數(shù)對螞蟻起到引導作用,讓螞蟻在分叉路口能夠更容易的找到距離目標節(jié)點較近的路徑提高搜索精度,同時能夠減少機器人在路徑規(guī)劃中轉(zhuǎn)過的角度總和,從而減小機器人在轉(zhuǎn)彎時所花費的時間。算法偽代碼如表1所示,算法流程圖如圖1所示。

圖1 柵格地圖Fig.1 Raster map

表1 基于角度參數(shù)的雙向蟻群算法偽代碼Table 1 Pseudocode of bidirectional ant colony algorithm based on angle parameters

表2 信息素獎勵系數(shù)算法性能影響Table 2 Pheromone reward coefficient algorithm performance impact

2.1 雙向蟻群算法

傳統(tǒng)的蟻群算法由于每次進行尋路的螞蟻都是從固定的起點向終點進行搜索,會導致在算法初期螞蟻的搜索比較盲目。且在算法的初期,螞蟻總是在起點附近進行尋找,而距離起點較遠的節(jié)點卻很少有螞蟻到達,這種情況導致蟻群算法解的多樣性較差,且降低了蟻群算法的效率。

文獻[11]中采用類似的思想來改進螞蟻的起始位置,但與本文不同的是,文獻[11]將螞蟻按照編號不同分別放在起點/終點上,再讓其向終點/起點進行路徑搜索。雖然收斂速度有所降低,但在某些地圖中,該算法仍容易使蟻群陷入局部最優(yōu)而導致其無法獲取全局最優(yōu)解。

針對傳統(tǒng)蟻群算法搜索精度不足的問題,本文提出的改進算法對螞蟻的起始位置進行改進,首先將之前的起點和終點設(shè)置為目標點1和目標點2,再將螞蟻放在柵格地圖中的一系列節(jié)點所組成的起點集合上,使螞蟻在起點集合中的不同節(jié)點上分別向目標點1或目標點2進行搜索。因此,起始位置的改進不僅增加解的多樣性以提高找到最優(yōu)解的概率,而且還能使每只螞蟻只搜索半張地圖就可以搜索到自己對應(yīng)的“目的地”,從而縮短蟻群算法的整體時間。

起點集合的選擇依據(jù)如圖1所示,在該柵格地圖中,機器人若想從起點到達終點,其可行路線只有包含節(jié)點2的A路線和包含節(jié)點1的B路線,即不存在一條從起點到終點的路徑能夠既不包括節(jié)點1,也不包括和節(jié)點1位于同一行的節(jié)點2。同理,大規(guī)模的地圖上,也不會出現(xiàn)一條從起點到終點的路徑能夠不包含起點到終點間任意一行或一列中的所有節(jié)點。因此在算法中我們只需要將一行或者一列的所有可行節(jié)點加入一個集合中,并讓螞蟻從該集合中的點出發(fā)向著自己所屬的目標節(jié)點去尋路,就可以在一次迭代中尋找到從多個起始節(jié)點出發(fā)的路徑,讓螞蟻能在迭代初期就走過一些在蟻群算法中不被考慮的節(jié)點,增加解的多樣性,從而提高算法的搜索精度和搜索效率。

基于上述起點選擇理論,本文所使用的獲得起點集合的方法為：對該柵格地圖的行和列進行遍歷,選擇行或列中可行節(jié)點最少的一行或一列,將其加入初始節(jié)點集合中,在算法的過程中,每只螞蟻根據(jù)自己的編號在起點集合中尋找自己所屬的起點,并根據(jù)編號尋找自己對應(yīng)目的地是初始起點還是初始終點。

如圖2所示,在進行遍歷之后,發(fā)現(xiàn)該列是地圖中所存在的可行節(jié)點最少的一列,因此將該列中的可行節(jié)點作為螞蟻的初始節(jié)點結(jié)合,開始尋路時,將2只螞蟻作為螞蟻1和螞蟻2放在某一相同起點并開始向各自對應(yīng)的終點進行路徑規(guī)劃。

圖2 起點集合選擇及螞蟻行走路線Fig.2 Starting point set selection and ant walking route

算法將蟻群需要搜索的地圖分為兩部分,每只螞蟻只需要在各自的搜索范圍進行搜索。因此,地圖兩側(cè)的信息素互不干涉,每只螞蟻只需要維護自己對應(yīng)搜索范圍的信息素矩陣即可。該起點位置改進優(yōu)勢如下：

1)將原本較大的地圖分割為2部分較小的地圖,使螞蟻能夠更容易搜索到最優(yōu)解;

2)螞蟻能夠在不同的起點去開始路徑搜索,搜索到終點的螞蟻有權(quán)利在自己走過的路徑上更新信息素,使得蟻群有全局信息素改變,產(chǎn)生了信息素之間的交流;

3)將地圖分為2部分后,各自所持有的信息素相互獨立,可以將2部分進行并行計算,相較于傳統(tǒng)蟻群算法更加節(jié)省時間;

4)讓螞蟻從不同的起點開始進行尋找,增大了解的多樣性,提高了獲得最優(yōu)解的概率。

2.2 信息素更新策略的改進

在傳統(tǒng)蟻群算法中,信息素的更新策略為只要走到終點的螞蟻都可以進行信息素更新,并沒有體現(xiàn)出走過最短路徑的螞蟻在信息素更新上的優(yōu)勢。因此,本文對信息素更新策略進行了改進,在本次迭代的最短路徑上再進行一次信息素更新,以強化最短路徑上的信息素以對下一輪迭代的螞蟻產(chǎn)生影響。

在本文中,向目標節(jié)點1和目標節(jié)點2進行尋路的螞蟻分別持有各自的信息素矩陣,并且在本次迭代中所求得的全局最優(yōu)解的2只螞蟻未必來源于同一組。因此,本文采取的信息素更新策略為：在本次迭代結(jié)束后,先讓所有到達自己所屬的目標節(jié)點的螞蟻根據(jù)所走路徑更新信息素,再將從同一起點出發(fā)的螞蟻所獲得的路徑進行拼接,求出本次迭代中所有螞蟻所走過的最短路徑,并在這些走過最短路徑螞蟻所走過的路徑上再進行一次信息素更新,其更新原則：

τij=τij+Δτij(t),i,j∈Lmin

(5)

Δτ(t)=ε*Q*(Lmax-Lmin)/Lmin

(6)

式中：ε為信息素獎勵系數(shù)Lmax為本次迭代所獲得的最大距離,Lmin是本次迭代獲得的最短距離;而此信息素更新的值相對比局部信息素更新的差值并不是很大,因此并未在當前迭代次數(shù)的最優(yōu)路徑上增加過多信息素以對后來迭代次數(shù)的螞蟻尋路造成決定性的作用,同時也可以在路徑上產(chǎn)生一定的信息素增量以給后來的螞蟻一個引導作用,且隨著迭代次數(shù)的增加,該增量的值逐漸趨于穩(wěn)定,不會在后期產(chǎn)生最短路徑波動等問題。

在上述信息素更新策略中,不采用信息素揮發(fā)系數(shù),因為本策略的目的為在地圖上對本次迭代所尋找到的全局最優(yōu)路徑上的信息素給予一定的獎勵,如果采取信息素揮發(fā)系數(shù)對信息素進行處理,則該路徑上的信息素濃度相對之前就有所減少,起不到對螞蟻尋優(yōu)過程的指引效果。同時在本文的信息素更新策略中,不對走過最長路徑的螞蟻所走過的路徑增加懲罰項,因為一旦在初期對其最長路徑進行懲罰,就有可能影響獲取全局最優(yōu)路徑的概率,從而對算法的效率產(chǎn)生影響。

2.3 融合角度參數(shù)的螞蟻轉(zhuǎn)移概率

為解決蟻群算法的迭代收斂緩慢以及最優(yōu)解初次出現(xiàn)的迭代次數(shù)比較大等問題,本文提出了方向參數(shù)并將其加入到螞蟻轉(zhuǎn)移概率中。在地圖中,最容易表示方向的參數(shù)就是角度。在機器人尋路過程中,當有多個可行節(jié)點供選擇時,優(yōu)先選擇與終點更加相近的目標節(jié)點,可以使機器人走過更短的路徑來到達終點位置。

在機器人的路徑規(guī)劃中,因為機器人的自身問題導致其轉(zhuǎn)彎也需要時間,因此,本文提出的角度參數(shù)可以在優(yōu)先考慮最短距離的同時讓機器人走過更小的轉(zhuǎn)角走到終點,可以更有效地減少機器人尋路所需要的時間。

如圖3所示,螞蟻在到達某個節(jié)點后,在選擇下一個節(jié)點時,根據(jù)其算法中使用的輪盤賭規(guī)則,其節(jié)點所對應(yīng)的概率值越大,則螞蟻選擇該節(jié)點的可能性也就越大。同時螞蟻在當前位置可以沿著①②③④繼續(xù)尋找下一節(jié)點,此時如果使用蟻群算法,則按照輪盤賭的規(guī)則,螞蟻可能選擇路徑①,則螞蟻需要在當前位置轉(zhuǎn)彎135°并在路徑①上留下信息素,在下一輪迭代中該信息素會繼續(xù)吸引螞蟻通過該路徑,從而讓螞蟻大概率走過該角度到達終點,而在機器人沿著該路徑移動時,在距離相同的條件下,該角度會對機器人的效率造成較大的影響。但在本文算法中采用角度參數(shù)來影響螞蟻的轉(zhuǎn)移概率,即選擇和當前節(jié)點的連線與當前節(jié)點和該螞蟻目標節(jié)點之間的夾角更小的路徑去走,這樣可以使路徑上的總體轉(zhuǎn)彎角度減小。即便當前迭代中,螞蟻選擇了路徑①并到達了終點,由于信息素更新規(guī)則中的獎勵機制使得其除非本次尋找到的是最優(yōu)路徑,否則對下一輪迭代螞蟻不會造成太大影響。因此,本文提出了角度參數(shù),其具體公式為：

圖3 角度參數(shù)Fig.3 Angle parameters

(7)

式中a為固定常數(shù),g為自適應(yīng)參數(shù),根據(jù)迭代次數(shù)的不同自適應(yīng)的發(fā)生改變,θ為待選擇節(jié)點和當前節(jié)點的連線與當前節(jié)點和該螞蟻目標節(jié)點之間的夾角。

由式(1)加入式(7)中的角度參數(shù)獲得新的螞蟻轉(zhuǎn)移概率公式為：

(8)

3 仿真實驗與分析

3.1 信息素獎勵系數(shù)的選擇

本文設(shè)定在不加入角度參數(shù)的情況下對信息素獎勵系數(shù)進行選擇,在ε值不同的情況下進行多組對比實驗,實驗結(jié)果如下。

在對ε值進行分析時,當取值為[0.01,0.02]時,算法獲得的最短路徑長度隨著該值的增大而減小,在取值大于0.02后,算法所獲得的最短路徑長度隨著該值的增大而增大,因此,本文將算法的信息素獎勵系數(shù)設(shè)定為0.02,即通過該值對路徑上增加的信息素濃度不會對螞蟻產(chǎn)生決定性的影響,卻依舊可以在一定程度上引導螞蟻選擇該較優(yōu)的路徑。

3.2 角度參數(shù)的選擇

本文在設(shè)定g=1的情況下對a值進行選擇,因該參數(shù)為固定參數(shù),不會在算法進行過程中隨著迭代次數(shù)的增加而進行改變,因此,該值的選擇在一定程度上決定了該角度公式對螞蟻方向引導的效率。在開放節(jié)點較多的地圖上進行機器人路徑規(guī)劃時,優(yōu)先選擇偏向目標節(jié)點的路徑大概率會使機器人走過更短的距離到達目標節(jié)點,因此,需要通過該參數(shù)來區(qū)分出“與目標節(jié)點所相近的節(jié)點”和那些“偏離目標節(jié)點的節(jié)點”。

而在實際應(yīng)用中,通常認為在選擇與當前位置和目標節(jié)點連線夾角小于90°的路徑會使機器人更快到達目標節(jié)點,因此應(yīng)該明確區(qū)分出夾角90°以上的路徑和夾角為90°以下的路徑。

經(jīng)過一系列Matlab仿真實驗的對比,結(jié)果如表3及圖4所示,在a為1.5時算法的效果最佳,因為當a為1.5的時候剛好能區(qū)分出該路徑與目標節(jié)點和當前節(jié)點的連線夾角是否小于90°,當該角度大于90°時,該參數(shù)的值小于1,在參數(shù)g的作用下,使其能夠有效削弱在那些走過與目標節(jié)點相反的路徑并經(jīng)過較長路徑依然到達終點的螞蟻在其走過路徑上留下的信息素對剩余迭代螞蟻在路徑選擇上所造成的影響,而當該角度小于90°時,在真實情況下,走過該條路徑的螞蟻往往能通過更短的路徑到達終點。

圖4 角度參數(shù)中常數(shù)a對算法性能影響Fig.4 The influence of the constant a in the angle parameter on the algorithm performance

表3 角度參數(shù)中常數(shù)a對算法性能影響Table 3 The influence of the constant a in the angle parameter on the algorithm performance

而參數(shù)g是根據(jù)迭代的過程發(fā)生改變的,因此該參數(shù)可以對算法前期解的多樣性以及算法后期解的收斂性產(chǎn)生較大的影響。

在設(shè)定a=1.5的情況下,g值的改變對算法最優(yōu)解初次出現(xiàn)及收斂速度的影響如表4及圖5所示。

圖5 角度參數(shù)中參數(shù)g對算法性能的影響Fig.5 The influence of the parameter g in the angle parameter on the performance of the algorithm

表4 角度參數(shù)中參數(shù)g對算法性能的影響Table 4 The influence of the parameter g in the angle parameter on the performance of the algorithm

經(jīng)過仿真實驗的效果對比,最終確定算法初期時將該參數(shù)g的取值設(shè)置為0來增加解的多樣性,在算法進行到中期時將該值設(shè)置為1,來加強方向的引導效果,又不會對蟻群對信息素的敏感性造成過多影響,到算法后期,將該值設(shè)置為4來加快算法的收斂效果。

如圖6所示,在初始條件下,每條路徑上初始信息素相等,螞蟻在角度參數(shù)的作用下會優(yōu)先選擇與終點角度相差較小的節(jié)點。而某些地圖中,這樣的節(jié)點并不會使的螞蟻尋找到更好的路徑,反而會引導螞蟻走到一條死路或走過很長的路徑到達目標節(jié)點,這使得螞蟻如果從一開始就選擇該路徑并進行尋找,繼而到達目標節(jié)點并在該路徑下留下信息素,就會造成剩余迭代次數(shù)的所有螞蟻都會被這條較長路徑上的信息素影響,無法獲得全局最優(yōu)解。

圖6 角度參數(shù)可能會產(chǎn)生的影響Fig.6 The possible effect of the angle parameter

在圖6所示地圖中,第一輪迭代的螞蟻在角度參數(shù)的作用下,會優(yōu)先選擇走到當前節(jié)點,繼而走到節(jié)點1,然后通過一條較長的路徑尋到終點并在路徑上留下信息素。這樣不僅沒有提升蟻群搜索的效果,反而降低了搜索的效率,甚至可能在算法初期讓螞蟻走到死路。因此,在算法初期應(yīng)降低該參數(shù)的影響,讓螞蟻能夠處于不受其他條件限制的情況下在柵格地圖中自由尋找路徑,增加了所獲得解的多樣性,繼而增加在算法前期獲得最優(yōu)解的概率。在算法進入中期之后,增大該參數(shù)以加強角度的引導,但不能將該值設(shè)置的過大,以免對螞蟻對信息素的敏感性造成影響,從而導致角度的引導性大于信息素的引導性,使算法收斂速度降低的同時影響螞蟻對最優(yōu)解的尋找。而在算法后期,則需加大該值以加快算法的收斂速度,若此時在a值相同的情況下該指數(shù)不夠大,則會對算法的效率產(chǎn)生影響;若該值過大則容易造成信息素和角度參數(shù)相互影響,使算法的迭代收斂曲線出現(xiàn)波動且持續(xù)不收斂的情況。

3.3 角度算子有效性

在選定了角度公式的參數(shù)后,為了驗證本文提出的角度參數(shù)的有效性,在Matlab仿真環(huán)境中且參數(shù)相同的情況下做了對比試驗。

如圖7所示,盡管2種方法均能在多幅柵格地圖內(nèi)找到最小值,但多次試驗中,加入角度參數(shù)的雙向蟻群算法所獲得的平均路徑長度要更短,且加入角度參數(shù)的雙向蟻群算法的收斂速度相比于未使用角度參數(shù)的雙向蟻群算法有著較為顯著的提升。因此證明該角度參數(shù)的提出及引入是合理且有效的。

圖7 角度參數(shù)效果對比Fig.7 Comparison of the effect of angle parameters

3.4 算法性能仿真實驗

為驗證本文改進蟻群算法的有效性,設(shè)備條件為：Windows10操作系統(tǒng),Intel(R) Core(TM) i7-10700F處理器,8 GB內(nèi)存,在MATLAB R2018仿真環(huán)境中分別對蟻群算法,本文算法和文獻[11]、文獻[12]及文獻[14]中的算法在參數(shù)相同的情況下,在20×20的地圖中和30×30的地圖中進行了對比,其中參數(shù)設(shè)定如表5所示。

表5 對比實驗參數(shù)設(shè)置Table 5 Comparison of experimental parameter settings

算法結(jié)果分析如下,其中黑色節(jié)點為障礙物節(jié)點,白色節(jié)點為可行節(jié)點,起始坐標均為(1,1)。

從圖8、圖9及表6中可以看出,在20×20的柵格地圖中,本文算法雖與傳統(tǒng)蟻群算法轉(zhuǎn)過的平均角度相同,但本文算法求得的最優(yōu)路徑相對蟻群算法卻有著較大的改善;本文算法與文獻[12]方法相比,在搜索到更短的最短路徑的同時,迭代收斂速度也有著明顯的增加,轉(zhuǎn)過的平均角度也比文獻[12]方法轉(zhuǎn)過的平均角度要低;在本文算法與文獻[11]中的算法進行對比時,雖然二者均獲得到了相同的全局最優(yōu)解,但本文算法的平均路徑長度、平均轉(zhuǎn)角要遠小于文獻[11],且收斂速度比文獻[11]更快;一系列實驗結(jié)果證明該改進在小規(guī)模地圖中是有效的,算法在加入角度參數(shù)等改進后,其迭代速度有著明顯的提升,且能獲得更好的全局最優(yōu)解,說明其容易陷入局部最優(yōu)解的問題也得到了改善,同時平均轉(zhuǎn)動角度也有所降低,使得機器人路徑規(guī)劃的總體效率提高。

圖8 20×20地圖5種算法機器人運動軌跡Fig.8 Robot movement trajectory with five algorithms on 20×20 map

圖9 20×20地圖5種算法機器人運動收斂趨勢對比Fig.9 Comparison of robot movement convergence trends of five algorithms on 20×20 maps

表6 20×20地圖6種算法對比實驗結(jié)果Table 6 Comparison experiment results of six algorithms on 20×20 map

而在與文獻[14]中的算法進行對比時,文獻[14]中的算法由于在信息素和啟發(fā)式因子中過多的考慮了待選擇節(jié)點和目標節(jié)點之間的距離,導致其在出現(xiàn)“選擇距離目標節(jié)點較近的節(jié)點會使螞蟻經(jīng)過更長的路線到達終點”這類陷阱時,算法的效果較差。而本文算法由于在初期讓螞蟻在不同的起點較為自由的搜索,從而不會出現(xiàn)讓其遷移概率過分依賴于與目標節(jié)點之間的距離關(guān)系這一現(xiàn)象,避免了這種問題的出現(xiàn)。同時,本文方法的旋轉(zhuǎn)角度要比文獻[14]中的旋轉(zhuǎn)角度更低,在機器人移動時會更節(jié)省時間,提高了機器人移動的效率。在與文獻[18]中的算法進行對比時,其收斂速度相對較快,但平均路徑長度相對較差,且平均旋轉(zhuǎn)角度相對較多,其原因可能是算法在初期即有方向參數(shù)的參與,導致算法在初期就會選擇與終點方向夾角小的節(jié)點行走,而導致本文3.2中提到的“繞路”現(xiàn)象的發(fā)生而造成路徑長度增加且轉(zhuǎn)角增多。而本文在對提出的角度參數(shù)進行處理時,通過減小其前期對算法的影響,有效的避免了該現(xiàn)象的發(fā)生。

如圖10、圖11和表7所示,在30×30的地圖中,本文算法在參數(shù)相同的情況下,相較于蟻群算法、文獻[11]和文獻[12]中的蟻群算法搜索到了更短的全局最短路徑,且平均路徑及旋轉(zhuǎn)角度相較于其他2種算法也更小;同時由本文算法中所獲得的最短路徑和平均路徑的差值很小可以看出,該方法所獲得的解波動不大,從而體現(xiàn)了該方法具有一定的穩(wěn)定性;且該方法的平均收斂速度相交于蟻群算法也提高了許多。在與文獻[14]進行對比時,雖然本文算法與該文獻算法都找到了相同的最小路徑,但因文獻[14]對通過較長路徑的螞蟻所走過的路線設(shè)置了懲罰項,導致如果該條路徑同時出現(xiàn)在最長路線和最短路線上,其路徑上的信息素并沒有實質(zhì)性的獎勵,反而可能會減小,從而未能保證每次都能求出最優(yōu)路線。而本文算法僅對最優(yōu)路線進行獎勵而不對最差路線進行懲罰,使解的多樣性得到擴充的同時,減小因懲罰項導致錯失最優(yōu)路徑的概率,從而使本文算法的平均路徑長度要優(yōu)于文獻[14]。在與文獻[18]進行比對時,其結(jié)果與20×20類似,其角度參數(shù)在初期影響較大而造成一條非最優(yōu)路徑上的信息素過高,導致其結(jié)果較差。而本文算法合理的調(diào)整了角度參數(shù)加入的時機,使算法能尋找到更短的最優(yōu)路徑。且本文算法機器人平均轉(zhuǎn)過的角度相對文獻[11-12,14,18]中的要更小,說明該算法能夠?qū)C器人路徑尋優(yōu)所走過的角度進行改善,從而提高機器人路徑規(guī)劃的效率。

圖10 30×30地圖5種算法機器人運動軌跡Fig.10 Robot movement trajectory on 30×30 map

圖11 30×30地圖中5種算法收斂趨勢對比Fig.11 Comparison of convergence trends of five algorithms in 30×30 map

表7 30×30地圖6種算法對比實驗結(jié)果Table 7 Comparison experiment results of six algorithms on 30×30 map

4 結(jié)論

1)在蟻群算法的基礎(chǔ)上通過將螞蟻起始位置以及目標位置進行改變并對最短路徑上的信息素進行獎勵,可以有效提高算法對最優(yōu)解的搜索。

2)通過加入角度參數(shù),對螞蟻搜索的過程進行引導,信息素濃度影響螞蟻對下一節(jié)點的選擇概率,可以有效解決算法的收斂速度問題。

3)所提出的算法解決了蟻群算法在機器人路徑規(guī)劃中收斂速度慢、容易陷入局部最優(yōu)解以及精度不足等問題,相比于其他幾種改進蟻群算法在機器人路徑規(guī)劃中擁有更好的尋優(yōu)效果和收斂速度以及更小的轉(zhuǎn)動角度。

如何有效解決動態(tài)路徑規(guī)劃問題將成為今后研究的主要工作。