基于改進狼群算法的AGV路徑規(guī)劃

程 俊, 董學(xué)平, 張志軍

(1.合肥工業(yè)大學(xué) 電氣與自動化工程學(xué)院,安徽 合肥 230009; 2.工業(yè)自動化安徽省工程技術(shù)研究中心,安徽 合肥 230009)

隨著社會經(jīng)濟發(fā)展和工業(yè)智能信息化的深入,智能化物流逐漸成為商業(yè)和工業(yè)領(lǐng)域必不可少的基礎(chǔ)設(shè)施,這使得自動引導(dǎo)小車(automated guided vehicle,AGV)得到越來越廣泛的應(yīng)用,同時也促進了對AGV關(guān)鍵技術(shù)的深入研究。路徑規(guī)劃作為該領(lǐng)域核心技術(shù)之一,具有非常廣泛的應(yīng)用場合,比如手機導(dǎo)航、無人駕駛車輛的避障和規(guī)劃路徑、智能物流等。

針對路徑規(guī)劃問題,國內(nèi)外學(xué)者做了大量的深入研究,提出了很多解決方法,其中包括遺傳算法[1]、蟻群算法[2]、粒子群算法[3]和神經(jīng)網(wǎng)絡(luò)[4]等。其中,文獻[5]基于狼群捕獵過程中的分工協(xié)作提出了狼群算法(wolf pack algorithm,WPA),該算法將狼群的捕獵活動抽象為游走、召喚、圍攻3種行為,并引入“勝者為王”的頭狼選擇機制和“適者生存”的更新機制。狼群算法的提出引起了國內(nèi)外學(xué)者的廣泛關(guān)注。文獻[6]將狼群算法成功應(yīng)用于無人機航跡規(guī)劃;文獻[7]在原始狼群算法的基礎(chǔ)上引入次頭狼召喚和圍攻的更新策略,提高了算法的全局尋優(yōu)能力,并將其應(yīng)用于空戰(zhàn)目標(biāo)火力分配問題上;文獻[8]提出了根據(jù)游走次數(shù)的奇偶性改變探狼搜索方向的方法,并且引入自適應(yīng)調(diào)節(jié)搜索步長的策略,提高了算法的求解精度。

狼群算法作為群體智能算法的一種,具有廣泛的應(yīng)用領(lǐng)域,同樣也適用于AGV最優(yōu)路徑求解問題。本文針對狼群算法易陷入局部最優(yōu)、搜索效率低等問題,提出了一種改進狼群算法(improved wolf pack algorithm,IWPA),并將其應(yīng)用于AGV路徑規(guī)劃。本文介紹了AGV運動空間的環(huán)境建模以及改進的狼群算法,比較了IWPA和WPA在函數(shù)優(yōu)化問題上的求解效果,并對2種算法分別進行了AGV路徑規(guī)劃仿真實驗和結(jié)果分析。

1 AGV路徑規(guī)劃問題

1.1 環(huán)境建模

在AGV路徑規(guī)劃研究中,描述環(huán)境的建模方法有很多種,常用的有可視圖法、自由空間法、拓?fù)浞ê蜄鸥穹ǖ萚9-11]。本文采用柵格法進行環(huán)境建模,將運動環(huán)境映射成大小相同的網(wǎng)格矩陣,每塊柵格的邊長都為1,AGV視作地圖中的一個質(zhì)點。一個5×5的柵格環(huán)境如圖1所示,以柵格左下角為坐標(biāo)原點,橫向為X軸,豎向為Y軸,則柵格j的坐標(biāo)為(aj,bj)。對地圖中的柵格采用實數(shù)編碼,則在M×M的柵格環(huán)境中,柵格坐標(biāo)與編號N的對應(yīng)關(guān)系為:

(1)

其中:mod為取余運算;fix為向靠近取整的運算。

帶障礙物的柵格地圖如圖1所示,AGV路徑規(guī)劃即要求在圖1中白色的可行區(qū)域內(nèi)規(guī)劃出一條從起始點到目標(biāo)點的最優(yōu)路徑。

圖1 帶障礙物的柵格地圖

1.2 適應(yīng)度函數(shù)的建立

利用狼群算法進行路徑規(guī)劃時,種群中的每匹狼都代表一條潛在的可行路徑,適應(yīng)度函數(shù)則是評價這條路徑優(yōu)劣程度的唯一標(biāo)準(zhǔn)。本文適應(yīng)度函數(shù)采用路徑長度、平滑度以及安全度作為評價指標(biāo)。

1) 路徑長度評價函數(shù)f1。計算公式為:

(2)

其中:a、b為當(dāng)前路徑中所經(jīng)過柵格的位置坐標(biāo);t為路徑節(jié)點個數(shù)。

2) 路徑平滑度評價函數(shù)f2。采用相鄰路段之間夾角之和的大小作為評價平滑度的指標(biāo),即

(3)

其中,θ(ljlj+1,lj+1lj+2)為相鄰2條路段ljlj+1和lj+1lj+2的夾角。f2值越小,路徑越平滑。

3) 路徑懲罰函數(shù)f3。路徑與障礙物相交的次數(shù)越多則函數(shù)值就越大,越容易在迭代過程中被淘汰。

(4)

其中:m為與障礙物相交的次數(shù);C為一個取值較大的正常數(shù)。

將f1和f2進行歸一化處理后,AGV路徑規(guī)劃的適應(yīng)度評價函數(shù)為:

f=μ1f1/dpath+μ2f2/(180°Nnum)+f3

(5)

其中:dpath為起點和終點與它們之間垂直交叉點的距離之和;Nnum為路徑的拐點總數(shù);μ1、μ2為權(quán)值,且μ1+μ2=1。

故AGV的最優(yōu)路徑規(guī)劃即為求解使適應(yīng)度函數(shù)f最小的坐標(biāo)集。

2 改進的狼群算法

2.1 狼群算法基本原理

狼群算法的基本過程主要包括以下步驟:

1) 狼群初始化。在D維空間中隨機初始化n匹人工狼的位置,則第i匹人工狼的位置可表示為Xi=(xi1,xi2,…,xiD),i=1,2,…,n。

2) 選取距離獵物最近的人工狼為頭狼,并將除頭狼外最優(yōu)的S-num匹狼選取為探狼,S-num隨機取[n/(α+1),n/α]中的整數(shù),α為探狼比例因子,并執(zhí)行游走搜索行為,向四周h個方向以步長Sa搜尋獵物。探狼i向第p(p=1,2,…,h)個方向游走后,在第d維空間位置更新為:

(6)

若探狼搜索到距離獵物更近的位置,則更新其當(dāng)前位置,并重復(fù)游走行為,直到某人工狼搜索到優(yōu)于頭狼的位置時,該探狼將代替頭狼發(fā)起召喚或直到游走達到最大游走次數(shù)Tmax。

3) 將頭狼和探狼以外的其余狼作為猛狼,在頭狼發(fā)起召喚后,猛狼以步長Sb向頭狼移動,猛狼i在第k+1次迭代后,其在第d維空間位置更新為:

(7)

在奔襲的過程中,若猛狼所處位置優(yōu)于頭狼,則該猛狼將代替頭狼發(fā)起召喚行為;否則猛狼將繼續(xù)奔襲,直到與頭狼的距離小于dnear時,對獵物發(fā)起圍攻。判定距離dnear的計算公式為:

(8)

其中:ω為距離判定因子;dmax、dmin為狼群在第d維空間位置坐標(biāo)的最大值和最小值。

4) 當(dāng)猛狼與獵物的距離小于dnear時,便聯(lián)合探狼以步長Sc對獵物進行圍攻,以期捕獲。狼群位置更新公式為:

(9)

其中,λ為[-1,1]間均勻分布的隨機數(shù)。若進行圍攻之后人工狼離獵物更近,則更新位置;否則保持原位置不變。

3種搜索步長在第d維空間中存在如下關(guān)系:

(10)

其中,S為步長因子。

5) 狼群的更新機制。根據(jù)適者生存的更新策略,淘汰適應(yīng)度最差的R匹狼,然后隨機生成R匹狼。R為隨機整數(shù),取值在[n/(2β),n/β]之間,其中β為比例因子。

2.2 狼群算法的改進

針對傳統(tǒng)狼群算法初始種群多樣性不足,探狼游走方向固定,易陷入局部最優(yōu),迭代后期搜索效率低等缺陷,本文從如下4個方面進行了改進,以進一步提高算法的尋優(yōu)效率。

2.2.1 改進的Sine混沌映射優(yōu)化初始種群

狼群算法中種群的初始位置和狼群的更新機制均采用隨機生成的方式,這種方式容易導(dǎo)致種群分布不均勻、多樣性不足,影響后期的迭代尋優(yōu)效率。而混沌映射具有遍歷性、規(guī)律性、隨機性等特點,可以有效避免這些缺陷。

產(chǎn)生混沌變量的Sine混沌模型映射公式為:

zk+1=φsin(πzk)

(11)

其中:zk為迭代序列,k∈N,z0∈(0,1];φ為控制參數(shù),φ越接近1時混沌性能越好。

當(dāng)取φ=1,迭代2 000次后,Sine混沌映射序列分布圖如圖2、圖3所示,可以發(fā)現(xiàn)序列的分布并不十分均勻,在[0,0.1]和[0.9,1.0]區(qū)間內(nèi)出現(xiàn)的頻率較高。

圖2 Sine映射分布直方圖

圖3 Sine映射分布圖

依據(jù)文獻[12]所提方法對Sine混沌映射進行改進,如式(12)所示,并利用式(13)將序列映射到狼群空間位置上。

(12)

xid=dmin+yid(dmax-dmin)

(13)

其中:y∈[0,1]為混沌迭代序列;φ為控制參數(shù)。

改進后的Sine映射分布圖如圖4、圖5所示。從圖4、圖5可以看出,混沌值分布更加均勻,出現(xiàn)的概率更加相近。因此采用改進的Sine映射進行狼群初始化和更新,有利于提高種群多樣性,進而提高算法的尋優(yōu)效率。

圖4 改進的Sine映射分布直方圖

圖5 改進的Sine映射分布圖

2.2.2 探狼隨機游走策略

在傳統(tǒng)的狼群算法中,探狼游走行為由式(6)決定,這使得探狼i不論迭代搜索多少次,方向只有h個,搜索方向固定,且每代之間的搜索方向都是平行的,削弱了算法的隨機性。文獻[8]提出根據(jù)游走次數(shù)的奇偶性改變搜索方向的方法,文獻[13]在游走行為中引入相位因子,以提高探狼搜索的靈活性。為了進一步豐富搜索方向,本文對探狼游走公式進行了改進,公式如下:

(14)

其中,v為隨機方向向量,計算公式為:

v=V(:,p)T,V=rand(D,h)

(15)

其中,rand為生成隨機數(shù)的運算。

這樣探狼在每次游走時,會隨機選擇h個方向進行搜索,方向不固定,增強了搜索的隨機性,從而提高了算法的全局尋優(yōu)能力。

2.2.3 頭狼選擇引入Metropolis準(zhǔn)則

原始算法中總是選擇適應(yīng)度最好的人工狼作為頭狼,執(zhí)行召喚行為。在迭代后期,種群多樣性降低時,易使種群陷入局部最優(yōu),降低算法的全局搜索能力。針對該問題,在探狼游走搜索后,對頭狼的選擇方式上引入Metropolis準(zhǔn)則[14]使得算法具有概率突跳的能力。

本文以種群迭代次數(shù)k來表示Metropolis準(zhǔn)則中的溫度,改進公式為:

(16)

其中,Kmax為種群最大迭代次數(shù)。

當(dāng)探狼i搜索到優(yōu)于頭狼的位置時,探狼i取代當(dāng)前頭狼發(fā)起召喚;當(dāng)所有探狼搜索至最大游走次數(shù)依然未搜索到優(yōu)于頭狼的位置時,按式(16)概率接受非最優(yōu)人工狼作為當(dāng)前種群的頭狼,隨著迭代次數(shù)的增加,算法接受非最優(yōu)人工狼作為頭狼的概率逐漸減小。

2.2.4 猛狼奔襲策略的改進

(17)

其中,λ為[0,1]內(nèi)的隨機數(shù)。

2.3 改進狼群算法步驟

1) 采用柵格法對AGV運動環(huán)境進行建模,對柵格進行編碼,并獲取障礙物信息。

2) 采用實數(shù)編碼,對狼群進行初始化。利用2.2.1節(jié)所述方法構(gòu)造人工狼初始位置,則第i匹人工狼位置為Xi=(xi1,xi2,…,xiD),i=1,2,…,n,每匹人工狼代表一條潛在的可行路徑;初始化算法的迭代次數(shù)Kmax、探狼比例α、狼群更新比例β、游走步長Sa、奔襲的步長Sb等。

3) 按照式(5)計算每匹狼的適應(yīng)度f(Xi),將適應(yīng)度最好的人工狼暫定為頭狼,除頭狼外適應(yīng)度最好的前S-num匹狼作為探狼。按照式(14)執(zhí)行游走搜索,若f(Xi)

4) 猛狼按式(9)向頭狼奔襲,若途中發(fā)現(xiàn)適應(yīng)度優(yōu)于頭狼,則將取代頭狼發(fā)起召喚。

5) 猛狼聯(lián)合探狼按式(17)執(zhí)行圍攻行為。

6) 更新頭狼位置,并淘汰掉適應(yīng)度最差的R匹狼,按改進的Sine混沌映射規(guī)則重新生成R匹狼。

7) 判斷是否滿足終止條件,若滿足,則算法結(jié)束;否則轉(zhuǎn)至步驟3)繼續(xù)進行搜索。

3 仿真實驗

3.1 函數(shù)測試與分析

為了驗證本文所提的IWPA的有效性和可行性,本文選擇了在函數(shù)優(yōu)化中廣泛使用的8個標(biāo)準(zhǔn)測試函數(shù)進行測試,并與WPA進行實驗對比。測試函數(shù)的基本信息見表1所列,表1中:U表示此函數(shù)為單峰;M表示多峰;S表示可分;N表示不可分。

實驗設(shè)置最大迭代次數(shù)為1 000,種群數(shù)量為100,探狼比例因子α=4,狼群更新比例因子β=5,ω=500,S=100,其他參數(shù)參考文獻[5]設(shè)置,分別進行100次的獨立實驗。實驗結(jié)果見表2所列,若結(jié)果小于1E-16,則視為0。

表1 8個標(biāo)準(zhǔn)測試函數(shù)

表2 函數(shù)優(yōu)化結(jié)果對比

由表2可知,首先在平均值與最佳值的對比上,IWPA比WPA尋優(yōu)能力更強,收斂精度更高。對Eason、Matyas單峰函數(shù)尋優(yōu)接近理論最優(yōu)值,體現(xiàn)了IWPA具有較強的開采能力,這得益于種群的多樣性以及猛狼良好的圍攻行為;對Rastrigin、Sumsquares等多峰函數(shù)具有較好的優(yōu)化效果,體現(xiàn)了IWPA跳出局部極值的能力,這得益于對頭狼的選擇上引入了Metropolis準(zhǔn)則,使得算法具有概率突跳的能力。從標(biāo)準(zhǔn)差的對比可以看出IWPA具有更好的魯棒性,在平均耗時上IWPA與WPA處于同一級別,說明IWPA在提升性能的基礎(chǔ)上并沒有明顯增加運行時間。

為了更直觀地說明IWPA的優(yōu)越性,給出了Rastrigin、 Eggcrate、Sumsquares 3個函數(shù)的收斂曲線,如圖6所示。從圖6可以看出,IWPA在收斂速度和求解精度上均有優(yōu)勢。

3.2 路徑規(guī)劃仿真實驗

為了驗證改進的狼群算法在AGV路徑規(guī)劃問題上的可行性,本文進行了仿真實驗。仿真環(huán)境為20×20的柵格地圖,起始坐標(biāo)為(0,0),終點坐標(biāo)為(20,20),種群維數(shù)為18,種群個數(shù)N=100,最大迭代次數(shù)K=200,探狼比例因子α=4,狼群更新比例因子β=5,最大游走次數(shù)T=10,步長因子s=20,μ1=3/5。在相同的條件下,將IWPA和WPA 2種算法各自運行100次,路徑規(guī)劃的數(shù)據(jù)統(tǒng)計結(jié)果見表3所列,各自規(guī)劃的最優(yōu)路徑如圖7、圖8所示。

表3 2種算法運行100次的數(shù)據(jù)比較

圖7 WPA的最優(yōu)路徑規(guī)劃

圖8 IWPA的最優(yōu)路徑規(guī)劃

從表3可以看出,在仿真環(huán)境中,IWPA規(guī)劃的最優(yōu)路徑距離比WPA的短1.7 m左右,總轉(zhuǎn)角度數(shù)小45°,從平均值和方差上可以看出IWPA尋優(yōu)更加穩(wěn)定、魯棒性更好。從圖7和圖8可以看出IWPA規(guī)劃的路徑更加平滑,充分說明了IWPA在AGV路徑規(guī)劃上的有效性和穩(wěn)定性。

4 結(jié) 論

本文在柵格法環(huán)境建模的基礎(chǔ)上,針對AGV路徑規(guī)劃問題,提出了一種改進的狼群算法。該算法利用改進的Sine混沌映射進行種群的初始化和更新,提高了種群的多樣性;探狼的隨機游走策略,增強了算法搜索的隨機性;在頭狼的選擇上引入Metropolis準(zhǔn)則,提高了算法跳出局部最優(yōu)解的能力;猛狼奔襲策略的改進有利于加快算法收斂。仿真實驗表明,在AGV路徑規(guī)劃的問題上,IWPA比WPA更加有效,具備一定的實用價值。