基于多生境遺傳算法的無人機航跡規(guī)劃

呂文鵬 許峰

摘要：基本遺傳算法易早熟和局部搜索能力欠佳，為此，將多生境遺傳算法應(yīng)用于無人機災(zāi)情巡查路徑優(yōu)化。基本思想是：在適應(yīng)值共享基礎(chǔ)上，在選擇算子中引入排擠機制，在交叉算子中采用間隔交叉，并使用最相似個體中適應(yīng)度最差的個體替換技術(shù)。數(shù)值實驗表明，多生境遺傳算法可以大大提高種群的多樣性，在很大程度上避免早熟，獲得比基本遺傳算法更優(yōu)的巡查路徑。

關(guān)鍵詞：無人機；航跡規(guī)劃；多生境遺傳算法；局部收斂性

DOI：10.11907/rjdk.172886

中圖分類號：TP319

文獻標(biāo)識碼：A文章編號：1672-7800（2018）007-0166-03

Abstract：Aimingattheshortcomingsofthebasicgeneticalgorithmwhichiseasytoprematureandthelocalsearchabilityispoor，themultinichegeneticalgorithmisappliedtotheUAVdisasterpatrolpathoptimization.Thebasicideaisthatonthebasisoffitnesssharing，thecrowdingoutmechanismisintroducedintotheselectionoperator，theintervalcrossoverisadoptedinthecrossoveroperator，andtheindividualsubstitutiontechniquewiththeworstfitnessamongthemostsimilarindividualsisadopted.Numericalexperimentsshowthatthenichegeneticalgorithmcangetbetterpatrolpaththanthebasicgeneticalgorithm.

KeyWords：UAV；pathplanning；multi-nichegeneticalgorithm；localconvergence

0引言

無人機已廣泛應(yīng)用于軍事偵察與打擊、城市規(guī)劃、資源調(diào)查、災(zāi)情巡查等領(lǐng)域。無人機任務(wù)規(guī)劃中最重要的是航跡規(guī)劃，即在一定約束條件下，尋找從起始點到目標(biāo)點的最優(yōu)路徑。合理的航跡規(guī)劃不僅節(jié)省資源，提高飛行效率，還可有效規(guī)避威脅，提高生存概率。

常用無人機航跡規(guī)劃方法有隨機搜索法、Voronoi圖法和優(yōu)化方法[1]。無人機航跡規(guī)劃往往包含復(fù)雜約束大規(guī)模優(yōu)化問題，主流方法是啟發(fā)式智能優(yōu)化算法，如蟻群算法、粒子群算法、模擬退火算法、遺傳算法等。早在1998年，Patcher[2]就討論了路徑規(guī)劃問題中的關(guān)鍵優(yōu)化技術(shù)及其復(fù)雜性；Dong、Zheng和Nikolos等系統(tǒng)研究了路徑規(guī)劃中進化算法的優(yōu)化原理[3-5]；Wu[6]最早將遺傳算法應(yīng)用于航行器的路徑規(guī)劃問題。目前，無人機航跡規(guī)劃優(yōu)化工作多集中于對已有啟發(fā)式智能優(yōu)化算法的改進研究[7-10]。

基本遺傳算法（SGA）對搜索空間和目標(biāo)函數(shù)要求不高，適用面廣，魯棒性強，具有隱并行性，且全局搜索能力較強。但在求解復(fù)雜優(yōu)化問題時，基本遺傳算法經(jīng)常表現(xiàn)出易陷于局部最優(yōu)解和局部尋優(yōu)精度不高的缺陷。為此，本文將多生境遺傳算法（MNGA）應(yīng)用于無人機航跡規(guī)劃問題，并根據(jù)數(shù)據(jù)實驗對該算法進行了性能測試。

1航跡規(guī)劃問題

無人機航跡規(guī)劃通常指在綜合考慮無人機的機動性能、碰地概率、突防概率、油耗、威脅和飛行時間約束等各種因素下，找到一條從起始點到目標(biāo)點的最優(yōu)飛行軌跡。

1.1無人機航跡規(guī)劃基本要求

無人機航跡規(guī)劃是從眾多的飛行航跡中選擇滿足一系列約束條件的最優(yōu)航跡，既要盡量減少被敵方摧毀的概率，又要降低自身可能撞地的概率，同時還要滿足無人機各種性能的約束條件。一般來說，無人機航跡規(guī)劃需要考慮下列因素：

（1）突防要求。無人機航跡規(guī)劃首要因素是規(guī)劃航跡的隱蔽性，要使敵方雷達捕獲不到我方無人機，或者雖捕獲卻不能有效攔截。達到突防要求通常采用兩種方式：一是使航跡遠(yuǎn)離威脅源；二是利用地形遮擋降低被敵方探測到的概率。

（2）無人機性能要求。航跡規(guī)劃必須考慮無人機的性能約束。無人機的性能對航跡的約束主要有：①最大轉(zhuǎn)彎角——此參數(shù)限制航跡只能在小于或等于該角度范圍內(nèi)轉(zhuǎn)彎；②最大爬升/俯沖角——此參數(shù)限制航跡在垂直平面內(nèi)上升和下滑的最大角度；③最小航跡段長度——此參數(shù)限制無人機在開始改變飛行姿態(tài)前必須直飛的最短距離；④最低飛行高度——雖然低空飛行可以減少被敵方探測到的概率，但飛得過低往往使與地面相撞的概率增加，所以航跡應(yīng)滿足最小飛行高度限制。

此外，無人機航跡規(guī)劃還必須考慮燃油限制和通信限制等。

（3）實時性要求。如果預(yù)先已掌握規(guī)劃區(qū)域完整、準(zhǔn)確的信息，即可規(guī)劃出一條從起點到終點的最優(yōu)航跡。但現(xiàn)代戰(zhàn)場環(huán)境瞬息萬變，不能保證事先所獲信息不再發(fā)生變化。另外，由于任務(wù)的不確定性，無人機往往要臨時改變飛行任務(wù)。這樣，預(yù)先規(guī)劃的航跡就不能滿足要求，這就要求無人機航跡規(guī)劃必須具有實時在線規(guī)劃功能。

1.2無人機災(zāi)情巡查問題

本文研究的無人機災(zāi)情巡查問題是根據(jù)2017年全國研究生數(shù)學(xué)建模競賽A題中的問題一[11]改編而來的。具體如下：

地震發(fā)生后，需使用無人機攜帶視頻采集裝置巡查A、B、C、D、E等5個重點區(qū)域中心方圓10km（并集記為S）以內(nèi)的災(zāi)情。現(xiàn)有9架無人機均從基地H（110，0）處派出，完成任務(wù)后再回到H，希望在4小時內(nèi)使區(qū)域S內(nèi)海拔3000m以下的地方盡可能多地被巡查到，試設(shè)計每個地區(qū)無人機的最優(yōu)巡查路線。

2無人機災(zāi)情巡查路徑優(yōu)化

2.1災(zāi)情巡查路徑優(yōu)化數(shù)學(xué)模型

若記n=7，dij為兩個地區(qū)i和j之間的距離，xij=0或1（0表示沒有選擇此路，1表示選擇地區(qū)i到j(luò)的路徑），則災(zāi)情巡查路徑優(yōu)化問題即轉(zhuǎn)化為如下路徑規(guī)劃問題模型：

其中，式（2）和式（3）分別表示每個點只有一條邊進去和出來，式（4）表示除起點終點外，各邊不構(gòu)成圈。

2.2多生境遺傳算法

基本遺傳算法的核心是選擇、交叉和變異3大遺傳算子，這3個算子的優(yōu)劣直接決定了算法性能的優(yōu)劣，改進或引入新的遺傳算子已成為遺傳算法研究的重要方向，多生境遺傳算法[12]正是在這一背景下提出的。

多生境遺傳算法在適應(yīng)值共享基礎(chǔ)上，將排擠機制引入到選擇算子和替換過程中。與傳統(tǒng)的輪盤賭選擇方式相比，多生境遺傳算法減小了選擇壓力，提高了搜索過程中的種群多樣性，在一定程度上避免了早熟現(xiàn)象，在許多問題中表現(xiàn)出良好的局部搜索能力[13]。

多生境遺傳算法步驟如下[12]：①產(chǎn)生初始種群，并對其進行適應(yīng)度評價；②對種群進行適應(yīng)度共享調(diào)整；③對種群進行基于排擠機制的選擇；④對種群進行間隔交叉和變異；⑤在種群中進行最相似個體適應(yīng)度最差個體替換；⑥若滿足終止判據(jù)，則算法結(jié)束，否則轉(zhuǎn)步驟②。

3數(shù)值實驗結(jié)果

根據(jù)問題數(shù)據(jù)，利用多生境遺傳算法，可以得出每個區(qū)域內(nèi)1-9號無人機的最優(yōu)巡查路徑，分別見圖1-圖5。

為了評測多生境遺傳算法在提高種群多樣性和避免過早收斂方面的效果，圖6和圖7分別給出了基本遺傳算法（SGA）和多生境遺傳算法（MNGA）的進化曲線。圖6和圖7表明：①MNGA無論在全局收斂性和局部收斂性上均優(yōu)于SGA；②SGA至少在兩個階段出現(xiàn)了過早收斂于局部最優(yōu)解現(xiàn)象，而MNGA則完全避免了早熟現(xiàn)象。因此，在無人機航跡規(guī)劃中采用多生境遺傳算法將獲得比基本遺傳算法更優(yōu)的航跡規(guī)劃。

4結(jié)語

本文針對基本遺傳算法易過早局部收斂和局部搜索能力較弱的缺陷，在無人機航跡規(guī)劃問題中引入多生境遺傳算法。數(shù)值實驗表明，這種算法可在很大程度上克服基本遺傳算法的早熟現(xiàn)象，較好地解決無人機航跡優(yōu)化問題。

必須指出的是，遺傳算法的理論尚未成熟，除了基本遺傳算法外，其收斂性無法得以證明，對算法的改進只能依賴對比實驗，這無疑限制和阻礙了遺傳算法的進一步研究。

參考文獻：

[1]TSOURDOSAS，WHITEB，SHANMUGAVELM.Cooperativepathplanningofunmannedaerialvehicles[M].北京：國防工業(yè)出版社，2013.

[2]PATCHERM，CHANDLERPR.Challengesofautonomouscontrol[J].IEEEControlSystemsMagazine，1998，18（4）：93-97.

[3]DONGJ，VAGNERSJ.ParallelevolutionaryalgorithmsforUAVpathplanning[C].AIAA1stIntelligentSystemsTechnicalConference，Chicago，2004.

[4]ZHANGC，LIL，XUF.Evolutionaryrouteplanningforunmannedairvehicles[J].IEEETransactionsonRobotics，2005（21）：609-620.

[5]NILOLOSI，VALAVANISK.Evolutionaryalgorithmbasedoffline/onlinepathplanningforUAVnavigation[J].IEEETransactiononSystems，ManandCybernetics-PartB，2003（33）：898-912.

[6]WUX，F(xiàn)ENGZ，ZHUJ.Ga-basedpathplanningformultipleUAVs[J].InternationalJournalofControl，2007，80（7）：1180-1185.

[7]李璠，郝應(yīng)光.基于改進混沌遺傳算法的無人機航跡規(guī)劃[J].電光與控制，2012，19（8）：15-19.

[8]魚佳欣，周春來，劉東平.改進遺傳算法的無人機航路規(guī)劃與仿真[J].計算機仿真，2013，30（12）：17-20.

[9]李楠，張建華.基于改進遺傳算法的無人機航路規(guī)劃[J].計算機仿真，2016，33（4）：91-95.

[10]林娜，劉二超.基于改進蟻群算法的無人機動態(tài)航路規(guī)劃[J].計算機測量與控制，2016，24（3）：149-153.

[11]2017全國研究生數(shù)學(xué)建模競賽試題[EB/OL].http：//gmcm.seu.edu.cn/01/49/c12a329/page.htm.

[12]譚艷艷，許峰.基于適應(yīng)值共享的多生境排擠遺傳算法[J].計算機工程與應(yīng)用，2009，45（5）：46-49.

[13]張鑫，許峰.基于多生境遺傳算法的衛(wèi)星軌道計算方法[J].軟件導(dǎo)刊，2017，16（5）：27-30.

（責(zé)任編輯：杜能鋼）