基于混合遺傳算法的無人機航線規劃

王永成 朱雨坤

摘 要：針對航線規劃中的路徑組合爆炸問題進行了分析和討論，運用遺傳算法提出了解決方案，并對遺傳算法的過早收斂問題，結合模擬退火算法設計出航線規劃混合遺傳算法，改善了算法的性能，最后通過仿真分析驗證了其有效性。

關鍵詞：航線規劃；混合遺傳算法；無人機；模擬退火算法

中圖分類號：V279 文獻標識碼：A 文章編號：1003-5168（2018）02-0043-05

UAV Route Planning Based on Hybrid Genetic Algorithm

WANG Yongcheng ZHU Yukun

（Zhengzhou University of Aeronautics，Zhengzhou Henan 450046）

Abstract： For the combination explosion problem of path in route planning are analyzed and discussed， using the genetic algorithm is put forward the solution， and to the problem of premature convergence of genetic algorithm， hybrid genetic simulated annealing algorithm designed route planning algorithm， improve the performance of the algorithm. Finally， the effectiveness of the simulation is verified by simulation.

Keywords： flight path planning；hybrid Genetic Algorithm；UAV；simulated annealing

1 研究背景

無人飛行器控制系統是一個復雜的系統，需要較高的可靠性。為了保證無人飛行器的可靠性，加強機身硬件設計固然重要，但軟件的設計也尤為重要。21世紀是信息爆炸的時代，特別是在現代化戰爭中，控制無人機需要快速有效地處理信息，這為設計工作帶來了巨大的挑戰。隨著信息激增，如何有效處理和快速做出反應和決策就成了難題[1-4]。

無人飛行器航線規劃需要綜合考慮目標的位置、地形分布、威脅覆蓋、天氣現象、武器性能及其他相關信息，選擇一條最優路線，來完成飛行任務并安全返回。為了實現快速響應，必須準確快速地規劃出一條從起點到目標點的“最優”航線。

遺傳算法具有很強的并行性和魯棒性，能在全空間進行隨機搜索，實現地形跟隨和地形回避[5-7]。但由于遺傳算法過早的收斂和易陷入局部最優的缺陷，所以只能搜索到近似最優的可行解，而結合模擬退火算法進行局部最優解優化，可以解決這一問題。

2 航線規劃問題建模

航線是飛機飛行的從起點到終點的路線。航線規劃是規劃出一條滿足約束條件的從起點到終點的最優航線。算法是影響航線規劃的重要因素。

目前，航線規劃已被證明是一個NP問題[8]。近年來，已經研發出了很多智能規劃算法，且各個算法各不相同，特點各異。在處理實際問題時，設計出一種合適的算法，在較短時間內規劃出滿意的航線至關重要。

2.1 航線規劃的要素

飛行器的航線規劃一般包括以下幾個要素。

2.1.1 航跡的表述。本文的表達是：節點序列Route{P，N1，N2，…，Nn-1，Q}，P為起始點，Q終止點，N1，N2，…，Nn-1是航跡節點。每一個航跡節點記錄該點的空間位置坐標信息及其他設定的航跡信息。航跡包括三維航跡和二維航跡（平面航跡）。

2.1.2 約束條件。航線的約束條件主要為：無人機自身的物理約束、任務需求的任務約束、航跡規劃空間的自然約束。無人機的自身物理約束包括最大航程、最高/低速度、最大彎角等；任務需求的任務約束包括目標數目、敵方火力威脅等[5]；航跡規劃空間的自然約束包括高山、高大的建筑物等。滿足這些約束條件才可能是可行性航線。

2.1.3 確定目標函數。目標函數是評價航線規劃的標準，是規劃的最終目的。不同的規劃有不同的目的，且側重點不同：有的航線要求時間最少；有的航線路徑最短；有的航線是無人機生存概率較高；有的航線是無人機的任務完成率最高；有的航線則綜合考慮多個因素。總之，確定不同的權重因子是設置目標函數的重要手段。

2.1.4 規劃空間表示。規劃航線要先預設一個區域，即飛機執行任務的區域。這個預先設置的區域就是航線規劃的區域，也稱為搜索空間。無人飛行器航線規劃是在三維空間內進行搜索。設（x，y，h）為空間內某一點的坐標，其中x和y為經緯度，h為海拔高度，h（x，y）表示點（x，y）的海拔高度，代表一個規劃空間。將x，y，h分別按不同的分辨率進行劃分，從而得到離散化的網格規劃空間。離散化所采用的分辨率越高，規劃結果的精度就越高，但所需的運算量較大；反之，規劃結果的精度就越低。

2.2 航線規劃中的威脅條件

2.2.1 第一類問題。在航線規劃過程中需要考慮很多因素，而安全因素是需要考慮的首位因素。無人飛行器在飛行探測過程中需要與敵方的飛機、防空區域保持一定的安全距離，因此這里需要避開的威脅主要包括自然威脅，即山川、雷電等[9]。各種威脅模型簡化為幾何形狀的組合[10]，有利于簡化計算。

對自然威脅的建模分為兩種：一是威脅區（見圖1），二是禁飛區（見圖2）。

[（x，y）][R]

圖1 威脅區域

[][][]

圖2 禁飛區

2.2.1.1 威脅區。威脅區域一般代表山脈。山脈的威脅程度主要由山脈的距離決定，距離越近，威脅程度越大。假設Eij為航點i點到j點的航線段，Lij為航線段Eij的距離長度。無人機受到威脅的程度與航線在威脅區域的長短及與威脅中心（x，y）的距離有關[11]。

[J=0Lijk=1Na（x-xk）2+（y-yk）2dl] （1）

式（1）中，（x，y）為威脅中心點，（xk，yk）為進入威脅區域的點；N為進入區域點的個數；a為常數。

2.2.1.2 禁飛區。禁飛區主要是指云層等惡劣天氣區，其對無人機的威脅服從均勻分布，其概率密度函數是：

[J（（x，y））=Ji（m-p）（n-q），m≤x≤p，n≤y≤q 0， 其他] （2）

式（2）中，Ji為禁飛區i的威脅程度；（m，n）（p，q）為禁飛區對角線的兩個點。

2.2.2 第二類問題。第二類問題主要包括任務完成率、無人機的安全系數、雷達探測最大化、通信、探測敵方的位置和開機時長等。

3 混合遺傳算法與航線規劃

3.1 遺傳算法

遺傳算法是一種全局優化的隨機搜索方法，其工作流程如圖3所示。

索空間][Efree：

可行空間][不可行區域][G]

圖5 環境示意圖

圖5為環境示意圖，障礙物用任意多邊形處理，起點用[S∶X0，Y0∈Efree]表示，終點用[G∶Xe，Ye∈Efree]表示。此外，評價函數中的安全性條件要給出飛行器與障礙物接近的裕度，用來取代飛行器的尺寸。

把整個活動區域的大小定義為：

[E=（L，M）∈R2∶La≤L≤Lb，Wa≤W≤Wb] （7）

完全無碰撞的自由區域定義為：

[Efree=E-i=1kObstacle] （8）

用一個簡單的例子實際仿真驗證一下。首先求出鏈接圖，將空間劃分為凸多邊形，然后算出各個鏈接線的中點。運用運籌學Dijkstra的最短路法求出圖形的最短路作為初始路徑，然后再用混合遺傳算法進行進一步優化。

圖6 航行環境圖

示例：起始點為[S∶X0，Y0∈Efree]，S（0，8），終點為[G∶Xe，Ye∈Efree]，G（9，1），陰影部分為障礙區域（見圖6）。則取鏈接節點的編號1到17的坐標（x，y）見表1。

表1 節點坐標

[節點編號 X坐標 Y坐標 1 0 8 2 0 6 3 1 9 4 2 9 5 3 8 6 3 6 7 1 5 8 2 5 9 5 4 10 5 2 11 6 5 12 7 5 13 8 4 14 8 2 15 6 1 16 7 1 17 9 1 ]

用Dijkstra算法求得最短路（見表2），其中最優路徑是h1-h2-h7-h10-h15-h16-h17，路徑長為12.8。

表2 最短路的節點

[航跡點數據 X的坐標 Y的坐標 起始點 0 8 點一 0 6 點二 1 5 點三 5 2 點四 6 1 點五 7 1 終點 9 1 ]

如例，簡單圖形中的17個點的規劃就這么復雜，隨著節點的增加，運算步驟會成倍增加。但在實際中，地形是復雜的，依靠Dijkstra算法根本無法規劃計算出來，即使利用大量的時間和人工運算出最優路線，但人們預先掌握的信息有限，不可能確切地知道未來會發生什么，也不知道規劃的目標是否會臨時改變，這也是靜態規劃的缺陷，需要實時動態規劃。因為任何突發狀況都可能造成整個運算重新再來一遍。對于突發情況，人們是無法快速、準確地作出有效判斷的，所以本文繼續嘗試了混合遺傳算法。

4.2 最優航線規劃設計算法的過程

4.2.1 編碼方案。編碼方案采用二進制表示方法；路徑通過對任何一個轉向點都可以作為一個最優的轉向點進行交叉操作；變異算子有兩種，一是進化初期大范圍的變異，二是針對可行路徑轉向點周圍的部分進行局部微調或者平滑曲線，適應度函數可行路徑與不可行路徑分開，并對不可行路徑進行懲罰。將航線規劃的所有節點組合在一起為一個個體，由于每個個體的節點不一樣，根據圖形航線規劃的范圍，先進行Dijkstra規劃出初始路徑，作為遺傳算法的初始解，編碼長度即可確定。

4.2.2 算法的初始化。路徑的初始化問題，初始種群是Dijkstra產生的，在整個規劃區域內隨機產生轉向點的位置坐標。對于路徑的最大長度，其與環境點的復雜度有關。

4.2.3 終止條件的確定。①規定遺傳代數的代次；②對于方差這類目標函數，可采用控制極差圖的控制偏差來終止算法；③檢查適應度的變化。

4.2.4 算法描述。整個算法流程如圖7所示。首先根據任務需求依據地圖信息設置任務計劃，并給出定量描述，設置進化代數計數器初值及初始溫度，依據決策變量設置初始化種群，然后計算種群中所有個體的適應度數值，如果滿足預先設定的終止條件，則表示該種群即為最優解，否則通過遺傳操作產生下一代種群，并對新產生的種群計算其個體適應度數值，再和終止條件進行比較，直到得到最優解為止。