基于改進(jìn)人工蜂群算法的災(zāi)害場景下路徑規(guī)劃*

朱金磊,袁曉兵,裴俊

(1 中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 微系統(tǒng)技術(shù)重點(diǎn)實(shí)驗(yàn)室, 上海 201800;2 中國科學(xué)院大學(xué), 北京 100049)

近年來,中國自然災(zāi)害頻繁劇烈,造成嚴(yán)重的經(jīng)濟(jì)損失和人員傷亡。災(zāi)害場景下的路徑規(guī)劃主要針對人員、移動(dòng)機(jī)器人、無人機(jī)等進(jìn)行物資輸送和救援工作,因此對規(guī)劃路徑的距離、平滑性、安全性等具備較高的精度要求。合理且高精度的路徑規(guī)劃算法無疑能最大程度地降低因自然災(zāi)害帶來的各項(xiàng)損失。

路徑規(guī)劃算法常被應(yīng)用于移動(dòng)機(jī)器人[1]、無人機(jī)[2-6]、人群疏散[7-8]、無線傳感網(wǎng)絡(luò)[9]、B5G/6G[10-11]等領(lǐng)域并發(fā)揮重要作用。常見算法包括Dijkstra算法和A*算法,但存在算法復(fù)雜度高且不一定能找到最優(yōu)路徑的弊端,神經(jīng)網(wǎng)絡(luò)算法存在收斂慢且易收斂到局部最優(yōu)的弊端。而群智能算法通過個(gè)體間相互協(xié)作和組織的天然分布式和自組織特性,在路徑規(guī)劃方面表現(xiàn)出更好的收斂速度和尋優(yōu)能力。常見的群智能算法包括布谷鳥算法、粒子群算法、螢火蟲算法、灰狼優(yōu)化算法、人工蜂群算法[12-14]等。

人工蜂群(artificial bee colony, ABC)算法的性能優(yōu)于許多其他基于種群的啟發(fā)式算法[15],但是與開發(fā)能力相比,ABC算法更注重探索,導(dǎo)致ABC算法的開發(fā)能力差,存在收斂速度慢及易陷入局部最優(yōu)等弊端[16]。文獻(xiàn)[17-18]在初始化階段生成一般初始化解的基礎(chǔ)上,加入了異構(gòu)的、對稱的或?qū)α⒌慕饧?增強(qiáng)了ABC算法的全局探索能力,但并沒有有效提升收斂速度。Zhang等[15]通過在食物源更新方程中加入自適應(yīng)步長因子來加快收斂速度,但是自適應(yīng)步長因子的值隨著地圖模型的變化而變化,不具備完備性,并且自適應(yīng)步長的確定需要花費(fèi)大量的計(jì)算資源。文獻(xiàn)[19-22]中在食物源更新方程中引入全局最優(yōu)個(gè)體信息來提升收斂速度和精度,但同時(shí)也伴隨著收斂過快、收斂至局部最優(yōu)解等弊端。文獻(xiàn)[23-24]則分別將ABC算法與概率路線圖方法和快速隨機(jī)搜索樹結(jié)合來解決收斂速度慢、易陷入局部最優(yōu)的弊端,但增加了算法復(fù)雜度。

通過借鑒先前研究學(xué)者研究經(jīng)驗(yàn),本文將隨機(jī)初始化改進(jìn)為全域采樣隨機(jī)初始化以保證初始解集完備性,并把開采次數(shù)加入到選擇概率計(jì)算中抑制部分局部最優(yōu)解,提升潛在較優(yōu)解選中概率,同時(shí)根據(jù)解在各個(gè)維度的開采次數(shù)設(shè)計(jì)全局最優(yōu)個(gè)體引導(dǎo)下的自適應(yīng)局部開發(fā)方程,提升局部開發(fā)精度。最后通過在不同災(zāi)害場景下與各算法進(jìn)行仿真對比,改進(jìn)后的ABC算法具備更優(yōu)的求解精度以及全局收斂性。

1 ABC算法原理分析

ABC算法是一種模擬蜜蜂群體智能搜索行為的生物優(yōu)化方法。該算法通過3種類型的蜂群相互合作從而尋找到最優(yōu)蜜源。第1種蜂群是雇傭蜂蜂群,其任務(wù)是尋找潛在的解決方案。第2種蜂群是跟隨蜂蜂群,其任務(wù)是對雇傭蜂所找到的潛在解決方案做進(jìn)一步精確搜索。第3種蜂群是偵察蜂蜂群,該蜂群通過重新生成新解替代那些陷入局部最優(yōu)的解決方案,提高ABC算法的全局搜索能力。

ABC算法與大多數(shù)仿生學(xué)算法類似,主要包含全局探索和局部開發(fā)2個(gè)過程。初始時(shí)隨機(jī)初始化以及偵察蜂階段對陷入局部最優(yōu)個(gè)體進(jìn)行隨機(jī)初始化主要實(shí)現(xiàn)全局探索,公式如下

(1)

式(1)表示第i個(gè)個(gè)體的第j維度的隨機(jī)初始化過程,其中R為[0,1]之間隨機(jī)數(shù),xjmin和xjmax分別表示第j維度的最小值和最大值。

ABC算法的局部開發(fā)主要發(fā)生在雇傭蜂階段以及跟隨蜂階段,開發(fā)過程主要通過與一個(gè)隨機(jī)選擇的個(gè)體進(jìn)行信息交互完成局部開發(fā),公式如下

(2)

式(2)表示第i個(gè)個(gè)體的第j維度進(jìn)行局部開發(fā)的過程,其中k≠i,R∈[-1,1]。

另外,在跟隨蜂階段的輪盤賭選擇前需要評估每一個(gè)解的好壞,由于實(shí)驗(yàn)采用的是災(zāi)害場景模型,故目標(biāo)函數(shù)和適應(yīng)度值計(jì)算如下:

obji=α×Jthr,i+β×Jlen.i+γ×Jθ,i,

(3)

(4)

其中:Jthr、Jlen和Jθ分別代表路徑危險(xiǎn)系數(shù)、路徑長度和路徑平滑因子,α、β和γ為加權(quán)系數(shù),用來平衡三者的影響強(qiáng)度。以圖1為例三者的計(jì)算如下所示

Jthr(b)=N×(1-Lob/R),

(5)

Jlen(ab)=Lab/(xb-xa),

(6)

(7)

圖1 部分路徑規(guī)劃結(jié)果Fig.1 Screenshot of path planning

其中:Lab表示a、b兩點(diǎn)間的歐式距離,N為較大值。式(6)中除以橫向距離以及式(7)中對計(jì)算所得余弦值加1后除以2主要為了實(shí)現(xiàn)近似歸一化,使距離因子和平滑因子盡可能相近,方便加權(quán)系數(shù)調(diào)整。

2 改進(jìn)ABC算法

2.1 小樣本初始化

在ABC算法中,初始位置需要較強(qiáng)的隨機(jī)性,同時(shí)滿足多樣性以及遍歷性需求。因此將初始化過程按如圖2所示改進(jìn),根據(jù)每一維度的探索上下限進(jìn)行等間隔采樣,然后隨機(jī)打亂并進(jìn)行連接的過程實(shí)現(xiàn)初始化,滿足小樣本在初始化時(shí)的隨機(jī)性,多樣性與完備性需求。

2.2 改進(jìn)的選擇概率計(jì)算

跟隨蜂階段,ABC算法根據(jù)每個(gè)食物源的適應(yīng)度值大小計(jì)算相應(yīng)的選擇概率,進(jìn)而完成輪盤賭選擇。但是這樣的選擇策略僅考慮了適應(yīng)度值,忽略了ABC算法另一個(gè)重要的因子trial即無效開采次數(shù),trial值較大的個(gè)體雖然適應(yīng)度值較大但可能是一個(gè)局部最優(yōu)解,而trial值較小的個(gè)體雖然適應(yīng)度值不高但有可能只是部分維度未開采至最優(yōu)解附近。因此將概率計(jì)算公式更新成如下所示,其中trial為0個(gè)體正好等于trial取開采上限lt個(gè)體的λ倍,而λ取大于1的較小值,如1.05,1.1等。

fit*=fit×(e-trial×ln(λ)/lt),

(8)

(9)

圖2 隨機(jī)初始化過程Fig.2 Random initialization process

2.3 改進(jìn)的局部開發(fā)方程

在ABC算法中,食物源局部開發(fā)方程是權(quán)衡局部開發(fā)和全局收斂性的關(guān)鍵所在,更新方程設(shè)計(jì)的優(yōu)劣極大地影響算法的收斂速度和尋優(yōu)精度。結(jié)合文獻(xiàn)[20]中GLABC算法的更新方程設(shè)計(jì)如下所示的全局最優(yōu)個(gè)體gbest引導(dǎo)下的自適應(yīng)局部更新方程。

δ=cos(π/2×τ(i,j)/lt),

(10)

(11)

其中:R∈[-1,1],i≠l≠k。若個(gè)體包含維度數(shù)為m,則τ代表SN×m大小的矩陣,用來記錄每個(gè)個(gè)體每個(gè)維度的開發(fā)情況。τ的更新方式與trial一致,當(dāng)?shù)趇個(gè)個(gè)體的第j維度更新后并不能得到更優(yōu)的結(jié)果時(shí),τ(i,j)加1,否則置0。算法根據(jù)個(gè)體在該維度的開發(fā)情況生成自適應(yīng)收斂因子δ來實(shí)現(xiàn)鄰域壓縮開發(fā)。同時(shí)余弦函數(shù)在[0,π/2]具備前期下降平緩后期下降較快的特點(diǎn),正好滿足ABC算法前期探索范圍大后期精確開發(fā)的需求。

2.4 改進(jìn)ABC算法流程

本文提出的改進(jìn)ABC算法詳細(xì)步驟如下:

步驟1 算法參數(shù)初始化以及蜜源信息初始化,其中包括種群數(shù)量SN,無效開采次數(shù)上限lt,蜜源初始位置信息等。

步驟2 算法進(jìn)入雇傭蜂階段,按式(11)進(jìn)行鄰域開發(fā),并進(jìn)行貪婪選擇,選取較優(yōu)蜜源,同時(shí)更新無效開采次數(shù)和τ矩陣。

步驟3 算法進(jìn)入跟隨蜂階段,按式(9)得到的概率值進(jìn)行輪盤賭選擇,對選中的個(gè)體按式(11)進(jìn)行鄰域開發(fā),同時(shí)按照貪婪策略選取較優(yōu)蜜源,同時(shí)更新無效開采次數(shù)和τ矩陣。

步驟4 算法進(jìn)入偵察蜂階段,對無效開采次數(shù)大于lt的個(gè)體按式(1)進(jìn)行重新初始化。

步驟5 如果找到最優(yōu)解或者迭代次數(shù)到達(dá)上限,轉(zhuǎn)至步驟6,否則轉(zhuǎn)至步驟2。

步驟6 輸出路徑規(guī)劃結(jié)果。

3 實(shí)驗(yàn)與分析

為驗(yàn)證改進(jìn)ABC算法的有效性,將改進(jìn)ABC算法與標(biāo)準(zhǔn)PSO算法、標(biāo)準(zhǔn)ABC算法、GLABC[20]算法、IABC[3]算法、IFABC[3]算法、NABC[13]算法、BEABC[3]算法進(jìn)行仿真對比。實(shí)驗(yàn)仿真環(huán)境為MATLAB R2016b、Core i5、64位Windows操作系統(tǒng)。

3.1 模型參數(shù)設(shè)置

實(shí)驗(yàn)中以森林火災(zāi)模型下人員及無人機(jī)路徑規(guī)劃作為基準(zhǔn)模型。如圖3 (a)中2006年四川省木里縣依吉火場所示,火場案例主要包括線火場和范圍火場兩類,其中下側(cè)黑實(shí)線為火災(zāi)已經(jīng)撲滅的區(qū)域。圖3(b)中使用一系列小圓對線火場進(jìn)行模擬,較大圓對范圍火場進(jìn)行模擬,同時(shí)星號(hào)作為路徑規(guī)劃的起點(diǎn),方框作為路徑規(guī)劃的終點(diǎn),圓形區(qū)域代表危險(xiǎn)區(qū)域,離中心點(diǎn)越近則危險(xiǎn)性越大。通過擬合火災(zāi)場景及細(xì)微調(diào)整生成如圖4所示5種不同復(fù)雜程度的災(zāi)害模型對算法求解精度、收斂性等進(jìn)行分析。

圖3 火災(zāi)模型轉(zhuǎn)換示意圖Fig.3 Fire model conversion diagram

為了客觀分析算法性能,所有算法的種群大小均設(shè)置為30,最大迭代次數(shù)分別為300、500和1 000次,探索維度為30,其中PSO算法的加速常數(shù)c1為2.05,加速常數(shù)c2為2.05,慣性權(quán)重w為0.707 1,改進(jìn)ABC算法λ為1.1,每組實(shí)驗(yàn)均在相同實(shí)驗(yàn)環(huán)境下運(yùn)行20次。記錄20次實(shí)驗(yàn)結(jié)果中的最小值、均值、方差以及單次運(yùn)行耗時(shí)作為算法評價(jià)指標(biāo)。

3.2 實(shí)驗(yàn)結(jié)果與分析

模型1～模型5分別對應(yīng)著5種不同復(fù)雜程度的災(zāi)害場景。模型1相對簡單且最優(yōu)路徑單一,但也極易出現(xiàn)小圓間穿越的不合理規(guī)劃路徑,且路徑規(guī)劃前半段存在較大的安全探索范圍,較大的探索范圍需要算法較多的迭代次數(shù)完成收斂。模型2相對復(fù)雜,模型3在模型2基礎(chǔ)上改進(jìn),進(jìn)一步增加了模型的復(fù)雜度,2種場景均存在較多的局部最優(yōu)解,需要算法具備較好的局部最優(yōu)規(guī)避能力。模型4和模型5均存在上側(cè)或下側(cè)通過的合理路徑,上側(cè)可通行區(qū)域較窄,其中模型5屬于常見的由較大點(diǎn)火源產(chǎn)生飛火而引發(fā)多處產(chǎn)生點(diǎn)火源的場景。

圖4 5種不同災(zāi)害場景Fig.4 Five different disaster scenarios

表1～表3列出了不同算法在迭代次數(shù)為300、500和1 000次下運(yùn)行20次得到的目標(biāo)函數(shù)的最小值、均值、方差以及單次運(yùn)行耗時(shí)的實(shí)驗(yàn)結(jié)果。從該實(shí)驗(yàn)結(jié)果可以看出,在不同場景下,ABC算法在最小值和均值方面的結(jié)果都優(yōu)于PSO算法,方差與PSO算法相近,算法復(fù)雜度略高于PSO算法導(dǎo)致算法耗時(shí)更長,但ABC算法整體性能更佳。相較于標(biāo)準(zhǔn)ABC算法,各類改進(jìn)后的ABC算法在最小值和均值方面均取得了更好的結(jié)果。在算法迭代初期由于各類改進(jìn)ABC算法增加額外計(jì)算耗時(shí),算法運(yùn)行耗時(shí)有小幅增加,但在迭代后期由于各類算法均具備較好的收斂特性,計(jì)算復(fù)雜度降低,算法運(yùn)行耗時(shí)與標(biāo)準(zhǔn)ABC算法相近甚至更低。

表1 300次迭代下各算法尋優(yōu)結(jié)果Table 1 Optimization results of each algorithm under 300 iterations

表2 500次迭代下各算法尋優(yōu)結(jié)果Table 2 Optimization results of each algorithm under 500 iterations

表3 1 000次迭代下各算法尋優(yōu)結(jié)果Table 3 Optimization results of each algorithm under 1 000 iterations

本文改進(jìn)下的ABC算法增加了更新后的適應(yīng)度值存儲(chǔ)矩陣以及每個(gè)個(gè)體每個(gè)維度開發(fā)情況的存儲(chǔ)矩陣,大小分別為SN×1以及SN×m,其中SN和m分別代表食物源總數(shù)與每個(gè)食物源包含的維度,均為較小值,并沒有增加較多的額外空間。該算法由于初始化時(shí)采用全局采樣隨機(jī)化的初始化方式,在Model1和Model5初始化范圍較大且迭代次數(shù)為300次時(shí)效果一般,而GLABC算法在Model1以及NABC在Model2和Model5下取得了更好的實(shí)驗(yàn)結(jié)果,但是兩者在算法迭代中易陷入局部最優(yōu)或者在局部最優(yōu)附近浪費(fèi)過多計(jì)算資源。本文改進(jìn)下的ABC算法雖然采用了與GLABC算法和NABC算法類似的全局最優(yōu)個(gè)體引導(dǎo)下的局部開發(fā),但是加入了與維度開發(fā)次數(shù)相關(guān)的自適應(yīng)收斂因子,增加了局部開發(fā)的精確性,提升了ABC算法的局部開發(fā)精度和收斂特性。同時(shí)本文提出的算法在選擇階段的選擇概率計(jì)算中加入了無效開采次數(shù)的影響,避免算法在局部最優(yōu)附近過度開發(fā)浪費(fèi)資源,提升潛在最優(yōu)解的選中概率。從表1～表3可以看出,GLABC算法和NABC算法由于易陷入局部最優(yōu)或在局部最優(yōu)附近浪費(fèi)過多資源的局限性,在迭代1 000次時(shí)實(shí)驗(yàn)效果遠(yuǎn)不如本文改進(jìn)下的ABC算法。而至于IABC算法、IFABC算法以及BEABC算法,雖然具備較好的收斂特性,但由于收斂速度慢以及開發(fā)精度低等缺陷,實(shí)驗(yàn)效果也不如本文提出的改進(jìn)ABC算法。同時(shí)本文提出的改進(jìn)ABC算法方差較小具備較好的全局收斂性,算法運(yùn)行中主要增加了式(8)和式(10)的計(jì)算資源消耗,從實(shí)驗(yàn)結(jié)果的time系數(shù)也可以看出并沒有明顯增加ABC算法的計(jì)算復(fù)雜度。

為更加直觀地顯示各個(gè)算法的尋優(yōu)進(jìn)程和收斂特性,圖5給出不同模型下各個(gè)算法均值的收斂變化曲線。從圖中可以看出不同改進(jìn)ABC算法均較好地提高了ABC算法的實(shí)驗(yàn)性能,其中IABC算法、IFABC算法、BEABC算法由于開發(fā)精度低導(dǎo)致目標(biāo)函數(shù)值的結(jié)果一般,GLABC算法和NABC算法在迭代初期具備較好的實(shí)驗(yàn)結(jié)果但是收斂速度慢,而本文改進(jìn)下的ABC算法目標(biāo)函數(shù)值更小且收斂性更好,具備更好的開發(fā)精度和收斂特性。

圖5 5種不同場景下的均值收斂曲線Fig.5 Mean convergence curve in five different scenarios

3.3 路徑規(guī)劃仿真結(jié)果

圖6給出了不同災(zāi)害模型下改進(jìn)ABC算法在迭代1 000次后得到的最優(yōu)路徑規(guī)劃結(jié)果。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的ABC算法在不同災(zāi)害場景下均能較好地規(guī)劃出安全、移動(dòng)距離短以及平滑的較優(yōu)路徑。

圖6 改進(jìn)ABC算法下路徑規(guī)劃結(jié)果Fig.6 Path planning results under improved ABC algorithm

4 結(jié)論

基于標(biāo)準(zhǔn)ABC算法全局探索能力強(qiáng),局部開發(fā)能力弱的特點(diǎn)提出一種自適應(yīng)收斂下的改進(jìn)ABC算法。在初始化階段采用全域采樣隨機(jī)初始化的方式可以保證初始解的隨機(jī)性和完整性;開采次數(shù)作為信息交互因子加入到選擇概率中,抑制局部最優(yōu)解選中概率,提升潛在較優(yōu)解選中概率;根據(jù)每個(gè)解在每個(gè)維度的開發(fā)次數(shù)設(shè)計(jì)全局最優(yōu)個(gè)體引導(dǎo)下的自適應(yīng)局部開發(fā)方程,提升局部開發(fā)精度。最后的仿真結(jié)果表明改進(jìn)ABC算法具備更優(yōu)的算法求解精度以及全局收斂性,能夠更好地解決復(fù)雜災(zāi)害場景下的路徑規(guī)劃問題。