改進的混沌遺傳算法求解無人機航跡規劃問題

鄭濤

摘? 要： 針對無人機航跡規劃問題展開研究，采用混沌遺傳算法對無人機低空追擊目標的航跡進行規劃。該方法將無人機在低空復雜環境中的動力學模型離散化，結合約束條件，將三維空間劃分為多個二維空間并利用柵格法進行二維建模，在二維空間下采用改進的混沌遺傳算法來路徑尋優，最終完成在三維空間中避開障礙物的航跡搜索過程。以建模工具Creator/Vega為仿真平臺，建立仿真環境。仿真結果表明，該算法能夠有效地規劃出一條滿足要求的航跡，且通過把三維空間轉化為二維建模，避免了在三維空間求解的復雜性，提高了算法的工程實用性。

關鍵詞： 三維航跡規劃; 無人機; 混沌遺傳算法; 混沌擾動; 擾動因子

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2020）11-26-05

Abstract： The paper discusses route planning issues of unmanned aerial vehicle by chaotic genetic algorithms， emphases on planning its tracking trajectory of avoiding obstacles at a low altitude. The method discretizes the dynamic model of low-altitude aircraft in complex environments， and according to all the constraints， the 3D space is divided into several 2D spaces， and the grid method is used for 2D modeling， and the improved chaotic genetic algorithm is used to optimize the path in the 2D space， thus completes the route planning process to avoid obstacles in the 3D space. Creator and Vega are used as modeling and developing tools to build the simulation platform. The simulation results prove that the proposed method can plan an approximate optimal path successfully， and avid solving the complexity of route planning problem in the 3D space by transforming 3D to 2D， which improves the engineering practicability.

Key words： three-dimensional route planning; unmanned aerial vehicle; chaotic genetic algorithm; chaotic perturbation; perturbation factor

0 引言

無人機航跡規劃就是指綜合考慮無人機機動性能、突防概率、碰地概率和飛行時間等約束因素下，尋找一條從起始點到目標點的最優或可行的飛行軌跡[1]。

由于遺傳算法的魯棒性，近年來有諸多學者，利用進化與遺傳算法進行路徑規劃研究，取得了一定的成果。魏亭等人提出了基于稀疏A*遺傳算法的無人機三維航跡規劃方法[2]，稀疏A*算法是一種啟發式搜索算法，它結合約束條件大大縮小了搜素空間，大大縮小搜素時間，但在三維空間中構造代價函數和啟發函數，由于函數求解過程需要在立體空間中計算，大大增加了算法的難度。劉群芳，李軍華在稀疏A*算法的基礎上結合進化原理，引入了文化算法，基于稀疏A*算法與文化算法的混合算法實現了動態目標的無人機航跡規劃，為有效解決復雜的多維非線性工程優化問題提供了一條分析方法，有很大的參考價值。本文利用混沌遺傳算法（Chaotic Genetic Algorithm， CGA）并進行擾動因子的改進，綜合考慮無人機的機動性能、地形高程障礙威脅以及飛行任務等多種因素，運用改進的CGA進行航跡規劃。

首先利用Creator/Vega進行三維空間建模，然后參考文獻[3]和文獻[4]的方式，將三維空間搜尋轉為二維空間求解，最后利用改進的CGA在二維空間展開航跡搜尋。經由對搜尋空間降維，下降算法難度，以獲得提升搜尋效率的目標。

1 三維航跡轉化為二維空間及在二維空間建模

CGA是在二維空間中的一種路徑優先搜索算法，而低空無人機的航跡是三維的，因此必須把三維轉化為二維空間搜索。在轉化過程中，如何使用CGA從初始點到達目標點進行航跡搜索，如何進行節點擴展，如何選擇候選節點就成為首要解決的問題。而正確的建立搜索空間，正是解決這些問題的先決條件。

在三維空間中，目標和障礙物位置已知情況下，無人機自初始位置選擇最佳避障路徑向目標位置行進的過程（如圖1）。

假定S為無人機的出發點，E為終止點，障礙物為一個長方體圖形A1B1C1D1-ABCD，當由S點直線飛行到E點時，會與障礙物發生碰撞。

探索路徑的三維搜尋空間，并繞開障礙物的前提下，過程建立如下：

Step1 連出發點到終止點的線段SE，找到SE線段與長方體障礙物的第一個交點M，經由M做與長方體頂面平行的平面，且此平面與該長方體依次交于H、I、G、K四點，改變擴展因子把此平面向周圍擴大搜尋空間為OPQR。擴展因子的選取值以無人機能夠旋轉的最大角度α為基準。

Step2 在二維水平空間確立搜尋區域（如圖2）。

H、I、G、K四點組成的平面為障礙物在搜尋空間的投影平面，剩余的區域為可通過的區域。首先在搜尋平面上按柵格進行劃分，按照柵格中心點的估計函數進行最優搜尋，找到向左或向右的飛行軌跡;然后將交點M向外擴展到點M1，在搜尋區域范圍內尋找啟發函數的最佳點M2;最后利用CGA可以找到由M1到M2的最佳搜尋路徑。則二維搜尋路徑最終由S到M1，再由M1到M2，M2到E。如圖2所示。

Step3 在三維垂直空間確立搜尋區域（如圖3）。

首先將OPQR平面以擴展因子的值不斷向上擴展，當超出障礙物的頂部時，求得無人機向上飛行的軌跡搜尋區域;其次在該三維空間的頂面柵格中計算出離目的地E路徑最短的柵格M2;然后應用CGA找出頂面中距離M1最短的柵格路徑。則三維搜尋路徑最終由S到M1，再由M1到M2，M2到E。

Step4 比較水平搜尋路徑（如圖2）和垂直向上搜尋路徑（如圖3）的路徑值，最后確定最佳路徑。

2 三維航跡規劃及算法設計

2.1 無人機的約束條件與優化函數

無人機在飛行時有很多的約束限制，不同條件下約束各異。本文研究的無人機的主要約束條件包括：最小步長限制（[Smin]），最大轉向角度（[θmax]），最大爬升/俯沖角，航跡距離約束，固定進入（接近）目標位置時的方向，飛行高度限制（[Hmax]）。綜合以上約束條件，采用如下代價函數：

本文把從擴展節點到目標節點之間的直線距離作為啟發函數[5]。即：

其中啟發函數表示的其實是從當前節點到目標節點實際代價的下限，這樣既滿足可納性，又滿足一致性。

2.2 航跡規劃的搜索步驟

Step1 粗略過濾障礙物。輸入障礙物的坐標，判定此障礙物是不是在（Sx，Sy，Sz）到（Ex，Ey，Ez）所組成的長方體范圍內。如果在，轉到Step2;如果只有一部分在，則對區域邊緣以n倍的Smin進行外擴，給n設定一個上限，這里設為3，轉到Step2;如果不在，則對超出的范圍的障礙物不予考慮，轉到Step5。

Step2 在起始位置S到目標位置E的連線上，按照Step1設定的長方體范圍判斷，障礙物是否與SE直線相交。若相交，則計算線段SE與障礙物的交點，否則，轉到Step5。

Step3 過交點上做與頂面平行和垂直的平面。對于平行平面，利用第3部分改進的CGA進行二維路徑規劃，找出最優路徑軌跡（如圖2）。對于垂直平面，使用擴展因子在平面中進行三維擴展（如圖3），擴展后的平面同樣采用CGA進行路徑尋優，然后選擇距離最短的那條路徑段作為最終的軌跡。

Step4 將交點1、交點2…，所有軌跡線交點的坐標添加到Vega路徑中，實現避障路徑規劃;

Step5 把S點移到當前位置，E點不變。按照SE方向繼續向前搜索，若到達目標位置，則退出。若碰到障礙物，則轉到Step2。

3 CGA二維路徑規劃及算法設計

在二維空間采用柵格法建模后，采用實數編碼，運用CGA來優化路徑。CGA是混沌算法（Chaos Algorithm，CA）和遺傳算法（Genetic Algorithm，GA）的集成，是在求解復雜優化問題使用的最廣泛的遺傳算法的基礎上，引入混沌擾動來解決單一遺傳的早熟和局部收斂的算法。

CGA設計思想是首先按照遺傳算法的基本步驟，即初始種群生成、選擇、交叉和變異生成路徑;然后引入混沌擾動。因篇幅所限，本文直接把遺傳算法變異后的解集代入混沌優化式中，對遺傳算法求解的詳細計算過程不做描述。

3.1 隨機擾動的確定

δ*為當前最優解（x1*，…，xr*）映射到[0，1]區間后形成的向量，稱為最優混沌向量;δk為迭代k次后的混沌向量，δ′k為加了隨機擾動后（x1，…，xr）對應的混沌向量[6]。其中0<α<1，采用自適應選取，這是因為搜索初期希望（x1，…，xr）變動較大，需要較大的α。隨著搜索的進行，（x1，…，xr）逐漸接近最優點，故需要選用較小的α，以便在（x1*，…，xr*）所在的小范圍內搜索[7]。本文應用式⑷確定α。

其中m為一整數，依優化目標函數而定;k為迭代次數。

3.2 CGA設計步驟

在3.1節確定擾動方案后，按CGA算法搜索待優化參數xi的步驟如下。

Step1 給變量設定取值范圍[ai，bi]、群體大小m、混沌算子中的吸引子μi及父代間的互換率Pc1，Pc2和子代的變異率Pm[8]。

Step2 選用式⑸所示的Logistic映射，關系式如下：

其中i表示混沌變量的序號，i=1，…，r;u表示種群序號，u=0，1，…，m;βi表示混沌變量，0≤βi≤1;μi表示吸引子。

取u=0，μi=4[9]。先給式⑸賦r個微小差異的初值，得到r個混沌變量βi（1），（i=1，…，r）。依次取u=1，2，…，m，可得到m個初始解群[10]。

Step3 用載波法[11]，將選定r個混沌變量βi（u+1）分別引入到式⑹的r個優化變量中，使其變換為混沌變量[x'i]，混沌變量的取值范圍，會相應切換到相應的優化變量的取值范圍[12]。

Step4 把式⑵作為適應度函數的判斷準則，計算式⑻生成的適應度值，把適應度值按照降序排列，因為f（X′）小于0時不能作為適應度，而且即便f（X′）非負，但若f（X′）對某一代群體相對變化范圍過小，相當于兩代值過于靠近或類同，會造成算法收斂速率很慢，因此還需要對f（X′）按下式作微小變化：

其中f′k（X′）為微小變化后的適應度值，fk（X′）為微小變化前的適應度值，f（X′）min為微小變化前的最小適應度值，f（X′）max為微小變化前的最大適應度值，m為群體大小，按式⑼調整后，適應度值均大于0，且適應度值的相對變化范圍加大，便于加大收斂速度。

Step5 把所有變量按十進制進行編碼，上一代群體中適應度值排在前10%的變量不參與遺傳的三種操作（復制、交叉、變異），直接進入下一代群體，剩下的90%由這三種操作生成，對子代群體按規則解碼。

Step6 對下一代群體按規則計算出符合自身條件的適應度值，然后按式⑾的規則適度調整，調整完畢按調整后的適應度值大小，對群體排序，求出適應度均值，并將其均值與適應度最大值按照式⑽進行比對，若式⑽成立，則認為尋優過程結束，輸出結果作為最優值;若式⑽不成立，執行Step7。

Step7 在當前代群體中，選取適應度較小的90%個體，找到其對應的最優解，先按照式⑸的方法給其加一混沌擾動，將其轉換為混沌變量，然后再按式⑹的方法映射為混沌優化變量，最后將混沌變量和混沌優化變量代入式⑶，進行迭代計算。隨著迭代次數的增加，式⑷計算出的[α]值不斷變化，迭代逐步向最優解逼近，逼近到先后兩次計算出的適應度平均值之差小于預先給定的某個小正數[ε2]時，運算結束。

Step8 按適應度值大小再次對群體排序，求出適應度平均值，按式⑽的規則將其與最大值比對，若式⑽建立，則尋優結束并輸出最優值，不然轉到Step5。

按上述八個步驟對變異后的基因加入混沌擾動，且僅對某一代群體中適應度較小的90%的基因加混沌擾動，相當于對這些基因進行啟發式的變異操作，可減少算法的進化代數，及早找到最優解;而且這種擾動有可能產生比前述10%較高適應度對應的基因更好的基因，有效地避免單純的遺傳算法局部收斂與早熟的問題，此外，由于遺傳已生成10%的適應度較高的基因，只對剩下90%的基因進行混沌擾動，縮小了遺傳算法的搜尋空間，可加速尋優速率。

4 仿真及結果分析

4.1 仿真環境

⑴ 軟件環境

Vega是MultiGen-Paradigm公司最主要的工業軟件環境，用于實時視覺模擬、虛擬現實和普通視覺應用。

Creator是MultiGen-Paradigm公司開發的一種用于創建逼真的三維模型和復雜地形的工具軟件。

VC++2015是Microsoft公司推出的Microsoft Visual Studio 2015工具包里的軟件之一，用于編寫日常應用軟件。

Matlab R2017b是MathWorks公司推出的專門用于科學、工程計算和系統仿真的高級語言。

⑵ 硬件環境

主機配置：Intel（R） Core（TM） i3-4130 CPU，1G內存，800G硬盤。操作系統：Windows 10。

4.2 仿真分析

本文首先在二維環境下仿真，在VC++平臺下實現CGA路徑尋優，并對相關數據借助Matlab曲線模擬進行分析;然后以Vega為仿真平臺，利用Creator工具建立100km×100km的三維地理環境模型，包括沙漠、沼澤地、湖泊、城鎮、鄉村、道路、高大植物等，以城鎮建筑物和高大植物為障礙物，演示低空無人機在擊中目標時，避開這些障礙物尋優航跡的情況。

⑴ 二維環境仿真

在二維平面仿真中，運用柵格法對環境進行劃分（如圖4）。

從圖4中可以看出，滿足約束條件的前提下，尋到了一條接近最優解的路徑。由于遺傳算法的隨機性，進行多次實驗求其均值。

從圖5看出，收斂速度較快，在第10代左右已尋到最優解，且隨著進化代數的增加，完好保持了最優解，并未發生傳統遺傳算法的解丟失情況。

⑵ 三維環境仿真

僅考慮二維環境的路徑規劃是遠遠不夠的，必須考慮在三維中的應用情況，驗證是否實現二維到三維的平滑過渡與無縫連接。

為此，本文以Creator/Vega為仿真平臺，建立仿真環境，完成對復雜地形地貌場景的設計。根據算法的設計情況，分別對水平與垂直兩種情況下的航跡進行驗證，避障仿真效果如圖6和圖7。

從圖6、圖7看出，用本文所設計方法進行三維環境路徑規劃，畫面運行流暢，不僅能避開障礙物，而且基本符合真實性和實時性的要求，所規劃出的路徑也相對較優。

⑶ 運行時間與CPU占用率

當柵格數較小時，改進的混沌遺傳算法較A*算法有所改善但并不明顯，是因為三維空間的數據值比較小，使得運算與二維的復雜度接近，如圖8所示。

但是隨著柵格數的增加，搜素空間也逐步加大，二維運算的優勢逐步顯現，運行時間大大縮短。因此當柵格數較小時，把三維空間轉化為二維空間的效果并不理想，甚至有可能因為在轉化過程中，轉化程序也占用一定的時間而降低算法性能。

5 結束語

仿真結果表明，本文算法充分考慮了地形信息，計算出來的航跡能主動的對障礙物進行判斷并繞行避障，在航跡最佳性，搜尋實時性和算法時效性上更高效，能夠滿足實時規劃需要。

參考文獻（References）：

[1] 李猛，王道波，盛守照.采用多重啟發蟻群優化算法的無人機航跡規劃[J].華南理工大學學報（自然科學版），2011.39（10）：37-43

[2] 魏亭，厲虹.基于稀疏A*遺傳算法的無人機三維航跡規劃[J].北京信息科技大學學報（自然科學版），2015.1：35-40

[3] ZENG Jia-you， XIE Yu-peng， BIAN Hong-fei， et al.Research on anti-saturation attack model of SAM to ARM[C]//International Conference on Communications in Computer and Information Science.Shanghai：Springer，2012：221-227

[4] Cheng L J， Ding Y S， Hao K R. An ensemble kernel classifier with immune clonal selection algorithm for automatic diseriminant of primary open-angle glaucoma[J]. Neurocomputing，2012.83（15）：1-11

[5] 馬云鵬，牛培峰，陳科，閆姍姍等.基于混沌分組教與學優化算法鍋爐NO_x模型優化研究[J].計量學報，2018.39（1）：125-129

[6] 李隘優.基于KCPSO算法對閩西地區崩塌地判釋[J].江南大學學報（自然科學版），2015.14（6）：746-750

[7] 虞亞平.京津冀能源需求預測分析及發展對策研究[D].天津理工大學碩士學位論文，2017

[8] 張志軍.長距離供水管道水錘分析優化與應用研究[D].西安建筑科技大學碩士學位論文，2016.

[9] 柳締西子，范勤勤，胡志華.基于混沌搜索和權重學習的教與學優化算法及其應用[J].智能系統學報，2018.13（5）：818-828

[10] 李曉萌，王道波，郭繼凱，楊華，王博航.基于某種生物啟發式算法的無人機航跡規劃[J].機械與電子，2018.36（11）：15-19

[11] 孫健，井立，劉朝君.突發威脅下的無人機航跡規劃算法[J].飛行力學，2018.36（3）：52-55

[12] 余巖，王宏遠，謝雨翔.一種在未知噪聲下的快速波達方向估計方法[J].系統工程與電子技術，2010.32（4）：707-711