基于改進粒子群蜣螂算法的機器人路徑規(guī)劃研究

摘 要：在機器人路徑規(guī)劃中，粒子群算法（Particle Swarm Optimization，PSO）是一種常用的算法。然而在迭代后期粒子群算法會出現(xiàn)粒子多樣性下降和易陷入局部最優(yōu)解的情況。為解決以上問題，本文提出了一種改進的粒子群蜣螂算法。建立柵格地圖模型對機器人進行路徑規(guī)劃，在粒子群算法中加入動態(tài)非線性調(diào)整慣性權(quán)重系數(shù)，引入懲罰系數(shù)來建立適應(yīng)度函數(shù)，并與引入了萊維飛行進行改進的蜣螂算法相結(jié)合，以增強算法的搜索能力。試驗仿真結(jié)果表明，與已有的粒子群算法相比，本文提出的改進粒子群蜣螂算法適用性更強，能夠找到更短的最優(yōu)路徑。

關(guān)鍵詞：路徑規(guī)劃；蜣螂算法；粒子群算法；萊維飛行

中圖分類號：TP 242" " " " " 文獻標(biāo)志碼：A

移動機器人在各個領(lǐng)域中得到廣泛應(yīng)用，其導(dǎo)航的核心環(huán)節(jié)是路徑規(guī)劃，具有重要的研究價值。針對路徑規(guī)劃問題，目前已有的方法包括Dijkstra算法、改進A*算法和快速擴展隨機樹（Rapidly-exploring Random Tree， RRT*）算法等。群體智能算法優(yōu)化也應(yīng)用于路徑規(guī)劃領(lǐng)域，例如魏冠偉[1]提出的改進型人工神經(jīng)網(wǎng)絡(luò)，王梓強[2]提出的改進遺傳算法，趙甜甜[3]提出的改進粒子群（Particle Swarm Optimization，PSO）算法等。

這些方法雖然提高了路徑規(guī)劃質(zhì)量，但是仍然存在不足，尤其是粒子群算法容易陷入局部最優(yōu)。因此，本文提出一種改進的粒子群蜣螂算法，利用迭代次數(shù)動態(tài)調(diào)整粒子群的慣性權(quán)重，引入萊維飛行對蜣螂偷竊行為進行改進，提高算法的搜索能力。結(jié)合粒子群的全局搜索和蜣螂算法的局部優(yōu)化來規(guī)劃最優(yōu)路徑。

1 環(huán)境建立

本文采用柵格地圖構(gòu)建移動機器人的工作環(huán)境，20 m×

20 m格柵地圖如圖1所示，白色柵格為自由柵格，黑色柵格為障礙物柵格，每個白色柵格均可選中成為路徑點，將機器人簡化為1個很小的質(zhì)點。路徑規(guī)劃的任務(wù)是在有障礙物的環(huán)境中為機器人找到1條從起點至終點的最優(yōu)路徑。

2 粒子群算法

2.1 基本粒子群算法

粒子群算法起源于模擬魚類或鳥類的覓食行為，假設(shè)在D維空間中有m個粒子，在第k次迭代中第i個粒子的位置向量為xik=（xk i1，xk i2，...，xk id），其中i=1，2，…，m。粒子的速度用向量表示為vik=（vk i1，vk i2，...，vk id），其中i=1，2，…，m。粒子根據(jù)自身的位置向量、速度向量、每個粒子的歷史信息以及種群信息在算法迭代的過程中不斷更新自己的位置。

算法更新過程如公式（1）、公式（2）所示。

=ω+c1r1（Pbest-）+c2r2（Gbest-） （1）

式中：vk+1 id 為當(dāng)?shù)趉+1次迭代時第i個粒子的速度，k為迭代次數(shù)；ω為慣性權(quán)重；vk id為當(dāng)?shù)趉次迭代時第i個粒子的速度；c1為粒子群算法中的學(xué)習(xí)因子；r1為分布在[0～1]的隨機數(shù)；Pbest為個體已知最優(yōu)解；xk id為第k次迭代時第i個粒子的位置；c2為粒子群算法中的學(xué)習(xí)因子； r2為分布在[0～1]的隨機數(shù)；Gbest為群體已知最優(yōu)解。

=+ " " " " " " " " " " " " " "（2）

式中：xk+1 id為第k+1次迭代第i個粒子的位置。

2.2 動態(tài)非線性遞減慣性權(quán)重

慣性權(quán)重是影響算法全局搜索與局部搜索能力、收斂速度與精度的重要參數(shù)。當(dāng)種群處于進化早期時，需要比較快的速度以便于全局搜索；當(dāng)種群處于進化后期時，需要比較慢的速度以便于局部搜索。文獻[4]提出了一種非線性遞減的慣性權(quán)重系數(shù)，使粒子能更細致地搜索優(yōu)化目標(biāo)，如公式（3）所示。

（3）

式中：ωmax、ωmin為慣性權(quán)重的最大值和最小值；K為最大迭代次數(shù)。

本文算法在公式（3）的基礎(chǔ)上添加了自適應(yīng)因子，如公式（4）所示。

（4）

式中：ωk+1第k+1次迭代的慣性權(quán)重；ωk為第k次迭代的慣性權(quán)重；n為調(diào)節(jié)參數(shù)；?為指數(shù)函數(shù)對權(quán)重系數(shù)的影響程度；β為指數(shù)函數(shù)的遞減速度；冪函數(shù)保證慣性權(quán)重在迭代初期較大，有助于全局搜索，在迭代后期較小，促進局部搜索，加快收斂速度；指數(shù)函數(shù)??exp（-βk）提供了一種平滑的遞減方式，增強了搜索的適應(yīng)性。

2.3 適應(yīng)度函數(shù)

路徑規(guī)劃的目標(biāo)是找到1條最短且比較平滑的路徑，該路徑能夠避開所有障礙物，并連接起點和終點。路徑長度的計算過程如公式（5）所示。

（5）

式中：f1為1個粒子與其所有相鄰點之間距離的和；d為當(dāng)前粒子位置；xi、yi為粒子現(xiàn)在的坐標(biāo)，i為粒子起始位置；xi+1、yi+1為粒子下一個位置的坐標(biāo)。

為減少機器人與障礙物的碰撞次數(shù)，本文引入懲罰函數(shù)。當(dāng)機器人與障礙物碰撞時懲罰因子變大時，生成碰撞路徑的概率變小，懲罰函數(shù)f2如公式（6）所示。

（6）

式中：N為生成的路線和障礙物的碰撞次數(shù)；M為1個較大的常數(shù)。

路徑的平滑程度是在路徑規(guī)劃中的1個重要指標(biāo)，因此引入路徑平滑程度，避免機器人路徑波動過大。路徑平滑程度計算過程如公式（7）所示。

（7）

式中：f3為生成路線上夾角值之和，其和越小，平滑度越高；Pi+1、Pi和Pi-1分別為第i+1、i和i-1個粒子的坐標(biāo)。

綜合所得適應(yīng)度函數(shù)f如公式（8）所示。

f=η?f1+ε?f2+γ?f3 " " " "（8）

式中：η、ε和γ分別為各自函數(shù)的加權(quán)因子，范圍均為0～1，η+ε+γ=1。

3 蜣螂算法

蜣螂算法（Dung Beetle Optimizer，DBO）[5]靈感來自蜣螂的不同行為。算法將種群劃分為滾球、覓食、繁衍和偷竊4個組群分別進行優(yōu)化。4種蜣螂種群的分布如圖2所示。

3.1 滾球蜣螂

滾球蜣螂可分為無障礙模式和障礙模式2種工作模式。當(dāng)采用無障礙模式時蜣螂的位置更新公式如公式（9）所示。

xit+1=xit+α?ξ?xit-1+b?|xit-xtworst| " " " " （9）

式中：xit+1為當(dāng)?shù)趖+1次迭代時蜣螂的位置；xit為當(dāng)?shù)趖次迭代時第i只蜣螂的位置；t為當(dāng)前迭代次數(shù)；α為自然系數(shù)，取-1或1，當(dāng)α為-1時與原方向偏離，當(dāng)α為1時與原方向無偏差；ξ為偏轉(zhuǎn)系數(shù)，ξ∈（0，0.2）；xit-1為當(dāng)?shù)趖-1次迭代時蜣螂的位置；b為常數(shù)，b∈（0，1），本文中為0.3；xtworst為適應(yīng)度最差的蜣螂位置；|xit-xtworst|為模擬光強的變化。

當(dāng)有障礙物時蜣螂的位置更新過程如公式（10）所示。

xit+1=xit+tanθ|xit-xit-1| " " " （10）

式中： θ為隨機數(shù)，θ∈[0，π]；tanθ為遇到障礙后蜣螂重新調(diào)整的方向，當(dāng)或π時，不更新當(dāng)前位置。

3.2 繁殖蜣螂

DBO利用雌蜣螂的產(chǎn)卵行為來模擬算法中種群的繁殖過程，其繁殖是根據(jù)邊界選擇策略進行模擬的，如公式（11）所示。

（11）

式中：Lb*、Ub*分別為產(chǎn)卵區(qū)的上邊界與下邊界；xtgbest為當(dāng)前局部最優(yōu)位置；T為最大迭代次數(shù)；Lb、Ub分別為搜索空間的上邊界和下邊界。

根據(jù)公式（11）可知，蜣螂的繁殖區(qū)域會隨著迭代進行調(diào)整，繁殖蜣螂的位置也進行調(diào)整，如公式（12）所示。

Bit+1=xtgbest+b1?（Bit-Lb*）+b2?（Bit-Ub*） （12）

式中：Bit+1為當(dāng)?shù)趖+1次迭代時第i個子代的位置；b1、b2為2個大小為1×D的獨立隨機向量，D為維數(shù)；Bit為第i個子代當(dāng)?shù)趖次迭代時的位置。

3.3 覓食蜣螂

小蜣螂成熟后會尋找食物，覓食區(qū)域的更新過程如公式（13）所示。

（13）

式中： Lbl、Ubl分別為最優(yōu)覓食區(qū)域的下邊界和上邊界；xtlbest為當(dāng)前種群局部最優(yōu)位置。

小蜣螂的位置更新過程如公式（14）所示。

xit+1=xit+C1?（xit-Lbl）+C2?（xit-Lbl） " " （14）

式中：C1為服從正態(tài)分布的隨機數(shù)，即C1～N（0，1）；C2為1×D∈（0，1）的隨機向量。

3.4 偷竊蜣螂

有一些蜣螂會偷竊種群中其他蜣螂的食物，偷竊蜣螂位置更新定義如公式（15）所示。

xit+1=xtlbest+S?g?（|xit-xtgbest|+|xit-xtbest|） " "（15）

式中：S為常數(shù)值；g為1×D的隨機向量。

3.5 萊維飛行

萊維飛行是一種隨機行走，其步數(shù)是由步長決定的。萊維飛行是一種非高斯的隨機過程，其具有遍歷性和隨機性，其平穩(wěn)增量服從萊維分布。其主要原理是模擬自然界中昆蟲的飛行行為，即無規(guī)則地向任意方向前進任意距離。該行為能夠擴大搜索范圍，提升效率。

根據(jù)偷竊蜣螂的位置更新公式可知，其搜索步長為固定值，可能會陷入局部最優(yōu)。因此引入萊維飛行可以有效提高算法的全局搜索能力，防止種群陷入局部最優(yōu)。根據(jù)Mantegna方法，萊維分布的步長如公式（16）所示。

（16）

式中：λ為萊維分布的參數(shù)，取值為1≤λ≤3，λ一般取值為1.5；u、v為服從正態(tài)分布的隨機變量，如公式（17）所示。

（17）

式中：u∶N（0，σu2）為均值為0、方差為σu2的正態(tài)分布隨機變量；v∶N（0，σu2）為均值為0、方差為σv2的正態(tài)分布隨機變量；Γ為伽馬函數(shù)；Γ的計算方法如公式（18）所示。

Γ（1+λ）=∫0∞wλe-1dw " " " " " "（18）

式中：w為積分變量。

引入萊維飛行后蜣螂偷竊位置更新如公式（19）所示。

xit+1=Levy（λ）?xtlbest+S?g?（|xit-xtgbest|+|xit-xtbest|） （19）

4 試驗仿真和結(jié)果分析

為了驗證文中提出的改進粒子群蜣螂算法在路徑規(guī)劃問題中的有效性，與傳統(tǒng)粒子群算法進行對比。采用柵格法構(gòu)建1張環(huán)境大小為 20 m×20 m的地圖，其中黑色區(qū)域為障礙物，白色區(qū)域為自由區(qū)域。相鄰柵格距離為1 m。坐標(biāo)（0，0）為原點，從左上角至右下角依次編號，坐標(biāo)（1，1）為起點，坐標(biāo)（20，20）為終點。

本文在粒子群算法的基礎(chǔ)上融合了蜣螂優(yōu)化算法中的蜣螂滾球、繁殖、覓食和偷竊行為，結(jié)合了粒子群算法和蜣螂算法的優(yōu)點。具體操作步驟如下。1）確定地圖各個節(jié)點的坐標(biāo)位置。2）初始化參數(shù)，將種群劃分為4個子群，設(shè)定粒子速度和位置。3）計算粒子的適應(yīng)度并根據(jù)適應(yīng)度值更新粒子最優(yōu)解以及全局最優(yōu)解。4）更新慣性權(quán)重。5）根據(jù)融合了萊維飛行的蜣螂算法對各個子群進行位置更新。6）判斷是否滿足終止條件，如果是，那么算法結(jié)束并輸出結(jié)果，否則返回第三步。

在同一張柵格地圖中對2種算法進行試驗，其路徑規(guī)劃比較如圖3所示，黑色直線表示2種算法生成的路徑軌跡。由圖3可知，2種算法都到達目標(biāo)點，但是粒子群算法規(guī)劃的路徑長度更長，路徑波動更明顯。在路徑規(guī)劃中，采用本文算法，路徑平滑程度更高，路徑長度更短。

粒子群與改進粒子群蜣螂算法對比如圖4所示，由圖4可知，與傳統(tǒng)粒子群算法相比，改進粒子群蜣螂算法在收斂速度和最優(yōu)值方面都具有明顯優(yōu)勢。在迭代初期，改進粒子群蜣螂算法收斂速度更快，最終找到了更優(yōu)的解，說明改進算法在全局搜索和局部優(yōu)化方面均優(yōu)于傳統(tǒng)算法。

將2種算法各自運行50次，結(jié)果見表1。

表1 2種算法結(jié)果對比

算法 最優(yōu)路徑 均值 方差

粒子群算法 31.752 6 37.142 5 130.520 7

改進粒子群蜣螂算法 27.102 5 32.576 5 110.254 1

由上文可知，與本文算法的最優(yōu)路徑相比，原粒子群算法的最優(yōu)路徑更短，方差更小，穩(wěn)定性更高，其生成的路徑更適于機器人的路徑規(guī)劃。

5 結(jié)論

在機器人路徑規(guī)劃問題中，傳統(tǒng)的粒子群算法存在迭代后期粒子多樣性下降、容易陷入局部最優(yōu)解等問題，本文提出一種改進粒子群蜣螂算法。采用動態(tài)非線性慣性權(quán)重，引入懲罰系數(shù)建立適應(yīng)度函數(shù)；在粒子群算法中融合蜣螂優(yōu)化算法中的滾球、繁殖、覓食和偷竊行為，結(jié)合萊維飛行來優(yōu)化全局搜索能力，采用劃分子群的方法提高算法性能。仿真和分析結(jié)果表明，與傳統(tǒng)粒子群算法相比，本文算法在移動機器人路徑規(guī)劃中生成的路徑平滑度更高，距離更短，適用性更強。

參考文獻

[1]魏冠偉，付夢印.基于神經(jīng)網(wǎng)絡(luò)的機器人路徑規(guī)劃算法[J].計算機仿真，2010，27（7）：112-116.

[2]王梓強，胡曉光，李曉筱，等.移動機器人全局路徑規(guī)劃算法綜述[J].計算機科學(xué)，2021，48（10）：19-29.

[3]趙甜甜，王思明.基于改進PSO算法的移動機器人路徑規(guī)劃[J].傳感器與微系統(tǒng)，2018，37（2）：57-60.

[4]張萬緒，張向蘭，李瑩.基于改進粒子群算法的智能機器人路徑規(guī)劃[J].計算機應(yīng)用，2014，34（2）：510-513.

[5]XUE J K，SHEN B.Dung" bele" optimizer：a" new" metaheuristic

algorithm for global optimization[J]. The Journal of Supercomputing，

2023，79（7）：7305?7336.