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

王永成 朱雨坤

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

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

中圖分類號：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 研究背景

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

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

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

2 航線規(guī)劃問題建模

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

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

2.1 航線規(guī)劃的要素

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

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

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

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

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

2.2 航線規(guī)劃中的威脅條件

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

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

[（x，y）][R]

圖1 威脅區(qū)域

[][][]

圖2 禁飛區(qū)

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

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

式（1）中，（x，y）為威脅中心點，（xk，yk）為進入威脅區(qū)域的點；N為進入?yún)^(qū)域點的個數(shù)；a為常數(shù)。

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

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

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

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

3 混合遺傳算法與航線規(guī)劃

3.1 遺傳算法

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

索空間][Efree：

可行空間][不可行區(qū)域][G]

圖5 環(huán)境示意圖

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

把整個活動區(qū)域的大小定義為：

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

完全無碰撞的自由區(qū)域定義為：

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

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

圖6 航行環(huán)境圖

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

表1 節(jié)點坐標

[節(jié)點編號 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），其中最優(yōu)路徑是h1-h2-h7-h10-h15-h16-h17，路徑長為12.8。

表2 最短路的節(jié)點

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

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

4.2 最優(yōu)航線規(guī)劃設計算法的過程

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

4.2.2 算法的初始化。路徑的初始化問題，初始種群是Dijkstra產(chǎn)生的，在整個規(guī)劃區(qū)域內(nèi)隨機產(chǎn)生轉(zhuǎn)向點的位置坐標。對于路徑的最大長度，其與環(huán)境點的復雜度有關。

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

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