支持强化学习RNSGA-II算法在航迹规划中应用

封 硕，郑宝娟，陈文兴，张婷宇

1.长安大学 工程机械学院，西安710064

2.长安大学 理学院，西安710064

3.武汉大学 数学与统计学院，武汉430072

1 引言

在战场环境中要为无人机规划出合理的路径需要考虑多方面的因素，如无人机本身的性能、地形因素、威胁，隐蔽性等，使其能够以更低风险和更廉价费用得到一个最优的路径，是一个NP完全问题，是无人机任务规划系统研究的难点之一。遗传算法作为智能优化算法的一种，具有很好的鲁棒性、并行性、全局收敛性优点[1]。将遗传算法应用于无人机路径规划目前已有大量研究成果：文献[2]介绍了三种路径规划方法：贪婪启发式、遗传算法和多种群遗传算法，证明了贪婪启发式算法与遗传算法相结合是解决无人机紧急着陆问题的有效策略。文献[3]提出一种主从并行矢量评估遗传算法（MSPVEGA）来解决航迹规划问题。MSPVEGA利用先进的计算能力并行处理多个遗传算法从而实现了无人机的自动化。然而，随着工程的发展，解决多个优化目标算法逐渐引起了学者的关注。传统的多目标优化算法利用权重线性组合目标函数，其中，权重的确定往往依赖于经验，往往不能很好地解决优化问题。针对多目标的遗传算法，文献[4]改进了非支配排序遗传算法（NSGA），提出了复杂度更低，更能保持种群多样性，具有Pareto占优的NSGA-II算法，已被越来越广泛地应用于解决多目标优化问题[5-9]，文献[10]将NSGA-II算法成功应用于无人机航迹规划，但是算法虽然设置了拥挤距离保持解之间的距离，然而当解陷入局部最优时还是很难跳出。为解决这个缺陷，文献[11]提出了一种双种群遗传粒子群算法，设置两个不同种群，每隔一定代数在两个种群之间进行精英的迁徙，验证了该算法比单一种群得到的解更具有分布性和多样性，然而种群之间迁徙参数是人为确定，不能很好地逼近最优解。文献[12]首次提出用强化学习来优化种群之间的迁徙参数，但是算法是基于单目标优化问题设计强化学习三要素，对多目标问题暂未考虑。文献[13]在文献[12]的基础上将种群划分为三类子种群从而实现各自迁徙，能有效地解决算法的收敛速度和全局收敛的矛盾，但是算法优化的目标函数只有一个且未应用验证有效性。

为了有效解决以上算法在收敛精度和航迹规划应用方面的不足，本文尝试用NSGA-II算法来解决三维战时环境下无人机路径规划问题。首先，建立两个不同种群，每隔一定代数对两个种群进行迁徙，避免单一种群解陷入局部最优。迁徙参数利用强化学习动态确定，强化学习的目的是优化种群多样性，使种群能自主保持多样性，从而加快算法收敛，提高收敛精度和速度。

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

2.1 规划空间

模型假设无人机处于山谷中，受到雷达的侦测，航迹规划问题需要综合考虑路径长度、威胁性及隐蔽性等众多因素作为优化的目标函数。雷达所形成的威胁区用圆形环表示[14]，其中内环区域为绝对威胁区，在本区域内飞行处于绝对危险状态，此时无人机绝对会被雷达侦测到，外环区域为最大威胁区，在此区域内飞行处于有一定威胁状态，此时无人机有被侦测到的可能性。确定无人机的飞行起始点和终点，航迹规划结果就是包括起点和终点在内的N个航迹点。本算法的任务是：确定出无人机航迹，包括起点和终点在内的N个航迹点。

2.2 优化目标及约束条件

航迹长度代价f1由以下优化函数表示，其中li为路径中第i段相邻两点移动的欧氏距离：

雷达的能量是随着其传播距离平方衰减的，假设无人机截面受到雷达的威胁后反射相同的能量，则航迹中的威胁值是航迹点到雷达中心的距离四次方：

式中，Thrj(i)为航迹点受到雷达的威胁[8]，j表示雷达的个数，j={1,2,…,M}

其中，d max j，d min j为第j个雷达的最大威胁半径和绝对威胁半径，θ为视线仰角，θmin为攻击下界角，无人机飞行过程中的隐蔽性代价f3由航迹所处的高度决定：

无人机飞行过程中还收到基本的约束条件，这些约束条件包括：最大拐弯角ψmax，最大爬升角φmax或俯冲角φmin，安全飞行高度约束hsafe等。

综上，考虑三维山谷情形下一个无人机飞行模型，最优目标需要考虑三方面因素，使得航迹长度代价、总威胁值、隐蔽性代价达到最小，约束条件，通俗的讲受约束于飞行安全距离、拐弯角在可操作范围内、爬升与俯冲可在正常可控范围，具体建立的优化模型如下：

约束条件中，zh为第i个航迹点所在位置的地形高度，ψi，φi为航路点的水平转弯角和爬升角。

3 支持强化学习RNSGA-II算法在航迹规划中的应用

在以上模型的基础上运用支持强化学习RNSGA-II算法实现三维空间航迹规划。RNSGA-II算法的基本思想如下：控制初始种群产生的随机性，使用两种随机量产生两个不同的初始种群，由于遗传算法初期需要增加种群的多样性避免解陷入早熟，所以在前50代设计迁徙规则让两个种群交换，具体迁徙为每隔一定代数令种群1的前m个精英群体与种群2随机m个群体交换，交换后形成新的种群1和种群2，再分别运用NSGA-II算法各自独立进化。把当前迭代过程中，选择出来（或指定的）要进行交换的小群体个数占总群体个数的百分比定义为迁徙比例，然而不同的迁徙比例得到的效果不同，因此迁徙参数的设置对算法的效果起着非常重要的作用，由此引入了强化学习来自主确定迁徙比例，使算法自主保持种群多样性的目的。

3.1 多目标优化函数的多样性衡量

传统的多目标优化问题大多转化为单目标来衡量解的多样性，所得到的多样性值往往不够精确，对多目标优化函数解的多样性的研究目前采用的办法是评价具有Pareto性的前沿解的均匀离散分布程度，一般解分布得越均匀，说明得到解的多样性效果越好，常用的多样性衡量指标有[15]解间距度量、熵度量、网格度量、聚类度量、方差度量、离散度量等。本文采用离散度量的方法来衡量解的多样性，结合强化学习动态确定迁徙参数。从而控制飞行路径精度。

离散度φ的定义如下：

di表示的是解的欧式距离：

其中，|A|为具有Pareto性的前沿解的个数。

δ为n-1个解的方差：

3.2 强化学习模型及组成元素

强化学习是一个环境交互式学习方式，如果Agent与环境交互的过程中某个动作得到了正的奖赏，则Agent会在以后的交互中更加趋于这个动作。Agent通过不断地与环境交互达到目的状态，且获得最优策略使期望折扣和最大。强化学习时最关注的是最终的满意的状态，即获得最优策略时其期望总值达到最大。本文中Agent学习程度可以通过与环境交互调整迁徙参数m来控制，当交互到种群1和种群2的多样性都比初始状态好时，认为当前的迁徙参数设定合理。强化学习的过程又可以细分为三个重要因素，其设计过程如下。

（1）状态

状态St( )t=1,2,…,9为当前种群多样性与初始种群多样性的比值，具体定义及表示的意义如表1所示，其中φ10、φ20为初始种群1和种群2的初始多样性值，φ1i、φ2i为种群1和种群2的第i代多样性值。种群状态的意义常分为：减少、不变、增加，2个种群有9种排列组合情况，结果如表1。

（2）动作

式中，m(t)为第t代种群的迁徙参数，dnanum为种群的数量，A为动作矩阵，对动作的设定有三种，保持参数m(t)不变，增加m(t)和减少m(t)。

（3）奖赏

本文对奖赏值的设置主要是为了搜索最好的迁徙参数m(t)、φi(t)和φi0(t)分别为第i个种群第t代的多样性值和初始种群i的多样性值。

表1 强化学习状态集合

3.3 支持强化学习NSGA-II算法应用步骤

综上所述，支持强化学习的RNSGA-II算法应用步骤如下：

步骤1初始化参数，设置算法相关参数：种群迭代次数t，种群规模dnanum，交叉概率Pc，变异概率Pm，输入所规划的三维空间，设置雷达所在的位置及作用半径，设置规划路线的起点和终点。

步骤2初始化种群1、种群2，采用三维坐标编码，控制坐标的随机性，使两个种群的初始化结果具有多样性。

步骤3对种群采用一点交叉，一点变异，产生新的种群记做子代Qt。

步骤4将种群Pt与子代种群Qt合并，新的种群记为Rt，对Rt种群进行非支配排序，拥挤度计算，产生新的种群Pt+1。

步骤5判断当前代是否为“迁徙”代，若是则执行步骤6，否则执行步骤3。

步骤6将种群1的前m个优势子代与种群2的随机m个子代交换，交换的“迁徙”参数m用强化学习方法产生。

步骤7判断种群是否达到最大迭代次数，如果达到，迭代结束，否则转步骤3。

4 仿真分析

基于上述算法设计，在Matlab上进行仿真实验，以某山区DEM[16]作为算例的实验环境，战时环境为1 000 m×1 000 m×1 000 m，设置种群1和种群2的最大迭代次数为100代，种群规模为50个染色体，交叉概率为0.8，变异概率为0.2。无人机和雷达的参数如表2和表3所示。

表2 无人机参数信息

表3 雷达参数信息

（1）路径规划结果

图1（a）为三类种群中具有Pareto前沿的航迹俯视图，其中种群1和种群2是相互迁徙的种群，种群3是经传统NSGA-II算法作用的种群。图1（b）为三类种群的三维路线点。从图中可以看出，三类种群都能成功规划出效果较好的路线，且都规避了绝对威胁半径。

图1（a）三种群航迹规划俯视图

图1（b）三种群三维路线图

（2）目标空间的非支配前沿解集

为了消除三个目标函数解的不同量纲的影响，对Pareto解集做了无量钢化处理，即对每一个目标函数的解分量与其最优值求比得到相对适应度。算法提取了非支配排序前10的非劣解，得到如图2的Pareto前沿解集分布，从图中可以看出种群1和种群2所得到Pareto的前沿解分布具有多样性，且均匀分布在解集中。

图2 种群Pareto前沿解分布

（3）目标函数收敛曲线比较

提取每次迭代过程中三个目标函数的最小值，得到各个目标函数的收敛曲线如图3所示，可以看出在迭代的过程中，种群1和种群2所得到的最优值比种群3结果更好，尤其是种群2所得到的结果最优。支持强化学习RNSGA-II算法的能改善NSGA-II算法陷入局部早熟的缺点。

图3（a）航迹隐蔽性收敛曲线比较

图3（b）航迹威胁性收敛曲线比较

图3（c）航迹长度收敛曲线比较

（4）算法对比结果分析

将经典NSGA-II算法，文献[16]提出的ENSGA-II算法，及本文提出的支持强化学习RNSGA-II算法所得到的结果进行对比分析，每种算法独立执行10次，将算法得到的最优航迹的各个适应值函数规范化到区间[1，2]上，求规范化后的最大值、最小值、平均值，并将其作为评价算法性能指标，结果越小则算法取值越好。表4～6给出各个算法最优适应度值的规范化统计。从表中可以看出，多次实验RNSGA-II算法所得到的最小值最好，经典NSGA-II算法和ENSGA-II算法都又陷入局部最优，且RNSGA-II算法在多次实验后得到的各个适应度平均值最小，性能最稳定。

表4 NSGA-II所得最优航迹各个适应度函数的规范化统计

表5 ENSGA-II所得最优航迹各个适应度函数的规范化统计

表6 RNSGA-II所得最优航迹各个适应度函数的规范化统计

（5）多样性分析

图4以迁徙代为6代为例，分析不同算法下种群的多样性。可以明显看出种群1和种群2所得到的非劣解多样性比种群3解的多样性更好。设置不同的迁徙代，以种群2为例，比较不同迁徙代对种群多样性的影响，从图5中可以明显看出，迁徙代为5代和6代所得到的种群多样性效果较好。图6以初始迁徙代为5代时Q学习对种群2多样性的作用分析，可以看出加入Q学习后种群2的多样性相对较好。

图4 迁徙代为6代时种群多样性比较

图5 不同迁徙代种群2多样性比较

5 结束语

图6 Q学习对种群2的影响

本文针对NSGA-II算法容易陷入早熟，收敛速度慢等问题，提出了支持强化学习RNSGA-II算法并应用在了无人机路径规划问题中。实验表明该算法提高了非支配解的多样性和收敛性，得到的解比NSGA-II算法得到的解更精确，避免了早熟现象，通过与其他算法的对比RNSGA-II算法多次实验得到的解依然最精确，且更稳定。通过进一步分析，加入强化学习后得到的解的多样性更好，且实验得到最优的迁徙代数是5代和6代。算法在提高多目标优化问题解的多样性和收敛性上效果显著，能很快找到具有Pareto性的前沿解，且得到的解更精确，对优化多目标无人机航迹规划提供了一定的借鉴思路。