采用改進(jìn)細(xì)菌覓食優(yōu)化算法的無(wú)人機(jī)航跡規(guī)劃*

魏永超a，鄧 嵐**，李 濤c，鄧 毅c，鄧春艷

(1.中國(guó)民用航空飛行學(xué)院 a.學(xué)院科研處；b.民航飛行技術(shù)與飛行安全科研基地；c.民航安全工程學(xué)院，四川 廣漢 618307)

0 引 言

基于上述算法的局限性，本文提出一種基于改進(jìn)細(xì)菌覓食優(yōu)化算法(Improved Bacterial Foraging Optimization,IBFO)的航跡規(guī)劃算法，且針對(duì)基本細(xì)菌覓食優(yōu)化算法(Bacterial Foraging Optimization,BFO)易早熟和收斂速度慢等缺陷，對(duì)算法的趨向步長(zhǎng)、游動(dòng)及遷徙操作進(jìn)行改進(jìn)。首先，在趨向時(shí)，通過賦予細(xì)菌自適應(yīng)的步長(zhǎng)來(lái)代替細(xì)菌的固定趨向步長(zhǎng)；其次，嵌入粒子群算法(Partical Swarm Optimization,PSO)的學(xué)習(xí)因子思想，一個(gè)細(xì)菌的游動(dòng)不僅受限于自身的覓食能力，還受到其他細(xì)菌的影響；最后，在遷徙時(shí)，提出一種自適應(yīng)的遷徙概率代替固定的遷徙概率。

算法通過比較目標(biāo)函數(shù)，找到代價(jià)最小的航跡點(diǎn)，最終得到最優(yōu)的航跡結(jié)果。通過Matlab建立三維環(huán)境模型，仿真測(cè)試后驗(yàn)證，該算法是可行和有效的，且相比基本的細(xì)菌覓食優(yōu)化算法和粒子群算法提高了收斂速度和求解質(zhì)量，能夠快速安全地實(shí)現(xiàn)無(wú)人機(jī)的航跡規(guī)劃。

1 IBFO算法原理

將基本的BFO算法通過三個(gè)方面的改進(jìn)得到IBFO，并應(yīng)用于無(wú)人機(jī)航跡規(guī)劃。

1.1 基本BFO理論

細(xì)菌覓食優(yōu)化算法(Bacterial Foraging Optimization，BFO)是由 Passino 基于大腸桿菌的覓食行為，于2002年提出的一種新型仿生類的群體智能優(yōu)化算法。該算法模仿Eeoli大腸桿菌在人體腸道內(nèi)吞噬食物的行為，通過模擬細(xì)菌遷徙、趨向、聚集、復(fù)制四種行為求解問題[9]。

(1)遷徙(Elimination and Dispersal)：當(dāng)細(xì)菌所處的局部環(huán)境逐漸發(fā)生變化或者突變時(shí)(如食物消耗殆盡或溫度突然升高)，細(xì)菌會(huì)隨機(jī)以給定的遷徙概率Ped遷徙到一個(gè)新的區(qū)域以應(yīng)對(duì)這種改變。該行為中，細(xì)菌中的個(gè)體以一定概率死亡并在一個(gè)新的區(qū)域生成一個(gè)新的細(xì)菌，從而更有利于算法跳出局部最優(yōu)解，進(jìn)而尋找全局最優(yōu)解[10]。

(2)趨向(Chemotaxis)：細(xì)菌將會(huì)進(jìn)行旋轉(zhuǎn)和游動(dòng)，趨向食物豐富或環(huán)境酸堿度適中的區(qū)域。旋轉(zhuǎn)是指向一個(gè)新的方向，游動(dòng)指若適應(yīng)度值得到改善則保持這一方向向前運(yùn)動(dòng)，直至適應(yīng)度值不再改善[11]。趨向行為的數(shù)學(xué)表達(dá)式為

(1)

式中：θi(j,k,l)表示細(xì)菌i在第j次趨向、第k次復(fù)制、第l次驅(qū)散后所處的位置，C(i)為細(xì)菌的趨向步長(zhǎng)，Δ(i)為細(xì)菌在搜索空間內(nèi)隨機(jī)方向上的一個(gè)單位向量。

(3)聚集(Swarming)：細(xì)菌在覓食時(shí)，不同個(gè)體間存在引力和斥力，引力使細(xì)菌更多地聚向食物豐富或環(huán)境酸堿度適中的區(qū)域，斥力使每個(gè)細(xì)菌在搜索空間內(nèi)都有一定的覓食區(qū)域，令其能在該位置上獲取能量來(lái)維持生存[12]。聚集行為的數(shù)學(xué)表達(dá)式為

(2)

(4)復(fù)制(Reproduction)：細(xì)菌進(jìn)化服從“適者生存、優(yōu)勝劣汰”，覓食能力弱的細(xì)菌會(huì)被淘汰，覓食能力強(qiáng)的細(xì)菌進(jìn)行復(fù)制。式(3)被稱為細(xì)菌i的適應(yīng)值，該值越小，表明細(xì)菌i越健康，覓食能力越強(qiáng)。

(3)

算法中，一個(gè)細(xì)菌代表一個(gè)解，搜索空間中細(xì)菌的位置對(duì)應(yīng)著優(yōu)化問題的解，優(yōu)化函數(shù)的適應(yīng)度值即目標(biāo)函數(shù)的值，代表解的優(yōu)良程度。

1.2 IBFO算法

BFO算法中，個(gè)體的步長(zhǎng)和遷徙概率是固定不變的，步長(zhǎng)的不變性會(huì)影響最優(yōu)解的精確度，遷徙概率不變則會(huì)導(dǎo)致算法后期的收斂速度變慢。基于上述考慮，本文在研究基本細(xì)菌覓食優(yōu)化算法基礎(chǔ)上，進(jìn)行了以下三個(gè)方向的改進(jìn)，得到了優(yōu)化能力更好的改進(jìn)細(xì)菌覓食優(yōu)化算法。

(1)細(xì)菌在移動(dòng)中的固定步長(zhǎng)會(huì)使收斂速度較慢，因此將固定步長(zhǎng)改進(jìn)為自適應(yīng)的步長(zhǎng)。文獻(xiàn)[13]中,采用Cmax為尋優(yōu)范圍最大值的1/4，同時(shí)依賴趨向、復(fù)制和遷徙的次數(shù)j、k、l的乘積來(lái)使搜索更加精確，并采用rand函數(shù)使運(yùn)算量減小，最后使得細(xì)菌在不同維度前進(jìn)不同的步長(zhǎng)，前期搜索效率高，后期搜索精度高。公式如下所示：

(4)

式中：rand()為從0～1的隨機(jī)數(shù)；Cmax=(MAXd-MINd)/4，MAXd為第d維尋優(yōu)范圍最大值，MINd為第d維尋優(yōu)范圍最小值；j，k，l分別為當(dāng)前趨向、復(fù)制和遷徙次數(shù)。

式(4)的改進(jìn)雖提高了步長(zhǎng)遞減的變化，但尋優(yōu)前進(jìn)的方向較隨機(jī)。本文的IBFO算法將在此基礎(chǔ)上，加入尋優(yōu)方向的限制，以提高算法的精度。

據(jù)細(xì)菌和最優(yōu)點(diǎn)之間的距離來(lái)調(diào)節(jié)步長(zhǎng)，若兩者距離遠(yuǎn)，則步長(zhǎng)加大；距離近，則步長(zhǎng)減小，從而提高收斂速度。將通過下列公式實(shí)現(xiàn)：

(5)

式中：Ji為當(dāng)前細(xì)菌i的適應(yīng)值，Jmax為當(dāng)前所有細(xì)菌最大的適應(yīng)值。

(2)嵌入粒子群算法的學(xué)習(xí)因子思想，一個(gè)細(xì)菌的游動(dòng)不僅受限于自身的覓食能力，還受到其他細(xì)菌的影響。即對(duì)于一個(gè)細(xì)菌，將它的適應(yīng)度函數(shù)值與當(dāng)前覓食能力最好的細(xì)菌進(jìn)行比較，通過交流學(xué)習(xí)覓食能力更好的細(xì)菌來(lái)提高自己的覓食能力。其函數(shù)由式(6)給出:

Δ(i)′=Δ(i)+C1rand()×(Jmax-Ji)+

(6)

(3)基本BFO算法中，遷徙概率為一個(gè)定值，即所有細(xì)菌都以Ped遷徙到一個(gè)新的區(qū)域，這可能會(huì)導(dǎo)致精英個(gè)體丟失，算法的收斂速度、精度和穩(wěn)定性降低[14]。因此，本文將采用自適應(yīng)的遷徙概率，通過下式實(shí)現(xiàn)：

(7)

式中：Jmin為當(dāng)前所有細(xì)菌最小的適應(yīng)值,Ped為設(shè)置的固定遷徙概率。

通過改進(jìn)，適應(yīng)度函數(shù)值小的細(xì)菌遷徙概率大，適應(yīng)度函數(shù)值大的細(xì)菌遷徙概率小。這將保證覓食能力最好的細(xì)菌一定會(huì)被遷移，從而提高了算法的穩(wěn)定性。

2 IBFO算法航跡規(guī)劃

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

航跡規(guī)劃的目的即在確保無(wú)人機(jī)安全飛行的前提下，規(guī)避威脅區(qū)域，如陡峭的山峰、惡劣的天氣等，最后規(guī)劃出一條從起點(diǎn)到終點(diǎn)的最短路徑。本質(zhì)上來(lái)說，就是一個(gè)求解包含眾多約束條件的函數(shù)最優(yōu)解問題[15]，其數(shù)學(xué)形式可由公式(8)表述：

minf=w1×minf1+w2×minf2+…

+wn×minfn。

(8)

式中：f(x)是目標(biāo)函數(shù)，w1、w2…wn是權(quán)重系數(shù)，f1(x)、f2(x)…fn(x)是約束條件函數(shù)。本文中航跡規(guī)劃模型將采用以下三個(gè)約束條件：

(1)路徑最短約束

即求從第一個(gè)導(dǎo)航點(diǎn)到最后一個(gè)導(dǎo)航點(diǎn)的最短總路徑長(zhǎng)度：

(9)

式中：dx、dy、dz為當(dāng)前導(dǎo)航點(diǎn)減去前一個(gè)導(dǎo)航點(diǎn)的x方向、y方向、z方向的距離差。

(2)飛行高度約束

無(wú)人機(jī)的飛行高度不能過高也不能過低。若飛行高度過高，會(huì)超出無(wú)人機(jī)機(jī)身承受范圍，對(duì)機(jī)體造成損傷；若飛行高度過低，會(huì)增加無(wú)人機(jī)的撞毀概率。因此，需要讓無(wú)人機(jī)在一個(gè)合適的高度飛行，且要求飛行過程中盡量保持平穩(wěn)，以減少油耗以及機(jī)器的損耗。由下式表示：

(10)

(3)轉(zhuǎn)彎角約束

轉(zhuǎn)彎角即是無(wú)人機(jī)從這個(gè)導(dǎo)航點(diǎn)到下個(gè)導(dǎo)航點(diǎn)轉(zhuǎn)過的角度。在飛行過程中，由于無(wú)人機(jī)自身的制造工藝約束，不同的無(wú)人機(jī)具有不同的物理性能，但都不能突然進(jìn)行大角度的轉(zhuǎn)彎。同時(shí)，約束轉(zhuǎn)彎角可以避免無(wú)人機(jī)迂回前進(jìn)。由式(11)、(12)所示：

(11)

ai=(xi+1-xi,yi+1-yi,zi+1-zi)T。

(12)

以上三個(gè)約束條件通過權(quán)重的分配，共同構(gòu)成了航跡規(guī)劃的目標(biāo)函數(shù)，從而將搜索一條航跡代價(jià)小的路徑規(guī)劃問題巧妙地變?yōu)橥ㄟ^智能優(yōu)化算法求目標(biāo)函數(shù)最小值的數(shù)學(xué)問題。這樣將實(shí)際問題進(jìn)行量化，轉(zhuǎn)化為規(guī)劃系統(tǒng)能識(shí)別的數(shù)學(xué)符號(hào)，是航跡規(guī)劃技術(shù)的發(fā)展的一大重要板塊。

2.2 IBFO無(wú)人機(jī)航跡規(guī)劃流程

如圖1所示，將IBFO算法應(yīng)用在求解無(wú)人機(jī)航跡規(guī)劃問題，可分為以下四個(gè)步驟：

Step1 讀取坐標(biāo)數(shù)據(jù)，完成數(shù)字地形高程圖的建模。設(shè)置起點(diǎn)S、終點(diǎn)T的坐標(biāo)。

Step2 初始化IBFO參數(shù)，包括細(xì)菌進(jìn)行遷徙行為的次數(shù)、細(xì)菌進(jìn)行趨向行為的次數(shù)、細(xì)菌進(jìn)行聚集行為的次數(shù)、細(xì)菌進(jìn)行復(fù)制行為的次數(shù)、細(xì)菌的遷徙概率、向前游動(dòng)的步長(zhǎng)、細(xì)菌種群大小、引力深度、引力寬度、斥力深度、斥力寬度、局部學(xué)習(xí)因子、全局學(xué)習(xí)因子、迭代次數(shù)。

Step3 算法迭代。細(xì)菌不斷進(jìn)行遷徙、趨向、聚集、復(fù)制操作，采用改進(jìn)的IBFO算法求解航跡規(guī)劃目標(biāo)函數(shù)最小值，同時(shí)，避免飛入天氣威脅區(qū)和禁飛區(qū)，得到從起點(diǎn)到終點(diǎn)的n個(gè)導(dǎo)航點(diǎn)。

Step4 迭代結(jié)束，規(guī)劃出最優(yōu)路徑。

此無(wú)人機(jī)航跡規(guī)劃優(yōu)化模型采用改進(jìn)的細(xì)菌覓食優(yōu)化算法，通過不斷迭代尋找目標(biāo)函數(shù)更小的導(dǎo)航點(diǎn)，在設(shè)定的迭代次數(shù)完成后結(jié)束迭代。迭代次數(shù)通過經(jīng)驗(yàn)取得，可以使目標(biāo)函數(shù)達(dá)到收斂。最終將得到的n個(gè)導(dǎo)航點(diǎn)連接起來(lái)，即得到了規(guī)劃出來(lái)的航跡。

圖1中，Ned為遷徒行為的次數(shù)，Nre為告別行為的次數(shù)，S為細(xì)菌種群個(gè)數(shù)，Nc為趨向行為的次數(shù)，Ns為趨向行為中單向運(yùn)動(dòng)最大步數(shù)，最小的適應(yīng)度函數(shù)值存儲(chǔ)為Jend。

圖1 將IBFO算法應(yīng)用于航跡規(guī)劃

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

3.1 航跡規(guī)劃環(huán)境建模

環(huán)境建模大致可分為兩類：基于二維平面建模和基于三維立體建模。目前，全球應(yīng)用較廣的是數(shù)字地形高程數(shù)據(jù)庫(kù)(Digital Terrain Elevation Data，DTED)。數(shù)字地圖的種類也有很多，包括數(shù)字柵格地圖、數(shù)字高程模型(Digital Elevation Model，DME)、數(shù)字線劃地圖和數(shù)字遙感影像圖等[16]。本文采用數(shù)字高程模型進(jìn)行三維立體建模，通過z=z(x,y)表示地形，其中(x,y)為平面二維網(wǎng)格坐標(biāo)，z為高度。

本文選取了緯度范圍從31度22分42.28秒到31度30分02.56秒，經(jīng)度范圍從102度52分23.26秒到102度59分52.05秒的真實(shí)地形，如圖2所示。

圖2 真實(shí)地形

隨后，通過數(shù)字地形高程數(shù)據(jù)庫(kù)獲取高程點(diǎn)，通過仿真，按照1∶100000的比例均勻離散化為139×139的坐標(biāo)空間。同時(shí)，由于在真實(shí)飛行中天氣威脅區(qū)和政治敏感禁飛區(qū)不可忽略，因此將這些區(qū)域在航跡規(guī)劃空間中等效為圓柱型區(qū)域，無(wú)人機(jī)在飛行過程中必須繞過這些障礙。算法經(jīng)過兩個(gè)步驟避開障礙：第一步，所有航跡點(diǎn)不會(huì)落在圓柱體中；第二步，已得到的兩個(gè)相鄰航跡點(diǎn)之間的連線與圓柱體不能有交點(diǎn)。

本文設(shè)置了兩個(gè)天氣威脅區(qū)和一個(gè)禁飛區(qū)。兩個(gè)天氣威脅區(qū)為紅色圓柱形，平面坐標(biāo)分別為(70,70)、(80,30)，半徑均為10；一個(gè)禁飛區(qū)為藍(lán)色圓柱形，平面坐標(biāo)為(100,100)，半徑為7，由于離散化坐標(biāo)空間，無(wú)單位。最后的數(shù)字地形高程圖如圖3所示。

圖3 數(shù)字地形高程圖

3.2 算法驗(yàn)證

為了驗(yàn)證本文算法的有效性，采用Matlab R2017b對(duì)算法進(jìn)行仿真。函數(shù)變量范圍為整個(gè)三維空間大小，算法具體參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

無(wú)人機(jī)航跡規(guī)劃仿真結(jié)果如圖4所示。仿真設(shè)置了兩個(gè)起點(diǎn)，起點(diǎn)1為紅色圓型，坐標(biāo)為(20,20,4.245)；起點(diǎn)2為紅色三角形，坐標(biāo)為(40,20,4.245)。終點(diǎn)為黑色*型，坐標(biāo)為(90,70,2.7)，坐標(biāo)中的高度單位為km。仿真采用了三個(gè)算法實(shí)現(xiàn)無(wú)人機(jī)航跡規(guī)劃，分別是改進(jìn)細(xì)菌覓食優(yōu)化算法、粒子群算法與基本的細(xì)菌覓食優(yōu)化算法，得到的航跡顏色分別為藍(lán)色、綠色、紅色，從圖中可以清晰地觀察到各條航跡。

圖4 航跡規(guī)劃仿真軌跡

為了更好、更直觀地進(jìn)行對(duì)比，將航跡投影到緯度坐標(biāo)，起點(diǎn)1到終點(diǎn)和起點(diǎn)2到終點(diǎn)的兩組航跡仿真結(jié)果分別如圖5和圖6所示，可以較為明顯地看出采用IBFO算法規(guī)劃的航跡路徑最短，飛行最平穩(wěn)。

圖5 起點(diǎn)1航跡規(guī)劃仿真軌跡投影圖

圖6 起點(diǎn)2航跡規(guī)劃仿真軌跡投影圖

同時(shí)，起點(diǎn)1到終點(diǎn)和起點(diǎn)2到終點(diǎn)的兩組目標(biāo)函數(shù)隨迭代次數(shù)變化情況分別如圖7和圖8所示,可以看出迭代次數(shù)為40的時(shí)候，目標(biāo)函數(shù)基本收斂，因此更改參數(shù)MAX為40，并測(cè)試算法運(yùn)行時(shí)間來(lái)對(duì)比收斂速度。

圖7 起點(diǎn)1目標(biāo)函數(shù)變化曲線

圖8 起點(diǎn)2目標(biāo)函數(shù)變化曲線

各條航跡的長(zhǎng)度、高度的均方差、目標(biāo)函數(shù)最終值以及算法運(yùn)行時(shí)間如表2所示。

表2 航跡規(guī)劃參數(shù)結(jié)果

由表2的兩組數(shù)據(jù)可清晰得出，相比采用BFO算法和PSO算法進(jìn)行航跡規(guī)劃，采用IBFO算法進(jìn)行航跡規(guī)劃的航跡長(zhǎng)度最短，高度均方差和目標(biāo)函數(shù)最小，算法運(yùn)行時(shí)間最短，因此采用IBFO算法規(guī)劃出的航跡是更優(yōu)的。

改進(jìn)的細(xì)菌覓食優(yōu)化算法相比基本的細(xì)菌覓食優(yōu)化算法和粒子群算法有以下優(yōu)點(diǎn)：

(1)算法具有更高的全局搜索能力。粒子群算法全局搜索時(shí)容易早熟,而改進(jìn)的細(xì)菌覓食優(yōu)化算法將固定步長(zhǎng)改為自適應(yīng)步長(zhǎng)，加入尋優(yōu)方向的限制以及嵌入學(xué)習(xí)因子思想，因此全局搜索能力得到很大的提高。

(2)算法具有更好的穩(wěn)定性。將固定遷徙概率改為自適應(yīng)遷徙概率，通過改進(jìn)加快了收斂速度，提高了算法的穩(wěn)定性，相比粒子群算法容易陷入局部最優(yōu)而導(dǎo)致的不易收斂，能更好地進(jìn)行航跡規(guī)劃。

4 結(jié)束語(yǔ)

本文提出了一種基于改進(jìn)的細(xì)菌覓食優(yōu)化算法，在無(wú)人機(jī)航跡規(guī)劃任務(wù)中得到應(yīng)用，同時(shí)利用數(shù)字地形高程數(shù)據(jù)庫(kù)進(jìn)行三維環(huán)境建模仿真，直觀展示出了航跡的軌跡。由仿真結(jié)果可得，基于改進(jìn)的細(xì)菌覓食優(yōu)化算法可以規(guī)劃出路徑更短、飛行更平穩(wěn)、油耗更小更經(jīng)濟(jì)的航跡。

本文對(duì)工程實(shí)際有引導(dǎo)意義，如在實(shí)際工程中實(shí)現(xiàn)，會(huì)大大優(yōu)化航跡規(guī)劃。但算法仍存在一些不足，如嵌入學(xué)習(xí)因子、引入自適應(yīng)機(jī)制改善啟發(fā)算法，雖帶來(lái)精度的提高，但同時(shí)會(huì)增加算法復(fù)雜度。下一步計(jì)劃融合其他人工啟發(fā)式算法繼續(xù)進(jìn)行算法的改進(jìn)，并考慮用無(wú)人機(jī)進(jìn)行真實(shí)的實(shí)驗(yàn)驗(yàn)證。