基于改進飛蛾撲火算法的無人機低空突防路徑規劃

黃 鶴，吳 琨，王會峰，楊 瀾, 茹 鋒，王 珺

（1. 長安大學 電子與控制工程學院，西安 710064； 2. 長安大學 西安市智慧高速公路信息融合與控制重點實驗室，西安 710064； 3. 長安大學 信息工程學院，西安 710064）

無人機以低風險、高機動能力等特點被廣泛地應用于軍事領域，在執行任務規劃中，低空突防技術是無人機協同作戰以及網絡化作戰的關鍵技術，合理高效的突防方法可以使無人機更有效地躲避威脅區域，提高任務執行效率及生存幾率，順利完成飛行任務。

無人機突防以有效的規劃路線方法[1]為基礎，其核心取決于尋優算法的優劣。近年來國內外學者在該領域進行了大量的研究，提出了諸多有效的突防路徑規劃算法，如最速下降法[2]、Voronoi 圖法[3]、遺傳算法[4]、A*智能算法[5]等。目前最新、使用最廣泛的方法是采用群體智能優化算法求解無人機突防路徑的問題。唐立等提出了一種基于改進的蟻群算法的路徑規劃方法[6]，通過構造泰勒多邊形構造路徑可行解并建立路徑安全度約束，縮小搜索范圍，再通過蟻群算法尋找最優路線。該方法提升了尋優效率，但路徑的精確度不高。宋宇等提出了一種基于三維規劃的改進粒子群優化方法[7]，提升了全局及局部搜索性能，但由于將威脅場考慮的比較簡單，并未考慮地形等因素，因此實際應用效果并不理想。近年來，許江波等通過自適應策略改進魚群算法，利用其全局尋優能力解決路徑規劃問題[8]，但該算法的不足還是搜索時間過長。

同時，在三維無人機路徑規劃過程中，由于地形與威脅源的信息量大，使群體智能優化算法尋求最優路徑時復雜度呈現指數上漲，極易陷入局部最優。而飛蛾撲火算法因其獨特的尋優方式及更新策略可以在復雜度較高的情況下具備良好的尋優能力。因此，本文提出一種基于改進飛蛾撲火算法的三維無人機低空突防方法，在保證高精確度的情況下，盡量縮短尋優時間，快速有效地獲得無人機突防的最優路徑。

1 無人機三維突防環境建模

在處理靜態三維環境的無人機突防問題時，最重要的是根據任務、威脅情況，以及地形等已知因素構建三維的地形和威脅環境約束。本文將基本地形、雷達監測、火炮威脅、無人機物理約束等進行數學建模，并通過數字融合，構建出三維環境下的地形約束。

1.1 地形約束

不同任務中，無人機面臨的實際戰場環境是不相同的，根據海拔不同，將地形分為平原地區，山地地區，丘陵地區三種地形，其中影響最大因素的是山峰，同時也要考慮海拔變化帶來的影響。首先，三維環境下的山峰建模如下所示：

其中，(x,y)為山峰地形在水平平面上對應的坐標，(x0,y0)為山峰地形在水平平面上的中心點坐標，h為高度參數，m1和m2反應山峰的陡峭程度。另外，航跡點的地形威脅代價如下：

其中：Kz為地形威脅系數，hi為第i個航跡點的海拔高度，Hi為第i個航跡點距離地形的垂直高度，fzi為第i個航跡點對應的威脅代價。此外，無人機低空突防需考慮高程代價，航跡點的高程代價如式(3)所示：

無人機在突防中的地形約束還需要考慮到飛行邊界范圍以及最大飛行高度，保證操控無人機的安全性。因此設定無人機飛行水平范圍為(Xmin，Ymin)和(Xmax，Ymax)，最大飛行高度為Hmax。

1.2 威脅模型約束

雷達、電磁威脅、導彈是無人機突防的主要威脅來源，具體建模如下：

(1) 雷達威脅

雷達主要通過電磁波來探測目標的距離，速度，相對位置等敵方信息，顯然，要使無人機順利突防，必須在飛行過程中避開雷達的探測范圍，保證安全。

描述雷達方程特性的方程如下：

其中，主要因素是P，也就是目標和雷達之間的距離，因此雷達方程簡化為雷達探測概率模型如下：

(2) 電磁威脅

一般情況下，電磁威脅可視作半球型，威脅模型如下：

其中，R為電磁干擾的半徑，α為Z 軸正向與半徑的夾角，β為半徑在水平面上的投影與X 軸正向的夾角。

(3) 導彈威脅

敵方導彈的威脅范圍內也被稱作禁飛區，必須躲避。在三維平面上，導彈威脅范圍近似于一個半球體。 無人機在禁飛區半徑內下被擊中的可能性為：

其中，Pk/v為常數，表示無人機在禁飛區半徑內被摧毀的概率；K0為比例系數，Rs為導彈威脅中心與無人機之間的斜距；α為視線俯視角。則：

在三維建模過程中，威脅源半徑較大，而無人機限高較低，因此可以將威脅源等效為圓柱地形處理[9]。航跡的威脅代價如下：

其中，KTj為威脅源j的威脅系數，rij為第i個航跡點到威脅源j中心的直線距離，RTj為威脅源j的威脅半徑，FT,ij為第i個航跡點到威脅源j中心的代價。

1.3 無人機約束

無人機在飛行過程中受自身的物理約束，主要有最大轉彎角α、最大下滑及爬升角β，以及燃油代價，中燃油代價用路程表示。各物理約束分別為：

式中，Kh和Kv分別為轉彎角和俯仰角威脅系數，Jh_angle,i和Jv_angle,i分別為第i個航跡點對應的α和β的代價函數。綜合各代價函數，可得出第i個航跡點的無人機物理約束代價函數為：

1.4 航跡代價函數

將地形約束、高程代價、威脅模型約束及無人機自身物理約束的代價加權綜合起來就構成最終的無人機代價函數，如式(15)所示。

式中，F(R)為整條航跡的代價，ω1，ω2，ω3，ω4為各代價的權重。

2 改進的飛蛾撲火算法

2.1 飛蛾撲火算法

飛蛾撲火算法（Moth-flame Optimization, MFO）是受到飛蛾圍繞火焰對數螺旋線形式運動的現象啟發而提出的一種新型的元啟發算法[10]。在算法中，飛蛾為待優化的問題，火焰為每次迭代的最優解，通過螺旋更新改變飛蛾自身的位置以及火焰的結構。

2.1.1 飛蛾種群的初始化

定義飛蛾的特征有d維，設初始飛蛾個數為n，路徑點的個數為d，則飛蛾種群M如式(16)所示。

其中，定義Mi為飛蛾種群M中的第i只飛蛾。飛蛾適應度的大小由OM表示：

其中，Omi為第i只飛蛾的適應度，通過相應的代價函數得到。初始火焰的集合與M大小一致，并隨著后續的迭代，火焰的數量會逐漸減小，火焰集合由F表示。

其中，第i個火焰由Fi表示。火焰的適應度值OF的大小同樣為n×1，如式(19)所示。

其中，ofi表示第i(i=1,2,…,n)個火焰的適應度值。OF矩陣是OM中每個向量排序之后的結果，所以F是M矩陣根據OF矩陣的排序得到的結果，這說明火焰F是飛蛾M在當前迭代搜索中的最優解。

2.1.2 迭代更新

MFO 算法每輪的更新機制可分為兩個階段：飛蛾撲火、飛蛾棄焰。

(1)飛蛾撲火：根據飛蛾的趨光性，飛蛾Mi圍繞對應的火焰Fj做對數螺旋曲線運動。定義對數螺旋曲線如式(20)所示：

其中，S(Mi,Fj)是飛蛾更新后的新位置，Di是第j個火焰與第i只飛蛾的歐式距離，b為常數參數，可調整對數螺旋曲線，通常取1。參數t為[-1,1]范圍內的一個隨機數，表示當前飛蛾的更新位置與火焰的接近度，則t=-1 代表飛蛾與火焰最近，t=1 則兩者相距最遠。具體過程如圖1 所示。

(2)飛蛾棄焰：為了提高算法的收斂速度并保證飛蛾種群向最優靠近，應逐漸減少較差的火焰，飛蛾僅圍繞保留下來的火焰做旋轉運動，從而避免飛蛾丟失最優解的情況。火焰自適應減少如公式(21)所示：

其中，flameno為當前火焰數量，N為種群數，l為當前的迭代次數，T為規定的最大迭代次數。

圖1 飛蛾運動軌跡圖Fig.1 Moth tracks

2.2 基于改進的MFO 算法的無人機三維路徑規劃

2.2.1 航跡編碼

在實際應用中，每條路徑都是由多個航跡點連接而成的線。定義種群中的一只飛蛾Mi即為一條路徑，Mi=[mi1,mi2,……,min]，每個航跡點mi1具有空間三維的屬性(x,y,z)。同時，在利用MFO 算法規劃三維的無人機突防路徑的問題時，首先確定航跡點數n，其次等距離x方向的航跡點坐標固定不變，通過對y和z坐標的尋優確定最優突防路線。

2.2.2 自適應慣性權重

慣性權重在平衡算法的全局及局部搜索能力中起著至關重要的作用。傳統MFO 算法中的火焰并未能被充分利用，因此，本文在飛蛾的更新策略上引入了自適應權重。通常，在群體智能算法中自適應權重加在步長上，而本文改變其更新機制，通過將自適應權重放在火焰上擾動火焰的位置保證充分發揮最優解的優勢。自適應權重ρ如下表示：

其中，fitness(i)為當前迭代中第i只飛蛾的適應度，l為當前迭代次數，當l逐漸增大時，自適應權重ρ趨向于1。引入權值后的位置更新策略如下：

將自適應慣性權重策略引入進MFO 的位置更新機制中，在算法前期，使得不易于快速收斂到局部最優解，在迭代過程中跳出局部最優尋求全局最優。在尋優后期，權重趨向于1，保證局部最優解的精確度。

2.2.3 改進的交叉算子與變異算子

遺傳算法在求解多峰函數及復雜問題時的高效性非常適合與MFO 相結合[11-13]。遺傳算子主要包括三個方面：交叉算子、變異算子、遺傳算子。針對MFO因自身尋優方法存在早熟性，在求解三維環境下最優路徑時無法快速定位到最優路徑等問題，本文將火焰矩陣與遺傳算法的交叉算子、變異算子相結合并加以改進，使算法在前期快速跳出局部最優，增強算法的收斂性能。主要思想是每次迭代時將最優火焰與其余隨機火焰進行交叉重組，并與原來父代的適應度作對比，若相對原來父代適應度較優，則替換父代。交叉算子表示如下：

其中，XAk代表第k代火焰矩陣中的最優火焰個體，XBk表示此外的任一隨機火焰個體，β為一系數，當β為常數時，稱為均勻交叉算子，當β隨迭代次數改變時，則稱為非均勻交叉算子。

新一代的火焰個體主要由系數β及上一代的個體來共同決定，當β趨近于0.5 時，子代遠離父代，可以拓寬搜索空間，保證火焰種群具有多樣性，當β遠離0.5 時，子代靠近父代，保證搜索范圍縮小，使得精確度提高。因此，在交叉算子的基礎上做如下做改進：

其中，min（β）及max（β）分別代表β的最大值及最小值。β系數曲線如圖2 所示.

圖2β 系數變化曲線圖Fig.2 Curve of β coefficient change

由圖2 可知，為了保證在迭代初期XA及XB在后代中有較為平均的基因占比，以及火焰矩陣的多樣性，取β的初始值為0.5，并使其在前期增長緩慢。隨迭代次數的增長β迅速靠近1，使種群多樣性降低，搜索精度增加。

呂曉英(以下簡稱呂)：我的審美觀念，或者說欣賞趣味，可能是屬于比較傳統的。我以為，小說、電影的中心應該是故事，音樂、歌曲的中心是旋律，我喜歡有故事性和旋律性的作品。而當今的許多作品卻似乎背離了這種傳統特征，小說、電影越來越不會講述一個故事，音樂、歌曲也越來越不會演繹一段旋律。可能就因此，我和許多小說的潛在讀者一樣，逐漸放棄小說，喜歡看電視劇勝過看電影，因為在電視劇這種文化形態中，故事性被表現得最為充分。

（2）高斯變異算子

由于地形比較復雜，在MFO 尋優過程中，個別航跡點迭代時無法跳出局部最優，使航跡出現較大偏差，需加入高斯變異算子對航跡點隨機干擾。設其中一個火焰為Fi=[f1f2...fd]，每一維度根據變異率p選擇是否產生變異。假設第k維產生變異，則高斯變異算子為

其中，fk為火焰第k維的特征，f'k為變異后的特征，λ為系數，受空間大小影響，決定變異的程度大小。

2.3 三次樣條插值平滑路徑算法

在無人機實際飛行中，為了保證無航跡轉彎角平滑，避免無人機受到自身物理約束及性能的限制，采用三次樣條改善最終突防路徑。設最終無人機突防路徑為：Z=(z1,z2……zn)，每個路徑點zk(k=1……n)有(x,y,z)三個維度，分別對(x1,x2……xn)、(y1,y2……yn)、(z1,z2……zn)做三次樣條插值，最終形成一條光滑路徑，三次樣條插值效果如圖3 所示。

圖3 三次樣條插值優化效果圖Fig.3 Cubic spline interpolation optimization effect diagram

總的算法流程如表1 和圖4 所示。

表1 本文算法流程Tab.1 Algorithm flow of this paper

圖4 本文算法流程圖Fig.4 The flow chart of this algorithm

3 改進的飛蛾撲火算法對比實驗

3.1 測試函數

由于無人機面對復雜地形突防時，多極值的尋優性能非常關鍵。選擇使用基準測試函數中兩個單峰函數Quartic 和Sum Squares 及兩個多峰函數Penalized1和Penalized2 來評估算法性能，它們能在復雜度較高的情況下驗證算法能否跳出局部最優。測試函數描述如下：

(1) Quartic 函數

(2) Sum Squares 函數

其中，xi∈[-100,100],n=10, 全局最小值處為（0,0…0）。

(3) Penalized 1 函數

其中，xi∈[-30, 30]，n=10，全局最小值處為（0,0…0）。

(4) Penalized 2 函數

其中，xi∈[-30,30]，n=10, 全局最小值處為（0,0…0）。

3.2 實驗驗證

采用上述4 種測試函數分別評估MFO 算法、灰狼算法(Grey Wolf Optimizer, GWO)算法[14]以及本文算法的尋優性能。圖5 為各算法在不同測試函數上的適應度曲線圖，表2 列出了各算法經過測試函數20次測試的均值及最優值。

由圖5 可知，GWO 在Quartic 函數上的尋優性能相比于MFO 較好，在其余測試函數上收斂速度及精度均不如MFO，而本文算法在各測試函數上收斂速度及精度均優于其余兩種算法，說明本文算法在復雜度較高的測試函數上有較強的尋優能力。由表2 可知，MFO 在Quartic 函數上表現較差，其余測試函數上最優值雖較好，但均值與最優值相差較大，波動明顯。GWO 在多峰測試函數上精度較低，但較為穩定。而本文算法在各多峰函數上精度相比于MFO 及GWO均有較大提升，并且尋優穩定。這說明，本文提出的改進方法可以有效幫助MFO 算法跳出局部最優解，增強了MFO 算法面對復雜問題時的全局尋優能力。

圖5 各算法在測試函數上的適應度曲線圖Fig.5 The fitness curve of each algorithm on test function

表2 三種算法在測試函數上的實驗對比Tab.2 Experimental comparison of three algorithms on test functions

4 無人機突防仿真測試及分析

仿真測試計算機的CPU 為Intel Core i7-9750U CPU 2.60GHz、內存為16GB，操作系統為Windows10，編譯軟件為Matlab R2018a。測試地形區域大小為100 km×100 km,測試限高為4 km。無人機航線的起始點與終止目標分別為(1, 3, 0.5)及(99, 98, 0.5)，敵方雷達及火炮距離的中心為(20, 13.5, 0)、(85, 60, 0)、(40, 59, 0)，作用半徑為9 km。MFO、GWO 和本文算法求得三條路徑的航跡點分別用圓圈、星號、及正方形表示。各算法種群數設為100，最大迭代次數為800 次。算法參數以及無人機突防軌跡圖分別如表3和圖6 所示。

表3 主要參數Tab.3 Main parameters

圖6 無人機突防路線軌跡圖Fig.6 Path map of UAV penetration route

通過MFO、GWO、本文算法在無人機突防路線軌跡圖中的對比可以看出，傳統MFO 規避了威脅源，但路徑中有部分穿過了地形，規劃的路線較長；GWO的規劃路線普遍飛行高度高，穿過了第一個威脅源，對無人機自身的物理約束沒有滿足，俯仰角過大；而本文算法可以有效地利用地形優勢，在規避山峰地形及各威脅源的同時，滿足無人機自身的物理約束，并做到貼地飛行，避免路徑中出現多余路線，從而達到低空突防的目的。算法的航程和最優代價如表4 所示，最優航線代價變化如圖5 所示。

表4 算法航程及最優代價Tab.4 Algorithm voyage and optimal cost

圖7 最優路線代價變化圖Fig.7 Optimal route cost change graph

仿真結果表明，MFO 在尋優前期可以跳出局部最優，但收斂速度相對較慢，在迭代到400 次左右陷入局部最優，求得的突防路徑最長；GWO 在復雜度較高的情況下效果較差，尋優過程中難以跳出局部極值，且精度較低，難以適應三維地形下無人機突防路徑規劃；而本文算法無論在精度、速度方面，都優于MFO及GWO，最短路徑比MFO 及GWO 算法分別降低了25.14 km 和14.77 km，求得路徑最短，代價分別降低了3.63 及10.25。通過算法比較，本文算法可以更為有效地避開威脅地形及威脅源，利用地形作掩護實現低空突防。

5 結 論

本文針對無人機的低空突防路徑規劃問題，提出了一種基于改進MFO 的三維無人機低空突防方法。首先，建立三維地形模型、威脅源模型及無人機物理約束模型，確定威脅代價函數。其次，針對MFO 算法易發生早熟收斂，收斂速度慢，陷入局部最優等問題，提出了兩種改進思路：(1)利用自適應權重改變MFO 的更新軌跡，加快算法的收斂速度并改善局部搜索性能；(2)在MFO 中引入交叉算子和變異算子，擴大搜索空間，進一步提升了算法精度，有效解決了MFO 自身缺陷。最后，利用三次樣條插值改善突防路徑，最大程度避免無人機受到自身物理約束的限制。實驗表明，該方法可以更精確、快速地使無人機自主避開危險區域選擇最優路徑，實現低空突防。