基于遺傳算法的無人機航路規(guī)劃研究

曹良秋 吳立巍

摘 要：針對無人機的多約束條件，將遺傳算法和具體的航路規(guī)劃問題相結(jié)合，把無人機的約束條件融合于算法中，設(shè)計了合理的染色體數(shù)據(jù)結(jié)構(gòu)、遺傳算子和航路評價函數(shù)。仿真分析表明，該算法能夠根據(jù)任務(wù)需求為無人機規(guī)劃出滿足生存概率和突防概率的飛行航路。

關(guān)鍵詞：無人機；遺傳算法；航路規(guī)劃；評價函數(shù)

中圖分類號：V249.3 文獻標識碼：A 文章編號：2095-2945（2018）24-0027-04

Abstract： In view of the multiple constraints of unmanned aerial vehicle （UAV）， the genetic algorithm is combined with the specific route planning problem， and the constraints of UAV are fused into the algorithm， and the reasonable chromosome data structure， genetic operator and route evaluation function are designed. Simulation results show that the algorithm can plan flight routes for the UAV to meet the survival probability and penetration probability according to the mission requirements.

Keywords： UAV； genetic algorithm； route planning； evaluation function

無人機在現(xiàn)代戰(zhàn)爭中的地位舉足輕重，無人機任務(wù)規(guī)劃系統(tǒng)核心技術(shù)之一則是航路規(guī)劃，通過合理規(guī)劃航路，可以使無人機有效規(guī)避威脅，提高生存概率和任務(wù)執(zhí)行效率。無人機航路規(guī)劃是指在一定的約束條件下，在分布了一些威脅區(qū)域的規(guī)劃空間中，通過規(guī)劃尋找讓從起始點到目標點的航跡優(yōu)化問題，使無人機具有最大生存率。

遺傳算法利用簡單的編碼技術(shù)和繁殖機制，建立起一個迭代過程，從而實現(xiàn)對問題的求解。遺傳算法具有很強的并行性和魯棒性，不受搜索空間的限制性假設(shè)的約束，不要求搜索空間連續(xù)，通過離散化搜索空間，從而大大縮小了搜索空間，提高搜索效率。

鑒于無人機航跡規(guī)劃和遺傳算法的特點，基于遺傳算法的航跡規(guī)劃具有很強的實用意義和研究價值。本文將遺傳算法的思想和無人機航路規(guī)劃的實際應(yīng)用相結(jié)合，通過采用實數(shù)基因編碼方式和特定的進化算子，能夠在規(guī)劃環(huán)境中為無人機在起飛前規(guī)劃出品質(zhì)較高的航路。

1 航路規(guī)劃空間

無人機航路規(guī)劃的目的是利用地形和敵情等威脅源、目標函數(shù)的分析應(yīng)用，規(guī)劃出滿足任務(wù)規(guī)劃要求的相對最優(yōu)的軌跡，本質(zhì)是多個約束條件下最優(yōu)或近似最優(yōu)可行解的求解問題，其系統(tǒng)框圖如圖1所示。航路規(guī)劃主要步驟是：

分析約束條件，對無人機飛行環(huán)境進行分析和建模，將無人機執(zhí)行任務(wù)的區(qū)域的地形、威脅、氣候以及無人機的性能參數(shù)等限制條件表示成符號信息。

選擇規(guī)劃算法，按目標函數(shù)對無人機的航路進行規(guī)劃，在限制條件下生成無人機的參考航路。

1.1 規(guī)劃空間建模

由于無人機巡航飛行時的高度不變，因此可以把三維航路規(guī)劃問題轉(zhuǎn)化為在某一定高平面下的二維航路規(guī)劃問題。一般來說，可以將各種威脅簡化成具有一定作用范圍的圓柱或圓錐幾何體的組合，其在二維平面的投影為具有一定半徑的圓形區(qū)域，如圖2所示。

1.2 航路評價建模

航路評價函數(shù)用于計算航路的適應(yīng)度，是判斷航路優(yōu)劣的重要標準以及引導(dǎo)搜索算法向最優(yōu)解逼近的關(guān)鍵。評估航路代價需要同時考慮航路的各種約束條件。

1.2.1 航路約束條件

2 基于遺傳算法的航路規(guī)劃

遺傳算法設(shè)定一個種群，該種群是由經(jīng)過基因編碼的一定數(shù)目的個體組成，每個個體就是帶有特征的染色體。染色體是由基因序列組成，每條染色體代表著問題的一個可能解。染色體根據(jù)問題域中的適應(yīng)度大小選擇個體，并借助遺傳算子以交叉、變異的方式不停地進化。這個過程就像自然進化一樣，適應(yīng)度高的個體更容易被選中，因此種群的整體適應(yīng)度將不斷提高。最后，得到的適應(yīng)度最高的染色體所代表的解就是問題的最優(yōu)解。

2.1 染色體編碼

染色體編碼是應(yīng)用遺傳算法進行航跡規(guī)劃的前提。編碼方法決定了個體的染色體排列形式，還決定了個體從搜索空間的基因類型變換到解空間的表現(xiàn)類型時的解碼方法，編碼方法也影響到交叉算子、變異算子等遺傳算子的運算方法。編碼方式可以是二進制數(shù)、浮點數(shù)、整數(shù)、字母或矩陣等的集合。已有研究表明，與問題的原始形式越接近，表現(xiàn)形式越有效，越能生成優(yōu)解。

本文采用變長度的實值基因編碼方式，如圖4所示。染色體的每個基因除了包含航路點的位置信息外（x，y），還包含狀態(tài)變量b，狀態(tài)變量包括了該節(jié)點航路段是否可行的標志。

初始種群可以隨機生成，染色體的最大長度（航路結(jié)點的最大數(shù)目）可作為預(yù)先確定的參數(shù)。在編碼時應(yīng)注意所有航路的初始和終點位置的坐標都是相同的，分別代表無人機的起始點和目標點。

2.2 航路評價函數(shù)

在計算一條航路的適應(yīng)度時應(yīng)綜合考慮安全性（威脅代價）和經(jīng)濟性（油料代價）的權(quán)重，式（7）中u表示威脅代價的權(quán)重系數(shù)，范圍在0～1之間，反映了設(shè)計者對威脅程度與油料代價選擇的傾向。當u接近1時表示應(yīng)優(yōu)先避免通過威脅區(qū)，保證無人機的安全；當u接近0時意味著航路盡可能短，威脅代價為次要因素。

2.3 遺傳操作

遺傳算法包括三個操作：選擇、交叉和變異。

（1）選擇操作：是指以一定概率從種群中選擇若干個體的操作，本文選擇的算法是比例選擇，也叫做輪盤賭選擇，其基本思想是個體被選中并遺傳到下一代群體中的概率與其適應(yīng)度大小成正比。具體執(zhí)行過程是：

a.計算種群所有個體的適應(yīng)度總和；

b.計算每個個體被選中的概率，即每個個體相對適應(yīng)度總和的比例；

c.使用模擬輪盤賭操作（即0到1之間的隨機數(shù)）確定各個個體被選中的次數(shù)。

（2）交叉操作：將兩條父代航路隨機分割成兩部分，將第一條航路的前半部分和第二條航路的后半部分組合，其余的二個部分組合，生成兩個新的子代個體。交叉的兩條航路長度可以不同。

（3）變異操作：以一定的變異概率隨機指定航路上某一個或幾個節(jié)點作變異運算，在這個過程中對最優(yōu)的個體不做變異操作。本文針對航路規(guī)劃的實際問題設(shè)計了四種變異算子，分別是擾動算子、刪除算子、插入算子和平滑算子。

a.擾動算子：對航路節(jié)點中的一個節(jié)點坐標隨機進行改變。如果原航路是可行的，則在可行范圍內(nèi)加以較小擾動，以提高航路的適應(yīng)值；如果原航路是不可行的，則可適當增大擾動幅度，以期獲得可行的航路；

b.刪除算子：刪除航路的一個中間節(jié)點。如果原航路是不可行的，該中間節(jié)點可以隨機選擇；如果原航路是可行的，則節(jié)點的選擇需要基于某些啟發(fā)式信息。

c.插入算子：隨機在兩個相鄰的航路節(jié)點中間插入一個新的航路節(jié)點。提高穿越威脅區(qū)域航路的可行性。

d.平滑算子：該算子在所選航路點相鄰兩個航路段上各插入一個隨機選擇的航路節(jié)點，然后刪除開始選擇的節(jié)點。如果某節(jié)點處航路轉(zhuǎn)彎角越大，選擇它進行平滑的概率越大。該算子只作用于不可行航路。

2.4 航路規(guī)劃步驟

（1）種群初始化。按照相應(yīng)的編碼方案隨機生成n條航路組成的初始種群P（0），設(shè)置進化代數(shù)計數(shù)器t=0，并設(shè)置最大進化代數(shù)；

（2）個體評價。依據(jù)不同的問題，計算群體P（t）中每條航路的適應(yīng)度值；

（3）遺傳操作。將選擇、交叉及變異算子作用于種群。種群P（t）經(jīng)過遺傳操作之后得到下一代種群P（t+1）。

（4）進化結(jié)束。如果進化代數(shù)小于最大進化代數(shù)，轉(zhuǎn)到步驟2，否則進化結(jié)束，從最終的種群中挑選出最優(yōu)解。

（5）將最優(yōu)解解碼，得到最優(yōu)航路。

3 仿真分析實例

運用matlab7.1對該算法進行仿真。設(shè)無人機飛行區(qū)域100km×100km，飛行任務(wù)區(qū)內(nèi)有六個威脅區(qū)，用“*”代表威脅源位置，圓圈范圍內(nèi)代表威脅區(qū)域。無人機起始點為（0，50），目標點為（100，50）。

遺傳算法參數(shù)設(shè)置為初始種群大小P=60，交叉概率Pc=0.7，變異概率Pm=0.1，最大進化代數(shù)T=200，權(quán)重系數(shù)u=0.5。進化結(jié)束條件為達到最大進化代數(shù)或該代種群適應(yīng)度均方差小于0.001。

圖8顯示了遺傳算法進行航路規(guī)劃的幾個不同的進化階段。圖9顯示了航路代價隨著進化過程的變化情況，在60代后收斂到最優(yōu)結(jié)果附近，在進化到137代時得到了最優(yōu)的航路，進化過程結(jié)束。

4 結(jié)束語

文章根據(jù)無人機定高飛行的特點，建立了合適的環(huán)境模型。針對無人機的多約束條件，通過對遺傳算法的研究，結(jié)合航路規(guī)劃的具體問題，將無人機的約束條件融合于算法中，設(shè)計了合理的染色體編碼、遺傳算子和航路評價函數(shù)。仿真分析表明，該算法能夠根據(jù)任務(wù)需求為無人機規(guī)劃出滿足生存概率和突防概率的飛行航路。

參考文獻：

[1]洪森.無人飛行器航跡規(guī)劃的研究[D].南京：南京航空航天大學，2011.

[2]胡中華.基于智能優(yōu)化算法的無人機航跡規(guī)劃若干關(guān)鍵技術(shù)研究[D].南京：南京航空航天大學，2011.

[3]辛貴州.無人飛行器航跡規(guī)劃算法研究[D].哈爾濱：哈爾濱工程大學，2010.

[4]董世建.復(fù)雜約束條件下航跡規(guī)劃方法研究[D].北京：北京理工大學，2016.

[5]俞琪.基于遺傳算法的快速航跡規(guī)劃方法研究[D].武漢：華中科技大學，2011.

[6]王睿，周洲，沈延航.高空長航時無人機航跡優(yōu)化研究[J].飛行力學，2006，24（3）：37-39.

[7]鄭銳，馮振明，陸明泉.基于遺傳算法的無人機航路規(guī)劃優(yōu)化研究[J].計算機仿真，2011，28（6）：88-91.

[7]蒙波.無人機航跡規(guī)劃與任務(wù)分析的仿真與實現(xiàn)[D].成都：電子科技大學，2010.

[8]李子杰，劉湘?zhèn)?，湯博，?基于進化算法的雷達對抗偵察無人機航路規(guī)劃[J].火力與指揮控制，201，38（6）：51-54.