基于多元策略改進(jìn)的灰狼算法機(jī)器人路徑規(guī)劃

齊鵬飛 丁鑫

（①河南省地震局，河南 鄭州 450016；②中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)，河南 鄭州 450001）

近年移動(dòng)機(jī)器人技術(shù)已逐漸滲入到生活中的各個(gè)領(lǐng)域內(nèi)，極大地節(jié)省了人力資源成本。而路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人領(lǐng)域的關(guān)鍵技術(shù)之一，它是指機(jī)器人在特定環(huán)境中，找出一條連接起點(diǎn)與終點(diǎn)的最佳路徑[1?2]。路徑規(guī)劃問(wèn)題上具有代表性的傳統(tǒng)算法有RRT法[3]、人工勢(shì)場(chǎng)法[4]、神經(jīng)網(wǎng)絡(luò)算法[5]和A*算法[6]等。除此之外，還有大量仿生算法例如蟻群算法[7]、遺傳算法[8]及粒子群算法[9]等等。這些算法也都在路徑規(guī)劃領(lǐng)域內(nèi)取得了不錯(cuò)的成效。

灰狼算法（GWO）是由Mirjalil S等提出的一種元啟發(fā)式算法，該算法模擬了灰狼的領(lǐng)導(dǎo)階層和捕獵過(guò)程。近年來(lái)灰狼算法開始應(yīng)用于路徑規(guī)劃領(lǐng)域，同樣取得了良好的表現(xiàn)。與其他群智能優(yōu)化算法一樣，灰狼優(yōu)化算法也存在一些不足之處。例如原灰狼算法在攻擊獵物時(shí)容易陷入停滯狀態(tài)，在搜索后期收斂速度逐漸變慢。因此國(guó)內(nèi)外許多學(xué)者提出了一系列改進(jìn)措施。文獻(xiàn)[10]提出了一種混合灰狼優(yōu)化算法，該算法利用混沌序列增強(qiáng)全局搜索的多樣性，從而平衡算法搜索和開發(fā)能力。文獻(xiàn)[11]提出了一種結(jié)合動(dòng)態(tài)進(jìn)化機(jī)制的灰狼算法來(lái)提高算法的局部搜索能力。但它沒(méi)有對(duì)算法的全局搜索能力進(jìn)行改進(jìn)。文獻(xiàn)[12]提出了一種融入混合差分進(jìn)化思想的改進(jìn)灰狼算法，解決了機(jī)械設(shè)計(jì)函數(shù)優(yōu)化問(wèn)題。然而，以上這些算法在研究灰狼捕獲獵物過(guò)程中，沒(méi)有將單只狼的信息對(duì)整個(gè)種群的影響考慮在內(nèi)。

因此，基于上述存在的問(wèn)題提出一種多策略改進(jìn)的灰狼優(yōu)化算法。首先為提升領(lǐng)頭狼在算法中的作用，提出了一種隨機(jī)游走策略。同時(shí)，引入一種基于光學(xué)凸透鏡原理的逆學(xué)習(xí)機(jī)制，對(duì)狼群種群中的劣勢(shì)個(gè)體進(jìn)行逆向?qū)W習(xí)，從而增加狼群個(gè)體多樣性，避免算法陷入局部最優(yōu)。最后，通過(guò)B-spline曲線對(duì)路徑進(jìn)行平滑操作，提高路徑平滑度。

1 基本灰狼算法

灰狼算法是Mirjalil S等人受灰狼捕食行為啟發(fā)提出的一種群體算法。GWO算法的核心思想來(lái)自于灰狼群體中自然發(fā)生的狩獵行為和社會(huì)領(lǐng)導(dǎo)現(xiàn)象。灰狼是群居的，平均每群5～12只狼。在它們的社會(huì)生活行為中，它們嚴(yán)格遵循社會(huì)等級(jí)，社會(huì)等級(jí)示意圖如圖1所示。在層次結(jié)構(gòu)中，最高層次的狼成員被稱為α，第二級(jí)成員被稱為β，隨后第三級(jí)和第四級(jí)成員分別被稱為delta (δ)和omega (ω)。領(lǐng)頭狼是一個(gè)領(lǐng)導(dǎo)者，對(duì)狩獵、睡覺、醒來(lái)的時(shí)間等問(wèn)題全權(quán)負(fù)責(zé)。領(lǐng)頭狼也被稱為統(tǒng)治狼，因?yàn)樗拿顣?huì)被狼群遵循。另外，領(lǐng)頭狼并不是群體中最強(qiáng)壯的成員，而是在管理狼對(duì)獵物的攻擊方面做得最好的。

圖1 灰狼群體的社會(huì)等級(jí)

在灰狼狩獵中發(fā)生的主要活動(dòng)是：跟蹤和追捕獵物；包圍和騷擾獵物直到其停止移動(dòng)；小心地向獵物移動(dòng)。GWO的數(shù)學(xué)模型如下：

階段1：這基本上是一個(gè)搜索階段，在搜索獵物的過(guò)程中，灰狼強(qiáng)烈遵循社會(huì)等級(jí)制度。

階段2：這一階段被稱為包圍階段，當(dāng)搜索過(guò)程完成后，他們的下一步是包圍獵物。圍捕獵物的表現(xiàn)如下。

式中：λ為狼和獵物之間的距離；Q為獵物位置；Gw代表灰狼的位置；η和μ為系數(shù)矢量；x在區(qū)間[0,2]線性遞減；v1、v2為[0,1]上的隨機(jī)向量；s為迭代次數(shù)。

階段3：當(dāng)搜索和包圍階段完成后，它們的下一個(gè)階段是狩獵。狼群位置更新的數(shù)學(xué)模型為

式（2）表示各個(gè)類型狼個(gè)體間的距離更新模型，式（3）代表移動(dòng)的方向與步長(zhǎng)，式（4）為新一代灰狼位置。

階段4：最后階段決定狼群是否攻擊目標(biāo)，或者尋找其他更強(qiáng)壯的獵物。

2 改進(jìn)灰狼算法

2.1 隨機(jī)游走策略

在更新狼群中每只狼位置的迭代過(guò)程中，領(lǐng)頭狼的選擇是非常重要的，因?yàn)槊恐焕堑奈恢枚际歉鶕?jù)領(lǐng)頭狼位置更新的。因此，領(lǐng)頭狼群需要擴(kuò)大活動(dòng)范圍，以避免由于局部最優(yōu)解的停滯而導(dǎo)致的早熟收斂問(wèn)題，并控制群體內(nèi)的社會(huì)行為。為此，本文提出一種隨機(jī)游走策略，即領(lǐng)頭狼通過(guò)隨機(jī)游走來(lái)增大搜索空間，然后ω狼根據(jù)搜索空間進(jìn)行位置更新。

隨機(jī)行走是由連續(xù)的隨機(jī)步長(zhǎng)組成的隨機(jī)過(guò)程。數(shù)學(xué)表達(dá)式如下 。

式中：WN表示當(dāng)前狀態(tài)；Si表示從任何隨機(jī)分布中選取的隨機(jī)步長(zhǎng)。

任意兩個(gè)連續(xù)隨機(jī)行走之間的關(guān)系定義為

式中：WN?1表示上一狀態(tài)和SN為上一狀態(tài)到當(dāng)前狀態(tài)所選取的步長(zhǎng)。步長(zhǎng)Si可以是不變的，也可以是變化的。因此，對(duì)于從位置x0開始的狼，假設(shè)它的最終位置是xN，那么隨機(jī)游走也可以定義為

其中：αi是控制每次迭代中的步長(zhǎng)si的參數(shù)，其值大于零。

2.2 透鏡逆學(xué)習(xí)策略

在灰狼算法中領(lǐng)頭狼影響著整個(gè)算法的性能，一旦其陷入局部最優(yōu)，那么算法尋優(yōu)效率將大打折扣，因此提高領(lǐng)頭狼的搜索范圍就顯得尤為重要。一般學(xué)習(xí)策略在一些優(yōu)化算法中取得了較好的效果，但在工程問(wèn)題中對(duì)算法性能影響不大，這是因?yàn)橐话銓W(xué)習(xí)策略在局部空間進(jìn)行逆解，豐富了種群的多樣性，但搜索范圍較窄，缺乏靈活性。為了提高領(lǐng)頭狼的搜索能力，提出一種基于凸透鏡成像的逆學(xué)習(xí)策略，并將其應(yīng)用于領(lǐng)頭狼的個(gè)體更新過(guò)程中，其具體原理描述如下：

定義1 逆向點(diǎn)：假定X=(x1,x2,···,xD)為D維空間內(nèi)的一個(gè)點(diǎn)，其中xi∈[aj,bj]，j=1,2,···,D，則X的逆向點(diǎn)為，且。

定義2 基點(diǎn)：如果在D維空間內(nèi)存在若干點(diǎn)o1,o2,···,om，對(duì)于任意一點(diǎn)X與X'到oi的歐幾里得距離分別為di和，假設(shè)，此時(shí)稱oi為X與X'在k=i時(shí)的基點(diǎn)。

在一維空間內(nèi)，假定有一高為h的個(gè)體P，其直角坐標(biāo)上的投影為x*，o為基點(diǎn)。o點(diǎn)放置一焦距為f的凸透鏡，此時(shí)可得一個(gè)高度為h'的像P'，其在直角坐標(biāo)上的投影為x'*。這個(gè)x'*就是個(gè)體x*通過(guò)透鏡逆學(xué)習(xí)產(chǎn)生的逆向個(gè)體，如圖2所示。

圖2 透鏡逆學(xué)習(xí)策略示意圖

根據(jù)上圖可得以下關(guān)系。

令k=h/h'，并且對(duì)式（8）進(jìn)行換算，可得到逆向點(diǎn)的數(shù)學(xué)表達(dá)式。

當(dāng)k=1時(shí)，上式可化簡(jiǎn)為

上式即為一般的逆學(xué)習(xí)策略，學(xué)習(xí)過(guò)程中個(gè)體不會(huì)發(fā)生變化。本文通過(guò)調(diào)節(jié)不同的k值，實(shí)現(xiàn)個(gè)體更新，從而豐富了狼群的多樣性。

將式（9）推廣至D維空間內(nèi)，可得關(guān)系式如下。

2.3 B-spline曲線平滑操作

B-spline是樣條曲線的一種特殊曲線形式，同時(shí)也是bezier曲線的一般形式。n次B-spline表達(dá)式為

式中：Pi為第i段控制點(diǎn)方程；Fi,n為n次B-spline 的基函數(shù)，其公式為

本文采用三次準(zhǔn)均勻B-spline對(duì)規(guī)劃的路徑進(jìn)行平滑處理。三次B-spline曲線的具體表達(dá)式如下。

2.4 多步長(zhǎng)移動(dòng)方式

基本灰狼算法中一般采用單步移動(dòng)模式，且轉(zhuǎn)移的方向只能為8個(gè)方向。在傳統(tǒng)的單步長(zhǎng)移動(dòng)模式下路徑距離更長(zhǎng)，且轉(zhuǎn)折次數(shù)也更多。因此本文采用多步長(zhǎng)移動(dòng)方式。示意圖如圖3所示，虛線為單步長(zhǎng)移動(dòng)，實(shí)線為多步長(zhǎng)移動(dòng)方式。由圖可知，多步長(zhǎng)移動(dòng)模式下路徑距離更短且轉(zhuǎn)折次數(shù)更少。

圖3 兩種步長(zhǎng)模式對(duì)比

2.5 改進(jìn)灰狼算法流程

本文改進(jìn)灰狼算法的具體步驟如下：

步驟1：初始化運(yùn)行環(huán)境及灰狼算法各項(xiàng)參數(shù)，確定需要人為設(shè)定的參數(shù)取值。

步驟2：初始化灰狼種群，計(jì)算出種群內(nèi)各個(gè)體的適應(yīng)度，然后由高到低進(jìn)行排列，分別將前三最佳個(gè)體位置賦予α狼、β狼和δ狼。

步驟3：根據(jù)式（2）～（4）更新種群內(nèi)各灰狼位置信息。

步驟4：依據(jù)式（1）更新α狼、β狼和δ狼位置。

步驟5：利用式（11）對(duì)個(gè)體進(jìn)行透鏡逆學(xué)習(xí)，獲得逆向解。

步驟6：用計(jì)算出的逆向解代替原解，加入種群內(nèi)進(jìn)行迭代操作。

步驟7：檢查是否達(dá)到最大迭代次數(shù)，若是則輸出路徑，否則返回步驟3。

步驟8：利用B-spline 曲線對(duì)上步得到路徑進(jìn)行平滑，然后輸出最佳路徑。

3 仿真及分析

3.1 環(huán)境建立

本文將柵格圖作為機(jī)器人建模環(huán)境。在柵格地圖中用黑色部分代表不可行域，白色部分則代表自由通行區(qū)域。若環(huán)境中存在障礙物無(wú)法完全占據(jù)一個(gè)柵格的情形，則進(jìn)行膨化操作使其充滿一格，如圖4所示。

圖4 膨化處理

假設(shè)柵格圖中，柵格號(hào)按從下至上，從左到右依次遞增。柵格地圖規(guī)格為m行n列，柵格號(hào)為K，柵格粒徑為1，則柵格中心坐標(biāo)可表示為

式中：x、y分別為中心點(diǎn)的橫、縱坐標(biāo)；mod為取余操作，int表示求整。

3.2 仿真分析

各算法進(jìn)行對(duì)比時(shí)選取的參數(shù)值均保持一致，其中灰狼種群規(guī)模為50，最大迭代數(shù)為100，x的最初取值為2。每種算法均仿真20次，得出平均仿真結(jié)果及指標(biāo)。基于Matlab2018b平臺(tái)搭建20×20柵格地圖環(huán)境，運(yùn)行內(nèi)存8 GB，CPU 2.5 Hz，設(shè)置起點(diǎn)為(0.5,0.5)，終點(diǎn)為(19.5,19.5)。

（1）普通多障礙環(huán)境

首先基于柵格地圖環(huán)境并設(shè)置相關(guān)參數(shù)值，分別對(duì)基本灰狼、文獻(xiàn)[10]算法、本文改進(jìn)的灰狼算法進(jìn)行仿真實(shí)驗(yàn)。仿真結(jié)果分別如圖5、6所示，各項(xiàng)指標(biāo)對(duì)比如表1。

表1 普通環(huán)境指標(biāo)對(duì)比

圖5 基本灰狼算法與文獻(xiàn)[10]算法結(jié)果圖

圖6 本文算法結(jié)果圖

從圖5～6及表1可以得到，與基本灰狼算法和文獻(xiàn)[10]改進(jìn)灰狼算法相比，本文改進(jìn)的灰狼算法規(guī)劃出的路徑長(zhǎng)度更平滑更短，拐點(diǎn)數(shù)遠(yuǎn)少于其他兩種算法，且算法尋優(yōu)效率更高。相比于基本灰狼算法和文獻(xiàn)[10]算法，其中路徑長(zhǎng)度分別減少約9.9%和5.6%，拐點(diǎn)數(shù)分別減少85.7%和70%，收斂代數(shù)分別減少約52.2%和26.6%，運(yùn)行時(shí)間分別縮短約52.7%和30%。這顯示出本文提出的改進(jìn)策略可行且規(guī)劃效率較高，能夠用于移動(dòng)機(jī)器人常規(guī)環(huán)境下的路徑規(guī)劃。

（2）多U型陷阱環(huán)境

為了進(jìn)一步檢驗(yàn)算法在復(fù)雜環(huán)境下的性能。基于柵格圖建立多U型陷阱環(huán)境的極端情形，在此種環(huán)境下因?yàn)橄葳遢^多，對(duì)算法的適應(yīng)性也提出了巨大挑戰(zhàn)。仍然將本文算法與基本灰狼算法及文獻(xiàn)[10]算法進(jìn)行對(duì)比，結(jié)果如圖7所示。其中實(shí)線為基本灰狼算法仿真路徑，虛線為文獻(xiàn)[10]算法仿真路徑，點(diǎn)線為本文算法仿真路徑，指標(biāo)對(duì)比如表2。

圖7 陷阱環(huán)境仿真圖

由圖7及表2可知，在多陷阱復(fù)雜環(huán)境下，本文算法因引入了隨機(jī)游走策略及透鏡逆學(xué)習(xí)機(jī)制，仍舊保持著較高的規(guī)劃效率。而基本灰狼算法遇到陷阱環(huán)境易陷入局部最優(yōu)，導(dǎo)致路徑距離長(zhǎng)，轉(zhuǎn)向多，尋優(yōu)效率較低。文獻(xiàn)[10]算法雖有改進(jìn)，但其效果不如本文算法。具體體現(xiàn)為相比于基本灰狼算法和文獻(xiàn)[10]算法，路徑長(zhǎng)度分別減少約18.9%和5.6%，拐點(diǎn)數(shù)分別減少93.7%和83.3%，收斂代數(shù)分別減少約59.5%和34.6%，運(yùn)行時(shí)間分別縮短約60.1%和38.6%。

表2 陷阱環(huán)境指標(biāo)對(duì)比

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)灰狼算法在路徑規(guī)劃時(shí)易陷入局部極值、探索效率低等不足，提出一種多元策略改進(jìn)的灰狼算法。首先為提升領(lǐng)頭狼在算法中的作用，提出了一種隨機(jī)游走策略。同時(shí)，引入一種基于光學(xué)凸透鏡原理的逆學(xué)習(xí)機(jī)制，避免算法陷入局部最優(yōu)。最后，通過(guò)B-spline曲線對(duì)路徑進(jìn)行平滑操作，提升路徑平滑度。分別基于普通環(huán)境及多U型陷阱環(huán)境進(jìn)行了仿真，普通環(huán)境下本文算法相比于基本灰狼算法，路徑長(zhǎng)度減少約9.9%，收斂代數(shù)減少約52.2%，轉(zhuǎn)彎次數(shù)減少85.7%，運(yùn)行時(shí)間縮短約52.7%，而在多U型陷阱環(huán)境條件下對(duì)比基本灰狼算法，本文算法優(yōu)勢(shì)更加明顯，路徑長(zhǎng)度減少約18.9%，拐點(diǎn)數(shù)分別減少93.7%，收斂代數(shù)減少約59.5%，運(yùn)行時(shí)間縮短約60.1%，展現(xiàn)出多元策略改進(jìn)灰狼算法的良好性能。