呂文鵬 許峰

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

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

DOI：10.11907/rjdk.172886

中圖分類號(hào)：TP319

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

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

KeyWords：UAV；pathplanning；multi-nichegeneticalgorithm；localconvergence

0引言

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

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

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

1航跡規(guī)劃問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2多生境遺傳算法

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

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

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

3數(shù)值實(shí)驗(yàn)結(jié)果

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

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

4結(jié)語

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

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

參考文獻(xiàn)：

[1]TSOURDOSAS，WHITEB，SHANMUGAVELM.Cooperativepathplanningofunmannedaerialvehicles[M].北京：國(guó)防工業(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)光.基于改進(jìn)混沌遺傳算法的無人機(jī)航跡規(guī)劃[J].電光與控制，2012，19（8）：15-19.

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

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

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

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

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

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

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