曹良秋 吳立巍

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

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

中圖分類號(hào)：V249.3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

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

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

1 航路規(guī)劃空間

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

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

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

1.1 規(guī)劃空間建模

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

1.2 航路評(píng)價(jià)建模

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

1.2.1 航路約束條件

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

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

2.1 染色體編碼

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

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

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

2.2 航路評(píng)價(jià)函數(shù)

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

2.3 遺傳操作

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

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

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

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

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

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

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

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

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

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

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

2.4 航路規(guī)劃步驟

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

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

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

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

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

3 仿真分析實(shí)例

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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