基于改進(jìn)野馬優(yōu)化算法的AGV路徑規(guī)劃*

李一銘，王跟成

(西藏民族大學(xué)信息工程學(xué)院，咸陽 712082)

0 引言

自動導(dǎo)引運(yùn)輸車(automated guided vehicle，AGV)路徑規(guī)劃問題是搜索一條從起始位置到目標(biāo)位置的最優(yōu)路徑問題。傳統(tǒng)的AGV路徑規(guī)劃策略有A*算法[1]、人工視場算法[2]和dijkstra算法[3]等，隨著智能仿生算法的發(fā)展和應(yīng)用，國內(nèi)外學(xué)者將蟻群算法(ACO)[4]、麻雀搜索算法(SSA)[5]等應(yīng)用于AGV路徑規(guī)劃。郭鵬等[6]提出一種并行搜索的遺傳算法，融合遺傳算法和雙向A*算法的基礎(chǔ)上，使用自適應(yīng)函數(shù)改進(jìn)遺傳算法的收斂性能，但算法的復(fù)雜度較高且運(yùn)行速度較慢；屈新懷等[7]提出一種靠近目標(biāo)粒子群算法，通過障礙物頂點劃分坐標(biāo)系，引入Metropolis準(zhǔn)則，使算法具備跳出局部最優(yōu)解的能力，通過自適應(yīng)引力系數(shù)，使算法在靠近目標(biāo)時搜索速度加快，進(jìn)一步加快算法收斂速度；劉暢等[8]提出一種改進(jìn)自適應(yīng)遺傳算法，通過引入逆轉(zhuǎn)算子和插入算子控制算法的進(jìn)化方向，算法的全局搜索能力有一定的提升，但算法后期收斂速度較慢。

本文提出一種基于改進(jìn)野馬優(yōu)化算法的AGV路徑規(guī)劃方法。首先在二維空間上構(gòu)建解空間，然后利用改進(jìn)野馬優(yōu)化算法進(jìn)行路徑搜索。通過引入非線性自適應(yīng)因子和黃金正弦分割系數(shù)提高算法路徑規(guī)劃能力，結(jié)合偏移進(jìn)化策略和發(fā)現(xiàn)者位置更新方式對算法提高了算法放牧行為位置更新的多樣性。由于優(yōu)化算法生成路徑拐點過多，使用3次B樣條曲線平滑路徑的同時減少路徑長度。通過仿真實驗對比不同的路徑規(guī)劃策略，結(jié)果表明本文算法提高了AGV路徑規(guī)劃的平滑性和性能，能夠減少5.84%的AGV路徑規(guī)劃長度，具有較高的算法收斂精度和運(yùn)行效率。

1 環(huán)境建模

出于模擬需要，通過柵格法[2]在二維平面上構(gòu)建解空間，搭建20×20柵格地圖環(huán)境，將障礙物定義為黑色不可行區(qū)域，白色柵格為可行區(qū)域作為路徑的生成節(jié)點。搜索最優(yōu)路徑規(guī)劃問題轉(zhuǎn)化為在柵格地圖的可視化基礎(chǔ)上，尋找一條從起始位置出發(fā)到目標(biāo)位置的最短路徑問題。柵格二維空間環(huán)境模型如圖1所示。

圖1 柵格地圖環(huán)境

2 野馬優(yōu)化算法

野馬優(yōu)化算法[9]模擬野馬種群的生活行為和繁衍行為。該算法中野馬群通常以一匹領(lǐng)導(dǎo)者、幾匹母馬和小馬駒的群居活動方式。野馬群的位置狀態(tài)分為位于領(lǐng)土位置中和位于非領(lǐng)土位置。通常領(lǐng)導(dǎo)者會出現(xiàn)在靠近母馬的地方以進(jìn)行交流。為了防止近親交配，小馬駒在青春期前離開他們的父母群體，其中公馬會加入到單一種群逐漸成熟到可以完成交配。野馬種群中最重要的是領(lǐng)導(dǎo)者，其決定種群在自由放養(yǎng)的非領(lǐng)地區(qū)域的移動方向和速度。

小馬駒通常大部分時間都在吃草，認(rèn)為領(lǐng)導(dǎo)者的位置為放牧區(qū)的中心，種群成員在以領(lǐng)導(dǎo)者為圓心進(jìn)行中心搜索，其表達(dá)式為：

(1)

式中，Stallion為領(lǐng)導(dǎo)者的位置；R為取值[-2,2]之間的隨機(jī)數(shù)，主要用來控制個體與領(lǐng)導(dǎo)者的角度。自適應(yīng)機(jī)制Z的計算表達(dá)式為：

P=R1

(2)

式中，P是由0和1組成的向量；R1和R3為[0,1]空間內(nèi)均勻分布的隨機(jī)向量；R2為取值[0,1]之間的隨機(jī)數(shù)。滿足條件(P==0)的隨機(jī)向量R1返回IDX索引；TDR為自適應(yīng)因子，從1線性遞減為0，表達(dá)式如下：

TDR=1-t×(1/Tmax)

(3)

交配行為由分配入臨時組且來自不同族群的青春期小馬駒交配產(chǎn)生，假設(shè)離開i組的小馬駒和離開j組的小馬駒分別加入了一個臨時組，這兩只小馬駒是雄性和雌性，由于這兩只小馬駒沒有家庭關(guān)系，因此進(jìn)入青春期后進(jìn)行交配。表達(dá)式為：

(4)

式中，XP表示種群k中個體p離群后再次進(jìn)入種群k的個體位置，其父母位置來自不同的種群。

領(lǐng)導(dǎo)者帶領(lǐng)種群前往合適的棲息地，若一個種群對棲息地占主導(dǎo)位置，那么該種群必須離開此地。領(lǐng)導(dǎo)者相對于棲息地的下一位置計算公式為：

(5)

式中，WH為最優(yōu)個體位置。野馬算法種群初始化為隨機(jī)初始化，在種群初始化階段若其中一名組員的適應(yīng)度值優(yōu)于領(lǐng)導(dǎo)者，則兩者根據(jù)式(6)進(jìn)行身份互換：

(6)

3 改進(jìn)策略

3.1 非線性自適應(yīng)因子

為了更好平衡算法全局搜索和局部挖掘能力，防止算法在迭代中后期陷入搜索停滯的狀態(tài)。大量文獻(xiàn)記載了非線性自適應(yīng)因子較線性自適應(yīng)因子的優(yōu)勢，非線性適應(yīng)因子可以保證算法在迭代前期下降速度加快，在算法迭代后期下降速度減緩，保證了算法全局搜索能力的同時確保了算法后期跳出搜索停滯狀態(tài)的能力。改進(jìn)算法線性迭代自適應(yīng)因子為非線性，表達(dá)式為：

(7)

式中，t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)。

3.2 偏移進(jìn)化策略

在標(biāo)準(zhǔn)野馬優(yōu)化算法中，小馬駒的位置主要取決于其來自不同種群的父母位置。此階段過程主要針對種群個體中適應(yīng)度最差的個體進(jìn)行操作，但小馬駒的生成位置較為固定缺乏多樣性，容易陷入搜索停滯狀態(tài)，不利于種群進(jìn)行全局搜索。本文在小馬駒繁殖過程中加入隨機(jī)偏移策略，通過隨機(jī)位置對小馬駒繁殖過程進(jìn)行擾動，提高算法多樣性。其隨機(jī)點生成位置表達(dá)式為：

Q=rand(1,d)×(ub-lb)+lb

(8)

式中，ub、lb為空間上下界；rand為[0,1]之間的隨機(jī)數(shù)，隨機(jī)運(yùn)動使得算法能夠?qū)λ阉骺臻g進(jìn)行充分的探索，因此如果算法陷入局部最優(yōu)，這種行為將幫助算法及時跳出。個體的新位置更新方式為：

(9)

式中，R4為隨機(jī)數(shù)，當(dāng)rand>0.5時，小馬駒通過標(biāo)準(zhǔn)算法的繁殖過程產(chǎn)生，當(dāng)rand≤0.5時，算法通過隨機(jī)偏移策略產(chǎn)生小馬駒。

受麻雀優(yōu)化算法發(fā)現(xiàn)者位置更新的啟發(fā)，在野馬優(yōu)化算法位置更新方式中加入發(fā)現(xiàn)者位置更新方式，提高算法放牧行為位置更新多樣性，其位置更新表達(dá)式為：

(10)

式中，q為正態(tài)分布的隨機(jī)數(shù)；L為長度為d的全1矩陣；R為預(yù)警值；ST為安全值，若R

3.3 黃金正弦分割因子

黃金正弦算法(Golden-SA)[10]是一種元啟發(fā)式算法，該算法受到黃金分割搜索的啟發(fā)可以遍歷正弦函數(shù)上的所有值即遍歷整個單位圓上的所有的點，通過引入黃金分割率，使算法在迭代過程中不斷收縮搜索范圍并且不斷逼近最優(yōu)解，既保證了算法的尋優(yōu)速度又確保了算法的收斂精度。Golden-SA算法與WHO算法的初始化方式相同，通過隨機(jī)在搜索空間的邊界內(nèi)生成隨機(jī)種群個體，表達(dá)式為：

(11)

式中，Xi為個體i的位置；ub為上界；lb為下界；c為取值空間[0,1]的隨機(jī)數(shù)。Golden-SA算法的核心是其參數(shù)c1、c2，表示黃金正弦分割系數(shù)，使搜索空間縮小并且在算法迭代過程中起到指引個體逐漸向全局最優(yōu)位置方向移動，表達(dá)式為：

c1=a(1-h)+bh

(12)

c2=ah+b(1-h)

(13)

式中，a=π；b=-π；h為黃金分割比率，通常取h=(5-1)/2=0.618 33。本文將黃金正弦分割系數(shù)引入野馬優(yōu)化算法的種群位置更新和領(lǐng)導(dǎo)者位置更新表達(dá)式中，引入后的位置更新表達(dá)式為：

(14)

(15)

3.4 B樣條曲線路徑平滑策略

改進(jìn)野馬優(yōu)化算法的部分路徑中還存在尖銳拐點。本文引入3次均勻B樣條曲線來平滑處理算法生成的路徑，在減少路徑尖銳拐點的同時減少路徑長度。當(dāng)k=3時的B樣條曲線數(shù)學(xué)表達(dá)式為：

(16)

(17)

(18)

(19)

3次均勻B樣條曲線的各節(jié)點矢量間插值為常數(shù)，第i段3次均勻B樣條曲線的數(shù)學(xué)表達(dá)式為：

(20)

由式(20)可得3次均勻B樣條曲線的基函數(shù)數(shù)學(xué)表達(dá)式為：

(21)

將式(20)帶入式(21)中，用矩陣形式表達(dá)為：

(22)

3.5 算法流程描述

步驟1：初始化野馬算法參數(shù)。種群規(guī)模N、最大迭代次數(shù)T、領(lǐng)導(dǎo)者比例PS、交配概率PC等；

步驟2：計算野馬種群個體的適應(yīng)度，創(chuàng)建野馬種群和領(lǐng)導(dǎo)者；

步驟3：根據(jù)式(9)和式(14)對野馬種群進(jìn)行位置更新；

步驟4：根據(jù)式(15)對領(lǐng)導(dǎo)者位置進(jìn)行更新；

步驟5：更新野馬種群適應(yīng)度值，若野馬種群中存在適應(yīng)度優(yōu)于領(lǐng)導(dǎo)者的適應(yīng)度個體，則按照式(6)更換領(lǐng)導(dǎo)者；

步驟6：判斷當(dāng)前是否達(dá)到最大迭代次數(shù)，若是，終止循環(huán)，否則跳轉(zhuǎn)步驟2；

步驟7：B樣條曲線對路徑進(jìn)行平滑處理后輸出最優(yōu)路徑。

算法流程圖如圖2所示。

圖2 算法流程圖

4 仿真驗證

為了驗證算法對AGV路徑規(guī)劃的有效性，本實驗選取20×20的二維柵格圖環(huán)境，AGV所處的起始位置為(0,0)，終點位置為(20,20)。實驗設(shè)置種群規(guī)模為50，最大迭代次數(shù)為200次。分別采用ACO算法、標(biāo)準(zhǔn)WHO算法、改進(jìn)野馬優(yōu)化算法(WHO-BC)進(jìn)行對比試驗。其中ACO算法的信息素重要程度因子a=1、b=5、q=2000、信息素的揮發(fā)因子p=0.7；WHO算法的設(shè)置為：PS=0.2、PC=0.13。算法對比結(jié)果如表1所示，生成的最優(yōu)路徑對比結(jié)果如圖3所示。

表1 3種算法數(shù)據(jù)結(jié)果

(a) ACO算法 (b) WHO算法

(c) WHO-BC算法圖3 路徑搜索結(jié)果對比圖

從圖3和表1中可以看出，WHO算法的最優(yōu)路徑長度為30.23，經(jīng)過改進(jìn)后WHO-BC算法的路徑長度為28.56，相較于標(biāo)準(zhǔn)WHO算法生成的路徑減少了5.84%，表明了本文所提出的改進(jìn)方法對于路徑長度縮短的有效性和可行性，能夠有效地平衡算法的全局搜索能力和局部勘探能力，加快算法收斂速度和精度。ACO算法生成的路徑長度31.86，存在過多拐點和無效路徑，相較于標(biāo)準(zhǔn)WHO和WHO-BC算法路徑長度全局搜索能力較差；ACO和WHO算法的迭代運(yùn)行時間分別為6.03 s和3.45 s，迭代次數(shù)為72和32次，而本文改進(jìn)的WHO-BC算法的運(yùn)行時間為2.57 s，迭代次數(shù)為27次，表明本文改進(jìn)方法通過引入偏移進(jìn)化策略增強(qiáng)了算法種群的多樣性，黃金正選分割因子在迭代過程總縮小搜索空間，引領(lǐng)算法個體逐漸向全局最優(yōu)位置方向移動，進(jìn)一步表明本文算法改進(jìn)的有效性和可行性。從整體上來看路徑尋優(yōu)能力上WHO-BC算法>標(biāo)準(zhǔn)WHO算法>ACO算法。

通過圖4的算法迭代對比試驗可以看出，本文改進(jìn)的WHO-BC算法位置總體靠下，相較于標(biāo)準(zhǔn)WHO算法具有跳出局部最優(yōu)解的能力。綜上所述，表明本文算法性能優(yōu)于對比算法，總體能夠減少5.84%的AGV路徑規(guī)劃長度。

圖4 算法迭代對比圖

5 結(jié)論

本文提出一種基于改進(jìn)野馬優(yōu)化算法的AGV路徑規(guī)劃方法。在標(biāo)準(zhǔn)野馬優(yōu)化算法的基礎(chǔ)上，通過引入非線性自適應(yīng)因子、偏移進(jìn)化策略、黃金正弦分割因子和發(fā)現(xiàn)者位置更新方式改進(jìn)算法的收斂速度和尋優(yōu)精度，并且通過B樣條曲線對算法生成的路徑進(jìn)行平滑處理，進(jìn)一步提高AGV路徑規(guī)劃的性能。經(jīng)過仿真對比試驗可知，改進(jìn)野馬優(yōu)化算法相較于ACO算法和標(biāo)準(zhǔn)WHO算法生成的路徑更加平滑并且路徑長度更短；通過迭代曲線和運(yùn)行時間對比試驗，表明改進(jìn)野馬優(yōu)化算法具有較高的效率和較好的收斂速度。