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

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

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

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

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

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

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

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

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

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

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

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

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

1 蟻群算法概述

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

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

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

(1)

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

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

(2)

1.2 信息素的揮發(fā)

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

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

(3)

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

(4)

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

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

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

圖1 柵格地圖Fig.1 Raster map

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

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

2.1 雙向蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

2.2 信息素更新策略的改進(jìn)

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

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

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

(5)

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

(6)

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

在上述信息素更新策略中,不采用信息素?fù)]發(fā)系數(shù),因?yàn)楸静呗缘哪康臑樵诘貓D上對(duì)本次迭代所尋找到的全局最優(yōu)路徑上的信息素給予一定的獎(jiǎng)勵(lì),如果采取信息素?fù)]發(fā)系數(shù)對(duì)信息素進(jìn)行處理,則該路徑上的信息素濃度相對(duì)之前就有所減少,起不到對(duì)螞蟻尋優(yōu)過程的指引效果。同時(shí)在本文的信息素更新策略中,不對(duì)走過最長路徑的螞蟻所走過的路徑增加懲罰項(xiàng),因?yàn)橐坏┰诔跗趯?duì)其最長路徑進(jìn)行懲罰,就有可能影響獲取全局最優(yōu)路徑的概率,從而對(duì)算法的效率產(chǎn)生影響。

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

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

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

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

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

(7)

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

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

(8)

3 仿真實(shí)驗(yàn)與分析

3.1 信息素獎(jiǎng)勵(lì)系數(shù)的選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 角度算子有效性

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

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

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

3.4 算法性能仿真實(shí)驗(yàn)

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

表5 對(duì)比實(shí)驗(yàn)參數(shù)設(shè)置Table 5 Comparison of experimental parameter settings

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

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

圖8 20×20地圖5種算法機(jī)器人運(yùn)動(dòng)軌跡Fig.8 Robot movement trajectory with five algorithms on 20×20 map

圖9 20×20地圖5種算法機(jī)器人運(yùn)動(dòng)收斂趨勢對(duì)比Fig.9 Comparison of robot movement convergence trends of five algorithms on 20×20 maps

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

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

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

圖10 30×30地圖5種算法機(jī)器人運(yùn)動(dòng)軌跡Fig.10 Robot movement trajectory on 30×30 map

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

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

4 結(jié)論

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

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

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

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