基于智能優(yōu)化算法的無人機航跡規(guī)劃研究

姜言金 盧利中 丁 偉 劉 旭 王光璞

（國網吉林省電力有限公司吉林供電公司，吉林 吉林 132012）

無人機是一種空中機器人，具有飛行速度快、機動性強的特點，在無人配送、無人巡檢、測繪以及軍事等相關領域具有廣闊的應用場景[1]。無人機在實際執(zhí)行任務中需要對路線進行路徑規(guī)劃，即根據(jù)某個優(yōu)化準則來選取路徑，例如能量代價最小、行走路線以及行走時間最短等，在其工作空間中找到1 條從起始狀態(tài)到目標狀態(tài)且可以避開障礙物的最優(yōu)路徑[2]。目前已有關于無人機路徑規(guī)劃的研究，規(guī)劃算法主要有沙貓群優(yōu)化算法、粒子群算法、D～*算法、蟻群算法、袋獾優(yōu)化算法、A～*算法、遺傳算法、果蠅算法以及灰狼優(yōu)化算法等，經過試驗仿真都具有較好的規(guī)劃效果[3]。飛蛾撲火算法（Moth-Flame Optimization，MFO）是一種仿生優(yōu)化算法，該算法是通過觀察、效仿飛蛾圍繞光源飛行行為提出的，具有尋優(yōu)速度快、設置參數(shù)少以及易于實現(xiàn)等優(yōu)點。該文將飛蛾撲火算法應用到無人機規(guī)劃優(yōu)化問題中，建立無人機航跡模型并進行仿真分析，以驗證飛蛾撲火算法在求解該類問題過程中的優(yōu)越性。

1 航跡規(guī)劃數(shù)學建模

1.1 總代價

建立綜合考慮無人機航跡長度代價、地形代價以及飛行高度代價的目標函數(shù)f[4]，如公式（1）所示。

式中：fL為無人機飛行的航跡長度代價；fT為無人機飛行的地形代價；fH為無人機飛行的高度代價；a、b和c為3個權重系數(shù)。

1.2 航跡長度代價

無人機飛行航跡長度越短，所需要的飛行時間及燃油就越少[5]，航跡長度代價如公式（2）所示。

式中：fL為航跡長度代價；N為航跡點總數(shù)；wn為第n個航跡點；wN為飛行目標地航跡點。

1.3 地形代價

無人機飛行要保證與地形障礙物有一定的安全距離，避免發(fā)生碰撞，采用地形代價描述[6]，如公式（3）、公式（4）所示。

式中：fT為地形代價；dsafe為最小安全距離；Am，n為坐標wm，n與（xm，n，ym，n，zTm，n）之間的垂直距離，Am，n=0 表示坐標wm，n與（xm，n，ym，n，zTm，n）之間的垂直距離大于最小安全距離，Am，n=1 表示坐標wm，n與（xm，n，ym，n，）之間的垂直距離小于最小安全距離；M為將相鄰航跡點的距離等分為M份。

1.4 飛行高度代價

無人機飛行高度越高，遇到的未知威脅和風險就越大，采用飛行高度代價描述[7]，如公式（5）、公式（6）所示。

式中：fH為飛行高度代價；H為無人機飛行高度最大值；Bm，n為坐標wm，n與（xm，n，ym，n，）之間的垂直距離，Bm，n=0 表示坐標wm，n與（xm，n，ym，n，）之間的垂直距離小于最大飛行允許高度，Bm，n=1 表示坐標wm，n與（xm，n，ym，n，）之間的垂直距離大于最大飛行允許高度。

2 飛蛾撲火算法

飛蛾撲火算法是一種高效的仿生智能優(yōu)化算法，該算法是通過觀察效仿飛蛾圍繞光源飛行行為提出的一種仿生優(yōu)化算法[8-9]。M為飛蛾個體集合，每個飛蛾個體都代表1 種優(yōu)化問題的解決方案，OM為個體對應的適應度值，如公式（7）所示。

式中：Mn，d為第n個飛蛾的d維位置；OMn為第n個飛蛾對應的適應度值；d為求解維數(shù)；n為飛蛾總數(shù)。

在算法中，火焰（光源）表示優(yōu)化問題的候選解，每只飛蛾都有對應的火焰，該火焰是其歷史尋優(yōu)的最優(yōu)解，如公式（8）所示。

式中：F、OF分別為火焰位置矩陣、其適應度值矩陣；Fn，d為第n個火焰的d維位置；OFn為第n個火焰對應的適應度值。

飛蛾圍繞火焰呈螺旋式飛行，在火焰附近不斷搜索更優(yōu)的候選解并對火焰位置進行更新。螺旋式飛行方式可以提高局部搜索能力，更新公式如公式（9）所示。

式中：l為當前迭代次數(shù)；Mil為第i只飛蛾；Fjl為第j個火焰；S（*）為螺旋函數(shù)。

飛蛾按螺旋函數(shù)規(guī)定的路徑圍繞火焰作螺旋式飛行，要求螺旋函數(shù)必須滿足螺旋路徑的起點為飛蛾位置，終點為火焰位置，飛行軌跡較為均勻地分布在可行解搜索空間，但是不應超過可行解搜索空間，如公式（10）、公式（11）所示。

式中：Dil=S（Mil，F(xiàn)jl）為第i只飛蛾與第j個火焰的空間距離；b為螺旋函數(shù)的常數(shù)；t為[-1，1]的隨機數(shù)。

由螺旋函數(shù)可知，t的取值可以顯示飛蛾與火焰的遠近程度，當t取值為-1 時，飛蛾距離焰最近；當t取值為1 時，飛蛾距離火焰最遠，即t取值越小，飛蛾與火焰的距離越近，同時火焰的更新頻率也越高。通過不斷調整t 的取值，使飛蛾遍歷整個搜索空間。為了使算法初期具有較強的爬坡能力，迭代后期具有較強的局部開發(fā)能力，需要對t的取值策略進行改進，規(guī)定t在[r，1]隨機取值（r為隨著迭代次數(shù)由-1 到-2 線性遞減的變量）。

飛蛾在火焰附近進行螺旋式搜索，當發(fā)現(xiàn)優(yōu)于當前火焰的候選解時，就更新火焰矩陣。為了減少算法計算量，提高收斂速度，火焰數(shù)量將隨著迭代數(shù)次逐漸減少，在迭代結束后僅剩下1 簇火焰，即優(yōu)化問題的最優(yōu)解，火焰數(shù)量更新公式如公式（12）所示。

式中：round（*）為取整函數(shù)；l、T分別為算法當前迭代次數(shù)、設置的最大迭代次數(shù)；Q為第一次迭代時的火焰數(shù)量。

在迭代過程中，所有減少的火焰對應的飛蛾根據(jù)當前最差火焰進行更新。

為了驗證飛蛾撲火算法求解優(yōu)化問題的優(yōu)越性，采用粒子群算法（PSO）和遺傳算法（GA）進行仿真比較，采用的單目標測試函數(shù)為Rastrigin 函數(shù)，如公式（13）所示。

式中：n為優(yōu)化問題的維數(shù)，n=2；xi為優(yōu)化變量；i為優(yōu)化變量的維數(shù)，i=1，這處取值1、2。

以二維變量的求解極小值優(yōu)化函數(shù)為例進行仿真驗證（選取Rastrigin 函數(shù)）。Rastrigin 函數(shù)的極小值點為（0，0），最優(yōu)函數(shù)值為0，設置Griewank 函數(shù)的尋優(yōu)區(qū)間為[-10，10]。Rastrigin 測試函數(shù)的圖形凹凸不平，存在多個高峰和溝壑，這增加了算法尋優(yōu)的難度，一旦算法陷入局部最優(yōu)區(qū)域，由于存在高峰，因此優(yōu)化算法很難再跳出繼續(xù)尋優(yōu)，增加了算法早熟收斂的可能性。

測試函數(shù)參數(shù)設置為Rastrigin 函數(shù)的尋優(yōu)區(qū)間為[-5，5]，變量維數(shù)為30。算法參數(shù)值設置為3 種算法的種群規(guī)模均為50，最大迭代次數(shù)均為1 000 次，其中粒子群算法的學習因子均為2，權重由0.9 線性遞減至0.4，遺傳算法的交叉率、變異率分別取值為0.9、0.025。3 種優(yōu)化算法的收斂曲線如圖1 所示。

圖1 Rastriginl 函數(shù)的收斂曲線

由圖1 可知，在整個搜索過程中，飛蛾撲火算法的最優(yōu)值不斷地更新，算法確定最優(yōu)值范圍后，其局部搜索能力更強，其原因是飛蛾撲火算法的種群多樣性更新、策略更佳，更好地均衡了全局與局部搜索能力，在算法初期可以快速尋優(yōu)，在陷入局部最優(yōu)時可以及時跳出局部陷阱。由于粒子群算法缺少局部搜索機制，因此一旦陷入局部最優(yōu)就很難跳出，導致早熟收斂。遺傳算法在初期具有較好的搜索性能，但是全局搜索能力較差，容易在局部最優(yōu)點過度開發(fā)，早熟收斂。綜上所述，與另外2 種算法相比，飛蛾撲火算法具有較高的求解精度。

3 仿真分析

為了驗證飛蛾撲火算法求解優(yōu)化問題的優(yōu)越性，采用粒子群算法和遺傳算法進行仿真比較。在MATLAB 軟件環(huán)境下運行，3 種算法的種群規(guī)模均為為50，最大迭代次數(shù)均為1 000 次，其中粒子群算法的學習因子均為2，權重由0.9 線性遞減至0.4，遺傳算法的交叉率、變異率分別取值為0.9、0.025。地圖大小為150 km×150 km×10 km，最小安全距離dsafe=5 m。基于粒子群算法、遺傳算法和飛蛾撲火算法的仿真結果分別如圖2～圖4 所示。

圖2 粒子群算法仿真結果

圖4 飛蛾撲火算法仿真結果

由圖2～圖4 可知，粒子群算法的求解精度最差，在算法早期尋優(yōu)過程中，由于種群多樣性較差，因此難以搜尋到最優(yōu)解，很容易早熟收斂，算法搜索到的最優(yōu)值為83.36。遺傳算法在早期尋優(yōu)過程中的搜索效果較好，然而一旦陷入局部最優(yōu)解就難以跳出，導致早熟收斂，全局搜索性能較差，算法搜索到的最優(yōu)值為80.86。與前2 種優(yōu)化算法相比，飛蛾撲火算法的求解精度最高，具有較強的全局搜索性能和較快的尋優(yōu)速度，算法搜索到的最優(yōu)值為78.96。飛蛾撲火算法的計算結果可以有效縮短航跡規(guī)劃計算時間并避開障礙物，得到的航跡路線可以滿足飛行安全要求，符合實際工程應用要求。

4 結語

與粒子群算法和遺傳算法相比，飛蛾撲火算法的尋優(yōu)速度更快、求解精度更高，可以縮短航跡規(guī)劃計算時間，同時可以得到1 條避開障礙物和威脅區(qū)域的最優(yōu)路徑，說明該方法在無人機路徑規(guī)劃中具有更強的穩(wěn)健性和可行性。