基于集中一体化遗传算法的协同航迹规划方法*

2021-08-06李文广李建增胡永江李永科赵月飞

火力与指挥控制 2021年6期

李文广，李建增，胡永江，李永科，赵月飞

（陆军工程大学石家庄校区，石家庄 050003）

0 引言

现阶段，根据无人机侦察对象的不同，多无人机协同侦察问题可分为“点对点”协同侦察［2］和“点对面”协同侦察两个方面［3］。

“点对点”协同侦察即侦察对象为点目标群，要求无人机以最小的时间代价完成侦察任务。如文献［4］将多无人机侦察点目标群的航迹规划问题先转化为多旅行商问题，然后利用遗传算法求解得到各任务航迹。但该算法仅限于点目标群规模较小的情况。为解决大规模点目标群的侦察问题，文献［5］首先对点目标群使用K-means 聚类算法，将多旅行商问题分解为单旅行商问题，然后利用优化后的遗传算法对问题进行求解。

“点对面”协同侦察即侦察对象为广域面目标，需要无人机能够对该任务区域进行全覆盖侦察，常用的覆盖方式有扫描线法［6-7］、栅格法［8］等。如文献［9］在保证区域全覆盖和满足无人机动力学约束的前提下，对无人机编队的转弯时机和转弯位置进行调整，完成了区域覆盖搜索任务。文献［10-11］根据无人机的性能，将任务区域分解为多个子任务区域，然后将子任务区域分配给各个无人机，由各个无人机使用扫描线法进行区域覆盖搜索，最终实现以最少的转弯次数完成侦察任务。

对于上述两种目标类型的航迹规划问题已有了较为成熟的研究成果，但是以铁路、公路等线目标为侦察对象的多无人机航迹规划问题，相关文献较少。针对侦察线目标的多无人机协同航迹规划问题，结合目标属性及最小时间代价要求，提出了一种基于集中一体化遗传算法的协同航迹规划方法。通过建立基于时间代价的航迹模型和采用集中一体化式遗传算法对模型进行求解，可得到具有最小时间代价的任务航迹。

1 基于时间代价的航迹模型

问题描述：利用m 架无人机对任务区域内的N条河流和道路进行侦察，每个目标均能被侦察到，且不能重复侦察并要求整体任务时间代价最小。

设L={L1，L2，…，LN}为待被侦察的线目标集合，V={V1，V2，…，Vm}为各无人机对应的巡航速度集合。第i 架无人机的位置为（xi，yi），其侦察的线目标数量为ni，且第j 个线目标的端点坐标（xj1，yj1）、（xj2，yj2），满足1≤i≤m，1≤j≤N。则第i 架无人机的航迹时间代价可表示为：

其中，li1表示无人机从起飞点飞向所分配到的第一

个线目标进入点的路径长度，li2表示各线目标之间

的路径长度，即从上一线目标飞出点到下一线目标进入点的路径长度，li3表示侦察各线目标时，在其上空飞过的路径长度，一般与线目标长度近似相等，li4表示从最后一个线目标飞出点返回无人机起飞点的路径长度。d（a，b）表示点a 和点b 之间的几何距离，dj表示第j 个线目标的长度。

则各个无人机侦察航迹的时间代价可以用T=（t1，t2，…，tm）表示。

基于时间代价的航迹模型其目标函数即为：

表示此次侦察任务的整体时间代价由花费时间最长的无人机所决定。

航迹模型的约束条件则为：

其表示所有线目标均被侦察，且无重复侦察。

2 集中一体化遗传算法

对于多无人机协同航迹规划问题的求解方法主要有分层解耦法和集中一体化法。后者是将初始生成的航迹长度当作任务分配代价函数的一个自变量，在任务分配的同时得到侦察航迹，通过不断迭代，来寻找最优解［12］。而分层解耦法则无法得到最优解或次优解。

针对侦察线目标的多无人机协同航迹规划问题，引入集中一体化方法并结合改进的遗传算法进行求解。但遗传算法存在收敛性较差且易陷入局部最优的问题［13］。所以在标准遗传算法的编码、染色体交叉和变异环节进行了合理优化，来弥补标准遗传算法的易早熟和收敛性差等缺点。

2.1 染色体编码

采用集中一体化求解的思想，即可在染色体编码阶段，使得每条染色体上所有基因可对应表示线目标的分配结果，以及各无人机的侦察序列等信息。染色体编码按以下步骤进行。

步骤1：产生一个行数为3，列数为N 的空矩阵E；

步骤2：第1 行的矩阵元素由区间［1，m］中的m个整数随机填入；

步骤3：第2 行的矩阵元素由区间［1，N］中的N个整数随机填入，要求整数无重复；

步骤4：第3 行的矩阵元素由整数1 或2 随机填入，最终形成矩阵E'。

以上是多类型基因编码方式，染色体的基因数由线目标数量所确定，每个染色体包含多个基因，每个基因由无人机编号、线目标编号和进入点编号构成。图1 即染色体编码的示意图。

图1 染色体编码示意图

其表示4 架无人机侦察6 个线目标，其中无人机1 的侦察序列为从起飞点起飞，然后从线目标3的右侧端点进入，再从线目标5 的左侧端点进入，最后返回起飞点，以此类推。

相关说明：定义无人机侦察线目标时，均从线目标的1 个端点进入，另1 个端点飞出；1 表示从线目标左侧端点进入，2 则表示从右侧端点进入。

2.2 适应度求解与优选

染色体的选择采用经典的轮盘赌法来对种群中的染色体进行优选，形成父代染色体种群，且染色体适应度越小，被优选的概率越大。

第s 条染色体对应的适应度为：

式中，Ts表示第s 条染色体其对应侦察序列下的各无人机时间代价的集合。

则整个种群最佳的适应度为：

式中，k 为遗传代数，k=1，2，…，r，fks表示第k 代中第s 条染色体对应的适应度。

2.3 染色体交叉

通过对两个染色体进行交叉操作，使得被选择的两个染色体之间交叉互换若干部分基因，达到遗传繁衍产生子代的作用。集中一体化式遗传算法对染色体进行交叉操作后，能够进一步使得种群向适应度值更优的方向进行迭代，也可以提高算法收敛速度。

首先，对父代染色体种群进行适应度求解及优选，选取父染色体A 和B。然后，随机产生两个不相等整数p 和q（p、q∈［1，N］），将父染色体A 中的第p 和q 个基因与B 中的第p 和q 个基因对应相互交换。为了保证每个目标都被侦察到且最多被侦察到一次，还需进行目标编号冲突检测。完成冲突检测后，再分别将染色体A'和B'中第p-q 之间的基因片段反转，即得到交叉操作后的子染色体C 和D。

相关说明：由于每个线目标要求至多被侦察一次，所以要对线目标的编号进行冲突检测。