基于改進(jìn)粒子群的混合金豺優(yōu)化算法的移動(dòng)機(jī)器人路徑規(guī)劃

常新中,岳哲鵬,郜海超,婁泰山,關(guān)廣勝

(1.河南應(yīng)用技術(shù)職業(yè)學(xué)院 學(xué)院辦公室,河南 鄭州 450042; 2.鄭州輕工業(yè)大學(xué) 電氣信息工程學(xué)院,河南 鄭州 450002)

隨著智能控制設(shè)備制造技術(shù)的發(fā)展以及傳感器技術(shù)的進(jìn)步,移動(dòng)機(jī)器人技術(shù)逐漸成為當(dāng)前的研究熱點(diǎn),在航天領(lǐng)域[1]、農(nóng)業(yè)[2-3]和工業(yè)[4]生產(chǎn)中發(fā)揮了重要的作用。移動(dòng)機(jī)器人在工作時(shí)需要根據(jù)一定的規(guī)則,在工作區(qū)域沿著一條最優(yōu)的路徑行走。因此,路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航的重要任務(wù)之一,也是目前研究的一個(gè)熱點(diǎn)[5]。路徑規(guī)劃所用的算法大致分為傳統(tǒng)算法和智能算法。傳統(tǒng)算法有A*算法[6]、Dijkstra算法[7]和禁忌搜索算法[8]等,但是這些算法往往存在計(jì)算效率低、路徑搜索能力差等缺點(diǎn),無(wú)法滿足技術(shù)發(fā)展的需求。智能算法具有算法簡(jiǎn)單、魯棒性強(qiáng)等特點(diǎn),在規(guī)劃路徑時(shí)不必依賴梯度信息[9]。于是,智能算法逐漸成為了當(dāng)前的研究熱點(diǎn)。智能算法被廣泛應(yīng)用于水下機(jī)器人、移動(dòng)機(jī)器人和無(wú)人機(jī)等裝備的路徑規(guī)劃中[10-12],但是其在尋優(yōu)時(shí)會(huì)陷入局部最優(yōu)而導(dǎo)致搜尋路徑不是最短的問(wèn)題。為此,國(guó)內(nèi)外學(xué)者近年來(lái)一直在不斷地探索新的智能算法,并對(duì)其進(jìn)行了一定的研究與應(yīng)用。宋阿妮等采用精英策略來(lái)改進(jìn)蟻群的信息素濃度,提高蟻群算法跳出局部最優(yōu)的能力,并引入信息素?cái)U(kuò)散策略來(lái)加強(qiáng)個(gè)體之間的交流,提高了算法在無(wú)人機(jī)三維路徑規(guī)劃中的適應(yīng)性[13]。魏博等通過(guò)模擬粒子運(yùn)動(dòng)規(guī)律來(lái)更新蜂群位置,提高算法的種群開(kāi)發(fā)能力,并利用反向輪盤(pán)賭的方法選擇蜜源,解決了人工蜂群在路徑規(guī)劃中迭代速度慢、規(guī)劃效率低的問(wèn)題[14]。劉志強(qiáng)等通過(guò)Tent混沌映射來(lái)提升灰狼算法的種群豐富性,并融合動(dòng)態(tài)權(quán)重因子和適應(yīng)度系數(shù)更新灰狼的個(gè)體位置,提高灰狼算法的全局搜索能力,降低了搜索成本[15]。

隨著智能算法的不斷拓展,許多優(yōu)秀算法被提出并得到了應(yīng)用。其中,金豺優(yōu)化(Golden Jackal Optimization,GJO)算法是由Chopra和Ansari在2022年提出的一種新型智能算法[16]。GJO算法模擬了金豺狼捕獵的過(guò)程,具有較強(qiáng)的尋優(yōu)能力、較高的收斂速度,受到了眾多學(xué)者的關(guān)注。謝豪等將GJO算法應(yīng)用于PID的參數(shù)優(yōu)化過(guò)程,利用GJO算法對(duì)PID的3個(gè)參數(shù)進(jìn)行設(shè)置并使其向最優(yōu)解迭代,提高了系統(tǒng)的調(diào)節(jié)能力[17]。Mahdy等將GJO算法應(yīng)用到超級(jí)充電站的運(yùn)行優(yōu)化中,利用GJO算法對(duì)PI增益進(jìn)行優(yōu)化,提高了系統(tǒng)的穩(wěn)定性[18]。Najjar等將GJO算法與長(zhǎng)短期記憶神經(jīng)網(wǎng)絡(luò)模型相結(jié)合,預(yù)測(cè)了Cu-Al2O3的摩擦學(xué)性能[19]。從實(shí)驗(yàn)結(jié)果來(lái)看,該算法對(duì)復(fù)合材料的磨損率和摩擦系數(shù)變化具有出色的預(yù)測(cè)能力。

GJO算法雖然在眾多領(lǐng)域都有較為出色的表現(xiàn),但仍然存在會(huì)陷入局部最優(yōu)、收斂速度慢以及未考慮金豺個(gè)體之間的經(jīng)驗(yàn)交流等問(wèn)題。因此,本文對(duì)粒子群優(yōu)化(Particle Swarm Optimization,PSO)[20]算法進(jìn)行改進(jìn)并將其引入GJO算法,優(yōu)化GJO算法的位置更新過(guò)程,提出一種改進(jìn)粒子群的混合金豺優(yōu)化(Hybrid Golden Jackal Optimization,HGJO)算法。同時(shí),將該算法應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃,并通過(guò)路徑規(guī)劃問(wèn)題的仿真實(shí)驗(yàn)驗(yàn)證該改進(jìn)算法的有效性與可行性。

1 移動(dòng)機(jī)器人的環(huán)境建模

利用智能算法對(duì)移動(dòng)機(jī)器人進(jìn)行的路徑規(guī)劃包括下列兩個(gè)基本步驟:一是針對(duì)機(jī)器人所處環(huán)境進(jìn)行建模;二是利用智能算法對(duì)路徑進(jìn)行反復(fù)迭代,以獲取最短路徑。只有在了解周圍的環(huán)境信息后才能進(jìn)行移動(dòng)機(jī)器人的路徑規(guī)劃。合理構(gòu)建環(huán)境地圖是獲取最優(yōu)規(guī)劃結(jié)果的前提。經(jīng)典的環(huán)境地圖表示方法有柵格法、可視圖法、距離轉(zhuǎn)換法、自由空間法等。與其他方法相比,柵格法具有實(shí)現(xiàn)簡(jiǎn)單、數(shù)據(jù)易于轉(zhuǎn)換等優(yōu)點(diǎn),被廣泛地應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃中。

圖1 采用柵格法建立的移動(dòng)機(jī)器人二維平面模型

2 金豺優(yōu)化算法

金豺優(yōu)化算法是根據(jù)金豺探索行為和狩獵行為進(jìn)行建模的。它包括探索階段和狩獵階段。

(1) 探索階段:金豺?qū)ふ也⒏櫕C物。金豺天生就會(huì)發(fā)現(xiàn)并追逐獵物,且往往是雄豺狩獵而雌豺跟隨的。獵物并不容易被捕獲,有時(shí)會(huì)逃逸。雄豺與獵物相對(duì)位置的變化情況可表示為:

Y1(1)=YM(t)-E·|YM(t)-rl·Prey(t)|

(1)

式中:YM(t)為雄豺的位置;rl·Prey(t)為獵物的運(yùn)動(dòng)軌跡;t為當(dāng)前迭代次數(shù)。

雌豺與獵物相對(duì)位置的變化情況可表示為:

Y2(1)=YFM(t)-E·|YFM(t)-rl·Prey(t)|

(2)

式中:YFM(t)為雌豺的位置。

(2) 狩獵階段:當(dāng)獵物受到金豺騷擾后,其逃逸能量就會(huì)開(kāi)始減少。隨后,金豺開(kāi)始包圍獵物。金豺在包圍獵物后就會(huì)撲向獵物并吃掉獵物。獵物逃跑過(guò)程的能量E可表示為:

E=E1E0

(3)

獵物的初始能量為:

E0=2a-1

(4)

式中:a為0到1之間的隨機(jī)值。

獵物逃逸時(shí)的能量為:

E1=C(1-t/T)

(5)

式中:C為恒定值,且C=1.5;T為最大迭代次數(shù)。在迭代時(shí),E1是從1.5按線性減少到0的。

萊維分布函數(shù)為:

rl=0.05LF(y)

(6)

萊維飛行函數(shù)為:

LF(y)=0.01μσ/|ν1/β|

(7)

GJO算法的位置更新公式為:

(8)

針對(duì)金豺狩獵行為,可建立下列模型:

(9)

式中:Prey(t)為獵物在t時(shí)刻的位置。

金豺從探索階段向狩獵階段轉(zhuǎn)換的條件是由E決定的。具體而言,當(dāng)|E|>1時(shí),金豺會(huì)進(jìn)行探索并尋找獵物;當(dāng)|E|<1時(shí),金豺會(huì)撲向獵物。

3 改進(jìn)粒子群的混合金豺優(yōu)化算法

PSO算法是利用粒子自身最優(yōu)位置和群體最優(yōu)位置來(lái)獲取最優(yōu)解的。其基本表達(dá)式為:

(10)

PSO算法雖然可以快速收斂,但是容易陷入局部最優(yōu)中。為了避免這一現(xiàn)象,本文將自適應(yīng)動(dòng)態(tài)權(quán)重因子w(t)和改進(jìn)的學(xué)習(xí)因子引入PSO算法,對(duì)PSO算法進(jìn)行改進(jìn),并將改進(jìn)后PSO算法引入GJO算法中。改進(jìn)粒子群的混合金豺優(yōu)化算法表達(dá)式為:

(11)

(12)

式中:wmax為初始慣性權(quán)重;wmin為最終慣性權(quán)重。當(dāng)?shù)_(kāi)始時(shí),混合金豺優(yōu)化算法以全局搜索最優(yōu)為主,其權(quán)重因子取值較大;隨著迭代次數(shù)的增加,其權(quán)重因子取值逐漸減小,局部搜索能力逐漸上升。

局部學(xué)習(xí)因子a1(t)和全局學(xué)習(xí)因子a2(t)分別表示個(gè)體經(jīng)驗(yàn)與群體中其他粒子經(jīng)驗(yàn)對(duì)整個(gè)粒子群運(yùn)動(dòng)模式的影響。當(dāng)a1(t)取值較大時(shí),個(gè)體對(duì)群體有較大的影響,導(dǎo)致算法收斂變慢;反之,當(dāng)a2(t)取值較大時(shí),群體會(huì)迅速喪失多樣性,導(dǎo)致算法陷入局部最優(yōu)。因此,需對(duì)學(xué)習(xí)因子進(jìn)行改進(jìn)。更為靈活的學(xué)習(xí)因子表達(dá)式為:

(13)

式中:a1e和a2e分別為局部學(xué)習(xí)因子和全局學(xué)習(xí)因子的終值;a1b和a2b分別為局部學(xué)習(xí)因子和全局學(xué)習(xí)因子的初值。

改進(jìn)粒子群的HGJO算法的位置更新公式為:

(14)

式中,γ取值為0.4。

改進(jìn)粒子群的HGJO算法流程如圖2所示。該算法流程包括8個(gè)步驟。

圖2 改進(jìn)粒子群的HGJO算法流程

Step1:生成柵格地圖并初始化位置坐標(biāo),設(shè)置起點(diǎn)和終點(diǎn);設(shè)置初始種群數(shù)量N、最大迭代次數(shù)T、維數(shù)d和初始速度等參數(shù)。

Step2:種群初始化,并在之后計(jì)算種群中各金豺的適應(yīng)度。

Step3:按照適應(yīng)度從大到小排序,選取最優(yōu)的金豺作為雄豺,次優(yōu)的金豺作為雌豺;與之對(duì)應(yīng)的位置信息分別為YM(t)和YFM(t)。

Step4:根據(jù)式(3)和式(7)計(jì)算獵物逃跑過(guò)程的能量E和萊維飛行函數(shù)。

Step5:按照式(12)和(13)計(jì)算自適應(yīng)動(dòng)態(tài)權(quán)重因子w(t)和學(xué)習(xí)因子a1(t)、a2(t)。

Step6:根據(jù)式(11)計(jì)算下一次迭代的速度Vi(t+1)。

Step7:由式(14)來(lái)更新種群的位置,并重新計(jì)算其適應(yīng)度。

Step8:判斷當(dāng)前迭代次數(shù)是否達(dá)到最大迭代次數(shù),若達(dá)到則輸出最優(yōu)解,反之循環(huán)Step2-Step7。

4 移動(dòng)機(jī)器人路徑規(guī)劃的仿真實(shí)驗(yàn)

為驗(yàn)證所提出算法的有效性,本文將其應(yīng)用在了移動(dòng)機(jī)器人的路徑規(guī)劃仿真實(shí)驗(yàn)中。使用的仿真軟件為Matlab 2021b,計(jì)算機(jī)配置為Intel(R)Xeon(R)CPU E3-1225 V2@3.20 GHz,內(nèi)存為8.00 GB。實(shí)驗(yàn)中,通過(guò)構(gòu)建30×30的柵格地圖來(lái)模擬大范圍隨機(jī)分布障礙物的情況。針對(duì)HGJO算法、GJO算法和PSO算法分別進(jìn)行了30次獨(dú)立實(shí)驗(yàn)。這3種算法的種群數(shù)量N=50個(gè),最大迭代次數(shù)T=500。3種算法的詳細(xì)參數(shù)如表1所示。

表1 3種算法的詳細(xì)參數(shù)

針對(duì)機(jī)器人路徑規(guī)劃的3種算法進(jìn)行了仿真實(shí)驗(yàn)。其結(jié)果如表2所示。圖3所示為3種算法針對(duì)30×30柵格地圖的規(guī)劃路徑。圖4所示為3種算法的仿真收斂曲線。

表2 針對(duì)機(jī)器人路徑規(guī)劃的3種算法的仿真實(shí)驗(yàn)結(jié)果

圖3 3種算法針對(duì)30×30柵格地圖的規(guī)劃路徑

圖4 3種算法的仿真收斂曲線

從表2和圖3可知:HGJO算法相比GJO算法在平均路徑長(zhǎng)度上縮短了1.920%,這是因?yàn)镠GJO算法比GJO算法最長(zhǎng)路徑的長(zhǎng)度小,能夠獲得較為優(yōu)秀的平均路徑長(zhǎng)度;與PSO算法相比,HGJO算法更為穩(wěn)定,在最長(zhǎng)路徑的長(zhǎng)度上沒(méi)有發(fā)生過(guò)大的情況;從運(yùn)行時(shí)間上來(lái)說(shuō),HGJO算法所需運(yùn)行時(shí)間最少,這從一個(gè)側(cè)面說(shuō)明所提出算法具有一定的競(jìng)爭(zhēng)能力;從標(biāo)準(zhǔn)差來(lái)看,HGJO算法的標(biāo)準(zhǔn)差較小,這表明HGJO算法具有較好的穩(wěn)定性。

從圖4可以看出:HGJO算法能夠多次跳出局部最優(yōu)陷阱,比GJO算法有更強(qiáng)的全局搜索能力;HGJO算法能收斂到全局最優(yōu)值,且具有較高的收斂精度。

5 結(jié)語(yǔ)

針對(duì)金豺優(yōu)化算法在移動(dòng)機(jī)器人路徑規(guī)劃應(yīng)用過(guò)程存在的迭代效率低以及會(huì)陷入局部最優(yōu)等問(wèn)題,本文提出一種改進(jìn)粒子群的混合金豺優(yōu)化算法。利用自適應(yīng)動(dòng)態(tài)權(quán)重因子和改進(jìn)的學(xué)習(xí)因子,對(duì)粒子群算法進(jìn)行改進(jìn)并將其引入GJO算法的位置更新中,能夠改善算法跳出局部最優(yōu)的性能。對(duì)移動(dòng)機(jī)器人路徑規(guī)劃的仿真實(shí)驗(yàn)證明:本文提出的算法在運(yùn)行時(shí)間上和收斂結(jié)果上都優(yōu)于GJO算法;在平均路徑長(zhǎng)度方面,本文提出的HGJO算法比GJO算法縮短了1.920%。仿真實(shí)驗(yàn)結(jié)果表明,HGJO算法是可靠和實(shí)用的。