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

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

中圖分類(lèi)號(hào)：TP 242" " " " " 文獻(xiàn)標(biāo)志碼：A

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

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

1 環(huán)境建立

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

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

2 粒子群算法

2.1 基本粒子群算法

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

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

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

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

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

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

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

慣性權(quán)重是影響算法全局搜索與局部搜索能力、收斂速度與精度的重要參數(shù)。當(dāng)種群處于進(jìn)化早期時(shí)，需要比較快的速度以便于全局搜索；當(dāng)種群處于進(jìn)化后期時(shí)，需要比較慢的速度以便于局部搜索。文獻(xiàn)[4]提出了一種非線性遞減的慣性權(quán)重系數(shù)，使粒子能更細(xì)致地搜索優(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ù)對(duì)權(quán)重系數(shù)的影響程度；β為指數(shù)函數(shù)的遞減速度；冪函數(shù)保證慣性權(quán)重在迭代初期較大，有助于全局搜索，在迭代后期較小，促進(jìn)局部搜索，加快收斂速度；指數(shù)函數(shù)??exp（-βk）提供了一種平滑的遞減方式，增強(qiáng)了搜索的適應(yīng)性。

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

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

（5）

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

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

（6）

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

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

（7）

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

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

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

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

3 蜣螂算法

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

3.1 滾球蜣螂

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

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

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

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

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

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

3.2 繁殖蜣螂

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

（11）

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

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

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

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

3.3 覓食蜣螂

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

（13）

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

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

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

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

3.4 偷竊蜣螂

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

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

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

3.5 萊維飛行

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

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

（16）

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

（17）

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

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

式中：w為積分變量。

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

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

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

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

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

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

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

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

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

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

粒子群算法 31.752 6 37.142 5 130.520 7

改進(jìn)粒子群蜣螂算法 27.102 5 32.576 5 110.254 1

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

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

[4]張萬(wàn)緒，張向蘭，李瑩.基于改進(jìn)粒子群算法的智能機(jī)器人路徑規(guī)劃[J].計(jì)算機(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.