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

曹良秋 吳立巍

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

關鍵詞：無人機；遺傳算法；航路規劃；評價函數

中圖分類號：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

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

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

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

1 航路規劃空間

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

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

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

1.1 規劃空間建模

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

1.2 航路評價建模

航路評價函數用于計算航路的適應度，是判斷航路優劣的重要標準以及引導搜索算法向最優解逼近的關鍵。評估航路代價需要同時考慮航路的各種約束條件。

1.2.1 航路約束條件

2 基于遺傳算法的航路規劃

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

2.1 染色體編碼

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

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

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

2.2 航路評價函數

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

2.3 遺傳操作

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

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

a.計算種群所有個體的適應度總和；

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

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

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

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

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

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

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

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

2.4 航路規劃步驟

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

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

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

（4）進化結束。如果進化代數小于最大進化代數，轉到步驟2，否則進化結束，從最終的種群中挑選出最優解。

（5）將最優解解碼，得到最優航路。

3 仿真分析實例

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

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

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

4 結束語

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

參考文獻：

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

[2]胡中華.基于智能優化算法的無人機航跡規劃若干關鍵技術研究[D].南京：南京航空航天大學，2011.

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

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

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

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

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

[7]蒙波.無人機航跡規劃與任務分析的仿真與實現[D].成都：電子科技大學，2010.

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