基于改进操作算子的遗传算法无人机航路规划

钱海力

（中国电子科技集团公司第二十八研究所 江苏省南京市 210007）

无人机在执行任务之前需要进行任务规划，其中，最为主要的一部分就是无人机的航路规划。合理有效航路规划能帮助无人机平台规避威胁，提高侦察和生存能力。运用改进操作算子的遗传算法对无人机的航路进行精细规划，能有效提高算法收敛速度，规划出更科学的任务航路。

1 遗传算法

遗传算法是以生物进化机制为基础的一种算法，属于搜索算法中的一种。美国密歇根大学霍兰德教授于1967年根据自然选择理论提出了关于遗传算法的相关概念，此后其学生在自己的研究著作中，总结了遗传算法的研究成果，即一种全局优化的搜索算法，其核心为：

（1）合理编码方式与有效终止条件；

（2）建立适合评价个体性能与适应度的函数；

（3）合理复制、交叉与变异操作[1]。

1.1 编码评测

遗传算法在应用中，先建立问题染色体，之后形成问题种群，最后，对染色体适应能力进行测量并对其进行迭代繁殖分析。遗传算法利用染色体表达优化搜索问题的解，通常运用字符或数值两种编码形式去描述染色体。编码评测方法是遗传算法问题建立之后的一种主要优化机制，评测能根据适应度对染色体适应性进行评价，通过对比分析方式不断对染色体个体进行优化迭代，最终找到最优解。在遗传算法优化中，染色体繁衍迭代，通过编码评测实现对染色体适应能力的计算，模拟生物的进化过程[2]。

1.2 终止条件

在繁衍过程中，使用突变操作或者交叉操作方法进行染色体迭代。其中，突变操作主要是使染色体某部位基因参数产生突然性变化；交叉操作采用染色体某个部位基因交换，适应性强的染色体会逐渐完成统治，适应性弱的部分会消失，提高整个种群适应能力。通过对整个群体的繁衍优化，其群体的适应能力会不断上升。因此，通过对染色体群体的适应性分析方法，能够掌握整体适应性上升或者下降的发展趋势，并最终作为算法的终止条件。此外，还可以通过规定染色体群繁殖时间，检验最优染色体是否达到相关要求，如果没有达到要求，则要进行重新运算，如果达到，则停止计算。

2 航路规划

2.1 空间建模

考虑地形因素、威胁因素、无人机平台运动因素等对其任务过程所产生的影响，分析无人机飞行的环境条件并进行数学抽象和描述，建立无人机飞行过程中的空间约束模型。基于无人机飞行过程空间约束模型，以最优化目标函数的方式对无人机的航路进行规划，从而生成无人机最优航路[3]。由于无人机任务剖面在巡航段时高度保持不变，因此采用二维空间模型，能比较直观地反映出其飞行过程中在同一高度平面的航路规划问题。针对任务空间中的威胁区域，本文采用圆形近似表示，将圆形半径作为威胁区域的有效覆盖距离，圆形范围内作为禁止飞行区域。

2.2 评价建模

航路规划的目标是综合考虑无人机飞行性能所产生的限制，规避飞行中面临的各类威胁到达指定目标点，在保证任务过中的生存能力的同时提高任务完成度。为实现上述目的，在评价建模中，需要选择最优目标函数，对无人机航路进行评价，判断各类约束条件的满足情况，并引导搜索算法逐步迭代逼近最优解。在航路规划评价中，航路规划结果为航路点间构成航路段，此时航路约束条件可以表示为航路段的约束。在具体规划过程中，考虑到无人机平台运动约束，定义最小路段为无人机在执行下一动作之前需要做出的最短飞行距离。

3 改进操作算子遗传算法无人机航路规划

3.1 规划要点

3.1.1 编码问题

染色体编码是无人机航路遗传算法规划中的重要前提，编码方法决定个体染色体排列形式，还决定个体从搜索空间基因变换到解空间的解码方法。编码方法影响到交叉、变异与选择算子，常用的编码方式可以为二进制、字母、整数或浮点数等。研究证明，编码方式与问题原始形式接近程度越高，则表现形式越有效，最终结论更优。但同时，编码方式越复杂，则搜索复杂度越高，搜索时间越长。

如前所述，在进行无人机的航路规划中，由于无人机任务剖面在巡航段时高度保持不变，主要考虑无人机在巡航高度平面内的运动，因此本文将三维航路规划问题转化为同一高度下的二维平面航路规划问题[4]，采用平面内优化搜索解决无人机航路规划问题。建立直角坐标系X-O-Y，将无人机航路划分为N 等分，得到L1（x1，y1），L2（x2，y2）...LN（xN，yN）共N 个航路节点。综合考虑无人机在飞行中受到的转弯约束或者方向性问题，将起始点到目标点的航路P 用节点集合描述表示，即：

其中，S 为航路起始点，G 为航路目标点。

为了方便运算，在进行无人机的飞行航路节点编码时仅将纵坐标作为基因进行编码，而横坐标的变化保持不变。本文采用浮点数形式进行编码，此时航路P 的编码形式为：y1y2...yN。

3.1.2 航路代价

航路代价主要考虑无人机任务过程中的油耗代价和威胁代价。一方面，无人机飞行过程中受自身油耗因素影响，其飞行航程受到受限；另一方面，任务过程中会遭遇雷达、导弹等各类威胁因素，其飞行空间受到限制。因此，为使无人机任务航路耗油最低且受威胁最小，要从航路长度、航路油耗量、航路点是否受威胁、航路段是否跨越威胁区等方面进行分析，并根据无人机的任务要求，调整各类型代价函数的权重大小，综合代价指标得到相对较优的无人机任务航路。

3.2 规划方案

3.2.1 适应度函数

在明确无人机航路编码问题及其在任务过程中面临的威胁、油耗等航路代价后，如何选择最优的算法对无人机飞行航路进行规划是解决问题的核心。可见，建立合适的适应度函数，是采用遗传算法解决无人机航路规划问题的关键。

在对无人机的航线规划中，基于提出的航路编码方式及航路代价条件，本文提出包含航路总长度f1、航路点是否在威胁区域内罚函数f2、航路段是否穿越威胁区罚函数f3 的适应度函数。即适应度函数F 可描述为：

其中，罚函数f2、f3 取1 时，航路点在威胁区域内或航路段穿越威胁区域，反之取0；w1、w2、w3 为权重系数，有w1+w2+w3=1。

3.2.2 遗传操作

对无人机航路进行规划时，根据适应度大小，选择适应度较强的个体，完成对个体的遗传操作，产生适应性更优的下一代个体。通常情况下，适应度高的个体被选择概率较大，适应度较低的个体被选择的概率较小。遗传算法的遗传操作即体现了生物界“优胜劣汰”的原则，其操作分为：选择、交叉、变异三个部分。

根据无人机航路规划问题复杂性，本文对选择算子进行改进。按照适应度从高到低的顺序对个体适应性进行排序，给定适应度阈值S，适应度高于S 的个体复制成n 份，适应度低于S 的个体不单独进行复制。通过这种方式，可以在确保群体内多样性的基础上，逐步淘汰适应度低的个体，并收敛得到最优解。

交叉是以交叉概率Pc 从群体中选择两个个体，并对个体内的某个、某些基因位进行交换。基于对遗传算法的交叉操作分析可知，当前主要的交叉方式包括了单点交叉、双点交叉和均匀交叉等。其中，双点交叉模式是个体中随机设置两个交叉点，之后进行基因交换的一种方式，具有适应性强和操作复杂度低的特点。因此，本文即采用两点交叉方式进行交叉操作。

变异方法是以较小的变异概率Pm 对个体编码串上某个单独、某些基因位进行随机改变。本文对变异算子进行改进，以变异概率Pm 选取个体的两个基因位，通过航路点坐标距离改变5000 米实现变异。基于无人机路径规划仿真验证和工程实践，当两个航路点之间坐标不超过5000 米时，能保证相邻航路点距离相差不大，而且航路点也不会产生跳跃现象，使无人机在飞行的过程中，能始终保持相对稳定的状态，同时也可以加快算法收敛速度，便于得到最优解。

3.3 改进策略

遗传算法中使用交叉算子作用于个体，会促使新个体的产生，这实质上是基因重组的过程，使算法在解空间中进行有效搜索。若交叉概率Pc 过大，种群中个体更新会变快，那么适应度高的个体将很快遭到破坏，即优良模式很快被破坏；若交叉概率太小，交叉操作将进行得很少，基因重组就会减少，最终使得搜索停滞，遗传算法不收敛。

遗传算法中变异操作实质上是对种群模式进行扰动，以增加基因种类的丰富性，有利于种群多样性的增加。但是，若变异概率Pm 太小，那么新模式就会很难产生，若有过大的变异概率，那么遗传算法的搜索将变得比较随机。

可见，交叉概率Pc 和变异概率Pm 的选取对遗传算法的收敛效率和解的最优性至关重要。分析可知，当个体的适应度越接近种群最大适应度时，其交叉和变异的概率应越低，此时其优良基因越可能在下一代个体中保留下来。因此，本文基于Logistic 方程提出一种对Pc 和Pm 的改进策略，实现在遗传算法迭代过程中对Pc 与Pm 的自适应调整，其数学描述如下：

其中，f'为要交叉的个体中适应度值较大的个体的适应度，f为要变异的个体的适应度，favg为种群中所有个体的平均适应度，fmax为种群中最大个体适应度，k1、k2为大于0 的常数。

通过仿真分析，对本文提出的航路规划方法的合理性和有效性进行判断。针对典型无人机航路规划任务，受限采用传统遗传算法仿真，初始种群设定为200 个，最大迭代次数设定为300，在使用轮盘选择方法和两点交叉模式，变异过程为实体变异。之后，在经过操作算子改进之后的遗传算法进行仿真分析，采用相同的参数指标操作，能够发现本文提出的基于改进操作算子的遗传算法相较传统方法在收敛迭代次数和收敛概率上有一定提升。结果证明，经过操作算子改进之后的遗传算法最优航线算法比传统算法的迭代速度更快，而且航路比较平滑，这些均有利于无人机任务的实施。经过改进之后遗传算法在多个评价标准上的指标均比传统算法更优，而且规划出的路径适合无人机平台正常飞行。同时规划得到的最优航路，合理规避了各类障碍物和威胁要素，缩短了飞行距离，可有效节约燃料，降低了能耗与成本。

4 总结

综上所述，在现代社会，特别是在军事领域，无人机应用越来越广泛，智能化需求不断提高，这些均对无人机航路规划方面提出了新的挑战。为此，本文基于对遗传算法以及无人机航路规划相关领域研究成果的分析研究，提出一种基于改进操作算子的遗传算法无人机航路规划方法，针对性地对遗传算法中选择算子、交叉算子、变异算子等遗传操作算子进行改进，提高了算法搜索效率。针对传统遗传算法中交叉概率Pc 和变异概率Pm 不变造成算法收敛速度慢的问题，本文基于Logistic 方程提出一种对Pc 和Pm 的改进策略，并通过仿真验证了本文提出算法的有效性。