基于NSGA-II 遺傳算法的智能飛行器航跡快速規劃

張偉聰，韓偉娜，白雪麗，韓 旭，任 寬，田麗麗

（1.北華航天工業學院機電工程學院；2.北華航天工業學院遙感信息工程學院，河北廊坊 065000）

0 引言

現代飛行器技術經過多年發展，結構和操作越來越復雜，在安全突防任務難度愈來愈大的情況下，智能飛行器航跡規劃占有重要地位。快速準確的航跡規劃可有效節約能源提高效率，其研究具有重大意義。

智能飛行器航跡規劃通常存在約束工況比較復雜和優化規模較大等問題時，一般情形會采用啟發式智能優化算法，如蟻群算法、粒子群算法、模擬退火算法、遺傳算法等［1］。Patcher 等［2］討論了路徑規劃問題中的關鍵優化技術及其復雜性；Dong 等［3］、Zhang 等［4］、Nikolos 等［5］系統研究了路徑規劃中進化算法的優化原理；Wu 等［6］最早將遺傳算法應用于航行器的路徑規劃問題；朱海斌等［7］引入量子遺傳算法克服了遺傳算法早熟問題；李文廣等［8］改進轉彎航跡規劃算法，降低了15%路徑。近年有關智能飛行器航跡規劃優化研究主要集中于對啟發式智能優化算法進行改進［9-13］。

傳統的遺傳算法在搜索空間和目標函數方面要求不高，具有范圍廣、魯棒性高以及全局搜索能力較強的優點，但是容易陷入局部求解，且收斂結果易反復。非支配排序遺傳算法（NSGA）經過個體支配關系的分層，在速度上有了很大提升。本文利用帶精英策略的非支配排序遺傳算法（NSGA-II）應用于智能飛行器的航跡規劃問題中，主要解決NSGA 的排序速度慢以及找到最優解時收斂容易反復的缺陷。

1 航跡規劃問題

智能飛行器航跡規劃指在環境及戰場危險情況如飛行時間、燃油消耗等全方位約束條件下，找到一條自給定起點至目標點的優質飛行軌跡，這是一個典型的多目標優化問題［14］。

復雜環境下的航跡快速規劃是智能飛行器控制課題的重要組成部分，飛行器的定位系統往往由于其自身結構限制無法做到精準定位，當誤差累積達到一定程度會導致整體任務失敗。

1.1 航跡規劃基本要求

假設智能飛行器飛行區域中出發點為A 點，目的地為B 點，其航跡約束如下：

（1）飛行器在空間飛行過程中需要實時定位，其定位誤差包括垂直誤差和水平誤差。飛機每飛行1m，垂直誤差和水平誤差將增加δ個專用單位（以下簡稱單位），到達終點時垂直誤差和水平誤差均小于θ個單位。為簡化問題，假設當垂直誤差和水平誤差均小于θ個單位時飛行器仍可按照規劃路徑飛行。

（2）飛行器在飛行過程中需要對定位誤差進行校正。飛行區域中存在一些安全位置（稱之為校正點）可用于誤差校正，當飛行器到達校正點即可根據該位置的誤差校正類型進行誤差校正。校正垂直和水平誤差的位置可根據地形在航跡規劃前確定。若垂直誤差、水平誤差都能得到及時校正，則飛行器可以按照預定航線飛行，通過若干個校正點進行誤差校正后最終到達目的地。

（3）在出發地A 點，飛行器的垂直和水平誤差為0；飛行器在垂直誤差校正點校正后，其垂直誤差將變成0，水平誤差保持不變；飛行器在水平誤差校正后，其水平誤差將變成0，垂直誤差保持不變；飛行器在垂直誤差不大于α1個單位、水平誤差不大于α2個單位時才能進行垂直誤差校正；在垂直誤差不大于β1個單位、水平誤差不大于β2個單位時才能進行水平誤差校正。

（4）飛行器在轉彎時受到結構和控制系統限制，無法完成即時轉彎，最小轉彎半徑設為200m。

1.2 智能飛行器航跡問題

本文研究智能飛行器的航跡規劃是根據2019 年全國研究生數學建模競賽F 題中的問題二改編［15］。綜合考慮優化目標，要求航跡長度盡可能小，在校正區域進行校正的次數盡可能少。繪制出數據集的航跡規劃，并求出飛行器從起點出發經過誤差校正點的編號及校正前誤差，討論算法的有效性。

2 智能飛行器航跡規劃

2.1 航跡規劃數學模型

在智能飛行器起點A 到終點B 的航跡規劃中，根據問題要求假設飛行器從一個校正節點到另一個校正節點之間始終進行勻速直線運動，記C=[c1,c2,c3...,ci,...,cn]為校正點集，n 為校正點個數；U=[u1,u2,u3...,ui,...,um]為水平校正集，V=[v1,v2,v3...,vi,...,vQ]為垂直校正集，m 為水平校正點個數，Q 為垂直校正點個數。

智能飛行器飛行路程目標函數為：

飛行器經過校正點的目標函數為：

式中：

上一個點到下一個點的路程長度為：

基于基本要求的約束條件如下：

其中Pij是兩個校正點之間的誤差增量。

對最小轉彎半徑約束為：

2.2 NSGA-II 算法求解過程

NSGA-II 算法的核心是父代與子代的合并，基于傳統遺傳算法進行基本操作。

（1）基于NSGA-II 遺傳算法的智能飛行器航跡規劃算法流程如圖1 所示。

Fig.1 Route planning flow of intelligent vehicle based on NSGA-II genetic algorithm圖1 基于NSGA-II 遺傳算法的智能飛行器規劃航跡流程

（2）智能飛行器航跡規劃算法添加以下約束：①當前后兩個校正節點距離超過最大誤差和單位距離誤差的比值時，解無效，生成的下一個節點間距離必須小于最大誤差和單位距離誤差的比值；②水平校正點和垂直校正點需分開進行約束，且節點到達下一個校正后才能校正誤差，利用當前誤差余量對下一個解的距離進行約束；③每個節點只能用一次，節點到達B 點附近就可嘗試直接連接B 點。

（3）產生的新解帶入目標函數找到優化目標下的最佳航跡：①利用交叉和變異因子產生新解；②輸出可行解，得出最優航跡；③記錄遍歷的校正點，得出最優航跡對應的最優校正點。

3 仿真結果

根據數據集中附件1 的數據，利用NSGA-II 算法將數據帶入約束進行迭代，本次迭代次數為30 次，得出對應的智能飛行器最優航跡規劃如圖2 所示，其中A 點代表起點，B 點代表終點，其它點分別是垂直和水平校正點。

Fig.2 NSGA-II genetic algorithm for optimal path planning of intelligent vehicle圖2 NSGA-II 遺傳算法智能飛行器規劃最優航跡

通過NSGA-II 算法綜合考慮實際情況，得到一條從起點A 到終點B 的最優路徑長度、最佳校正節點數的航跡規劃：起 點A→180→344→165→534→316→312→198→340→583→終點B。根據算法得到多約束規劃的值分別為：

從圖2 得到智能飛行器從起點A 出發經過誤差校正點的編號及校正前的誤差結果如表1 所示。

Table 1 Route planning results表1 航跡規劃結果

與NSGA 算法相比，NSGA-II 算法能實現快速、準確的搜索性能。分析智能飛行器航跡規劃總路徑和校正次數后發現，NSGA-II 算法相對于NSGA 算法收斂速度快了一倍，且最優結果不易反復。在同時迭代50 次后，NSGA-II算法與NSGA 算法的對比結果如圖3 和圖4 所示。

Fig.3 Total distance iterative curve of intelligent vehicle based on two genetic algorithms圖3 兩種遺傳算法智能飛行器總路程迭代曲線

Fig.4 Two kinds of genetic algorithms for intelligent vehicle calibration圖4 兩種遺傳算法智能飛行器校正次數迭曲線

圖中虛線代表采用NSGA 算法進行規劃的結果迭代情況，實線代表采用NSGA-II 算法進行規劃的結果迭代情況。從圖中可以很容易看出，NSGA-II 算法避免了NSGA 算法的一些缺點，可以更準確快速地獲得智能飛行器在滿足約束條件下的最優軌跡，并且在找到最優軌跡時收斂不會出現局部反復。

4 結語

本文采用NSGA-II 算法進行了多約束條件下智能飛行器的航跡規劃。實驗表明該算法能快速且準確得出最優軌跡，解決了NSGA 算法最終結果不收斂的問題。值得指出的是，改進的遺傳算法越來越多，無疑對解決智能飛行器的航跡規劃問題提供了保障，但同時每次都需要通過對比實驗進行改進，在很大程度上限制了遺傳算法的發展速度。