復(fù)合形引導(dǎo)蜂群尋優(yōu)的無(wú)人機(jī)航跡多目標(biāo)規(guī)劃

劉 剛，裴紅蕾

（無(wú)錫工藝職業(yè)技術(shù)學(xué)院，江蘇 宜興 214200）

1 引言

無(wú)人機(jī)在軍用和民用領(lǐng)域均取得廣泛應(yīng)用，如植保無(wú)人機(jī)、救援無(wú)人機(jī)和空中偵查無(wú)人機(jī)等。植無(wú)人機(jī)在空中作業(yè)時(shí)必須躲避障礙物，同時(shí)為了達(dá)到經(jīng)濟(jì)性必須規(guī)劃出最短路徑；軍事無(wú)人機(jī)在執(zhí)行任務(wù)時(shí)也必須躲避敵人偵查和打擊區(qū)域，因此，無(wú)人機(jī)航跡規(guī)劃對(duì)無(wú)人機(jī)安全性和經(jīng)濟(jì)性意義重大。

無(wú)人機(jī)航跡規(guī)劃分為二維規(guī)劃和三維規(guī)劃，無(wú)人機(jī)在定值高度層飛行時(shí)為二維航跡，研究對(duì)象為無(wú)人機(jī)在二維空間的航跡規(guī)劃?；谌褐悄芩惴ǖ臒o(wú)人機(jī)航跡規(guī)劃是當(dāng)前研究的熱點(diǎn)[1]，包括遺傳算法、人工蜂群算法、粒子群算法、狼群算法、混沌捕食生物地理學(xué)算法等。文獻(xiàn)[2]將平衡演化策略引入到人工蜂群算法中，平衡了全局開(kāi)發(fā)和局部開(kāi)發(fā)能力，提高了航跡規(guī)劃速度；文獻(xiàn)[3]使用復(fù)合形法引導(dǎo)狼群搜索，提高了航跡解算速度；文獻(xiàn)[4]使用混沌捕食生物地理學(xué)算法規(guī)劃無(wú)人機(jī)航跡，此方法時(shí)效性更高；文獻(xiàn)[5]提出了改進(jìn)量子遺傳算法的無(wú)人機(jī)航跡規(guī)劃方法，仿真結(jié)果表明此方法規(guī)劃效率高、穩(wěn)定性好；文獻(xiàn)[6]提出了基于改進(jìn)智能單粒子優(yōu)化算法的無(wú)人機(jī)三維航跡規(guī)劃，與局部學(xué)習(xí)粒子群算法相比具有更強(qiáng)的尋優(yōu)能力。基于智能算法的無(wú)人機(jī)航跡規(guī)劃主要問(wèn)題在于算法原理或算法結(jié)構(gòu)不合理，導(dǎo)致難以搜尋到最優(yōu)航跡，或航跡不符合航跡要求。

基于人工蜂群算法，研究了無(wú)人機(jī)的二維航跡規(guī)劃問(wèn)題。在傳統(tǒng)人工蜂群算法基礎(chǔ)上，從初始化方法、蜜源搜索方法、蜜源選擇方法、復(fù)合形引導(dǎo)尋優(yōu)等四個(gè)方面進(jìn)行了改進(jìn)，達(dá)到提高航跡規(guī)劃的精度、速度和穩(wěn)定性的目的。

2 二維航跡規(guī)劃問(wèn)題描述

2.1 二維航跡規(guī)劃環(huán)境建模

設(shè)定無(wú)人機(jī)在定值高度層飛行，雷達(dá)、防空導(dǎo)彈、防空火炮等威脅簡(jiǎn)化為圓模型，如圖1所示。圓模型參數(shù)包括威脅中心、威脅半徑、威脅等級(jí)等三個(gè)參數(shù)。在此需要強(qiáng)調(diào)的是，威脅半徑為雷達(dá)、導(dǎo)彈的威脅半徑與無(wú)人機(jī)外接圓半徑之和，這樣可以將無(wú)人機(jī)簡(jiǎn)化為一個(gè)質(zhì)心。

圖1 無(wú)人機(jī)航跡規(guī)劃環(huán)境模型Fig.1 UAV Route Planning Environment Model

無(wú)人機(jī)航跡規(guī)劃的二維環(huán)境由給定起始點(diǎn)S、目標(biāo)定T及若干威脅區(qū)域組成，如圖1所示。航跡規(guī)劃描述為在S與T之間規(guī)劃出一條能夠避開(kāi)威脅區(qū)域且長(zhǎng)度最短的航跡。為了簡(jiǎn)化計(jì)算，將二維規(guī)劃問(wèn)題簡(jiǎn)化為一維規(guī)劃問(wèn)題，建立新坐標(biāo)系O′X′Y′，坐標(biāo)原點(diǎn)O′與S點(diǎn)重合，以S→T方向?yàn)閄′軸正向，Y′軸過(guò)O′點(diǎn)與X′垂直。在線段ST間等間距地插入個(gè)點(diǎn)，將ST等分為D+1段，在每個(gè)等分點(diǎn)上做ST的垂線Li，航跡規(guī)劃問(wèn)題就轉(zhuǎn)化為在各垂線Li上確定縱坐標(biāo)pi，將點(diǎn)pi進(jìn)行光滑連接就得到了無(wú)人機(jī)航跡。

記某點(diǎn)在坐標(biāo)系 OXY 中為（x，y），在坐標(biāo)系 O′X′Y′中對(duì)應(yīng)為（x′，y′），則兩者轉(zhuǎn)換關(guān)系為：

式中：θ—X軸與X′軸的夾角；（xs，ys）、（xT，yT）—起點(diǎn)S、目標(biāo)點(diǎn)T在坐標(biāo)系OXY中的坐標(biāo)。

2.2 航跡規(guī)劃約束條件

為提高航跡規(guī)劃效率和可行性，從無(wú)人機(jī)運(yùn)動(dòng)規(guī)律和硬件性能的角度出發(fā)，對(duì)航跡進(jìn)行以下幾個(gè)方面的約束：

（1）航跡長(zhǎng)度約束。無(wú)人機(jī)執(zhí)行任務(wù)時(shí)攜帶燃料有限，油耗與航跡長(zhǎng)度有很強(qiáng)的正相關(guān)關(guān)系，因此設(shè)置一個(gè)航跡長(zhǎng)度上限Lmax，航跡長(zhǎng)度約束公式為：

（2）轉(zhuǎn)向角約束。無(wú)人機(jī)由子航跡pk-1pk運(yùn)動(dòng)到pkpk+1時(shí)要經(jīng)歷轉(zhuǎn)彎過(guò)程，如圖2所示。規(guī)定轉(zhuǎn)彎角為ζ。為了保證無(wú)人機(jī)的飛行安全，必須設(shè)定轉(zhuǎn)向角閾值ζmax， 則轉(zhuǎn)向角約束可描述為：

圖2 子航跡圓滑處理Fig.2 Smooth Processing of Sub Route

轉(zhuǎn)彎點(diǎn)處的航跡需要做平滑處理，做航跡pk-1pk和pkpk+1的共切圓，航跡點(diǎn)pk-1和pk+1之間使用圓弧代替折線，實(shí)現(xiàn)航跡的平滑處理。

2.3 航跡規(guī)劃目標(biāo)函數(shù)

無(wú)人機(jī)航跡規(guī)劃目標(biāo)函數(shù)設(shè)置了三個(gè)方面的代價(jià)函數(shù)，分別為安全代價(jià)、長(zhǎng)度代價(jià)、轉(zhuǎn)向代價(jià)。

（1）安全代價(jià)函數(shù)。威脅區(qū)域是無(wú)人機(jī)飛行時(shí)時(shí)刻關(guān)注的要素，記無(wú)人機(jī)到第j個(gè)威脅中心距離為dxj，第j個(gè)威脅半徑為Rj，則無(wú)人機(jī)受第j個(gè)威脅的影響指數(shù)為：

式中：a，b＞1—威脅補(bǔ)償系數(shù)；Kj—第j個(gè)威脅物的威脅強(qiáng)度等級(jí)參數(shù)。當(dāng) dxj≤Rj時(shí)定義為高度危險(xiǎn)區(qū)域，當(dāng) Rj＜dxj＜bRj時(shí)定義為一般危險(xiǎn)區(qū)域，當(dāng)dxj＞bRj時(shí)定義為安全區(qū)域。

無(wú)人機(jī)航跡由D+1個(gè)子航跡組成，在此給出第i個(gè)子航跡受所有威脅的代價(jià)函數(shù)。取第i個(gè)子航跡9個(gè)樣本點(diǎn)，分別為1/10～9/10位置節(jié)點(diǎn)處受到威脅指數(shù)平均數(shù)，如圖3所示。作為此航跡的平均威脅指數(shù)，那么第i個(gè)子航跡受到的威脅定義為威脅平均數(shù)與長(zhǎng)度之積。則第i個(gè)子航跡安全代價(jià)函數(shù)為：

式中：li—第i個(gè)子航跡長(zhǎng)度；Ni—無(wú)人機(jī)所受威脅數(shù)量。

圖3 子航跡威脅采樣點(diǎn)Fig.3 Threat Sampling Point of Sub Route

（2）長(zhǎng)度代價(jià)。無(wú)人機(jī)航跡由D+1段子航跡組成，雖然在轉(zhuǎn)彎處進(jìn)行了圓弧平滑處理，但是依然可以使用直線段近似計(jì)算，則第個(gè)子航跡的長(zhǎng)度代價(jià)函數(shù)為：

（3）轉(zhuǎn)向代價(jià)。轉(zhuǎn)向會(huì)增加無(wú)人機(jī)的飛行時(shí)間和油耗，在一定程度上也會(huì)減少無(wú)人機(jī)使用壽命，因此轉(zhuǎn)彎次數(shù)越少越好，轉(zhuǎn)彎半徑越大越好。無(wú)人機(jī)的轉(zhuǎn)向代價(jià)函數(shù)為：

其中，轉(zhuǎn)彎角ζi的定義，如圖2所示。

綜合安全代價(jià)函數(shù)、長(zhǎng)度代價(jià)函數(shù)、轉(zhuǎn)向代價(jià)函數(shù)，得到無(wú)人機(jī)航跡規(guī)劃的目標(biāo)函數(shù)為：

式中：P=｛p1，p2，L，pD｝—無(wú)人機(jī)航跡；k1、k2、k3—長(zhǎng)度代價(jià)因子、威脅代價(jià)因子、轉(zhuǎn)向代價(jià)因子，通過(guò)調(diào)節(jié)k1、k2、k3可以實(shí)現(xiàn)優(yōu)化中心的調(diào)節(jié)。

3 傳統(tǒng)人工蜂群算法

3.1 算法原理

人工蜂群算法是受蜂群群體采蜜時(shí)分工協(xié)作啟發(fā)而提出的，算法通過(guò)以下5個(gè)步驟實(shí)現(xiàn)[7-8]：

（1）初始化。記種群數(shù)量為NB，初始時(shí)種群中所有個(gè)體均為偵查蜂，被隨機(jī)分配到各蜜源位置，即：

式中：i=1，2，L，NB—蜜蜂個(gè)體編號(hào) j=1，2，L；D—解的維度—第 j個(gè)位置點(diǎn)的上下界；rand（0，1）—（0，1）間的隨機(jī)數(shù)。

（2）蜜源評(píng)價(jià)。依據(jù)航跡規(guī)劃的目標(biāo)函數(shù)構(gòu)造蜜源評(píng)價(jià)函數(shù)，從而對(duì)蜜源優(yōu)劣做出評(píng)價(jià)。蜜源評(píng)價(jià)函數(shù)為：

式中：fi—第i只蜜蜂的適應(yīng)度值，這里fi=Ji表示第i只蜜蜂的目標(biāo)函數(shù)。使用蜜源評(píng)價(jià)函數(shù)對(duì)蜂群所有個(gè)體的蜜源進(jìn)行評(píng)價(jià)，蜜源較優(yōu)的偵查蜂轉(zhuǎn)化為雇傭蜂，蜜源靠后的偵查蜂轉(zhuǎn)化為觀察蜂。

（3）雇傭蜂蜜源搜索。雇傭蜂在當(dāng)前位置附近進(jìn)行蜜源搜索，當(dāng)新蜜源適應(yīng)度優(yōu)于原蜜源時(shí)則選擇新蜜源，否則繼續(xù)進(jìn)行搜索，雇傭蜂通過(guò)這種貪婪規(guī)則不斷優(yōu)化蜜源，雇傭蜂的搜索位置更新方法為：

（4）觀察蜂選擇與鄰域搜索。觀察蜂依據(jù)適應(yīng)度值計(jì)算選擇各蜜源的概率，為：

式中：pi—觀察蜂選擇雇傭蜂的概率；—雇傭蜂數(shù)量。

由式（12）可知，依據(jù)各蜜源適應(yīng)度值確定選擇概率，可以保證較優(yōu)蜜源更大的選擇概率，確保更優(yōu)蜜源附近的細(xì)致搜索。觀察蜂選擇雇傭蜂后與雇傭蜂一起進(jìn)行鄰域搜索，觀察蜂的位置更新方法和蜜源選擇方法與雇傭蜂一致。

（5）偵查蜂的蜜源搜索。若某只蜜蜂在一個(gè)蜜源鄰域連續(xù)搜索次數(shù)達(dá)到一個(gè)上限且適應(yīng)度值沒(méi)有明顯提高，則此蜜蜂放棄當(dāng)前蜜源，轉(zhuǎn)化為偵查蜂，在搜索區(qū)域內(nèi)進(jìn)行隨機(jī)搜索，其位置更新方式為：

式中：j=1，2，L；D—解的維度。

3.2 算法流程圖

根據(jù)3.1節(jié)的算法原理，給出算法流程圖，如圖4所示。

圖4 人工蜂群算法流程圖Fig.4 Flow Chart of Artificial Bee Swarm Algorithm

4 復(fù)合形引導(dǎo)蜂群算法及流程

4.1 復(fù)合形引導(dǎo)蜂群算法

為了提高人工蜂群算法的尋優(yōu)能力和尋優(yōu)速度，從以下4個(gè)方面對(duì)算法進(jìn)行改進(jìn)。

（1）改進(jìn)蜜源初始化。蜜源初始化的結(jié)果是生成一個(gè)NB×D的矩陣，每個(gè)行相量xi=（xi1，xi2，L xiD）表示一個(gè)蜜源位置。如果使用式（9）所示的傳統(tǒng)初始化方法，前后航跡點(diǎn)之間沒(méi)有任何關(guān)聯(lián)，導(dǎo)致初始化的大部分航跡不符合轉(zhuǎn)向要求，也就意味著航跡不可行，不但浪費(fèi)了搜索時(shí)間，還占用了計(jì)算資源。為了解決這一問(wèn)題，如圖5所示。依據(jù)此圖推導(dǎo)出蜜源初始化方法為：

式中：（2xi（j-1）-xi（j-2））—圖5中點(diǎn)A的縱坐標(biāo)；step—由轉(zhuǎn)向角閾值確定的步長(zhǎng)。

圖5 蜜源初始化方法Fig.5 Honey Source Initialization Method

（2）改進(jìn)雇傭蜂和觀察蜂的蜜源搜索方法。傳統(tǒng)算法中，雇傭蜂和觀察蜂采用隨機(jī)位置更新方式搜索蜜源，當(dāng)前最優(yōu)蜜源沒(méi)有起到任何“榜樣作用”。為了充分發(fā)揮較優(yōu)蜜源在種群中的優(yōu)勢(shì)，提出隨機(jī)搜索與最優(yōu)蜜源引導(dǎo)相結(jié)合的位置更新方式，設(shè)定概率值P1，在（0，1）內(nèi)產(chǎn)生隨機(jī)數(shù)?，若?＜P1則使用最優(yōu)蜜源引導(dǎo)的位置更新方法，若?≥P1則使用式（11）給出的位置更新方法。最優(yōu)蜜源引導(dǎo)的位置更新方法為：

式中：xbext—蜂群搜索到的最優(yōu)蜜源。

（3）改進(jìn)蜜源選擇方法。傳統(tǒng)算法中，依據(jù)蜜源適應(yīng)度值大小決定是否接受蜜源，這種選擇方式過(guò)早地將有潛力的蜜源淘汰掉，使算法前期收斂較快，算法后期收斂較慢。為了解決這一問(wèn)題，提出了蜜源選擇的Metropolis準(zhǔn)則[9]，蜜蜂由當(dāng)前蜜源轉(zhuǎn)o向新蜜源n的轉(zhuǎn)移概率為：

式中：p（0/n）—由當(dāng)前蜜源o向新蜜源n轉(zhuǎn)移的概率，下降函數(shù)T（t）=T（t-1）·σ；σ—退火系數(shù)，取 σ=0.7。

分析式（16）可知，當(dāng)新蜜源適應(yīng)度小于原蜜源時(shí)，仍有一定的轉(zhuǎn)移概率，有利于保留具有潛力的蜜源；在算法初期，退火溫度T（t）較高，適應(yīng)度差的蜜源轉(zhuǎn)移概率較大，保留有潛力蜜源的概率也大，有利于算法跳出局部最優(yōu)；算法后期退火溫度逐漸減小，算法更加“關(guān)注”優(yōu)質(zhì)蜜源，更多蜜蜂在優(yōu)質(zhì)蜜源鄰域內(nèi)細(xì)致搜索，提高尋優(yōu)精度。

（4）復(fù)合形法引導(dǎo)蜂群尋優(yōu)。為了提高傳統(tǒng)算法收斂速度，提出了復(fù)合形法引導(dǎo)的人工蜂群算法，復(fù)合形法通過(guò)不斷的反射、延伸和收縮等操作引導(dǎo)蜂群向最優(yōu)蜜源靠近[10]，在算法迭代一次結(jié)束后，選取u個(gè)優(yōu)秀蜜源，按適應(yīng)度由大到小排序（x1，x2，L，xu），則復(fù)合形法對(duì)蜂群引導(dǎo)步驟為：

（1）計(jì)算復(fù)合形形心xc=1/u·

（2）計(jì)算反射點(diǎn) xr=xc+α（xc-xu），式中 α=1.3 為反射系數(shù)，若 xr優(yōu)于xu，則使用xr替換xu，否則轉(zhuǎn)至 Step4；

（3）計(jì)算延伸點(diǎn) xe=xr+β（xr-xc），式中 β=0.6 為延伸系數(shù)，若 xe優(yōu)于 xu，則使用 xe替換 xu，否則轉(zhuǎn)至（4）；

（4）計(jì)算收縮點(diǎn) xs=xu+χ（xc-xu），式中 χ=0.7 為收縮系數(shù)，若 xs優(yōu)于xu，則使用xs替換xu，否則繼續(xù)；

（5）判斷是否達(dá)到最大迭代次數(shù)，若是則結(jié)束，否則轉(zhuǎn)至（1）。

4.2 復(fù)合形引導(dǎo)人工蜂群算法流程

根據(jù)4.1節(jié)對(duì)傳統(tǒng)人工蜂群算法原理的改進(jìn)，給出改進(jìn)人工蜂群算法步驟為：（1）初始化改進(jìn)算法參數(shù)：種群規(guī)模NB、單蜜源最大停留次數(shù)Limit、最大迭代次數(shù)MaxCycle、概率值P1、復(fù)合形法最大引導(dǎo)次數(shù)MaxGuide，設(shè)置trial（i）=0，iter=0；（2）按照式（14）進(jìn)行種群初始化，依據(jù)適應(yīng)度值將蜜蜂分為雇傭蜂和觀察蜂；（3）雇傭蜂進(jìn)行鄰域搜索，使用Metropolis準(zhǔn)則判斷是否接受新蜜源，而后將蜜源信息傳遞給觀察蜂；（4）觀察蜂根據(jù)各蜜源適應(yīng)度值確定選擇概率，而后與雇傭蜂一起進(jìn)行鄰域搜索，使用Metropolis準(zhǔn)則判斷是否接受新蜜源，若蜜源更新則trial（i）=0，若不更新則，trial（i）=trial（i）+1；（5）判斷trial（i）＞Limit是否成立，若成立則第i只蜜蜂轉(zhuǎn)化為偵查蜂，使用式（13）進(jìn)行隨機(jī)搜索，若不成立則轉(zhuǎn)至下一步；（6）從尋優(yōu)結(jié)果中選出適應(yīng)度值最大的前u個(gè)蜜源，使用復(fù)合形法引導(dǎo)尋優(yōu)次；（7）輸出全局最優(yōu)蜜源，iter=iter+1，判斷 iter＞MaxCycle 是否成立，若成立則算法結(jié)束，否則轉(zhuǎn)至（3）。

5 仿真驗(yàn)證

為了驗(yàn)證復(fù)合形引導(dǎo)人工蜂群算法和建立模型在無(wú)人機(jī)規(guī)劃中的有效性，使用Matlab R2014a軟件進(jìn)行仿真驗(yàn)證。無(wú)人機(jī)工作在（100×100）的區(qū)域內(nèi)，航跡點(diǎn)個(gè)數(shù)為21，環(huán)境中的威脅區(qū)域，如表1所示。算法主要參數(shù)設(shè)置為：最大迭代次數(shù)MaxCycle=500、種群規(guī)模NB=60、單蜜源最大停留次數(shù)Limit=5、復(fù)合形使用蜜源數(shù)量u=10。

表1 各威脅參數(shù)Tab.1 Parameters of Every Threaten

為了形成對(duì)比，分別使用改進(jìn)人工蜂群算法、基于混沌擾動(dòng)的改進(jìn)人工蜂群算法[11]、傳統(tǒng)人工蜂群算法進(jìn)行航跡規(guī)劃，各算法進(jìn)行仿真20次，每種算法規(guī)劃的最優(yōu)航跡，如圖6所示。計(jì)算各算法在相同迭代次數(shù)時(shí)目標(biāo)函數(shù)平均值，結(jié)果如圖7所示。由圖6可知，三種算法規(guī)劃的航跡都能夠躲避威脅，順利完成任務(wù)。但是改進(jìn)人工蜂群算法規(guī)劃的航跡最為平滑、長(zhǎng)度最短且轉(zhuǎn)向角最小。由圖7可知，改進(jìn)人工蜂群算法迭代50次時(shí)基本收斂，收斂速度最快且尋優(yōu)結(jié)果也最好。為了更加有力地比較三種算法的性能，統(tǒng)計(jì)三種算法的尋優(yōu)結(jié)果，如表2所示。表2中算法耗時(shí)為20次尋優(yōu)的平均耗時(shí)，收斂迭代次數(shù)為算法基本收斂時(shí)的迭代次數(shù)，尋優(yōu)耗時(shí)為20次仿真尋找到最優(yōu)解的平均耗時(shí)，收斂值均值與標(biāo)準(zhǔn)差為20次仿真目標(biāo)函數(shù)值的均值與標(biāo)準(zhǔn)差。分析表2可知，提出的改進(jìn)人工蜂群算法單次循環(huán)的耗時(shí)略小于另外兩種算法，但是改進(jìn)算法在迭代50次時(shí)就收斂，較傳統(tǒng)人工蜂群算法與混沌擾動(dòng)人工蜂群算法分別減少了4倍、6倍；改進(jìn)算法的尋優(yōu)耗時(shí)為0.82s，比傳統(tǒng)人工蜂群算法與混沌擾動(dòng)人工蜂群算法降低了約一個(gè)數(shù)量級(jí)；改進(jìn)算法目標(biāo)函數(shù)值均值與標(biāo)準(zhǔn)差均小于傳統(tǒng)人工蜂群算法與混沌擾動(dòng)人工蜂群算法，說(shuō)明改進(jìn)算法規(guī)劃的航跡更優(yōu)、穩(wěn)定性更強(qiáng)。

圖6 不同算法的航跡規(guī)劃結(jié)果Fig.6 Route Planning Result of Different Algorithm

圖7 不同算法的目標(biāo)函數(shù)值曲線Fig.7 Goal Function Value of Different Algorithm

表2 不同算法優(yōu)化結(jié)果統(tǒng)計(jì)Tab.2 Optimization Result Statistics of Different Algorithm

6 結(jié)論

研究了無(wú)人機(jī)的二維航跡規(guī)劃問(wèn)題，建立了環(huán)境規(guī)劃模型和問(wèn)題數(shù)學(xué)模型，從初始化方法、蜜源搜索方式、蜜源選擇方法、復(fù)合形法引導(dǎo)蜂群尋優(yōu)等四個(gè)方面改進(jìn)了人工蜂群算法，經(jīng)仿真驗(yàn)證改進(jìn)算法的尋優(yōu)速度、尋優(yōu)精度、尋優(yōu)穩(wěn)定性均有很大提高。