陳旭東,楊光永,徐天奇,樊康生

(云南民族大學(xué)電氣信息工程學(xué)院,昆明 650000)

0 引言

機器人的路徑規(guī)劃問題在機器人導(dǎo)航領(lǐng)域的研究一直都是熱點,而路徑規(guī)劃是指機器人根據(jù)地圖信息尋找起點到終點的一條無碰撞且代價最小的路徑。

針對路徑規(guī)劃問題,許多學(xué)者提出了眾多智能算法應(yīng)用在路徑規(guī)劃研究中,如蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、粒子群算法等智能算法。楊北辰等[1]針對傳統(tǒng)蟻群算法存在收斂速度慢、容易陷入局部最優(yōu)等問題將一種自適應(yīng)歸檔更新方法應(yīng)用在蟻群算法中,根據(jù)路徑信息建立了多目標(biāo)性能評估模型,對路徑進行多指標(biāo)優(yōu)化,提高算法的收斂速度。張毅等[2]將初始化成功的無碰撞路徑轉(zhuǎn)化為一連串的柵格地圖中柵格序號,再將路徑序號轉(zhuǎn)化成路徑進行優(yōu)化,但是該算法中參數(shù)選擇人需憑借經(jīng)驗選取,且對環(huán)境的依賴性強。魏冠偉等[3]利用人工神經(jīng)網(wǎng)絡(luò)優(yōu)化路徑,但是由于人工神經(jīng)網(wǎng)絡(luò)的局限性,該方法存在收斂速度慢、全局搜索能力差、易陷入局部最優(yōu)等缺點。

而對于粒子群算法(particle swarm optimization)在路徑規(guī)劃中的應(yīng)用,其具有收斂速度快,模型簡單,待調(diào)參數(shù)少等特點。但是算法在后期由于種群多樣性減少容易陷入局部最優(yōu)值,使得優(yōu)化效果并不理想。

國內(nèi)外許多學(xué)者為提升粒子群算法的性能提出了許多改進方法。LIU等[4]在粒子群算法尋優(yōu)過程中引入非線性慣性權(quán)重調(diào)整提高了算法性能?；ㄚS昊等[5]通過在粒子群算法尋優(yōu)過程中同步調(diào)整學(xué)習(xí)因子與慣性權(quán)重,提高了算法收斂速度以及收斂精度,并且為增強算法的全局尋優(yōu)能力引入了變異機制擴大粒子搜索空間。朱任等[6]借鑒了小生境思想,基于粒子群算法基礎(chǔ)上提出利用順序聚類算法將不同的粒子劃分到不同的小生境,并根據(jù)小生境的迭代數(shù)制定不同的搜索策略一次提升算法總體性能。楊妹蘭等[7]采用比粒子自身適應(yīng)值更好的鄰近粒子為學(xué)習(xí)對象,并且分兩個階段用不同更新速度公式,提高了粒子間的信息交流,同時平衡了算法的局部開發(fā)性能與全局尋優(yōu)能力。廖瑋霖等[8]利用三黑洞系統(tǒng)捕獲策略以及多維隨機干擾策略,使算法提高了局部搜索能力同時還兼顧了全局開拓能力,并且通過協(xié)調(diào)因子從全局尋優(yōu)轉(zhuǎn)變維向局部搜索,進而提高收斂速度。

上述各改進方法均綜合提高了粒子群算法的性能,然而目前改進的粒子群算法大多著重于平衡算法的收斂精度和收斂速度。雖具有一定的改善效果,但是由于兩者的矛盾性,提升效果依舊具有局限性。針對所述問題,本文提出一種多策略融合改進粒子群算法應(yīng)用在路徑規(guī)劃中,首先建立機器人路徑規(guī)劃所需的柵格地圖模型,并對傳統(tǒng)的粒子群算法作進一步的改進,利用中垂線算法的收斂策略加快算法的收斂速度;以最優(yōu)粒子爆炸策略避免陷入局部最優(yōu)解;采用自適應(yīng)慣性權(quán)重更新方法進一步提升算法的性能;最后將全局最優(yōu)解繼續(xù)進行局部搜索,提高全局最優(yōu)解適應(yīng)度值。

1 多策略融合粒子群算法

1.1 粒子群算法

粒子群算法的核心是利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產(chǎn)生問題的最優(yōu)解。其數(shù)學(xué)模型為:

(1)

(2)

1.2 多策略融合粒子群算法

1.2.1 中垂線算法

中垂線算法的核心思想是:任意線段的中垂線上任意一點到該線段的兩端點的距離相等。示意圖如圖1所示,假設(shè)在一個足夠小的區(qū)域內(nèi)(矩形區(qū)域)存在一個最優(yōu)點P和兩個隨機點M和N,連接MN并作線段MN的中垂線L。由圖1可知|PM|<|PN|,因中垂線L上任意點到M點與N點的距離相等,則P點必定位于L左側(cè)M點的區(qū)域。在中垂線算法中,以最優(yōu)點到該點的距離作為適應(yīng)度,即在圖1中M點適應(yīng)度比N點適應(yīng)度更好。

圖1 算法原理圖

以圖1為例,中垂線算法的收斂過程為:判定線段|PM|是否小于|PN|,若小于,則判定最優(yōu)值P必存在于矩形左側(cè)網(wǎng)格區(qū)域;舍棄原N點,在矩形左側(cè)網(wǎng)格區(qū)域隨機生成N′點;作M和N′構(gòu)成線段的中垂線L′,此時可知,N′點的適應(yīng)度必定比M點的適應(yīng)度更佳,由此可知最優(yōu)值所在區(qū)域必存在于L′右側(cè)區(qū)域(圖1中陰影網(wǎng)格區(qū)域)。重復(fù)以上步驟可不斷縮小最優(yōu)點P的所處區(qū)域。

1.2.2 融合中垂線算法的粒子變化策略

若在圖1中右側(cè)區(qū)域隨機加入粒子G,如圖2所示。采用傳統(tǒng)粒子群更新策略必然需要經(jīng)多次更新才能使N點、G點的位置到達中垂線左側(cè)區(qū)域。

圖2 粒子變化原理圖

針對傳統(tǒng)粒子群更新速度慢的問題首先將粒子N和G的位置先移動到N′和G′的位置,由于傳統(tǒng)粒子群的更新策略會使粒子回到中垂線左側(cè)區(qū)域,因此本文采用改進粒子群更新策略更新粒子速度和位置。

粒子移動的實現(xiàn)方式為:首先判斷粒子是否存在于最優(yōu)點所在區(qū)域,設(shè):

(3)

式中:d表示粒子維度,假設(shè)某粒子存在于最優(yōu)點所在區(qū)域,則x滿足:

(4)

式中:j表示x的第j維,

(5)

為減小算法的時間復(fù)雜度和增強算法全局尋優(yōu)能力,判定僅需任意兩維元素滿足式(3)則位于中垂線左側(cè)區(qū)域。

若該粒子位于中垂線右側(cè)區(qū)域,則N點更新公式為:

(6)

(7)

為驗證中垂線算法的性能,本文選取Rosenbrock函數(shù)作為實驗函數(shù),驗證其全局尋優(yōu)能力。圖3和圖4為融合中垂線算法的改進PSO算法尋找Rosenbrock函數(shù)最小值時粒子的變化。公式為:

(8)

圖3 PSO算法粒子變化圖

從圖3和圖4的粒子位置變化對比可看出,改進PSO算法能夠更快收斂到最優(yōu)值,而傳統(tǒng)粒子群算法粒子位置變化太過分散。因此驗證了中垂線算法具有很好的收斂能力。

1.2.3 最優(yōu)粒子爆炸策略

在傳統(tǒng)粒子群算法中,全局最佳粒子Gbest按常規(guī)更新公式更新時,下一代種群的粒子位置一般會比前一代的粒子位置更差,最優(yōu)粒子的作用并沒有顯現(xiàn)出來。因此本文在最優(yōu)粒子Gbest附近生成一定數(shù)量的爆炸粒子,生成方式為:

(9)

由式(9)生成的第n個爆炸粒子exn的j維變量,這些粒子生成于最優(yōu)粒子的周圍。

采用生成爆炸粒子的策略是為了算法更好的跳出局部最優(yōu),該策略依舊選取Rosenbrock函數(shù)作為實驗函數(shù),驗證其該策略的可行性。由圖5可知,傳統(tǒng)PSO算法會陷入局部最優(yōu)值,而采用最優(yōu)爆炸粒子策略能夠使算法更好的跳出局部最優(yōu)值。

圖5 適應(yīng)度收斂對比

1.2.4 改進粒子速度更新

利用中垂線算法改進后,若依舊利用傳統(tǒng)粒子群算法的粒子歷史位置信息反而會導(dǎo)致粒子遠離最優(yōu)點。故粒子速度更新策略變?yōu)?

(10)

由于經(jīng)過最優(yōu)粒子爆炸策略后,若種群粒子總數(shù)為m,在最佳粒子周圍生成了n個爆炸粒子,那么m-n個傳統(tǒng)粒子按照式(10)更新,新生成的爆炸粒子按照式(11)更新。

(11)

1.2.5 線性動態(tài)慣性權(quán)重調(diào)整方法

在傳統(tǒng)粒子群算法中,慣性權(quán)值是一個定值。如果取值太大雖然加快了搜索速度但是在算法后期不利于粒子后期小范圍的搜索,若取值太小,雖然增加了局部搜索能力但是則不利于算法速度會銳減。針對以上問題,本文采用線性遞減規(guī)律改變慣性權(quán)重。權(quán)重ω的變化式為:

(12)

式中:ωmax是最大權(quán)值,通常設(shè)為0.8;ωmin是最小權(quán)值,通常設(shè)為0.5;Tmax為最大迭代,t為粒子當(dāng)前迭代。引入線性動態(tài)慣性權(quán)重調(diào)整方法是為了增加算法的全局搜索能力以及局部探索能力,本文采用Rosenbrock函數(shù)作為實驗函數(shù)進行驗證。由圖6可看出引入線性動態(tài)慣性權(quán)重能夠很好的提升算法的收斂速度以及搜索精度。

1.3 多策略融合粒子群算法求解流程

根據(jù)上述所提策略并將其融合而提出的多策略融合改進粒子群算法的具體步驟為:

步驟1:隨機初始化各個參數(shù),如學(xué)習(xí)因子,初始粒子速度位置,爆炸粒子數(shù)目,種群學(xué)習(xí)率;

步驟2:通過適應(yīng)度函數(shù)計算適應(yīng)度值;

步驟3:適應(yīng)度最佳的粒子作為全局最優(yōu)點M,適應(yīng)度次優(yōu)的粒子作為N點;

步驟4:利用式(12)求出粒子慣性權(quán)重;

步驟5:利用式(9)生成爆炸粒子;

步驟6:利用式(10)和式(11)更新粒子速度;再由式(2)更新粒子位置;

步驟7:計算所有更新后粒子的適應(yīng)度值;

步驟8:更新Gbest(M點)和N點的值;

步驟9:結(jié)束條件達到則停止搜索,否則回到步驟2繼續(xù)執(zhí)行。

1.4 算法時間復(fù)雜度分析

假設(shè)粒子數(shù)為m,最大迭代次數(shù)為T,粒子維度為D,爆炸粒子數(shù)為e,粒子群算法的時間復(fù)雜度主要是粒子速度和位置更新,可知標(biāo)準粒子群算法的時間復(fù)雜度為O(mDT)。由本文算法的步驟可知,在中垂線算法策略中,粒子每更新一次,本文的粒子位置更新策略增加的時間有判斷粒子是否處于正確位置以及將粒子移動的時間都是O(mD),而確定兩個最優(yōu)粒子的位置,增加的時間為O(m),舍棄個體歷史最優(yōu)位置則減少的時間為O(m);最優(yōu)粒子爆炸策略的時間為O(eD);而線性慣性權(quán)重調(diào)整是減小了算法的運行時間,因此該策略的增加的時間為O(0),則本文算法總的時間復(fù)雜度為O(2mDT+eDT),略去低階項后可知本文算法時間復(fù)雜度比標(biāo)準粒子群算法大致相同。

2 算法性能測試

為了驗證多策略融合粒子群算法的可行性和優(yōu)越性,將本文改進后的算法(MFPSO)與均值粒子群優(yōu)化算法(MeanPSO)、線性遞減慣性權(quán)重粒子群優(yōu)化算法(LDWPSO)、基于終端交叉和轉(zhuǎn)向擾動的粒子群優(yōu)化算法(TCSPSO)以及文獻[8]的多策略融合的粒子群優(yōu)化算法(MSPSO)[8]在5個基準測試函數(shù)下進行對比實驗。設(shè)置迭代次數(shù)為1000,種群數(shù)量為80,各算法其他參數(shù)設(shè)置如表1所示,5個測試函數(shù)的取值范圍、最小值等信息如表2所示,其中F1～F3為單峰基準測試函數(shù),F4、F5為多峰基準測試函數(shù)。本文實驗平臺為:MATLAB 2022(Intel Core i5,2.11 GHz CPU and 16 GB RAM)。

表1 各算法參數(shù)設(shè)置

表2 基準測試函數(shù)

為了驗證本文算法的性能,本文使用兩組基準函數(shù)進行測試并且從收斂速度和收斂精度兩方面來對比,為了降低由于偶然性引起的實驗誤差,本文分別在5個測試函數(shù)中獨立進行50次實驗。測試函數(shù)的收斂曲線對比如圖7所示,實驗結(jié)果如表3所示。其中橫坐標(biāo)代表迭代次數(shù),縱坐標(biāo)代表適應(yīng)度的對數(shù)值。

表3 實驗數(shù)據(jù)

(a) F1測試函數(shù)收斂曲線對比 (b) F2測試函數(shù)收斂曲線對比

從圖7a～圖7e可以看出,本文算法相較于其它4種算法,在收斂速度以及收斂精度方面具有很大的提升。本文算法不僅尋優(yōu)精度明顯優(yōu)于其他5種算法,同時在算法初期由于引入了中垂線算法增加了粒子的游離速度,使得算法前期收斂速度明顯加快。并且能夠在較少的迭代次數(shù)就能達到較好的尋優(yōu)精度,這是因為在粒子速度更新階段引入了線性遞減規(guī)律慣性權(quán)重,使得算法能夠更好的平衡全局搜索能力以及局部拓展能力,具有更好的搜索范圍,而其余算法不同程度的出現(xiàn)了停滯過程,尋優(yōu)精度較低等問題。由表3可以看出,測試函數(shù)為F1～F3和F5時無論是單峰或多峰基準測試函數(shù),本文算法在獨立實驗結(jié)果的最小值和均值都是最小,而當(dāng)測試函數(shù)為F4時,最小值雖與MeanPSO、TCSPSO、MSPSO相等,但是平均值相較于其余4種算法是最低的。綜上所述,本文改進的MFPSO算法整體性能優(yōu)于其他4種改進算法。

3 多策略融合粒子群算法在路徑規(guī)劃中的應(yīng)用

3.1 全局最優(yōu)解局部搜索策略

傳統(tǒng)PSO算法的初始化策略通常為隨機策略,在算法末期,可能得到的全局最優(yōu)解并不是最優(yōu)的解,針對此問題,本文在算法末期采取把全局最優(yōu)解(最優(yōu)路徑)繼續(xù)進行局部搜索,如果新的適應(yīng)度值小于原先適應(yīng)度值,則將新路徑作為最優(yōu)路徑。效果對比圖(以20×20為例)如圖8～圖10所示。

圖8 傳統(tǒng)PSO路徑規(guī)劃

圖10 路徑長度對比

從圖8～圖10可以看出,采取全局最優(yōu)解局部搜索策略的粒子群路徑規(guī)劃能夠?qū)鹘y(tǒng)粒子群產(chǎn)生的最優(yōu)路徑繼續(xù)搜索尋優(yōu)得到更佳的規(guī)劃路徑。

3.2 適應(yīng)度函數(shù)建立

機器人路徑規(guī)劃是根據(jù)地圖信息尋找起點到終點的一條無碰撞且代價最小的路徑。其代價函數(shù)是檢驗算法優(yōu)化程度的重要指標(biāo)。本文代價函數(shù)分成兩部分,第一部分用來判斷路徑的長短,第二部分用來判斷平滑程度。路徑長度的計算公式為:

(13)

式中:fit1為相鄰點的距離的和,d表示維度。

平滑度的計算公式為:

(14)

路徑中機器人行進的角度有4種情況,分別為直線、鈍角、直角和銳角,其中直線平滑度最好,鈍角、直角次之。由于機器人行進中銳角是不允許的,所以對除直線外的另外3種情況給予懲罰,可以根據(jù)實際情況更改懲罰值大小。

fit2=1/(fit2+c)

(15)

適應(yīng)度函數(shù)的兩部分分別取一個權(quán)重值,則適應(yīng)度函數(shù)公式如下:

f=a·fit1+b·fit2

(16)

式中:a、b分別為長度因子、平滑度因子,可根據(jù)路徑長度和平滑度之間的權(quán)重選擇參數(shù)a和b。

3.3 路徑規(guī)劃問題

為進一步驗證本文提出的融合多策略改進的粒子群算法的實用性與可行性,本文采用傳統(tǒng)柵格地圖來模擬機器人的工作環(huán)境。黑色區(qū)域為障礙物,把白色區(qū)域為可行區(qū)域,其中深灰色點標(biāo)志(左下角)為機器人的起始點,淺灰色點標(biāo)志(右上角)為機器人的結(jié)束點;地圖的邊界是整個路徑規(guī)劃的最外圍區(qū)域,當(dāng)成障礙對待。

本文采用在20×20與30×30規(guī)模的簡單柵格環(huán)境和20×20與30×30規(guī)模的復(fù)雜柵格環(huán)境,將本文改進粒子群算法用于柵格地圖路徑規(guī)劃問題中,并與文獻[8]算法(MSPSO)、傳統(tǒng)粒子群算法(PSO)、麻雀搜索算法(SSA)、進行對比并記錄平均路徑長度、最優(yōu)路徑長度。本文粒子群初始參數(shù)設(shè)置為:迭代次數(shù)為500;種群數(shù)量設(shè)置為100;權(quán)重系數(shù)最大值ωmax為0.9;權(quán)重系數(shù)最小值ωmin為0.4;社會因子c2設(shè)為2。

3.3.1 簡單環(huán)境

各算法在20×20柵格地圖簡單模型的最短規(guī)劃路徑對比如圖11所示,在30×30柵格地圖簡單模型的最短規(guī)劃路徑對比如圖12所示,簡單環(huán)境的最優(yōu)路徑收斂曲線對比如圖13所示,各算法實驗數(shù)據(jù)統(tǒng)計如表4所示。

表4 簡單環(huán)境各算法路徑統(tǒng)計表

(a) MFPSO (b) MSPSO

(a) MFPSO (b) MSPSO

(a) 20×20簡單路徑收斂曲線 (b) 30×30簡單路徑收斂曲線

由圖11和圖12可得,本文算法在20×20、30×30的簡單環(huán)境下找到的最優(yōu)路徑均優(yōu)于其余3種算法;從表4可以看出在20×20柵格地圖得到最優(yōu)路徑是27.649 2,比MSPSO減少了0.806 2,并且在30×30柵格地圖下,得到的最優(yōu)路徑比MSPSO減少了2.474 3,由此可以說明MSPSO在較復(fù)雜的柵格地圖環(huán)境的搜索精度會降低;從圖13可以看出MSPSO雖然在算法初期能夠快速的收斂到最優(yōu)值,但是正在后期存在搜索能力不足,搜索精度不夠。

3.3.2 復(fù)雜環(huán)境

各算法在20×20柵格地圖復(fù)雜模型的最短規(guī)劃路徑對比如圖14所示,在30×30柵格地圖復(fù)雜模型的最短規(guī)劃路徑對比如圖15所示,復(fù)雜環(huán)境的最優(yōu)路徑收斂曲線對比如圖16所示,各算法實驗數(shù)據(jù)統(tǒng)計如表5所示。

表5 復(fù)雜環(huán)境各算法路徑統(tǒng)計表

(a) MFPSO (b) MSPSO

(a) MFPSO (b) MSPSO

由圖14和圖15最優(yōu)路徑對比圖可知,算法都能夠?qū)崿F(xiàn)到達終點且尋找到了最優(yōu)路徑的目的。但是除了MFPSO和MSPSO,其它算法路徑的波動性明顯,并且路徑會經(jīng)過障礙點,生成的路徑平滑度差、距離長、算法規(guī)劃出的路徑存在繞彎路甚至于規(guī)劃出有障礙的路徑等情況。而本文算法相對MSPSO,本文提出的改進粒子群算法在路徑長度和路徑平滑度上都優(yōu)于MSPSO,能夠迅速的找到路徑最短且不經(jīng)過障礙物的最優(yōu)路徑,且路徑平滑度也適于機器人實際運動軌跡。

由圖16最優(yōu)路徑收斂曲線反應(yīng)的情況可知由于 MFPSO能迅速收斂至最小適應(yīng)度值,這是由于通過中垂線算法(MA)優(yōu)化粒子群算法的粒子位置變化,搜索前期加快了粒子群的收斂能力;搜索后期采用最有粒子爆炸策略與全局最優(yōu)解局部搜索策略使算法不易陷入局部最優(yōu)解,增強了全局搜索能力。綜上所述,本文提出的多策略融合粒子群算法無論在收斂速度還是尋優(yōu)能力都優(yōu)于其它4種算法,因此將本文算法應(yīng)用在機器人路徑規(guī)劃中能有效的減小機器人規(guī)劃路徑的長度。

由表5各算法的路徑規(guī)劃統(tǒng)計數(shù)據(jù)可知,可以清楚的看出MFPSO具有更好以及更穩(wěn)定的最優(yōu)路徑規(guī)劃能力。兩種不同規(guī)格地圖環(huán)境下MFPSO得到的最短路徑長度分別為28.627 4和48.472 2,均小于其它算法得到的最短路徑,且MFPSO的平均值也最小,由于最優(yōu)路徑長度反映了算法的有效性和優(yōu)越性;而平均值則反映算法進行路徑規(guī)劃的穩(wěn)定性。因此由結(jié)果可知把多策略融合改進的粒子群算法應(yīng)用在移動機器人路徑規(guī)劃中具有一定的優(yōu)勢。

4 結(jié)論

針對傳統(tǒng)的粒子群算法在移動機器人路徑規(guī)劃中存在慣性權(quán)值不適、迭代后期粒子群體多樣性下降等問題,提出一種融合多策略的改進粒子群搜索算法(MFPSO)。改進后的粒子群算法具有更快的收斂速度和尋優(yōu)能力,同時也加強了跳出局部最優(yōu)解的能力。在算法初期,利用中垂線算法的收斂策略加快算法的收斂速度;采用自適應(yīng)慣性權(quán)重更新方法進一步提升算法的性能,在算法后期以最優(yōu)粒子爆炸策略使算法跳出局部最優(yōu)值;再將全局最優(yōu)解繼續(xù)進行局部搜索提高機器人路徑的規(guī)劃能力。仿真結(jié)果表明,本文所提出的多策略融合改進粒子群算法在機器人路徑規(guī)劃中展現(xiàn)出更好的路徑尋優(yōu)能力。