基于遗传算法的无人机航路规划研究

曹良秋 吴立巍

摘 要：针对无人机的多约束条件，将遗传算法和具体的航路规划问题相结合，把无人机的约束条件融合于算法中，设计了合理的染色体数据结构、遗传算子和航路评价函数。仿真分析表明，该算法能够根据任务需求为无人机规划出满足生存概率和突防概率的飞行航路。

关键词：无人机；遗传算法；航路规划；评价函数

中图分类号：V249.3 文献标识码：A 文章编号：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

無人机在现代战争中的地位举足轻重，无人机任务规划系统核心技术之一则是航路规划，通过合理规划航路，可以使无人机有效规避威胁，提高生存概率和任务执行效率。无人机航路规划是指在一定的约束条件下，在分布了一些威胁区域的规划空间中，通过规划寻找让从起始点到目标点的航迹优化问题，使无人机具有最大生存率。

遗传算法利用简单的编码技术和繁殖机制，建立起一个迭代过程，从而实现对问题的求解。遗传算法具有很强的并行性和鲁棒性，不受搜索空间的限制性假设的约束，不要求搜索空间连续，通过离散化搜索空间，从而大大缩小了搜索空间，提高搜索效率。

鉴于无人机航迹规划和遗传算法的特点，基于遗传算法的航迹规划具有很强的实用意义和研究价值。本文将遗传算法的思想和无人机航路规划的实际应用相结合，通过采用实数基因编码方式和特定的进化算子，能够在规划环境中为无人机在起飞前规划出品质较高的航路。

1 航路规划空间

无人机航路规划的目的是利用地形和敌情等威胁源、目标函数的分析应用，规划出满足任务规划要求的相对最优的轨迹，本质是多个约束条件下最优或近似最优可行解的求解问题，其系统框图如图1所示。航路规划主要步骤是：

分析约束条件，对无人机飞行环境进行分析和建模，将无人机执行任务的区域的地形、威胁、气候以及无人机的性能参数等限制条件表示成符号信息。

选择规划算法，按目标函数对无人机的航路进行规划，在限制条件下生成无人机的参考航路。

1.1 规划空间建模

由于无人机巡航飞行时的高度不变，因此可以把三维航路规划问题转化为在某一定高平面下的二维航路规划问题。一般来说，可以将各种威胁简化成具有一定作用范围的圆柱或圆锥几何体的组合，其在二维平面的投影为具有一定半径的圆形区域，如图2所示。

1.2 航路评价建模

航路评价函数用于计算航路的适应度，是判断航路优劣的重要标准以及引导搜索算法向最优解逼近的关键。评估航路代价需要同时考虑航路的各种约束条件。

1.2.1 航路约束条件

2 基于遗传算法的航路规划

遗传算法设定一个种群，该种群是由经过基因编码的一定数目的个体组成，每个个体就是带有特征的染色体。染色体是由基因序列组成，每条染色体代表着问题的一个可能解。染色体根据问题域中的适应度大小选择个体，并借助遗传算子以交叉、变异的方式不停地进化。这个过程就像自然进化一样，适应度高的个体更容易被选中，因此种群的整体适应度将不断提高。最后，得到的适应度最高的染色体所代表的解就是问题的最优解。

2.1 染色体编码

染色体编码是应用遗传算法进行航迹规划的前提。编码方法决定了个体的染色体排列形式，还决定了个体从搜索空间的基因类型变换到解空间的表现类型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。编码方式可以是二进制数、浮点数、整数、字母或矩阵等的集合。已有研究表明，与问题的原始形式越接近，表现形式越有效，越能生成优解。

本文采用变长度的实值基因编码方式，如图4所示。染色体的每个基因除了包含航路点的位置信息外（x，y），还包含状态变量b，状态变量包括了该节点航路段是否可行的标志。

初始种群可以随机生成，染色体的最大长度（航路结点的最大数目）可作为预先确定的参数。在编码时应注意所有航路的初始和终点位置的坐标都是相同的，分别代表无人机的起始点和目标点。

2.2 航路评价函数

在计算一条航路的适应度时应综合考虑安全性（威胁代价）和经济性（油料代价）的权重，式（7）中u表示威胁代价的权重系数，范围在0～1之间，反映了设计者对威胁程度与油料代价选择的倾向。当u接近1时表示应优先避免通过威胁区，保证无人机的安全；当u接近0时意味着航路尽可能短，威胁代价为次要因素。

2.3 遗传操作

遗传算法包括三个操作：选择、交叉和变异。

（1）选择操作：是指以一定概率从种群中选择若干个体的操作，本文选择的算法是比例选择，也叫做轮盘赌选择，其基本思想是个体被选中并遗传到下一代群体中的概率与其适应度大小成正比。具体执行过程是：

a.计算种群所有个体的适应度总和；

b.计算每个个体被选中的概率，即每个个体相对适应度总和的比例；

c.使用模拟轮盘赌操作（即0到1之间的随机数）确定各个个体被选中的次数。

（2）交叉操作：将两条父代航路随机分割成两部分，将第一条航路的前半部分和第二条航路的后半部分组合，其余的二个部分组合，生成两个新的子代个体。交叉的两条航路长度可以不同。

（3）变异操作：以一定的变异概率随机指定航路上某一个或几个节点作变异运算，在这个过程中对最优的个体不做变异操作。本文针对航路规划的实际问题设计了四种变异算子，分别是扰动算子、删除算子、插入算子和平滑算子。

a.扰动算子：对航路节点中的一个节点坐标随机进行改变。如果原航路是可行的，则在可行范围内加以较小扰动，以提高航路的适应值；如果原航路是不可行的，则可适当增大扰动幅度，以期获得可行的航路；

b.删除算子：删除航路的一个中间节点。如果原航路是不可行的，该中间节点可以随机选择；如果原航路是可行的，则节点的选择需要基于某些启发式信息。

c.插入算子：随机在两个相邻的航路节点中间插入一个新的航路节点。提高穿越威胁区域航路的可行性。

d.平滑算子：该算子在所选航路点相邻两个航路段上各插入一个随机选择的航路节点，然后删除开始选择的节点。如果某节点处航路转弯角越大，选择它进行平滑的概率越大。该算子只作用于不可行航路。

2.4 航路规划步骤

（1）种群初始化。按照相应的编码方案随机生成n条航路组成的初始种群P（0），设置进化代数计数器t=0，并设置最大进化代数；

（2）个体评价。依据不同的问题，计算群体P（t）中每条航路的适应度值；

（3）遗传操作。将选择、交叉及变异算子作用于种群。种群P（t）经过遗传操作之后得到下一代种群P（t+1）。

（4）进化结束。如果进化代数小于最大进化代数，转到步骤2，否则进化结束，从最终的种群中挑選出最优解。

（5）将最优解解码，得到最优航路。

3 仿真分析实例

运用matlab7.1对该算法进行仿真。设无人机飞行区域100km×100km，飞行任务区内有六个威胁区，用“*”代表威胁源位置，圆圈范围内代表威胁区域。无人机起始点为（0，50），目标点为（100，50）。

遗传算法参数设置为初始种群大小P=60，交叉概率Pc=0.7，变异概率Pm=0.1，最大进化代数T=200，权重系数u=0.5。进化结束条件为达到最大进化代数或该代种群适应度均方差小于0.001。

图8显示了遗传算法进行航路规划的几个不同的进化阶段。图9显示了航路代价随着进化过程的变化情况，在60代后收敛到最优结果附近，在进化到137代时得到了最优的航路，进化过程结束。

4 结束语

文章根据无人机定高飞行的特点，建立了合适的环境模型。针对无人机的多约束条件，通过对遗传算法的研究，结合航路规划的具体问题，将无人机的约束条件融合于算法中，设计了合理的染色体编码、遗传算子和航路评价函数。仿真分析表明，该算法能够根据任务需求为无人机规划出满足生存概率和突防概率的飞行航路。

参考文献：

[1]洪森.无人飞行器航迹规划的研究[D].南京：南京航空航天大学，2011.

[2]胡中华.基于智能优化算法的无人机航迹规划若干关键技术研究[D].南京：南京航空航天大学，2011.

[3]辛贵州.无人飞行器航迹规划算法研究[D].哈尔滨：哈尔滨工程大学，2010.

[4]董世建.复杂约束条件下航迹规划方法研究[D].北京：北京理工大学，2016.

[5]俞琪.基于遗传算法的快速航迹规划方法研究[D].武汉：华中科技大学，2011.

[6]王睿，周洲，沈延航.高空长航时无人机航迹优化研究[J].飞行力学，2006，24（3）：37-39.

[7]郑锐，冯振明，陆明泉.基于遗传算法的无人机航路规划优化研究[J].计算机仿真，2011，28（6）：88-91.

[7]蒙波.无人机航迹规划与任务分析的仿真与实现[D].成都：电子科技大学，2010.

[8]李子杰，刘湘伟，汤博，等.基于进化算法的雷达对抗侦察无人机航路规划[J].火力与指挥控制，201，38（6）：51-54.