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

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

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

0 引言

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

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

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

1 航跡規(guī)劃問題

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

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

1.1 航跡規(guī)劃基本要求

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

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

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

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

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

1.2 智能飛行器航跡問題

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

2 智能飛行器航跡規(guī)劃

2.1 航跡規(guī)劃數(shù)學模型

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

智能飛行器飛行路程目標函數(shù)為：

飛行器經(jīng)過校正點的目標函數(shù)為：

式中：

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

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

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

對最小轉彎半徑約束為：

2.2 NSGA-II 算法求解過程

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

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

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

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

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

3 仿真結果

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

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

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

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

Table 1 Route planning results表1 航跡規(guī)劃結果

與NSGA 算法相比，NSGA-II 算法能實現(xiàn)快速、準確的搜索性能。分析智能飛行器航跡規(guī)劃總路徑和校正次數(shù)后發(fā)現(xiàn)，NSGA-II 算法相對于NSGA 算法收斂速度快了一倍，且最優(yōu)結果不易反復。在同時迭代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 兩種遺傳算法智能飛行器校正次數(shù)迭曲線

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

4 結語

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