粒子群算法改進(jìn)灰狼算法的機器人路徑規(guī)劃

梁景泉，周子程，劉秀燕

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

0 引言

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

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

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

1 環(huán)境建模

機器人全局路徑規(guī)劃問題的描述為：對于一個給定的二維地形，存在著有限個障礙物，算法的任務(wù)就是找到一個令機器人能夠從起點到終點且安全不觸碰障礙物的路徑，并保證該路徑為全局最短路徑［14］。常見的環(huán)境建模方法有很多，如點集拓?fù)浞ā⒖梢晥D法和柵格法等，本文選用柵格法，其目標(biāo)函數(shù)可表示為：

式中，L 為路徑長度，np為路徑點個數(shù)，（xi，yi）為對應(yīng)路徑點的坐標(biāo)。

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

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

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

2 基礎(chǔ)算法

2.1 GWO

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

Fig.2 Hierarchical structure of grey wolf population圖2 灰狼群體等級結(jié)構(gòu)

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

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

2.2 PSO

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

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

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

式中，V 表示速度；ω 為用于平衡全局與局部的慣性因子，數(shù)值一般為非負(fù)；r1、r2為分布在［0，1］范圍內(nèi)的隨機變量；c1、c2為學(xué)習(xí)因子，一般為非負(fù)數(shù)；Pib表示對應(yīng)粒子的歷史最優(yōu)位置；Pgb為全局最優(yōu)位置。

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

3 基于PSO改進(jìn)的GWO

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

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

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

改進(jìn)算法的具體流程如圖3所示。

Fig.3 Flow of improved algorithm圖3 改進(jìn)算法流程

4 實驗結(jié)果與分析

實驗相關(guān)參數(shù)設(shè)置如表1 所示。其中，種群數(shù)量指計算過程中共有多少匹狼參與搜索過程；最大迭代次數(shù)指算法終止條件，當(dāng)?shù)螖?shù)達(dá)到最大時算法結(jié)束并輸出最優(yōu)解；ω指每匹狼的慣性因子，選取經(jīng)多次實驗后得到的較優(yōu)數(shù)值；C1、C2、C3 為定義的3 個學(xué)習(xí)因子，在本次實驗中與r1、r2、r3 相關(guān)，r1、r2、r3 均根據(jù)研究經(jīng)驗與實際驗證取值為0.5。

Table 1 Parameter setting表1 參數(shù)設(shè)置

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

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

PSO-GWO 與GWO 得到的路徑圖比較如圖5 所示。可以看出，GWO 并未找到最優(yōu)路徑，存在部分多余路徑，而經(jīng)過改進(jìn)后，PSO-GWO 能更加高效地對環(huán)境中的障礙進(jìn)行分析，以更高的效率找到優(yōu)于GWO 規(guī)劃結(jié)果的更短路徑。

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

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

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

5 結(jié)語

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