基于多生境遗传算法的无人机航迹规划

吕文鹏 许峰

摘要：基本遗传算法易早熟和局部搜索能力欠佳，为此，将多生境遗传算法应用于无人机灾情巡查路径优化。基本思想是：在适应值共享基础上，在选择算子中引入排挤机制，在交叉算子中采用间隔交叉，并使用最相似个体中适应度最差的个体替换技术。数值实验表明，多生境遗传算法可以大大提高种群的多样性，在很大程度上避免早熟，获得比基本遗传算法更优的巡查路径。

关键词：无人机；航迹规划；多生境遗传算法；局部收敛性

DOI：10.11907/rjdk.172886

中图分类号：TP319

文献标识码：A文章编号：1672-7800（2018）007-0166-03

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

KeyWords：UAV；pathplanning；multi-nichegeneticalgorithm；localconvergence

0引言

无人机已广泛应用于军事侦察与打击、城市规划、资源调查、灾情巡查等领域。无人机任务规划中最重要的是航迹规划，即在一定约束条件下，寻找从起始点到目标点的最优路径。合理的航迹规划不仅节省资源，提高飞行效率，还可有效规避威胁，提高生存概率。

常用无人机航迹规划方法有随机搜索法、Voronoi图法和优化方法[1]。无人机航迹规划往往包含复杂约束大规模优化问题，主流方法是启发式智能优化算法，如蚁群算法、粒子群算法、模拟退火算法、遗传算法等。早在1998年，Patcher[2]就讨论了路径规划问题中的关键优化技术及其复杂性；Dong、Zheng和Nikolos等系统研究了路径规划中进化算法的优化原理[3-5]；Wu[6]最早将遗传算法应用于航行器的路径規划问题。目前，无人机航迹规划优化工作多集中于对已有启发式智能优化算法的改进研究[7-10]。

基本遗传算法（SGA）对搜索空间和目标函数要求不高，适用面广，鲁棒性强，具有隐并行性，且全局搜索能力较强。但在求解复杂优化问题时，基本遗传算法经常表现出易陷于局部最优解和局部寻优精度不高的缺陷。为此，本文将多生境遗传算法（MNGA）应用于无人机航迹规划问题，并根据数据实验对该算法进行了性能测试。

1航迹规划问题

无人机航迹规划通常指在综合考虑无人机的机动性能、碰地概率、突防概率、油耗、威胁和飞行时间约束等各种因素下，找到一条从起始点到目标点的最优飞行轨迹。

1.1无人机航迹规划基本要求

无人机航迹规划是从众多的飞行航迹中选择满足一系列约束条件的最优航迹，既要尽量减少被敌方摧毁的概率，又要降低自身可能撞地的概率，同时还要满足无人机各种性能的约束条件。一般来说，无人机航迹规划需要考虑下列因素：

（1）突防要求。无人机航迹规划首要因素是规划航迹的隐蔽性，要使敌方雷达捕获不到我方无人机，或者虽捕获却不能有效拦截。达到突防要求通常采用两种方式：一是使航迹远离威胁源；二是利用地形遮挡降低被敌方探测到的概率。

（2）无人机性能要求。航迹规划必须考虑无人机的性能约束。无人机的性能对航迹的约束主要有：①最大转弯角——此参数限制航迹只能在小于或等于该角度范围内转弯；②最大爬升/俯冲角——此参数限制航迹在垂直平面内上升和下滑的最大角度；③最小航迹段长度——此参数限制无人机在开始改变飞行姿态前必须直飞的最短距离；④最低飞行高度——虽然低空飞行可以减少被敌方探测到的概率，但飞得过低往往使与地面相撞的概率增加，所以航迹应满足最小飞行高度限制。

此外，无人机航迹规划还必须考虑燃油限制和通信限制等。

（3）实时性要求。如果预先已掌握规划区域完整、准确的信息，即可规划出一条从起点到终点的最优航迹。但现代战场环境瞬息万变，不能保证事先所获信息不再发生变化。另外，由于任务的不确定性，无人机往往要临时改变飞行任务。这样，预先规划的航迹就不能满足要求，这就要求无人机航迹规划必须具有实时在线规划功能。

1.2无人机灾情巡查问题

本文研究的无人机灾情巡查问题是根据2017年全国研究生数学建模竞赛A题中的问题一[11]改编而来的。具体如下：

地震发生后，需使用无人机携带视频采集装置巡查A、B、C、D、E等5个重点区域中心方圆10km（并集记为S）以内的灾情。现有9架无人机均从基地H（110，0）处派出，完成任务后再回到H，希望在4小时内使区域S内海拔3000m以下的地方尽可能多地被巡查到，试设计每个地区无人机的最优巡查路线。

2无人机灾情巡查路径优化

2.1灾情巡查路径优化数学模型

若记n=7，dij为两个地区i和j之间的距离，xij=0或1（0表示没有选择此路，1表示选择地区i到j的路径），则灾情巡查路径优化问题即转化为如下路径规划问题模型：

其中，式（2）和式（3）分别表示每个点只有一条边进去和出来，式（4）表示除起点终点外，各边不构成圈。

2.2多生境遗传算法

基本遗传算法的核心是选择、交叉和变异3大遗传算子，这3个算子的优劣直接决定了算法性能的优劣，改进或引入新的遗传算子已成为遗传算法研究的重要方向，多生境遗传算法[12]正是在这一背景下提出的。

多生境遗传算法在适应值共享基础上，将排挤机制引入到选择算子和替换过程中。与传统的轮盘赌选择方式相比，多生境遗传算法减小了选择压力，提高了搜索过程中的种群多样性，在一定程度上避免了早熟现象，在许多问题中表现出良好的局部搜索能力[13]。

多生境遗传算法步骤如下[12]：①产生初始种群，并对其进行适应度评价；②对种群进行适应度共享调整；③对种群进行基于排挤机制的选择；④对种群进行间隔交叉和变异；⑤在种群中进行最相似个体适应度最差个体替换；⑥若满足终止判据，则算法结束，否则转步骤②。

3数值实验结果

根据问题数据，利用多生境遗传算法，可以得出每个区域内1-9号无人机的最优巡查路径，分别见图1-图5。

为了评测多生境遗传算法在提高种群多样性和避免过早收敛方面的效果，图6和图7分别给出了基本遗传算法（SGA）和多生境遗传算法（MNGA）的进化曲线。图6和图7表明：①MNGA无论在全局收敛性和局部收敛性上均优于SGA；②SGA至少在两个阶段出现了过早收敛于局部最优解现象，而MNGA则完全避免了早熟现象。因此，在无人机航迹规划中采用多生境遗传算法将获得比基本遗传算法更优的航迹规划。

4结语

本文针对基本遗传算法易过早局部收敛和局部搜索能力较弱的缺陷，在无人机航迹规划问题中引入多生境遗传算法。数值实验表明，这种算法可在很大程度上克服基本遗传算法的早熟现象，较好地解决无人机航迹优化问题。

必须指出的是，遗传算法的理论尚未成熟，除了基本遗传算法外，其收敛性无法得以证明，对算法的改进只能依赖对比实验，这无疑限制和阻碍了遗传算法的进一步研究。

参考文献：

[1]TSOURDOSAS，WHITEB，SHANMUGAVELM.Cooperativepathplanningofunmannedaerialvehicles[M].北京：国防工业出版社，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，FENGZ，ZHUJ.Ga-basedpathplanningformultipleUAVs[J].InternationalJournalofControl，2007，80（7）：1180-1185.

[7]李璠，郝應光.基于改进混沌遗传算法的无人机航迹规划[J].电光与控制，2012，19（8）：15-19.

[8]鱼佳欣，周春来，刘东平.改进遗传算法的无人机航路规划与仿真[J].计算机仿真，2013，30（12）：17-20.

[9]李楠，张建华.基于改进遗传算法的无人机航路规划[J].计算机仿真，2016，33（4）：91-95.

[10]林娜，刘二超.基于改进蚁群算法的无人机动态航路规划[J].计算机测量与控制，2016，24（3）：149-153.

[11]2017全国研究生数学建模竞赛试题[EB/OL].http：//gmcm.seu.edu.cn/01/49/c12a329/page.htm.

[12]谭艳艳，许峰.基于适应值共享的多生境排挤遗传算法[J].计算机工程与应用，2009，45（5）：46-49.

[13]张鑫，许峰.基于多生境遗传算法的卫星轨道计算方法[J].软件导刊，2017，16（5）：27-30.

（责任编辑：杜能钢）