基于改进型遗传算法的多无人机任务分配

徐宾王，宁 芊

（四川大学电子信息学院，成都 610000）

0 引言

无人机（unmanned aerial vehicle, UAV）因其成本低、灵活性高、隐蔽性强而被广泛应用于战场侦察、联合攻击、应急救援等行动［1-2］。无人机集群相对于单架无人机在执行任务上有更多的优势，可以执行更多样化的任务，以及更高效地进行大范围搜索［3］。

对于无人机航迹规划问题，优化算法可分为两类［4］。第一类是传统优化算法，例如动态规划算法、A*算法、Dijkstra 算法、随机搜索树算法等［5-10］，该类算法为确定算法，搜索解空间范围较大、效率较低，只适合场景和约束简单的情况；第二类是群智能优化算法，例如遗传算法、粒子群算法、蚁群算法、差分进化算法等［11-15］，该类算法往往具有显式的并行性，因此搜索解的效率更高，另外有较好的鲁棒性和收敛性等优势。群智能优化算法存在产生劣质搜索过程的问题，在算法上针对该问题进行优化能有效提升算法性能。

无人机个体任务分配是一个无人机集群行为决策所需面临的重要问题。相比于单架无人机，多无人机协同任务分配需要建立更加复杂的数学模型，解决随之带来的复杂度提升问题非常重要。在军用场景中往往存在探测雷达和攻击武器等两种对我方无人机侦察活动的威胁，该类威胁在大部分研究中往往被设置为静态威胁，实际上也存在威胁为动态的情况［16］，对于该情况算法应采取不同的处理方式。

目前群智能算法，例如蚁群算法（ACO）、遗传算法（GA）、粒子群算法（PSO）等，是用于解决无人机任务规划问题的主流算法，但在算法收敛速度、搜索解的效率、算法运行速度等方面，传统的群智能算法仍存在改进的空间。Han 等［17］提出了一种避免近亲繁殖的机制和一种分层变异规则来解决局部极值问题，还提出了突发威胁对策机制，以提高算法在检测到突发威胁后快速收敛的能力。Roberge 等［18］提出利用图像处理单元对遗传算法加速的方法，结果表明其算法速度相较于在CPU上提升约48倍。

通过对相关文献的分析，在以下几个方面还可以再做改进：

（1）在三维空间中对无人机任务进行分配，考虑雷达火力等威胁以及地形约束；

（2）设置动态威胁，在算法上针对随时间变化的威胁做出优化。

1 问题建模

1.1 问题描述

假设有n个基地，这些基地需要派出无人机执行侦察任务，一共需要侦察m个任务点（Mission Point），空间中存在地形障碍，敌方探测雷达，敌方火力覆盖区域等威胁。将m个任务点按照整体代价较小的方式分配给n个基地，每个基地的无人机从基地点出发按照该分配方式的顺序依次遍历为其分配的若干任务点。

基地任务点分配结果和顺序可通过零一矩阵的方式来进行描述：

AssignResult={Aijk}N×M×M，其中有i∈[0,n)和j,k∈[0,m)。

其中：Aijk= 1 代表第i个基地第j个选择遍历的任务点为k；反之如果其等于0，则代表该基地遍历到第j个点时没有选择任务点k。

该矩阵需要满足以下三个约束：

（3）同一个任务点在同一个基地的多次选择遍历时只能被选择一次，需满足

第i个任务点分配结果的代价为

该式表示无人机从基地点bi出发依次经过m个任务点pj后返回基地点bi的代价，其中pj为分配矩阵{Aijk}N×M×M中索引为i的基地点选中的为矩阵中值为1 的任务点；Cpq代表点p和点q两点线路的代价，并且遍历顺序为索引j从小到大的顺序。

该分配方式的总代价为

算法优化目标为总代价最小，即：

对以上问题做出如下假设前提：

（1）环境信息已经提前获得，雷达和火力为动态威胁，其运动规律已知；

（2）任务点位置固定，需完成对所有任务点的遍历，且同一个任务点只侦察一次；

（3）每个基地派出的无人机速度恒定，完成任务点的遍历后需返回原基地。

1.2 代价函数模型

任意两点连线间代价由两部分构成，静态代价，如地形和航程所带来的代价；动态代价，如雷达和火力带来的代价。由于动态代价存在较强的时序性，因此无法在确定具体的基地任务点分配方式之前计算出该情况下的动态代价。

对于静态代价，可以采用将任意两点间代价提前计算出的方式，把计算出的数据做成一张路径——代价表，之后在需要任意两点间代价时可以直接查询该表。静态代价由路径长度产生的航程代价（Voyage cost）构成，该代价可由两点间欧式距离计算得到。

探测雷达覆盖范围和火力覆盖范围滞留代价采用同一计算方法。假设有M个雷达，设某一个雷达为Raday，该作用范围为R，此时的威胁代价为Threatxy，已知雷达中心坐标随时间函数，即可采用空间中两点间距离公式求出路径点Rx到雷达中心点RPxy距离为Dxy，有：

该路径点的总代价Threatx为

该路径总威胁代价ThreatCost为

设两点间总代价为TotalCost，探测雷达滞留代价为DetectorCost，攻击雷达滞留代价为WeaponCost，加以权重则有：

对于一个基地（Base）而言，算法可能为其分配多个任务点（Mission Point），设为该基地分配了K个任务点，基地的无人机依次遍历这K个任务点再回到基地，一共产生K条路径。

此时这种分配给该基地这些任务点的方式总代价为这K条路径代价的总和，对于多个基地则将每个基地所分配任务点的代价累加起来，即可得到总代价。

1.3 任务约束

算法为无人机基地分配任务点时需要考虑无人机的物理特性，因此存在以下约束使算法运行结果符合实际情况：

（1）地形障碍约束。

无人机实飞路线不能穿越地形，即在同样的横纵坐标情况下，无人机高度应高于地面，设无人机t时刻坐标为(xU(t),yU(t),zU(t))，地形函数为zT=terrian(x,y)，则应满足如下约束：

（2）最大航程约束。

为了确保无人机的燃油储备能够支持无人机完成所有规划任务点的侦察任务，各个基地间需要协同规划，均匀分配任务点，即任意基地i执行侦察任务的飞行总距离LiS和无人机最大航程Lmax间满足如下约束：

（3）最大转弯角约束。

由于无人机本体性能限制，无人机实飞过程中完成大转角动作非常困难，为规划出实际可行的任务点遍历方式，空间中两相邻航路段间的夹角α和最大转弯角αmax满足约束条件：

为将问题转化为无约束组合优化问题，引入惩戒因子ζ，设Pi为基地i不满足约束的路径点个数，基地i的惩戒代价满足

算法优化目标为

1.4 环境模型

为符合无人机实践飞行的环境，采取函数拟合山区地形的方式对地形等静态威胁进行建模，地形建模基于文献［19］所提出的函数模拟法。

雷达和火力的覆盖模型如下：

其中：Si表示第i个雷达或火力的覆盖范围的点集，为一个球体的范围；Ri为该雷达的辐射范围；(xRi,yRi,zRi)为该雷达的中心点坐标。

雷达或火力武器的运动轨迹假设为空间中圆形轨道，方程如下：

其中：TRi为运动轨迹的半径；(xRi,yRi,zRi)为运动轨迹的中心坐标；t是参数方程的自变量取值，范围为[ 0,2π ]。

2 改进型遗传算法

2.1 遗传算法流程

遗传算法受自然界生物的进化过程启发，通过程序模拟生物染色体的交叉变异以及淘汰过程来解决寻优问题，本文采取的染色体编解码方式同文献［20］，遗传算法的整体流程如下：

（1）初始化起始种群染色体；

（2）计算初始种群个体适应度；

（3）选择当前种群个体进行染色体交叉变异产生子代种群；

（4）计算子代种群个体适应度；

（5）将子代种群作为当前种群，并判断是否迭代到一定次数或者种群适应度停止变化代数是否达到阈值，如果是，则停止迭代返回结果；否则回到第三步。

2.2 分组并行缓存优化算法

遗传算法并行性体现于个体适应度计算，并且该部分是遗传算法较为耗时的部分。采用多线程的方式并发计算种群适应度能够使算法运行时间大大减少。

定义一个基地的任务点及其遍历顺序为该基地的分组，在计算种群适应度时，先将该种群中所有基地的所有不同分组统计出来，再来利用多线程并发计算每个分组的代价。将并发的方式从并发计算个体适应度变为并发计算分组代价，即可消除在计算当前种群的适应度时的计算冗余。

上述方法不能解决不同代种群分组计算的冗余问题。本文建立了一个分组代价缓存机制，缓存的键为基地分组，值为该基地分组的代价。在计算每一代种群的适应度时确定当前基地分组是否命中缓存，未命中则记录下当前基地分组，在遍历完所有个体的基地分组后得到仍需要计算的基地分组，之后再并行计算这些基地分组的代价，计算完后将这些基地分组代价写入分组代价缓存中。计算流程如图1所示。

图1 分组代价计算流程

2.3 竞争策略

传统遗传算法在算法性能上存在改进空间，可通过改进遗传算法机制使其寻优能力和收敛速度得到提升。传统遗传算法在运行时，当前种群中最优个体的适应度往往随迭代次数震荡上升，输出解适应度随迭代次数增长也比较缓慢，并且由于多旅行商问题搜索空间非常大，算法收敛也相对困难。

基于此，本文采用了改进的淘汰策略。传统遗传算法将子代种群直接作为下一代种群来进行迭代，进行随机染色体交叉产生子代的适应度不一定比亲代更高，原因可能是高适应度亲代个体染色体对应某个基地任务点分组的代价较小，而染色体交叉操作破坏了该分组，因此传统遗传算法在进行解搜索时会产生劣质搜索过程。本文在产生下一代种群时，将亲代种群和子代种群进行混合，将混合后种群按照适应度从高到低排序，再选择所有适应度排名为前一半的个体，将其作为下一代种群个体。

3 算法仿真

为验证算法的有效性和可行性，算法运行的平台为64 位Windows 10，Intel Core i5-9300H CPU（2.40 GHz），16 GB RAM，算法基于C++11编写，算法编译器为Visual Studio 2017。场景设置为5 个基地，15 个任务点，空间中存在两个探测雷达和攻击雷达以及地形和山峰，四个雷达均沿与水平面平行的圆形轨道运动。具体信息见表1～表3。

表1 雷达和武器信息

表2 代价权重

表3 基地任务点坐标

3.1 改进型遗传算法结果

最终规划出的任务分配效果三维图和俯视图分别如图2和图3所示，其中网格线部分为雷达和武器作用范围，圆形实线部分为相应雷达武器的运动轨道。

图2 基地任务点分配结果三维图

图3 基地任务点分配结果俯视图

根据规划结果可以看出，算法输出解得到的基地任务点分配方式能够避免因穿越地形产生绕行代价，并且能够在一定程度上减少在雷达和火力范围内的滞留时间。

3.2 算法对比

此部分设置了遗传算法与模拟退火算法的对比，以及遗传算法自身在改进前后的对比。模拟退火算法（SAA）没有种群概念，为保证与遗传算法对比的公平性，对比实验中设置400个模拟退火算法并行运行，参数设置见表4～表5。

表4 遗传算法参数

表5 模拟退火算法参数

由于改进型遗传算法相较于原遗传算法有两点不同，所以本文设置了三组对比实验，分别为原始遗传算法（GA）、缓存优化型遗传算法（Cache Optimized GA）和缓存加机制优化型遗传算法（Cache And Mechanism Optimized GA），从运行时长、输出解适应度以及寻优能力三个方面比较这三种算法。在该平台分别运行三种算法各10次，结果见表6和表7。

表6 算法运行时长

表7 算法输出解适应度

从表6 实验数据可以得出，模拟退火算法在运行时间上相较于原始遗传算法有较小的优势，但相较于最终缓存加机制优化型遗传算法还有不小差距。遗传算法在改进前后，10 次实验取平均值，缓存优化相较于原始遗传算法减少了约37%的运行时间，而机制优化则在这个基础上再减少了约88%的运行时间，算法运行效率上的提升较为明显。

可以看出模拟退火算法在输出解适应度方面比遗传算法差，搜索效率较差。遗传算法自身改进前后对比方面，机制优化对最终输出解适应度略有提升，缓存以及机制的优化使遗传算法搜索解的效率显著提升。

图4 分别为最终改进后遗传算法、原遗传算法和模拟退火算法输出解适应度随种群迭代次数变化的情况，改进后的遗传算法拥有优异的性能，能够在较短的迭代次数内收敛到较优解上。

图4 算法解适应度迭代曲线

4 结语

本文针对场景中存在动态威胁情况下GA 速度过慢、收敛性较差等局限性，提出一种基于缓存命中策略和机制优化型GA，通过实验对比可以得出以下结论：

（1）基于分组和缓存思想的优化方式能够有效减少算法运算时间，并且保证算法得到可行解适应度不会下降，为多旅行商问题等NP 难题提供了一种较为有效和通用的优化思路；

（2）淘汰机制优化后的GA 相比之前收敛速度更快，能够收敛到适应度较好的输出解；

（3）设计的算法具有较好的性能，能够有效解决在有动态威胁的复杂场景侦察任务分配问题。

在以下方面还能做出改进：

（1）对未知威胁的应对；

（2）设置不同类型的任务，不同类型任务间存在一定约束，同类型任务点存在一定优先级。