齊鵬飛 丁鑫

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

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

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

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

1 基本灰狼算法

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

圖1 灰狼群體的社會等級

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

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

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

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

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

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

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

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

2.1 隨機(jī)游走策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)k=1時，上式可化簡為

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

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

2.3 B-spline曲線平滑操作

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

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

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

2.4 多步長移動方式

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

圖3 兩種步長模式對比

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

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

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

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

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

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

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

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

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

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

3 仿真及分析

3.1 環(huán)境建立

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

圖4 膨化處理

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

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

3.2 仿真分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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