郭拉克，李文生，韩帅涛

(中国洛阳电子装备试验中心，河南洛阳 471000)

0 引言

无人机航路规划是根据任务目标，确定一条合理的最优航路，该航路满足无人机性能约束、任务要求和环境约束，并使无人机任务效能达到最优。可行航路的优劣评估受多项指标因素的影响，传统的思路是通过加权将多项指标综合成单指标进行处理，但该方法存在指标间量纲不一致、过分依赖权重、主观性强、优度进展不可控等固有缺陷。多目标优化 (向量优化)由于可以实现多个指标的共同优化，近年来受到学者们的广泛关注，并产生了大量的研究成果，在多个领域得到了广泛的应用［1-5］。文献 ［6］提出了一种适用于多目标优化的非支配排序进化算法NSGA，文献［7］提出了其改进算法NSGA－II，改进了原来算法的不足之处，引入了精英策略，并提高了算法的运算速度和鲁棒性，同时保证了非劣最优解的均匀分布。文献［8］提出了一种新的排序和筛选策略，通过循环计算的删除当前拥挤距离最小的解，提高多目标进化的收敛性和多样性。本文采用多目标优化思想，建立了无人机航路规划的多目标优化模型，并给出了基于NSGA－Ⅱ的模型求解方法，为无人机航路规划研究提供了新的思路和方法。

1 多目标优化问题模型

多目标优化问题，一般可以定义为在一定约束条件下，对多个目标函数共同进行优化的最优问题。当效能受多个目标影响时，多个目标之间往往会出现冲突，即不存在使所有目标同时达到最优的解。一个目标性能的改善，往往以降低其他一个或多个目标性能为代价。以最小化问题为例，可以描述为如下标准形式［4］:

其中:fi(x)为目标函数;x为待优化的决策变量;gi(x)≤0为变量x的线性不等式约束。满足约束条件的决策变量称为可行解或可行个体，所有可能的可行解的集合称为决策空间，决策空间中所有可行解的像 (目标函数向量)的集合称为目标空间。

定义1:如果可行个体p至少有一个目标函数比可行个体q的好，而且个体p的所有目标都不比个体q的差，即:

那么称个体p支配个体 q，或者称个体 q受个体 p支配，记为p＜q，反之记为p>q。

定义2:当前决策集中，对于某个可行个体 p，如果不存在可行个体q，使得p>q，则称可行个体p为多目标优化问题的非支配解或非劣解，又称为Pareto最优解。当前决策集中的所有Pareto最优解构成Pareto前端，简称前端。

定义3:如果某个可行个体在整个决策空间范围内不受任何其他可行个体支配，则称该个体为全局Pareto最优解。所有全局Pareto最优解构成全局Pareto前端。

多目标优化的目标就是寻找这样一组可行解，它包含尽可能多的非劣解，解集中的个体尽可能逼近问题的全局Pareto前端，且个体分布尽可能均匀。

2 无人机多目标航路规划模型

假设无人机航路规划过程以航路长度、航路安全性、航路隐蔽性为效能目标函数。包括起始点和目标点在内共有N个航路点，分别记为P(n)，n={1，2，…，N}，一条完整的航路记为P。则:

航路总长度:

其中:dis为空间两点间的欧氏距离。

航路安全性以无人机受敌方防御火力的威胁程度衡量:

其中:thri为第i个火力威胁在空间点的威胁度，i={1，2…M}，M 为战场中威胁总数［9］。

其中:dmaxi为第i个火力威胁的最大威胁半径，dmaxi为绝对威胁半径 (该距离内威胁恒定为最大值)，θ为视线仰角，θmini为攻击下界角。

航路隐蔽性以航路点的平均高度衡量:

其中:Pnz为第n个航路点的飞行高度。

航路约束条件包括最小飞行高度约束、最大拐弯角约束和最大爬升/俯冲角约束。

综上，无人机多目标航路规划问题可以描述为:

其中:P(n)·h为第n个航路点处的地形高度，θpn，φpn为该航路点处的拐弯角和爬升/俯冲角，safeh，θmax，ɸmin，ɸmax分别为无人机最小安全离地高度、最大拐弯角和最大爬升和最大俯冲角。

3 无人机多目标航路规划的NSGA－Ⅱ算法

NSGA－Ⅱ算法具有运行速度快，收敛性好，解集分布均匀，鲁棒性强等优点，是目前应用最广的多目标进化算法 (MOEA)，该算法包括编码设计、种群初始化、精英选择、交叉操作、变异操作和快速非支配排序几个步骤。本文将该算法应用于无人机多目标航路规划问题的求解，具体步骤如下［5］:

3.1 编码设计

无人机航路点在空间中表现为离散点，因此采用正整数编码。首先将战场空间栅格化，得到NX×NY×NZ的搜索空间。则代表一条航路的染色体为P=(P1，P2…PN)，N为航路点总数。Pi=(Pix，Piy，Piz)为该航路第i个航路点坐标。其中Pix∈ {1，2…NX}，Piy∈ {1，2…NY}，Piz∈{1，2…NZ}。

3.2 种群初始化

初始化所有染色体的首个航路点为起始点，末位航路点为目标点，此两点不参与交叉变异操作。约束范围内随机产生其余航路点。NSGA－Ⅱ算法中每个染色体P都有两个重要属性:非支配排序Prank和拥挤度Pd。前者表示染色体所属的非支配层级，层级数小的染色体相对于其他层级染色体，处于非支配地位，因而更优秀。后者用于表示目标空间内同一非支配层级内染色体周围个体的密度，拥挤度越大，染色体代表性越强，染色体更优秀。染色体的非支配排序Prank和拥挤度Pd均通过快速非支配排序获得，因此对于初始种群，参与选择操作前，需要额外进行一次快速非支配排序。

3.3 精英选择

精英策略就是保留父代中的优良个体进入子代，防止已获得的Pareto最优解丢失，并逐渐提高种群所代表的解的质量。NSGA－Ⅱ算法采用锦标赛机制产选择出与父代种群大小相同的新群体，用于进行后续的遗传操作。从父代种群中随机选择任意两个染色体p和q。首先比较其非支配排序，如果prank＜qrank，则染色体p胜出，反之染色体q胜出;如果prank=qrank，则比较其拥挤度，如果pd＞qd，则染色体p胜出，反之染色体q胜出，胜出染色体加入新群体。反复从父代种群选择个体进行锦标赛，直至满足新种群规模。

3.4 交叉操作

对通过选择的群体，进行概率为Pc的交叉操作。从通过选择的群体中随机选择任意两个染色体进行配对，随机设定交叉位置n，使配对个体交换序号n及其以后的航路点编码信息。为防止交叉位置航路发生突变，需要检测交叉处航路点的最大拐弯角约束和最大爬升/俯冲角约束，如果不满足约束条件，则进行平滑处理:

如果原始染色体为可行解，则变异操作后染色体亦可保证为可行解。

3.5 变异操作

对通过交叉的群体，进行概率为Pm的变异操作。从通过交叉的群体中随机选择任意染色体进行变异，随机设定变异位置n，对变异个体序号为n的航路点位置进行随机扰动。为防止变异位置航路发生突变，需要检测交叉处航路点的最大拐弯角约束和最大爬升/俯冲角约束，如果不满足约束条件，则进行平滑处理。如果原始染色体为可行解，则变异操作后染色体亦可保证为可行解。

3.6 快速非支配排序

选择出的群体经过交叉和变异操作，形成子代群体。将子代群体和父代群体合并，形成种群规模为的混合种群，对混合种群进行快速非支配排序，选出最优的dnanum个染色体，即为新的父代种群。快速非支配排序结束后，重新返回锦标赛选择环节，进行下一次迭代，直至算法结束。

3.6.1 np和Sp计算

快速非支配排序中，种群中每个个体p都有两个参数np和Sp，其中np为种群中支配个体p的个体数，即比个体p优的个体数;Sp为种群中被个体p支配的个体的集合。

首先，根据公式 (3－6)，计算种群中个体适应度，为尽快淘汰非可行解，可以将非可行解的目标函数值设为极大 (适应度极小)。然后，初始化每个个体的np=0，Sp=Ø，通过循环遍历，对种群中任意两个个体p和q进行支配性判定 (定义1)，如果p＜q，则nq=nq+1，Sp=Sp∪q;反之np=np+1，Sq=Sq∪p。

3.6.2 非支配分级

非支配分级用于划分种群中个体的非支配层级。

Step 1:初始化非支配层级数i=1。

Step 2:找到种群中所有np=0的个体，令其Prank=i。从种群中移除np=0的个体，并遍历np=0个体的Sp，对任意 q∈Sp，令 nq=nq－1。

Step3:i=i+1，重复Step 2，直至种群中所有个体都已经被划分层级。

3.6.3 拥挤度计算

用于表示目标空间内同一非支配层级内染色体周围个体的密度。初始化该非支配层级内所有个体拥挤度Pd=0。对非支配层级内所有个体按目标函数向量的第m个分量进行升序排序，假设非支配层级内有染色体个数k，排序为i的个体当前拥挤度为P，其目标函数向量的第m个分量值为fm［i］，则染色体拥挤度计算为:

其中:fmmax和fmmin分别为层级内目标函数向量的第m个分量的最大值和最小值。排序边缘个体直接赋予极大拥挤度，即依次遍历航路长度、航路安全性、航路隐蔽性3个目标函数分量，计算染色体拥挤度。

3.6.4 最优解排序

基于精英策略的最优解排序就是选取父代子代混合种群的最优个体作为新的父代，使得原父代中的优良个体得以保留，从而防止Pareto最优解。具体方法是，先按非支配排序Prank从小到大将非支配层级整体选入新父代，直到如果将某非支配层级完全选入新父代会超过规定的父代种群规模。此时按拥挤度从大到小，依次将非支配层级拥挤度最大的若干个个体选入新父代，使其满足规定种群规模，此时的新父代即为混合种群中的最优个体集合。

3.7 终止条件

当种群多目标进化算法的运行时间达到最大允许值或者种群迭代次数达到事先规定的上限，则进化结束，取当前最优Pareto最优解集为输出结果，通过解码得到备选方案集，并根据作战目标和指战员意图，从中选择最合适的规划结果。

4 仿真算例

假设无人机约束参数如表1，战场环境为1 000 m×1 000 m×500 m，战场敌方地面火力威胁数量为3，威胁参数如表2，其中火力威胁高度直接取所处位置的地形高度。

表1 无人机性能约束参数

表2 敌方火力威胁参数

设定染色体长度为50，种群规模为60，最大迭代次数为100。采用NSGA－Ⅱ算法，仿真结果如下图。

图1～图3为当前种群航路长度、航路安全性、航路隐蔽性最优值与最差值随着迭代次数的收敛曲线，可以看到迭代过程中，3个航路指标的表现出了共同进化的特征，且最优值与最差值的收敛代数均不超过30代，表现出了良好的收敛性，证明了NSGA－Ⅱ算法的优越性。

为抵消不同指标项量纲带来的影响，将Pareto解适应度向量的各个分量与种群中该分量的最优值 (最小值)的比值称为相对适应度。通过快速非支配排序从最终种群中选取10个最优Pareto解，图4为其相对适应度向量在目标空间的分布，可以看出Pareto前端的空间散布非常均匀，说明获得的Pareto最优解具有良好的代表性。表3列出了最优Pareto解的相对适应度。

图1 航迹长度收敛曲线

图2 航路威胁度收敛曲线

图3 航路隐蔽性收敛曲线

从图4和表3可以看出，经过迭代收敛，种群中的最优Pareto解普遍达到了较优秀水平，但并不存在各方面都优于其他Pareto解的绝对最优解，而是体现出了一定的多样性，即不同的Pareto解都具有各自的优势，分别适应不同的任务需求。在复杂多变的战场环境中，指挥人员可以根据不同任务需求的倾向性，选择当前最合适的方案，而不必依赖于应变能力很差的固定指标权重，体现出了良好的灵活性和适应性。更重要的是，多元化的解集在空间均匀分布，各个最优Pareto解不仅相互竞争，而且互为备份，指挥人员不必担心面临，由于指标权重或量纲等问题产生出某方面具有“短板”的劣质最优解，导致无合适方案可用的尴尬情况。这是多目标优化区别于加权单目标优化的重要特征，也是多目标优化的最大优势。

图4 最优Pareto解目标空间分布

表3 最优Pareto解相对适应度

假设指挥人员决定采用冒险策略发起一次快速隐蔽的打击，并愿意承担一定的风险，则其可能会选择航路方案10，图5和图6分别为其三维路线图和二维俯视图。图中同心圆的外圈表示敌方火力威胁的最大威胁半径，内圈为绝对威胁半径。

图5 最优航路三维图

5 结语

本文建立了无人机航路规划问题的多目标优化模型，并给出了基于NSGA－Ⅱ的求解方法。相比于传统加权单目标优化，该方法能够兼顾无人机航路规划的多个不同指标要求，更加符合无人机作战的实际特点，并具有很强的灵活性和适应性。仿真算例表明了该方法解决无人机航路规划问题的可行性和有效性，为无人机航路规划研究提供了新的思路［1013］。

图6 最优航路二维俯视图