粒子群算法改進灰狼算法的機器人路徑規劃

梁景泉，周子程，劉秀燕

（青島理工大學信息與控制工程學院，山東青島 266525）

0 引言

近些年來，元啟發式算法在路徑規劃問題中的應用越來越廣泛，代表算法包括遺傳算法、蟻群算法和粒子群優化算法（Particle Swarm Optimization，PSO）。國內學者對元啟發式算法進行了大量研究，例如王潤澤等［1］提出利用蟻群算法進行動態路徑規劃，但由于該算法自身的局限性，前期搜索過程較慢，后期也有可能陷入局部最優解；繆裕青等［2］提出利用模擬退火算法改進的PSO 優化任務卸載策略，充分利用空閑的車載單元計算能力，但在精度方面仍不夠理想；趙睿等［3］提出利用改進遺傳算法優化自動導引車集結路徑，算法中加入了基于時間倉的調整策略，從而使收斂速度進一步加快，但存在易過早得出最優解的問題。目前國內外還存在很多改進的單一算法，如Tsai 等［4］提出的改進遺傳算法、Lee 等［5］提出的改進粒子群算法、Zhang 等［6］提出的改進蟻群算法、王海泉等［7］提出的改進人工蜂群算法、張文輝等［8］提出的改進人工魚群算法等，均可用于路徑規劃問題求解，但鮮有研究進行兩種方法的聯合改進。

灰狼優化算法（Grey Wolf Optimizer，GWO）是由Mirjalili 等［9］提出的元啟發式算法，屬于群體智能算法，模仿灰狼的捕獵策略和階層領導。該算法相較于其他群體優化算法有諸多優勢，例如更加靈活、更容易實現以及求解過程中不需要計算梯度等。雖然GWO 在眾多領域都有著良好表現，但其具有后期收斂速度慢和全局尋優能力不夠強的問題［10］。因此，以該算法為基礎，構建更加高效可靠的路徑規劃算法成為很多學者的努力方向。例如，曹建秋等［11］通過A*算法進行頭狼初始化以獲取較優起點，從而加快算法最優解的出現；王永琦等［12］采用反向學習方法構建初始灰狼種群，以提高初始解的質量，并借助精英反向學習策略探索優秀解的反向解，從而提升算法整體效率；袁光輝［13］通過引入非線性慣性權重以及自適應交叉編譯策略對GWO 進行改進，以提高算法的收斂精度和速度。

目前，GWO 算法在路徑規劃實際應用方面仍有許多不足之處，為提高該算法的全局尋優能力和收斂速度，本文引入PSO 的思想改進GWO 算法，使其具有更加優秀的收斂速度和全局尋優能力。

1 環境建模

機器人全局路徑規劃問題的描述為：對于一個給定的二維地形，存在著有限個障礙物，算法的任務就是找到一個令機器人能夠從起點到終點且安全不觸碰障礙物的路徑，并保證該路徑為全局最短路徑［14］。常見的環境建模方法有很多，如點集拓撲法、可視圖法和柵格法等，本文選用柵格法，其目標函數可表示為：

式中，L 為路徑長度，np為路徑點個數，（xi，yi）為對應路徑點的坐標。

使用柵格法對機器人需要通過的環境進行建模后得到m×n 的區域，其中原點為機器人的初始位置，機器人最終要移動到的目標位置用（m，n）表示。如果障礙區域的形狀不是規則正方形，那么將其補齊為正方形，建模時認定障礙物大小為整數個全柵格，若部分區域存在少量障礙，但障礙面積不滿一個柵格，則將其看作一個柵格計算。

采用式（2）建立的柵格地圖示例如圖1 所示，有障礙物的柵格為黑色，表示機器人不能通過，不存在障礙物的柵格為白色，表示機器人能夠通過。

Fig.1 Raster map model for path planning example圖1 路徑規劃柵格地圖模型圖例

2 基礎算法

2.1 GWO

GWO 是受灰狼的狩獵策略和社會等級啟發得到的算法?；依欠譃? 個等級，即阿爾法狼（α）、貝塔狼（β）、德爾塔狼（δ）和歐米茄狼（Ω），見圖2。領頭或占優勢的狼被稱為α 狼，數量最少，主要負責為群體作出決策，如打獵時間等，它們并不一定是最強的成員，但卻一定擁有最強的管理能力；狼群社會中第二等級的是β 狼，它們在許多活動或決策中協助α 狼，強化α 狼命令的執行，并向α 狼提供反饋；δ 狼服從α 狼和β 狼管理，但它們主宰著Ω 狼；Ω 狼是狼群中最低級的灰狼，它們總是屈從于其他類型的狼［9］。

Fig.2 Hierarchical structure of grey wolf population圖2 灰狼群體等級結構

灰狼群體的狩獵策略是其另一個重要特點：狼群會在α 狼的領導下識別獵物位置并將其包圍［15］。在灰狼的狩獵策略數學模型中，一般將最優秀的解決方案視為α，第二和第三最佳方案分別命名為β 和δ，其余命名為Ω。以下為灰狼捕獵機制的數學模型：

每次迭代后，新的灰狼組成員都會根據上一代α、β、δ狼（最優秀的三匹狼）更新位置，從而逐漸接近獵物，完成狩獵過程。

2.2 PSO

PSO 是Kennedy 和Eberhart［16］兩位學者受到動物社會行為（如鳥類、魚群的行為）啟發提出的用于求解各類復雜優化問題的算法。該算法最初用于研究鳥類的覓食行為，但在實際應用中發現其優化能力強大，尤其在多維空間中表現突出。

該算法設計了一種理想粒子，鳥群中的每一個體都被抽象成這種粒子，每個粒子只具有位置和速度兩種屬性，每一個體都會單獨搜尋最優解，并將其記為自身歷史最優位置，而這個粒子的自身歷史最優也會與整個群的其他粒子分享，全局最優解即為最優粒子的自身歷史最優。粒子的適應度（與目標的距離）決定了其優劣，適應度的計算公式根據問題的不同而不同。

PSO 的初始態是一群隨機分布的粒子，這些粒子各自會被初始化一個隨機速度，經過不斷迭代，最優解會逐漸產生。在迭代過程中，每個粒子都會根據其慣性、自身歷史最優位置和全局最優位置進行位置更新，公式如下：

式中，V 表示速度；ω 為用于平衡全局與局部的慣性因子，數值一般為非負；r1、r2為分布在［0，1］范圍內的隨機變量；c1、c2為學習因子，一般為非負數；Pib表示對應粒子的歷史最優位置；Pgb為全局最優位置。

值得一提的是，最初的PSO 很容易陷入局部最小，因此在算法中引入慣性權值ω，其值越高，粒子速度被保留得越好，能夠更快搜索整個解的區間，因此具有更強的全局尋優能力，但也會使局部尋優能力更弱，更容易錯過最優解，反之亦然。由于引入了ω，PSO 的適用性有了相當程度的提高，能應用于更多實際問題。

3 基于PSO改進的GWO

與大多數算法的改進方法不同，本文進行的改進不會使兩種算法一個接一個單獨進行計算，而是在運行過程中同時進行迭代進化，最終根據兩個不同變量同時參與的結果生成問題的最終解決方案。因此，改進算法具有優化的PSO 局部尋優能力與GWO 全局尋優能力。

首先是GWO 的α 狼、β 狼和δ 狼（3 個最佳方案）迭代中的位置更新公式優化，具體見式（14）-式（16）。由式（10）、式（11）可知，GWO 的全局尋優與局部尋優能力主要由控制因子a 調節，某些情況下，由于搜索過程過于復雜，a無法有效平衡算法局部尋優與全局尋優的側重。因此作為原方程式的替換，本文通過添加慣性權重ω控制GWO中全局尋優能力與局部尋優能力之間的平衡。

其次是將PSO 中的速度概念引入GWO 的位置和結果更新公式，具體見式（17）與式（18）。GWO 與PSO 不同，其在迭代過程中只考慮了α 狼、β 狼、δ 狼之間的關系與交流，忽略了自身經驗的影響。而PSO 是善于利用粒子自身屬性與信息的算法，因此在GWO 結果更新公式中融入PSO 的思想，能夠得到性能更加優秀的改進算法。

改進算法的具體流程如圖3所示。

Fig.3 Flow of improved algorithm圖3 改進算法流程

4 實驗結果與分析

實驗相關參數設置如表1 所示。其中，種群數量指計算過程中共有多少匹狼參與搜索過程；最大迭代次數指算法終止條件，當迭代次數達到最大時算法結束并輸出最優解；ω指每匹狼的慣性因子，選取經多次實驗后得到的較優數值；C1、C2、C3 為定義的3 個學習因子，在本次實驗中與r1、r2、r3 相關，r1、r2、r3 均根據研究經驗與實際驗證取值為0.5。

Table 1 Parameter setting表1 參數設置

PSO 改進的GWO（PSO-GWO）與GWO 在實驗樣例測試中得到的結果比較如圖4 所示。從圖中可以看出，PSOGWO 的初始適應度值小于GWO，收斂速度比GWO 也有明顯提高，最終得到的最優適應度值亦小于GWO，算法性能明顯提升。

Fig.4 Comparison of results between（PSO-GWO）and GWO in experimental sample test圖4 PSO-GWO與GWO在實驗樣例測試中的結果比較

PSO-GWO 與GWO 得到的路徑圖比較如圖5 所示?？梢钥闯觯珿WO 并未找到最優路徑，存在部分多余路徑，而經過改進后，PSO-GWO 能更加高效地對環境中的障礙進行分析，以更高的效率找到優于GWO 規劃結果的更短路徑。

為驗證改進算法的性能，在柵格地圖上隨機生成障礙物進行5 次仿真測試，分別記錄GWO 與PSO-GWO 的適應度與迭代次數。由表2 可知，PSO-GWO 比GWO 的適應度（路徑長度）平均減少了4 個單位，迭代次數平均減少56次。綜合分析可知，PSO-GWO 的性能更優、適應性更強，在大多數情況下都能獲得比GWO 更優的規劃路線。

Fig.5 Comparison of optimization paths between PSO-GWO and GWO圖5 PSO-GWO與GWO優化路徑比較

Table 2 Performance comparison between PSO-GWO and GWO表2 PSO-GWO與GWO性能比較

5 結語

針對機器人路徑規劃問題，本文提出采用PSO 改進GWO，獲得了比GWO 更優秀的性能，例如在大多數情況下能得到更好的初始適應度值，獲得適應度最優解和搜索最優解所需的迭代次數更少，說明改進算法具有良好的時間效率和較強的適應性。然而，該算法尚未在復雜多變的實際環境中進行測試，后續會將該算法應用于實際環境中路徑規劃問題的求解，檢驗其實際可用性與抗干擾性。