基于混合灰狼算法的機器人路徑規劃*

王永琦,江瀟瀟

(上海工程技術大學電子電氣工程學院,上海 201620)

1 引言

機器人路徑規劃RPP(Robot Path Planning)是機器人技術領域一項極其重要的課題，該課題的研究目的在于以優化目標(如線路長度、能源消耗)為指導確定一條從起點到終點的最佳路徑[1]。近年來，智能化技術獲得了快速發展，而不斷推進的產業智慧升級則進一步開拓了移動機器人的應用前景，相應的實際應用場景包含智慧生產、貨物搬運、水下作業和異常環境探測等方面[2]。鑒于此，進行RPP問題的算法設計研究具有極其重要的理論意義和工程價值。

國內外學者圍繞RPP問題開展了大量的研究工作，并取得了豐碩的成果[3]。經典的路徑規劃算法包括視圖法、人工勢場法、自由空間法和A*算法等，簡單實用的性質使得上述經典算法具有一定的工程應用價值，然而相關算法的缺陷同樣限制了其在不同類型RPP問題方面的應用。例如，視圖法的路徑由多條直線構建而成，線路棱角明顯，難以確保全局最優；人工勢場法易陷入局部最優，存在終點不可達的缺陷；自由空間法計算復雜性較高，對復雜障礙空間的RPP問題適用性較差。近年來快速發展的進化算法技術為解決RPP問題提供了新思路，現階段已有多種相關算法在RPP問題上獲得了成功應用，包括蟻群算法、遺傳算法和粒子群算法等。與此同時，基本蟻群算法搜索時間長且易停滯，遺傳算法易生成包含障礙物的不可行路徑，以上缺陷一定程度上限制了進化算法求解RPP問題的效率。鑒于此，以進化算法為基礎，構建高效可靠的機器人路徑規劃方法成為學者努力追尋的目標。

受灰狼群體捕獵行為的啟發，Mirjalili等[4]于2014年提出了一種新型進化算法——灰狼GWO(Grey Wolf Optimization)算法。相較于其他算法，GWO算法具有架構簡單、控制參數少和計算效率高等優點。研究表明，GWO算法的整體尋優性能相比于遺傳算法、粒子群算法以及人工蜂群算法等更具優勢[5]。目前，該算法在眾多工程領域獲得了廣泛應用，包括車間調度、數值優化、圖像融合以及電力系統配置等[6-8]。鑒于GWO算法在眾多領域的良好表現，本文將其運用于RPP這一重要工程問題。

GWO算法采用隨機方法構建初始解，這在一定程度上限制了算法的搜索效率；同時，該算法僅以優質解引導種群進化，這使得搜索過程易陷入局部最優。針對以上不足，本文提出HGWO(Hybrid Grey Wolf Optimization)算法，在其設計過程中融入反向學習機制和融合了歷史信息的個體位置更新方法。具體而言，在初始化階段，HGWO算法采用反向學習方法構建初始種群，力求提高初始解的質量；在進化過程中，HGWO算法首先引入PSO思想來改善GWO算法的個體位置更新過程，通過融合每個灰狼個體的歷史信息以構筑更高效的種群進化方法；同時，借助精英反向學習策略探索當前種群中精英個體的反向解空間，力求增強算法的勘探能力。

2 GWO與PSO算法

2.1 GWO算法

灰狼以群居生活方式為主，各群體中平均存在5～12只灰狼，并具有嚴格的等級制度，圖1展示了灰狼群體的金字塔分層示意圖。整個群體包括α、β、δ和ω4層。第1層為種群中的頭狼，稱為α狼，該灰狼個體負責群體各項決策事務；第2層為β狼，負責協助管理決策；第3層為δ狼，負責偵察、放哨和捕獵等相關事務；第4層為ω狼，負責平衡種群內部的關系。

Figure 1 Hierarchy of grey wolves圖1 灰狼群體等級結構

GWO算法以灰狼個體表示待優化問題的解，并通過模擬灰狼的等級制度和狩獵行為實現對測試問題的迭代尋優。對于當前待優化問題，適應度最佳的灰狼個體設為α狼，次優和第3優的灰狼個體分別以β狼和δ狼表示，其余個體稱為ω狼。在GWO算法中，低等級的灰狼個體必須服從高等級灰狼個體的指導，整個尋優過程由優勢灰狼個體指導種群向目標獵物包圍。算法的種群進化公式歸納如下：

D=|C·Xp(t)-X(t)|

(1)

C=2·r1

(2)

X(t+1)=Xp(t)-A·D

(3)

A=2a·r2-a

(4)

(5)

其中，式(1)和式(2)定義了灰狼個體與目標獵物之間的距離D，t為當前迭代次數，X(t)表示當前種群中某一灰狼個體的位置，Xp(t)為目標獵物的位置，距離調節系數C由[0,1]上均勻分布的隨機變量r1確定。式(3)～式(5)定義了灰狼個體的更新方式，其中r2表示[0,1]上均勻分布的隨機變量，T為最大迭代次數，收斂因子a隨著迭代搜索的進行從2線性遞減為0。位置調節系數A由a和r2確定。

鑒于獵物目標的位置(即當前問題的解)通常是未知的，GWO算法充分利用優勢灰狼個體的位置信息進行迭代尋優，即利用α、β和δ狼的位置信息判斷獵物的大致位置，進而指導狼群逐步逼近獵物目標，相應的數學公式描述如下：

Dα=|C1·Xα(t)-X(t)|

(6)

Dβ=|C2·Xβ(t)-X(t)|

(7)

Dδ=|C3·Xδ(t)-X(t)|

(8)

X1(t)=Xα(t)-A1·Dα

(9)

X2(t)=Xβ(t)-A2·Dβ

(10)

X3(t)=Xδ(t)-A3·Dδ

(11)

(12)

其中，Xα(t)、Xβ(t)和Xδ(t)分別表示當前種群中α、β和δ狼的位置，C1,C2,C3為距離調節參數，由式(2)生成。X(t)為某一ω狼的位置。式(8)～式(10)計算了α、β和δ狼與候選ω狼之間的距離Dα、Dβ和Dδ。A1、A2、A3為位置調節系數，由式(4)生成。基于此，式(9)～式(12)定義了ω狼更新后的最終位置。圖2所示為GWO算法的實現原理。

Figure 2 Schematic diagram of GWO圖2 GWO算法原理示意圖

綜合以上描述，GWO算法的實現流程歸納如下：

步驟1初始化：利用隨機方法構建初始灰狼種群。

步驟2種群排序：計算每個灰狼個體的適應度值，并據此確定當前種群中的α、β、δ和ω狼。

步驟3參數更新：確定GWO算法的參數a、A和C。

步驟4種群進化：依據式(6)～式(12)更新ω狼的位置。

步驟5終止條件判斷：若滿足算法的終止條件，終止迭代并輸出最優解；否則，轉步驟2。

2.2 PSO算法

Eberhart和Kennedy兩位學者通過模擬鳥類覓食行為提出了PSO算法，并用其求解各類復雜優化問題[9]。在PSO算法中，鳥群中的每只鳥被抽象為一個粒子，每個粒子具有位置和速度，食物與當前粒子間的距離被定義為適應度，其數值大小決定了當前粒子的優劣，其計算公式依據實際問題特征進行設定。在算法迭代過程中，每個粒子借助自身歷史最優位置和整個種群的全局最優位置進行位置更新。

假設待優化問題的維度為D′，以符號N表示種群規模，當前種群中第i個粒子在第d維的速度和位置信息分別記為Vid和Xid，則算法采用以下公式進行粒子的速度更新和位置更新：

Vid(t+1)=ω′·Vid(t)+c1·r1·

(Pid-Xid(t))+c2·r2·(Pgd-Xid(t))

(13)

Xid(t+1)=Xid(t)+Vid(t+1)

(14)

其中，t表示當前迭代次數;ω′為慣性因子，取值在[1,3]時算法的優化性能較好;學習因子c1和c2為非負常數，一般取c1=c2=2;r1和r2表示[0,1]上的隨機數。Pid表示第i個粒子自身歷史最優位置在第d維的取值，Pgd表示整個種群全局最優位置在第d維的取值。

綜合以上描述，PSO算法的實現過程如圖3所示。

Figure 3 Flow chart of PSO圖3 PSO算法實現流程

3 HGWO算法

本文借助反向學習機制和融合歷史信息的個體位置更新方法構筑HGWO求解算法。具體而言，在初始化階段，采用反向學習方法構建初始種群，力求提高初始解的質量；在進化過程中，引入PSO思想來改善算法的個體位置更新過程，借助每個灰狼個體的歷史信息指導種群進化；同時，結合精英反向學習策略，探索當前種群中精英個體的反向解空間，著力克服算法易陷入局部最優的缺陷。

3.1 反向學習初始化方法

為提升初始狼群的質量，HGWO算法借助反學習方法生成初始解[10]。具體而言，算法首先通過隨機的方式生成N個灰狼個體，隨后為每個個體生成一個反向解，最后以優化目標為依據對2N個解進行評價，并選取其中最優的N個解構建初始種群。

步驟1分別令i←1和d←1，并轉步驟2。

步驟2若i≤N成立，轉步驟3；否則，轉步驟7。

步驟3若d≤D′成立，轉步驟4；否則，轉步驟5。

步驟5令d←d+1，若d>D′，令d←1,轉步驟6；否則，轉步驟3。

步驟6令i←i+1，并轉步驟2。

3.2 融合歷史信息的個體位置更新方法

在個體位置更新環節，GWO算法僅考慮ω狼與當前種群中優勢灰狼個體(α、β和δ狼)間的信息交流，而忽略了其自身經驗的引導。研究表明，自身經驗對進化算法的個體更新過程具有重要影響[11]。鑒于此，本文引入PSO思想來改善GWO算法的個體位置更新過程，力求構筑更高效的種群進化方法，新的個體位置更新方法歸納如下：

X(t+1)=ω1·X1(t)+ω2·X2(t)+ω3·X3(t)+

c·r·(Xbest(t)-X(t))

(15)

(16)

(17)

(18)

其中，式(15)的第1部分表示群體優勢個體的經驗對ω狼的引導，慣性權重系數ω1、ω2和ω3采用式(16)～式(18)進行自適應調整，力求動態地權衡算法的全局和局部搜索性能；式(15)的第2部分為自身歷史經驗對ω狼的引導，c為學習因子，r為[0,1]上的隨機數。

3.3 精英反向學習策略

加強對優秀個體周圍空間的搜索對強化進化算法勘探新解的能力具有重要影響，為此，本文將精英反向學習策略融合于HGWO算法，以探索當前種群中精英個體的反向解的空間信息，力求提升算法的性能[12]。

反向解定義如下：以參數D′表示當前待優化問題的維度，在第t次迭代過程中，以Xid表示當前種群中解向量Xi在第d維的取值，則Xi的反向解X′i為：

(19)

在每次迭代過程中，HGWO算法率先采用融合歷史信息的個體位置更新方法實現種群進化，隨后對更新后的種群進行個體排序。結合相關研究和實際測試效果[13]，選取其中前10%的優秀灰狼個體構建精英種群Pb，依據反向解的定義生成Pb的反向種群P′b，選取混合種群Pb∪P′b中前50%的優秀解進入下一代。

3.4 HGWO算法流程

基于以上描述，HGWO算法的實現流程歸納如下：

步驟1初始化：利用反向學習初始化方法構建初始種群，并計算每個解的目標函數值。

步驟2種群排序：依據適應度值對當前種群進行排序，劃分α、β、δ和ω狼。

步驟3參數更新：確定GWO算法的參數a、A和C。

步驟4更新歷史信息：確定各灰狼個體的自身歷史最優解。

步驟5種群進化：依據式(15)～式(18)更新ω狼的位置。

步驟6精英搜索：采取精英反向學習策略更新種群。

步驟7終止條件判斷：若滿足終止條件，停止迭代并輸出最優解；否則，轉步驟2。

4 路徑規劃

4.1 環境模型

圖4展示了機器人路徑規劃問題的環境模型，其中灰色方塊為起點，黑色方塊為終點，黑色圓表示一系列障礙物。在當前坐標系下，每個障礙物的數學表達式為：

(x-a)2+(y-b)2=r2

(20)

其中，點(a,b)表示障礙物的坐標中心，r為半徑。

Figure 4 Environment model圖4 環境模型

本文采用導航點模型構建機器人路徑，當前問題的解以π={(x0,y0),(x1,y1),…,(xn,yn),(xn+1,yn+1)}表示，(x0,y0)為起點，(xn+1,yn+1)為終點，剩余其他點表示算法所需規劃的坐標。顯然，當前問題的決策維度由導航點的數目確定。此外，通過直接將路徑點相連而獲得的線路圖棱角較為明顯。

在確保求解精度的前提條件下，為降低問題的優化維度并對線路曲線進行平滑處理，本文借助Spline樣條插值法構造路徑曲線，圖5給出了相應的示意圖[14]。其中，采樣導航點為測試算法所需優化的點坐標，而其余的插值導航點則由Spline樣條插值法確定。相對而言，該方法僅需優化較少數目的采樣導航點坐標，算法求解難度進一步降低；同時，插值法所得的路徑曲線更為平滑流暢，求解效果更佳。

Figure 5 Spline interpolation圖5 Spline樣條插值法示意圖

4.2 路徑評價函數

當前機器人路徑規劃問題以最小化線路長度為優化目標，借助懲罰函數法處理避障約束條件，相應的路徑評價函數構造如下：

(21)

(22)

其中，?為懲罰系數，K為障礙物總數，(ak,bk)表示當前環境中障礙物k的中心，rk為其半徑。

5 實驗結果與分析

為驗證本文提出的HGWO算法的性能，分別將其應用于基準測試函數以及機器人路徑規劃問題，在2.4 GHz、內存4 GB、Intel(R) Core(TM) i5-2430M CPU的計算機上進行仿真實驗，編程平臺選用Matlab 2017a。

5.1 基準測試函數

為驗證HGWO算法的性能，選取文獻[15]中的5個基準函數進行仿真。表1歸納了測試函數的相關情況，其中參數D′表示問題維度，f1、f2和f3具有單峰性質，f4和f5具有多峰性質，上述函數極其復雜，難以取得全局最優解，因此常用于評價進化算法的搜索性能。

Table 1 Benchmark functions

為驗證HGWO算法的搜索性能，首先開展HGWO與GWO 2種測試算法的對比分析，力求驗證改進措施的有效性。測試過程相關參數設置如下：測試函數的維度D′分別設為20和40，GWO和HGWO算法的種群歸納和最大迭代次數分別設置為50和2 000，HGWO算法的學習因子c設為2，對比算法的其他參數維持與文獻[4]相同的取值。針對各個測試算例，2種算法均獨立運行20次，表2歸納了2種算法的測試結果。

Table 2 Comparison of test results between GWO and HGWO

由表2的測試結果可知，相比于GWO算法，HGWO算法在各測試問題上獲得的均值更小，這表明本文所提出的HGWO算法的整體優化效果更令人滿意。同時，HGWO算法獨立運行20次所得結果的標準差相較于GWO算法更具優勢，這說明HGWO算法的穩定性更強。

為進一步驗證HGWO算法的尋優性能，將其與另外3種改進灰狼算法進行對比，包括CGWO(Chaotic Grey Wolf Optimization)算法[16]、EGWO(Enhanced Grey Wolf Optimization)算法[17]和LGWO(Grey Wolf Optimizer with Lévy flight)[18]算法。測試過程相關參數設置如下：測試函數的維度D′設為40，4種測試算法的種群規模和最大迭代次數分別設為50和2 000，對比算法的其他參數設為與文獻[16-18]相同的值。此外，針對各個測試算例，算法均獨立運行20次，表3歸納了4種算法的測試結果。

由表3的測試結果可知，HGWO算法所得測試結果的均值優于CGWO、EGWO和LGWO算法的，這表明反向學習機制和融合歷史信息的個體位置更新方法的嵌入，顯著提升了GWO算法的性能。同時，HGWO算法多次獨立運行結果的標準差更小，表明該算法的魯棒性更強，能更高效穩定地求解各類復雜函數優化問題。

Table 3 Comparison of test resultsamong four improved GWOs

5.2 路徑規劃仿真

為進一步驗證HGWO的尋優性能，進行CGWO、EGWO、LGWO和HGWO算法求解簡單環境以及復雜環境中路徑規劃問題的對比實驗。2種環境下的障礙物總數分別設為6和12，且采樣導航點數和插值點數目分別設為10和100。測試過程的算法參數設置如下：4種算法的種群規模和最大迭代次數分別設置為30和300，HGWO算法的學習因子c設為2，對比算法的其他參數維持與參考文獻[16-18]相同的取值；對于2種測試環境，4種測試算法均獨立運行20次。實驗結果如圖6～圖9以及表4和表5所示。

Figure 6 Optimal paths obtained by four GWOs in a simple environment圖6 簡單環境中4種灰狼算法得到的最優路徑

Figure 7 Optimal paths obtained by four GWOs in a complex environment圖7 復雜環境中4種灰狼算法得到的最優路徑

Figure 8 Convergence curves obtained by four GWOs in a simple environment圖8 簡單環境中4種灰狼算法的最優進化曲線

Figure 9 Convergence curves obtained by four GWOs in a complex environment圖9 復雜環境中4種灰狼算法的最優進化曲線

圖6和圖7分別展示了4種測試算法在簡單環境和復雜環境下所得的最優路徑，據此可知本文提出的HGWO算法所尋得的路徑曲線最短，特別是在復雜環境下，HGWO算法的優越性更為顯著。與此同時，圖8和圖9給出了4種灰狼算法在

Table 4 Comparison of results obtained byfour GWOs in a simple environment

Table 5 Comparison of results obtainedby four GWOs in a complex environment

2種測試環境中的最優進化曲線，據此可知，反向學習初始化方法使得HGWO算法在初期能夠獲得高質量的解，而融合歷史信息的個體位置更新方法和精英反向學習策略增強了算法的勘探能力，克服了傳統GWO算法易陷入局部最優的不足。表4和表5歸納了各測試算法20次獨立運行所得結果，據此可知，本文提出的HGWO算法所得的路徑曲線在最優、最劣和均值3方面均獲得了最佳表現。

6 結束語

本文構建了一種混合灰狼算法，并將其與Spline樣條插值法相結合以求解機器人路徑規劃問題。HGWO算法采用反向學習方法生成初始種群，著力提高初始解的質量；在進化過程中，借助灰狼個體的歷史信息指導種群進化，并融合精英反向學習策略探索當前種群中精英個體的反向解的空間信息，以達到增強算法勘探能力的目的。在實驗部分，進行了函數優化以及路徑規劃2組對比實驗，HGWO算法的橫縱向對比實驗驗證了其良好的優化精度和穩健的魯棒性。