基于多策略融合改進粒子群算法的路徑規劃研究*

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

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

0 引言

機器人的路徑規劃問題在機器人導航領域的研究一直都是熱點,而路徑規劃是指機器人根據地圖信息尋找起點到終點的一條無碰撞且代價最小的路徑。

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

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

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

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

1 多策略融合粒子群算法

1.1 粒子群算法

粒子群算法的核心是利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產生問題的最優解。其數學模型為:

(1)

(2)

1.2 多策略融合粒子群算法

1.2.1 中垂線算法

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

圖1 算法原理圖

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

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

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

圖2 粒子變化原理圖

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

粒子移動的實現方式為:首先判斷粒子是否存在于最優點所在區域,設:

(3)

式中:d表示粒子維度,假設某粒子存在于最優點所在區域,則x滿足:

(4)

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

(5)

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

若該粒子位于中垂線右側區域,則N點更新公式為:

(6)

(7)

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

(8)

圖3 PSO算法粒子變化圖

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

1.2.3 最優粒子爆炸策略

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

(9)

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

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

圖5 適應度收斂對比

1.2.4 改進粒子速度更新

利用中垂線算法改進后,若依舊利用傳統粒子群算法的粒子歷史位置信息反而會導致粒子遠離最優點。故粒子速度更新策略變為:

(10)

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

(11)

1.2.5 線性動態慣性權重調整方法

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

(12)

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

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

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

步驟1:隨機初始化各個參數,如學習因子,初始粒子速度位置,爆炸粒子數目,種群學習率;

步驟2:通過適應度函數計算適應度值;

步驟3:適應度最佳的粒子作為全局最優點M,適應度次優的粒子作為N點;

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

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

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

步驟7:計算所有更新后粒子的適應度值;

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

步驟9:結束條件達到則停止搜索,否則回到步驟2繼續執行。

1.4 算法時間復雜度分析

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

2 算法性能測試

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

表1 各算法參數設置

表2 基準測試函數

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

表3 實驗數據

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

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

3 多策略融合粒子群算法在路徑規劃中的應用

3.1 全局最優解局部搜索策略

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

圖8 傳統PSO路徑規劃

圖10 路徑長度對比

從圖8～圖10可以看出,采取全局最優解局部搜索策略的粒子群路徑規劃能夠將傳統粒子群產生的最優路徑繼續搜索尋優得到更佳的規劃路徑。

3.2 適應度函數建立

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

(13)

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

平滑度的計算公式為:

(14)

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

fit2=1/(fit2+c)

(15)

適應度函數的兩部分分別取一個權重值,則適應度函數公式如下:

f=a·fit1+b·fit2

(16)

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

3.3 路徑規劃問題

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

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

3.3.1 簡單環境

各算法在20×20柵格地圖簡單模型的最短規劃路徑對比如圖11所示,在30×30柵格地圖簡單模型的最短規劃路徑對比如圖12所示,簡單環境的最優路徑收斂曲線對比如圖13所示,各算法實驗數據統計如表4所示。

表4 簡單環境各算法路徑統計表

(a) MFPSO (b) MSPSO

(a) MFPSO (b) MSPSO

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

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

3.3.2 復雜環境

各算法在20×20柵格地圖復雜模型的最短規劃路徑對比如圖14所示,在30×30柵格地圖復雜模型的最短規劃路徑對比如圖15所示,復雜環境的最優路徑收斂曲線對比如圖16所示,各算法實驗數據統計如表5所示。

表5 復雜環境各算法路徑統計表

(a) MFPSO (b) MSPSO

(a) MFPSO (b) MSPSO

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

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

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

4 結論

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