王永成 朱雨坤

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

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

中圖分類號：V279 文獻(xiàn)標(biāo)識碼：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)是一個復(fù)雜的系統(tǒng)，需要較高的可靠性。為了保證無人飛行器的可靠性，加強(qiáng)機(jī)身硬件設(shè)計(jì)固然重要，但軟件的設(shè)計(jì)也尤為重要。21世紀(jì)是信息爆炸的時代，特別是在現(xiàn)代化戰(zhàn)爭中，控制無人機(jī)需要快速有效地處理信息，這為設(shè)計(jì)工作帶來了巨大的挑戰(zhàn)。隨著信息激增，如何有效處理和快速做出反應(yīng)和決策就成了難題[1-4]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[（x，y）][R]

圖1 威脅區(qū)域

[][][]

圖2 禁飛區(qū)

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

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

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

2.2.1.2 禁飛區(qū)。禁飛區(qū)主要是指云層等惡劣天氣區(qū)，其對無人機(jī)的威脅服從均勻分布，其概率密度函數(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ū)對角線的兩個點(diǎn)。

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

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

3.1 遺傳算法

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

索空間][Efree：

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

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

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

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

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

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

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

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

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

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

表1 節(jié)點(diǎn)坐標(biāo)

[節(jié)點(diǎn)編號 X坐標(biāo) Y坐標(biāo) 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é)點(diǎn)

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

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

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

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

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

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

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