基于改进遗传算法的多无人机航路规划方法*

2019-06-15刘超

火力与指挥控制 2019年1期

关键词：航路航迹交叉

刘超

（中国飞行试验研究院飞行仿真航空科技重点实验室，西安 710089）

0 引言

单无人机在侦查目标数量较多情况下不能很好地完成侦察任务［1］，因此，实战中常需采用多无人机协同行动对某个区域进行完整侦察［2］。

多无人侦察机协同的航路规划问题与单架无人机规划相比所要面临的问题有很多不同之处，资源优化分配及协调是其中两个需要解决的关键问题。侦察无人机可以看作是一种“资源”，需要让多架无人机进行空间和时间上的合理分配来实现资源配置的最优化［3］。

为更好解决多无人机航路规划问题，本文建立了多机协同侦察任务/航路规划数学模型，并将其转化为MTSP问题来求解侦察任务分配及排序问题，并提出改进的遗传算法以获得更好的规划结果。

1 问题分析

1.1 多无人机侦察任务需求

应用场景为单基地情况下的多无人机协同侦察任务/航路规划，该问题的详细描述为：在满足相关约束条件的前提下，采用多架无人机对于不同位置的多个目标进行侦察，相关约束有：

1）从基地出发并完成各自分配的侦察任务后，无人机都应返回基地；

2）须满足关于传感器类型和成像质量的要求［4］；

3）每个侦察目标不能重复进行侦察；

4）满足无人机自身约束，诸如性能约束和时间约束条件等。

以上4项约束条件为前提，最后的优化结果要实现：

a.侦察目标数量最大化；b.执行任务的总代价最小。

1.2 侦察航路规划问题分析

为了使模型能够反映问题的特点，应对各具体要素进行分析。

1）侦察图像的质量评价

2）在满足任务要求同时，尽可能减少执行任务无人机的数量

对于任务规划人员而言，总是期望高效地完成侦察任务，以此来达到资源和效益的最大化。目前已有的很多模型并没有考虑到这一问题。

3）多目标优化问题分析

一般情况下，在进行协同侦察任务规划时，期望的结果是“最优”的结果，即尽可能多的侦察目标、无人机飞行航迹总和尽可能短，安全程度尽可能大等等。

1.3 目标的分配和排序

多无人侦察机进行任务分配则可以看成是对多名旅行商进行规划，等效于在满足约束条件的情况下，让多个旅行商遍历所有的目的地。因此，可将多无人侦察机航路规划问题转化成MTSP问题求解。

2 多无人机航路规划MTSP模型

作为较典型的组合优化问题［5-6］，MTSP是TSP问题的扩展。在该问题下，多侦察目标的任务分配和排序可以这样描述：

给定数量为n的目标集合，有m架无人侦察机从目标n1出发分别访问余下的n-1个目标。每一个目标只能有且仅有一架无人机执行侦察任务，并且所有无人机的总航程越小越好。

定义变量：

目标函数为：

其中：

式（2）中，cij为无人机从目标i到达目标j的直线距离。约束条件为：

式（1）表达使m架无人机的总航行距离最短；式（2）表达每一架无人机的航行距离大小；式（3）表达所有无人机从指定地点起飞，每个目标仅需访问一次。

3 遗传算法求解多无人机MTSP

3.1 编码方式

采用符号编码方式，利用1、2以及n分别代表目标1、目标2以及目标n，利用0来表示起点和终点。

对所有目标进行标记，其列表集合为W；给每个目标分配一个1…n之间的序号，该序号存在于集合W中。如两架无人侦察机，有9个目标点，其编码为：

图1 符号编码及解码

解码为第1架无人机飞行路线为从起点经过目标 1、2、3、4、5 后返回起点，第 2 架无人机飞行路线为从起点经过目标6、7、8、9后返回起点。

3.2 适应度函数

用L表示生成的各条航迹长度之和，用M表示航迹中最长的航迹与最短的航迹长度之差。种群进化既要使得飞行的总长度较小，又要使得各条航迹的长度相似，即L和M都要越小越好。所以适应度函数为：

式（4）中，L为全部航迹长度之和；M为最长的航迹与最短的航迹长度之差的绝对值；a为L的权值；b为M的权值。F的值越小，个体适应度就越好。

3.3 选择操作

在对每个个体依照其适应度的大小进行评价的基础上采用轮盘赌的方式进行选择操作，其目的在于提高遗传算法的收敛性和计算效率，表达式为：

3.4 交叉操作

采用置换交叉方式［7］，在两个父体上随机选取个数相同基因序列进行交换，其余位置与交换位置比较，如果有基因相同，则按照距离的大小依次替换为不同的基因，确保目标不被重复访问或遗漏。如图2所示，两个父代个体基因为：

随机选取交换位置为从位置5到位置8，经过交换后，两个个体分别为：

图3 交叉操作后基因位示意

其余位置上的基因依次与交换后的基因比较，S1n中基因5、7、9均重复，根据基因5的前一位基因1，计算基因2、6、3中与基因1距离最小的基因代替原有基因，如基因段16的长度比基因段12和13都小，则用6代替原来的5，以此类推，完成所有基因的替换。则交叉操作后的子代基因可能为：

图4 距离最小的基因位代替示意

如果在交叉操作中，出现两个个体的位置段内，一个含有起点0而另一个不含有，则不含0的基因段少交换一位，含有0的基因段0的位置不变，比如原有基因为：

图5 交叉操作前0基因位置意图

交换位置为3到6。由于S1中基因段不含0，则少交换一位，只交换5、8、2三个位置的基因，S2中0的位置不变，则交叉操作后的子代基因可能为：

图6 交叉操作后0基因位置意图

交叉操作是一种保持进化种群保留优良遗传基因的有效方法。

3.5 变异操作

变异操作指的是一条染色体上的两个基因以一定的概率进行交换并产生新的个体。图7是变异操作前染色个体基因示意图。

图7 变异操作前基因位置示意

图8 变异操作后基因位置示意

图8是位置5的基因位与位置10的基因位随机交换后的新染色个体。变异操作保持种群多样性的有效方法。

4 遗传算法的改进

采用一种改进的称为三交换［7］启发交叉方法，其改进主要有两点：

1）将传统两条染色体参与交叉操作改为3条；

2）交叉和变异概率不再固定，以降低染色体近亲繁殖的概率，以控制进化过程［8-9］。

4.1 三交换启发交叉方法的基本思想

通过3条染色体进行交叉操作来产生后代，以图9列出的8个目标为例来说明这一过程，其中cij由表1给出，设3条父代染色体为：

图9 三染色体交叉操作示意SUM1=42，SUM2=40，SUM3=46

SUM1，SUM2，SUM3分别为这 3 种方案需要飞行的距离，随机选出初始目标j=1，Sj=3右转动，使3成为3父代的第1位置。

图10 父代的第1位置示意

由于 c（3，2）＞c（3，5），所以有：

图11 父代位置重排示意

由此规则计算可得：SUM0=24

图12 三染色体交叉优化示意

SUM0为3个父代所产生子代的距离或惩罚费用总和，显然 SUM0远远小于 SUM1，SUM2和 SUM3。

表1 8个目标间的距离

4.2 交叉概率变参方法

设K=1，则Pc的表达式为：

式中，f′=（SUM1+SUM2+SUM3）/3为当前交叉的 3条父代染色体的平均值；ffit为当前代中最短的路程值；f为当前代的平均值；SUM1，SUM2，SUM3分别为未交叉的3个父代的总航程或惩罚费用。

若某子代当中的所有个体的适应度值很接近，说明结果可能陷入了局部最优，这时须增大Pc来摆脱这种情况。

若当前一代的最优值和其3个父代的平均值之差较大时，说明父代可通过交叉来产生更好的个体。

4.3 变异概率的变参方法

变异概率Pm的变参形式表达如下：

fbest为当前代中最佳值；f为当前代的平均值；f′当要进行变异的父代。

随着f′的变化而设置不同的变异概率是为了防止算法陷入局部最优。当fbest与f很接近时，某代中所有的值可能陷入了局部最优解，所以通过让Pm较大的方法来摆脱可能产生的局部最优解。当fbest与f′相差很远时，说明f′离最优值还相差很大，所以要增大变异概率。

5 仿真验证

5.1 多侦察目标分配和排序仿真验证

两架无人侦察机的起点和终点均相同，飞行高度为12 km，飞行速度保持不变，速度为250 m/s，飞行最大距离为70 km，传感器的成像时间为6 s，最大焦距f=1.75 m。任务规划的环境区域是一个25 km×25 km的正方形区域，地形平坦。区域中共有20个待侦察目标，目标均视为点目标。目标参数如表2所示。

表2 待侦察目标参数表坐标单位：km

所有目标分配及侦察顺序结果如下页图13所示。

第1架无人机的飞行顺序为：起点－目标20－目标6－目标17－目标4－目标13－目标7－目标11－目标1－终点。

图13 仿真结果示意图

第2架无人机的飞行顺序为：起点－目标2－目标16－目标9－目标19－目标14－目标8－目标15－终点。

目标侦察完成情况及拍摄图像质量如表3所示。

表3 目标侦察情况表

5.2 仿真分析

从表3可看到，侦察环境中一共存在20个待侦察目标，按照预先任务分配和规划的航路，两架无人机共侦察到15个目标，这15个目标点的侦察质量均达到要求。数量侦察效率为75%，飞行总距离为105 969.9 m。虽然飞行总距离偏大，但每一架无人机的飞行距离减小了，其中，第2架无人机的飞行距离为55 845.3 m，远远小于低于飞行最大距离限制。

根据图和表的内容可以看出，在多任务复杂环境下，所提方法可以保证多无人机能够按照规划的航迹从起点出发，在侦察了多个目标后返回终点，取得很好的侦察效果。