改進(jìn)的混沌遺傳算法求解無人機(jī)航跡規(guī)劃問題

鄭濤

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

關(guān)鍵詞： 三維航跡規(guī)劃; 無人機(jī); 混沌遺傳算法; 混沌擾動(dòng); 擾動(dòng)因子

中圖分類號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

無人機(jī)航跡規(guī)劃就是指綜合考慮無人機(jī)機(jī)動(dòng)性能、突防概率、碰地概率和飛行時(shí)間等約束因素下，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或可行的飛行軌跡[1]。

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

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

1 三維航跡轉(zhuǎn)化為二維空間及在二維空間建模

CGA是在二維空間中的一種路徑優(yōu)先搜索算法，而低空無人機(jī)的航跡是三維的，因此必須把三維轉(zhuǎn)化為二維空間搜索。在轉(zhuǎn)化過程中，如何使用CGA從初始點(diǎn)到達(dá)目標(biāo)點(diǎn)進(jìn)行航跡搜索，如何進(jìn)行節(jié)點(diǎn)擴(kuò)展，如何選擇候選節(jié)點(diǎn)就成為首要解決的問題。而正確的建立搜索空間，正是解決這些問題的先決條件。

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

假定S為無人機(jī)的出發(fā)點(diǎn)，E為終止點(diǎn)，障礙物為一個(gè)長方體圖形A1B1C1D1-ABCD，當(dāng)由S點(diǎn)直線飛行到E點(diǎn)時(shí)，會(huì)與障礙物發(fā)生碰撞。

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

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

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

H、I、G、K四點(diǎn)組成的平面為障礙物在搜尋空間的投影平面，剩余的區(qū)域?yàn)榭赏ㄟ^的區(qū)域。首先在搜尋平面上按柵格進(jìn)行劃分，按照柵格中心點(diǎn)的估計(jì)函數(shù)進(jìn)行最優(yōu)搜尋，找到向左或向右的飛行軌跡;然后將交點(diǎn)M向外擴(kuò)展到點(diǎn)M1，在搜尋區(qū)域范圍內(nèi)尋找啟發(fā)函數(shù)的最佳點(diǎn)M2;最后利用CGA可以找到由M1到M2的最佳搜尋路徑。則二維搜尋路徑最終由S到M1，再由M1到M2，M2到E。如圖2所示。

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

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

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

2 三維航跡規(guī)劃及算法設(shè)計(jì)

2.1 無人機(jī)的約束條件與優(yōu)化函數(shù)

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

本文把從擴(kuò)展節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的直線距離作為啟發(fā)函數(shù)[5]。即：

其中啟發(fā)函數(shù)表示的其實(shí)是從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)實(shí)際代價(jià)的下限，這樣既滿足可納性，又滿足一致性。

2.2 航跡規(guī)劃的搜索步驟

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

Step2 在起始位置S到目標(biāo)位置E的連線上，按照Step1設(shè)定的長方體范圍判斷，障礙物是否與SE直線相交。若相交，則計(jì)算線段SE與障礙物的交點(diǎn)，否則，轉(zhuǎn)到Step5。

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

Step4 將交點(diǎn)1、交點(diǎn)2…，所有軌跡線交點(diǎn)的坐標(biāo)添加到Vega路徑中，實(shí)現(xiàn)避障路徑規(guī)劃;

Step5 把S點(diǎn)移到當(dāng)前位置，E點(diǎn)不變。按照SE方向繼續(xù)向前搜索，若到達(dá)目標(biāo)位置，則退出。若碰到障礙物，則轉(zhuǎn)到Step2。

3 CGA二維路徑規(guī)劃及算法設(shè)計(jì)

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

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

3.1 隨機(jī)擾動(dòng)的確定

δ*為當(dāng)前最優(yōu)解（x1*，…，xr*）映射到[0，1]區(qū)間后形成的向量，稱為最優(yōu)混沌向量;δk為迭代k次后的混沌向量，δ′k為加了隨機(jī)擾動(dòng)后（x1，…，xr）對(duì)應(yīng)的混沌向量[6]。其中0<α<1，采用自適應(yīng)選取，這是因?yàn)樗阉鞒跗谙Ｍ▁1，…，xr）變動(dòng)較大，需要較大的α。隨著搜索的進(jìn)行，（x1，…，xr）逐漸接近最優(yōu)點(diǎn)，故需要選用較小的α，以便在（x1*，…，xr*）所在的小范圍內(nèi)搜索[7]。本文應(yīng)用式⑷確定α。

其中m為一整數(shù)，依優(yōu)化目標(biāo)函數(shù)而定;k為迭代次數(shù)。

3.2 CGA設(shè)計(jì)步驟

在3.1節(jié)確定擾動(dòng)方案后，按CGA算法搜索待優(yōu)化參數(shù)xi的步驟如下。

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

Step2 選用式⑸所示的Logistic映射，關(guān)系式如下：

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

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

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

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

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

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

Step6 對(duì)下一代群體按規(guī)則計(jì)算出符合自身?xiàng)l件的適應(yīng)度值，然后按式⑾的規(guī)則適度調(diào)整，調(diào)整完畢按調(diào)整后的適應(yīng)度值大小，對(duì)群體排序，求出適應(yīng)度均值，并將其均值與適應(yīng)度最大值按照式⑽進(jìn)行比對(duì)，若式⑽成立，則認(rèn)為尋優(yōu)過程結(jié)束，輸出結(jié)果作為最優(yōu)值;若式⑽不成立，執(zhí)行Step7。

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

Step8 按適應(yīng)度值大小再次對(duì)群體排序，求出適應(yīng)度平均值，按式⑽的規(guī)則將其與最大值比對(duì)，若式⑽建立，則尋優(yōu)結(jié)束并輸出最優(yōu)值，不然轉(zhuǎn)到Step5。

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

4 仿真及結(jié)果分析

4.1 仿真環(huán)境

⑴ 軟件環(huán)境

Vega是MultiGen-Paradigm公司最主要的工業(yè)軟件環(huán)境，用于實(shí)時(shí)視覺模擬、虛擬現(xiàn)實(shí)和普通視覺應(yīng)用。

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

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

Matlab R2017b是MathWorks公司推出的專門用于科學(xué)、工程計(jì)算和系統(tǒng)仿真的高級(jí)語言。

⑵ 硬件環(huán)境

主機(jī)配置：Intel（R） Core（TM） i3-4130 CPU，1G內(nèi)存，800G硬盤。操作系統(tǒng)：Windows 10。

4.2 仿真分析

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

⑴ 二維環(huán)境仿真

在二維平面仿真中，運(yùn)用柵格法對(duì)環(huán)境進(jìn)行劃分（如圖4）。

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

從圖5看出，收斂速度較快，在第10代左右已尋到最優(yōu)解，且隨著進(jìn)化代數(shù)的增加，完好保持了最優(yōu)解，并未發(fā)生傳統(tǒng)遺傳算法的解丟失情況。

⑵ 三維環(huán)境仿真

僅考慮二維環(huán)境的路徑規(guī)劃是遠(yuǎn)遠(yuǎn)不夠的，必須考慮在三維中的應(yīng)用情況，驗(yàn)證是否實(shí)現(xiàn)二維到三維的平滑過渡與無縫連接。

為此，本文以Creator/Vega為仿真平臺(tái)，建立仿真環(huán)境，完成對(duì)復(fù)雜地形地貌場景的設(shè)計(jì)。根據(jù)算法的設(shè)計(jì)情況，分別對(duì)水平與垂直兩種情況下的航跡進(jìn)行驗(yàn)證，避障仿真效果如圖6和圖7。

從圖6、圖7看出，用本文所設(shè)計(jì)方法進(jìn)行三維環(huán)境路徑規(guī)劃，畫面運(yùn)行流暢，不僅能避開障礙物，而且基本符合真實(shí)性和實(shí)時(shí)性的要求，所規(guī)劃出的路徑也相對(duì)較優(yōu)。

⑶ 運(yùn)行時(shí)間與CPU占用率

當(dāng)柵格數(shù)較小時(shí)，改進(jìn)的混沌遺傳算法較A*算法有所改善但并不明顯，是因?yàn)槿S空間的數(shù)據(jù)值比較小，使得運(yùn)算與二維的復(fù)雜度接近，如圖8所示。

但是隨著柵格數(shù)的增加，搜素空間也逐步加大，二維運(yùn)算的優(yōu)勢(shì)逐步顯現(xiàn)，運(yùn)行時(shí)間大大縮短。因此當(dāng)柵格數(shù)較小時(shí)，把三維空間轉(zhuǎn)化為二維空間的效果并不理想，甚至有可能因?yàn)樵谵D(zhuǎn)化過程中，轉(zhuǎn)化程序也占用一定的時(shí)間而降低算法性能。

5 結(jié)束語

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

參考文獻(xiàn)（References）：

[1] 李猛，王道波，盛守照.采用多重啟發(fā)蟻群優(yōu)化算法的無人機(jī)航跡規(guī)劃[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2011.39（10）：37-43

[2] 魏亭，厲虹.基于稀疏A*遺傳算法的無人機(jī)三維航跡規(guī)劃[J].北京信息科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 馬云鵬，牛培峰，陳科，閆姍姍等.基于混沌分組教與學(xué)優(yōu)化算法鍋爐NO_x模型優(yōu)化研究[J].計(jì)量學(xué)報(bào)，2018.39（1）：125-129

[6] 李隘優(yōu).基于KCPSO算法對(duì)閩西地區(qū)崩塌地判釋[J].江南大學(xué)學(xué)報(bào)（自然科學(xué)版），2015.14（6）：746-750

[7] 虞亞平.京津冀能源需求預(yù)測(cè)分析及發(fā)展對(duì)策研究[D].天津理工大學(xué)碩士學(xué)位論文，2017

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

[9] 柳締西子，范勤勤，胡志華.基于混沌搜索和權(quán)重學(xué)習(xí)的教與學(xué)優(yōu)化算法及其應(yīng)用[J].智能系統(tǒng)學(xué)報(bào)，2018.13（5）：818-828

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

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

[12] 余巖，王宏遠(yuǎn)，謝雨翔.一種在未知噪聲下的快速波達(dá)方向估計(jì)方法[J].系統(tǒng)工程與電子技術(shù)，2010.32（4）：707-711