基于改进NSGA-II 算法的多目标无人机路径规划*

樊 娇，雷 涛，董南江，王 锐

（1.陕西科技大学电子信息与人工智能学院，西安 710021；2.国防科技大学系统工程学院，长沙 410073）

0 引言

无人机路径规划通常需要同时优化多个指标，如最小化路径长度、威胁等。多个指标之间通常互相冲突，给优化求解带来了较大的挑战。为有效处理多个优化指标，大多传统方法将多个指标通过加权和方法转换为一个优化指标。这类方法虽然简单直观，但权重设置较难，并且一次优化只能找到一条路径，很难满足决策者的多样化需求。进化多目标优化算法可以同时对多个指标（目标函数）进行优化，找出一组非支配（Pareto 最优）解，在无人机路径规划中得到越来越多的应用。

Ganguli 等人在无人机机翼的设计中采用NSGA-II 算法对空气动力学和结构两个目标函数进行优化，在冲突目标间进行折衷，为设计人员提供多种设计可能性。Conesamunoz 等人在群机器人从事农业任务的路径规划中，考虑到既要使成本最小化又要覆盖整个领域，采用了NSGA-II 算法对时间成本和费用成本两个目标进行优化，并在异质条件下进行大量实验得到最佳路径计划。周德云等人采用改进的CO-NSGA-II 算法，对多无人机的多个性能指标同时进行优化，将各无人机的航迹规划看作一个子种群，在子种群内部进行独立的非支配排序，种群间采用协同进化策略进行合作，并用时间空间协同系数代替NSGA-II 中的拥挤度，有效地实现了多无人机的协同航迹规划。王瑛等人在三维多目标航迹规划中以航迹最短、角度改变量最小等4 个代价作为规划目标，引入飞行规则约束，采用NSGA-II 算法进行模型求解，得到了多组具有不同属性的可行航迹。

针对中大型固定翼无人机路径规划问题，结合进化多目标优化算法的优势，本文提出一种基于改进NSGA-II 算法的多目标无人机路径规划方法。

1 进化多目标优化

1.1 多目标优化

多目标优化是指在一定约束条件下，对多个指标（目标函数）同时进行优化，求得一组Pareto最优解。通常，一个多目标优化问题中的各个目标是相互冲突的，即改善一个目标的性能会导致其他目标的性能降低。典型的多目标优化问题，如式（1）所述：

定义2：Pareto 最优解。不被任何一个解支配的解，称为Pareto 最优解。

定义3：Pareto 最优解集。决策空间中Pareto 最优解的集合。

定义4：Pareto 前沿。所有最优解对应的目标函数构成Pareto 前沿，也即Pareto 最优集在目标空间的像。

1.2 多目标优化算法NSGA-II

NSGA-II 是当前应用最为广泛的一个进化多目标优化算法。它的基本思想如下：首先采用非支配排序，即基于Pareto 支配的关系，对个体进行分层排序；然后引入拥挤距离保持种群个体的多样性，即同一非支配层中的个体，拥挤距离越大越好；最后，算法通过（）的精英保留策略，提高优化搜索效率，即个子代种群个体与个父代种群个体通过竞争，选择出个较好的个体作为下一代的父代种群。

2 环境建模

无人机路径规划的基础是环境建模，通常包括地形建模、障碍物及威胁区建模等。

地形建模中，在不影响路径规划实用性的前提下，假设无人机的飞行高度、速度始终保持一致，将三维路径规划简化为二维环境。

威胁区一般指雷达探测区域、导弹打击区域、禁飞区区域等，这里主要考虑因信号干扰带来的威胁。为简化起见，将威胁简化为圆形区域，具体模型表述如下：

用上述方法对航迹规划空间进行建模，结果如图1 所示。

图1 路径规划环境建模示意图

START和GOAL 分别为起始点和目标点，圆环区域为信号干扰威胁区。其中，实线区域内部为威胁重灾区，属于硬约束，要求无人机必须绕开此类区域；虚线和实线之间的部分为威胁干扰波及区域，属于软约束，无人机可以通过此类区域，但是会面临一定的威胁。假定威胁程度与无人机靠近圆心的距离呈反比，无人机距离威胁中心越远，所受干扰越弱；无人机距离威胁中心越近，所受干扰越强。

3 无人机路径规划多目标优化模型

3.1 路径代价模型

路径代价的计算是无人机路径规划的核心。通常路径代价包括路径长度、路径威胁等，两个指标在多数情况下是相互冲突的，即路径短的往往受威胁较大，受威胁小的路径又较长，传统路径规划通过加权法将多个目标转换为单个目标进行优化，为了避免加权法中权重设置的难题，亦可采用进化多目标优化算法，先找出一组Pareto 最优的路径，然后根据需要（或决策者的偏好信息）选择其中的某一条路径。因此，本文以路径长度和路径威胁两个目标作为路径评价的标准。

3.1.1 路径长度代价

路径长度是多个航迹段的距离总和，一般情况下受无人机装载油量的限制，为了减少油耗、节省时间，要求路径长度尽可能短。路径长度代价如式（2）：

3.1.2 路径威胁代价

威胁代价需要综合考虑雷达威胁、导弹威胁、信号干扰、禁飞区等约束条件。为简化处理，本文将各类威胁表述为圆形区域，并设置相关的威胁干扰区和重灾区。威胁区域主要用信号干扰威胁程度来衡量，如式（4）：

其中，var 是航迹点数，是威胁区个数，r是第个威胁区的半径，dis表示每条路径中第个航迹点到第个威胁区的距离。路径总威胁值等于该条路径中各航迹点威胁的总和，无人机在当前航迹点的威胁值与无人机和威胁源之间的距离成反比。距离越小，所受威胁干扰越大。当威胁干扰大于给定值时，则需要增加其路径代价，以有效避开硬威胁区域。

3.2 无人机路径规划模型

除了考虑路径长度和威胁值，在路径规划中，还需考虑一些约束条件，包括最小航迹段长度约束、最大航迹长度约束和最大拐弯角约束。

目标函数的构造如式（5）：

气焰赫赫的风云八虎，不到一年，三虎死于非命，均被烈焰焚烧而死，死状极惨。一般人提及此事，皆心有余悸；苟活于世的三虎，以及他们的后台德公公，此后寝无眠，食无味，惶惶不可终日。

4 基于改进NSGA-II 算法的无人机路径规划

4.1 路径编码

无人机的路径可以看作是一系列坐标点连接成的线段，本文采用实数编码方式对路径进行编码，路径以坐标点的形式储存，具体编码结构如下：

4.2 种群初始化

随机生成条路径作为初始化种群。具体每条路径中的路径点，即坐标和坐标值随机初始化生成。为便于计算，将路径点用元胞存储。一个元胞内所有的路径点构成一个路径个体，其中起始点坐标和目标点坐标固定，中间路径点随机生成。

4.3 进化算子

下面阐述无人机路径规划算法中进化算子的设计。

1）环境选择算子：选择算子建立在种群中适应度的评估上，采用锦标赛选择法，每次从种群中随机选择2 个个体，对每个个体的适应度值进行比较，选出适应度值高的个体进入下一代，重复选择至下一代种群达到原来的种群规模。

图2 交叉操作

3）变异算子：从交叉后的种群中随机选择一个个体，以的概率对中间航迹点进行高斯变异操作，用均值为交叉后的航迹点坐标值、方差为10的正态分布的随机数来替换交叉后的航迹点，以搜索到原个体附近的某个局部区域。然后引入最大拐弯角约束，对超过拐弯角最大值的路径进行平滑。这种变异方法结合最大拐弯角约束，能够有效避免航迹点发生突变。

4）扰动算子：对航迹点进行微小的扰动，采用高斯扰动的方法，用均值为变异后的航迹点坐标值、方差为0.5 的正态分布的随机数数组来替换变异后的航迹点，并对扰动后的航迹点坐标进行越界处理，使产生的航迹能够在预定的范围内。

5）增加删除算子：对每一个航迹点，比较其与下一航迹点连成的航迹段到威胁区域中心的距离与威胁区半径的大小。如图3（a）～图3（c）所示：＞，则航迹段不受威胁；＜且两个航迹点均在威胁区外，则航迹段不受威胁；＜且过威胁区，则找两点与威胁区的切点node1、node2（如图3（d）所示），并将这两点加入路径中；其他情况下，如第个路径点在威胁区外，第+1 个路径点在威胁区内，则寻找下一个在威胁区外的路径点，并删去第+1 个路径点。

图3 距离与威胁区半径的大小比较图

6）平滑算子：无人机改变航向的过程中需要相应时间和转弯角度的限制，转弯角度太小，航迹实际无法飞行，为了使无人机实际可飞并且与威胁保持一定距离，采用3 次样条插值法，对路径中的拐角进行平滑，使其产生平滑轨迹。

4.4 个体非支配排序

采用NSGA-II 算法中经典的非支配分层策略对个体进行排序。首先，找出种群中位于Pareto 前沿第1 层的个体，即不被任何其他个体Pareto 支配的个体；其次去除位于第1 层级的个体，在剩余的个体中采用同样的方法，找出不被其他任何个体Pareto 支配的个体，这些个体记为Pareto 第2 层；以此类推，将所有个体分配至对应的非支配层。位于Pareto 非支配层（即第1 层）的个体为当前最优解集。

4.5 拥挤距离

为保证种群的多样性，针对同一非支配层的个体，算法更倾向于选择密度较大的个体。为了提高无人机路径的多样性，本文使用改进的拥挤距离算子来衡量个体密度。改进的算子同时考虑个体在决策空间和目标空间个体的拥挤度，以二者的平均值作为个体最终的拥挤距离。

目标空间中个体的拥挤距离计算如式（6）所示：

决策空间中个体的拥挤距离计算如下：

1）按照航迹点顺序，找出路径上每个点到路径的最短距离（a，b），求和并除以路径的总点数作为路径到路径的距离（，）。计算公式如下：

2）按照1）的方法求得所有路径间的距离并得到一个距离矩阵。

3）根据该距离矩阵及非支配排序中得到的排序等级计算每个个体的距离密度。

最后将目标空间个体的拥挤距离和决策空间个体的距离密度的平均值作为最终的拥挤距离。

4.6 算法流程

本文所提出的基于改进NSGA-II 算法的步骤如下：

1）初始化参数，随机生成个个体作为初始父代种群；

2）计算路径规划模型的目标函数值；

3）执行选择、交叉、变异及增加删除算子操作，生成新的个子代个体；

4）计算新生成个体种群的目标值；

5）合并父代和子代种群；

6）对合并后的种群进行非支配排序，并计算个体的拥挤距离；

7）根据非支配排序和拥挤距离，在合并种群中选出较好的个体作为新的父代种群；

8）判断算法终止条件，若未达到最大进化代数maxgen 则跳转3），否则算法运行结束，输出最优结果。无人机路径规划的改进NSGA-II 算法流程图，如图4 所示。

图4 无人机路径规划的改进NSGA-II 算法流程图

5 仿真算例

假定在某次侦察行动中，要求多架无人机从同一区域起飞，前往某一指定目的地。将飞行区域简化为50 km×50 km 的二维空间，假设在该区域存在7 个信号干扰威胁源，每个威胁的波及区域半径是绝对威胁半径的2 倍，如表1 所示。无人机的最大航迹长度为500 km，最小航迹段为0.2 km，最大拐弯角不超过60°。

表1 信号干扰威胁参数

设定种群大小为80，单条路径由17 点组成（起点、终点和15 个中间航迹点），最大进化代数为60；交叉概率取0.85，变异概率取0.1。采用改进的NSGA-II 算法求解模型，为了克服随机性带来的影响，将算法在所规划的二维环境下运行20 次，每次运行60 代，从仿真得到的多组结果中选取最具有代表性的路径作为Pareto 解集的逼近解集。结果如图5 所示。

图5 基于改进NSGA-II 算法的Pareto 最优路径效果图

从图5 的仿真结果可以看出，改进的NSGA-II算法找到了一组具有多样性的Pareto 最优路径，即有些路径虽然长，但是路过的威胁区域少；有些虽然路径短，但是需经过威胁区域。不存在路径又短且受威胁又小的绝对最优解。如下页表2 所示，路径7 的飞行距离最短，但受威胁程度最大；路径5的威胁程度最小，但其飞行距离却最长。同时，所找到的路径均有效避开了威胁重灾区。

具体各条路径的目标函数值（信息）如表2 所示。

表2 路径属性

为进一步验证所提算法的有效性，本文实验对比改进的NSGA-II、NSGA-II和基本GA 算法。其中，GA 算法采用加权和的方法处理两个目标值，3个算法在同一环境下分别独立运行20 次。图6和图7 分别给出了基于NSGA-II和GA 算法的求解结果。算法运行时间如表3 所示。

表3 3 种算法的平均耗时（运行20 次）对比结果

图7 基于GA 算法的最优路径效果图

对比3 种进化算法的运行结果发现，基于GA算法产生的路径平均长度为77.41，耗时约31.58，虽然平均耗时比改进的NSGA-II 算法短，但是仅能获取一条路径。NSGA-II 算法和改进的NSGA-II 算法均能产生多条非支配路径，但是通过对比图5和图6 可以发现，NSGA-II 算法找到的解多样性较差，路径呈明显的簇状分布。而改进的NSGA-II 算法产生的路径更分散、多样性更高，更有利于辅助决策者根据实际需求选择合适路径。

图6 基于NSGA-II 算法的最优路径效果图

6 结论

路径规划是实现无人机自主化、智能化的关键技术之一，本文以路径长度和威胁程度为优化目标，构建了无人机路径规划的两目标优化模型。为有效求解该模型，提出了改进的NSGA-II 算法，该方法在传统NSGA-II 的基础上，引入了适用于路径规划问题的交叉、变异以及增加删除算子，引入了混合目标空间和决策空间信息的新型拥挤距离算子，并通过最大拐弯角约束缓解变异操作带来的航路突变问题。仿真算例表明，改进的NSGA-II 算法能有效找出一组多样性较好的Pareto 最优路径，其求解效果明显优于传统的NSGA-II 算法。值得指出的是，本文仅考虑了二维环境下的静态路径规划，尚没有考虑多无人机之间的协同。今后，将在此基础上进一步研究三维空间下的静态、动态多无人机的路径规划，并充分考虑环境的不确定性等因素对路径规划带来的影响。