采用改進細菌覓食優化算法的無人機航跡規劃*

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

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

0 引 言

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

算法通過比較目標函數，找到代價最小的航跡點，最終得到最優的航跡結果。通過Matlab建立三維環境模型，仿真測試后驗證，該算法是可行和有效的，且相比基本的細菌覓食優化算法和粒子群算法提高了收斂速度和求解質量，能夠快速安全地實現無人機的航跡規劃。

1 IBFO算法原理

將基本的BFO算法通過三個方面的改進得到IBFO，并應用于無人機航跡規劃。

1.1 基本BFO理論

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

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

(2)趨向(Chemotaxis)：細菌將會進行旋轉和游動，趨向食物豐富或環境酸堿度適中的區域。旋轉是指向一個新的方向，游動指若適應度值得到改善則保持這一方向向前運動，直至適應度值不再改善[11]。趨向行為的數學表達式為

(1)

式中：θi(j,k,l)表示細菌i在第j次趨向、第k次復制、第l次驅散后所處的位置，C(i)為細菌的趨向步長，Δ(i)為細菌在搜索空間內隨機方向上的一個單位向量。

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

(2)

(4)復制(Reproduction)：細菌進化服從“適者生存、優勝劣汰”，覓食能力弱的細菌會被淘汰，覓食能力強的細菌進行復制。式(3)被稱為細菌i的適應值，該值越小，表明細菌i越健康，覓食能力越強。

(3)

算法中，一個細菌代表一個解，搜索空間中細菌的位置對應著優化問題的解，優化函數的適應度值即目標函數的值，代表解的優良程度。

1.2 IBFO算法

BFO算法中，個體的步長和遷徙概率是固定不變的，步長的不變性會影響最優解的精確度，遷徙概率不變則會導致算法后期的收斂速度變慢。基于上述考慮，本文在研究基本細菌覓食優化算法基礎上，進行了以下三個方向的改進，得到了優化能力更好的改進細菌覓食優化算法。

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

(4)

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

式(4)的改進雖提高了步長遞減的變化，但尋優前進的方向較隨機。本文的IBFO算法將在此基礎上，加入尋優方向的限制，以提高算法的精度。

據細菌和最優點之間的距離來調節步長，若兩者距離遠，則步長加大；距離近，則步長減小，從而提高收斂速度。將通過下列公式實現：

(5)

式中：Ji為當前細菌i的適應值，Jmax為當前所有細菌最大的適應值。

(2)嵌入粒子群算法的學習因子思想，一個細菌的游動不僅受限于自身的覓食能力，還受到其他細菌的影響。即對于一個細菌，將它的適應度函數值與當前覓食能力最好的細菌進行比較，通過交流學習覓食能力更好的細菌來提高自己的覓食能力。其函數由式(6)給出:

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

(6)

(3)基本BFO算法中，遷徙概率為一個定值，即所有細菌都以Ped遷徙到一個新的區域，這可能會導致精英個體丟失，算法的收斂速度、精度和穩定性降低[14]。因此，本文將采用自適應的遷徙概率，通過下式實現：

(7)

式中：Jmin為當前所有細菌最小的適應值,Ped為設置的固定遷徙概率。

通過改進，適應度函數值小的細菌遷徙概率大，適應度函數值大的細菌遷徙概率小。這將保證覓食能力最好的細菌一定會被遷移，從而提高了算法的穩定性。

2 IBFO算法航跡規劃

2.1 航跡規劃目標函數

航跡規劃的目的即在確保無人機安全飛行的前提下，規避威脅區域，如陡峭的山峰、惡劣的天氣等，最后規劃出一條從起點到終點的最短路徑。本質上來說，就是一個求解包含眾多約束條件的函數最優解問題[15]，其數學形式可由公式(8)表述：

minf=w1×minf1+w2×minf2+…

+wn×minfn。

(8)

式中：f(x)是目標函數，w1、w2…wn是權重系數，f1(x)、f2(x)…fn(x)是約束條件函數。本文中航跡規劃模型將采用以下三個約束條件：

(1)路徑最短約束

即求從第一個導航點到最后一個導航點的最短總路徑長度：

(9)

式中：dx、dy、dz為當前導航點減去前一個導航點的x方向、y方向、z方向的距離差。

(2)飛行高度約束

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

(10)

(3)轉彎角約束

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

(11)

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

(12)

以上三個約束條件通過權重的分配，共同構成了航跡規劃的目標函數，從而將搜索一條航跡代價小的路徑規劃問題巧妙地變為通過智能優化算法求目標函數最小值的數學問題。這樣將實際問題進行量化，轉化為規劃系統能識別的數學符號，是航跡規劃技術的發展的一大重要板塊。

2.2 IBFO無人機航跡規劃流程

如圖1所示，將IBFO算法應用在求解無人機航跡規劃問題，可分為以下四個步驟：

Step1 讀取坐標數據，完成數字地形高程圖的建模。設置起點S、終點T的坐標。

Step2 初始化IBFO參數，包括細菌進行遷徙行為的次數、細菌進行趨向行為的次數、細菌進行聚集行為的次數、細菌進行復制行為的次數、細菌的遷徙概率、向前游動的步長、細菌種群大小、引力深度、引力寬度、斥力深度、斥力寬度、局部學習因子、全局學習因子、迭代次數。

Step3 算法迭代。細菌不斷進行遷徙、趨向、聚集、復制操作，采用改進的IBFO算法求解航跡規劃目標函數最小值，同時，避免飛入天氣威脅區和禁飛區，得到從起點到終點的n個導航點。

Step4 迭代結束，規劃出最優路徑。

此無人機航跡規劃優化模型采用改進的細菌覓食優化算法，通過不斷迭代尋找目標函數更小的導航點，在設定的迭代次數完成后結束迭代。迭代次數通過經驗取得，可以使目標函數達到收斂。最終將得到的n個導航點連接起來，即得到了規劃出來的航跡。

圖1中，Ned為遷徒行為的次數，Nre為告別行為的次數，S為細菌種群個數，Nc為趨向行為的次數，Ns為趨向行為中單向運動最大步數，最小的適應度函數值存儲為Jend。

圖1 將IBFO算法應用于航跡規劃

3 實驗分析

3.1 航跡規劃環境建模

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

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

圖2 真實地形

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

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

圖3 數字地形高程圖

3.2 算法驗證

為了驗證本文算法的有效性，采用Matlab R2017b對算法進行仿真。函數變量范圍為整個三維空間大小，算法具體參數設置如表1所示。

表1 參數設置

無人機航跡規劃仿真結果如圖4所示。仿真設置了兩個起點，起點1為紅色圓型，坐標為(20,20,4.245)；起點2為紅色三角形，坐標為(40,20,4.245)。終點為黑色*型，坐標為(90,70,2.7)，坐標中的高度單位為km。仿真采用了三個算法實現無人機航跡規劃，分別是改進細菌覓食優化算法、粒子群算法與基本的細菌覓食優化算法，得到的航跡顏色分別為藍色、綠色、紅色，從圖中可以清晰地觀察到各條航跡。

圖4 航跡規劃仿真軌跡

為了更好、更直觀地進行對比，將航跡投影到緯度坐標，起點1到終點和起點2到終點的兩組航跡仿真結果分別如圖5和圖6所示，可以較為明顯地看出采用IBFO算法規劃的航跡路徑最短，飛行最平穩。

圖5 起點1航跡規劃仿真軌跡投影圖

圖6 起點2航跡規劃仿真軌跡投影圖

同時，起點1到終點和起點2到終點的兩組目標函數隨迭代次數變化情況分別如圖7和圖8所示,可以看出迭代次數為40的時候，目標函數基本收斂，因此更改參數MAX為40，并測試算法運行時間來對比收斂速度。

圖7 起點1目標函數變化曲線

圖8 起點2目標函數變化曲線

各條航跡的長度、高度的均方差、目標函數最終值以及算法運行時間如表2所示。

表2 航跡規劃參數結果

由表2的兩組數據可清晰得出，相比采用BFO算法和PSO算法進行航跡規劃，采用IBFO算法進行航跡規劃的航跡長度最短，高度均方差和目標函數最小，算法運行時間最短，因此采用IBFO算法規劃出的航跡是更優的。

改進的細菌覓食優化算法相比基本的細菌覓食優化算法和粒子群算法有以下優點：

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

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

4 結束語

本文提出了一種基于改進的細菌覓食優化算法，在無人機航跡規劃任務中得到應用，同時利用數字地形高程數據庫進行三維環境建模仿真，直觀展示出了航跡的軌跡。由仿真結果可得，基于改進的細菌覓食優化算法可以規劃出路徑更短、飛行更平穩、油耗更小更經濟的航跡。

本文對工程實際有引導意義，如在實際工程中實現，會大大優化航跡規劃。但算法仍存在一些不足，如嵌入學習因子、引入自適應機制改善啟發算法，雖帶來精度的提高，但同時會增加算法復雜度。下一步計劃融合其他人工啟發式算法繼續進行算法的改進，并考慮用無人機進行真實的實驗驗證。