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

梁景泉，周子程，劉秀燕

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

0 引言

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

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

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

1 環(huán)境建模

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

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

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

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

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

2 基礎(chǔ)算法

2.1 GWO

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

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

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

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

2.2 PSO

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

PSO 改進(jìn)的GWO（PSO-GWO）與GWO 在實(shí)驗(yàn)樣例測(cè)試中得到的結(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在實(shí)驗(yàn)樣例測(cè)試中的結(jié)果比較

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

為驗(yàn)證改進(jìn)算法的性能，在柵格地圖上隨機(jī)生成障礙物進(jìn)行5 次仿真測(cè)試，分別記錄GWO 與PSO-GWO 的適應(yīng)度與迭代次數(shù)。由表2 可知，PSO-GWO 比GWO 的適應(yīng)度（路徑長(zhǎng)度）平均減少了4 個(gè)單位，迭代次數(shù)平均減少56次。綜合分析可知，PSO-GWO 的性能更優(yōu)、適應(yīng)性更強(qiá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é)語(yǔ)

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