基于AC-DSDE进化算法多UAVs协同目标分配

黄 刚 李军华

多无人机协同目标分配优化问题(Multi-UAV cooperative target allocation optimal problem,MUCTAOP)是指在复杂任务环境中,为无人机编队分配一个或一组有序任务,即对有限的UAVs 资源进行合理的分配,同时编队整体效率达到最优[1].文献[2−4]指出多机协同目标分配优化问题具有协同性较高、计算难度大、复杂度高等特点.在目标分配过程中,既要考虑飞行器的性能差异、战场势态的复杂性、任务执行权重等因素;还需要考虑可行的飞行代价、合理的分配算法及各种协同约束条件.

近年来,为了解决多机协同目标分配问题,研究者们提出了很多优秀算法.这些协同目标分配算法主要可以分为三类:

1) 基于数学规划法的协同目标分配

数学规划法是解决集中式分配问题的经典方法;在处理维数较低的分配情况时,该方法简单灵活,求解速度较快;但在处理维数较高的情况时,求解的难度呈指数级增长,且要求已知研究对象所有的信息,将复杂作战环境信息过度简化,因此仅适合低维的简单任务环境问题求解.例如匈牙利算法[5]、混合整数线性规划法(Mixed integer linear programming,MILP)[6]、动态规划法[7].

2) 基于协商法的协同目标分配

协商法能够有效解决分布式目标分配问题,该类算法计算灵活,可以将不同层次的分配问题,在各个节点上进行分布处理.但在复杂任务环境中,随着分配规模的增大,系统的鲁棒性较差;同时,对协同约束的处理能力较差,致使其实现效果偏差较大.例如基于合同网的协商算法(Contract net based negotiation algorithm,CNBNA)[8],基于共识捆绑算法(Consensus-based bundle algorithm,CBBA)[9].

3) 基于进化算法的协同目标分配

该类算法是建立在自然选择与群体遗传基础上的寻优算法,实质上遵循“优胜劣汰”和“适者生存”的思想,具有较高鲁棒性和广泛适用性.但是该类算法容易出现局部最优解,收敛速度较慢,以及停滞等现象[10−13].例如遗传算法[14]、粒子群算法[15]、蚁群算法[16]、差分进化算法[17]等.

由于人们对无人机系统需求不断提高,尤其是三维真实环境和异构多无人机体系构建,使该领域的研究更注重复杂高精,密切贴合实际等要求.数学规划法与协商法在目标分配过程中都简化了三维真实环境.进化算法灵活的编码结构适合复杂三维问题的建模和求解[18].因此,进化算法逐渐成为多机协同目标分配研究方法之一.其中差分进化算法(Differential evolution algorithm,DE)运行稳定、收敛速度较快、空间复杂度较低,在处理高维问题中显示出较好的结果.因此,本文重点研究基于DE的多无人机协同目标分配.

尽管DE 算法已经很好地处理多无人机协同目标分配问题,但在处理高维复杂环境下多机协同目标分配仍然存在如下难点:

1) 现用的进化策略进行目标分配求解时,往往只关注优化的某一个方面,选择适合探索(寻找更多全局最优区域)和开发(加速收敛到最优区域速度)的适当繁衍方案是一个两难选择.例如,具有高随机性的变异方案侧重于探索,而贪婪的变异方案侧重于开发,这就导致了在解决组合优化问题时存在不足.针对不同策略的改进和混合,以平衡探索性与开发性也是目前的一个难点.

2) 如何构建符合实际问题约束函数,文献[14,17−18]采用了大量的约束,但文献中仍假设无人机具有相同航程,不变的速度;虽然简化了问题的复杂度,但忽略了实际战场中异构UAV 自身不同的性能.因此构建合理实际的约束函数才更符合真实优化目标的需要.

为解决这些难点,本文提出适用于三维环境下多无人机协同目标分配的近似聚类混合双策略差分进化算法(Approximate clustering dual-strategy differential evolution algorithm,AC-DSDE).该方法有助于平衡种群的多样性与收敛性;然后,结合归档技术的代间变异方法取代原来的随机灭绝,以增加搜索覆盖范围的可控性;最后,构建加权混合适应度函数,在文献[22]的基础上,限制无人机载弹量,即限制无人机可执行的任务数.其方法的主要特征和优点描述如下:

1) 首先,根据父代种群适应度值将个体分成“开发性个体”与“探索性个体”两个子种群,“探索性个体”能够有效识别问题空间中的最优解区域;“开发性个体”能够加速优化收敛的速度.通过这种方式,在进化过程中可以根据不同性质的个体指导种群的进化.其次,采用混合双策略变异方案,使每个个体根据搜索进程,动态调整变异策略,有助于探索性与开发性达到平衡.然后,结合归档技术与代间变异率来储存一定数量的较优收敛的个体,避免进化过程中种群的随机变异,导致已经搜索到的优解变得无效;同时建立选择概率函数,选择一定数量的“探索性个体”与“开发性个体”,有助于收敛的过程中跳出局部最优解.

2) 构建加权混合适应度函数,将估计航程代价、航程时间和约束违背量之和作为适应度函数;加入载弹量约束,限制无人机巡游模式中执行目标数,将问题的约束作为惩罚函数应用于进化算法的重要评价阶段,使得运行过程更加符合真实的战争环境.

1 相关工作

1.1 差分进化算法

差分进化(Differential evolution algorithm,DE)算法[17]类似于很多经典的进化算法,是一种高效的全局优化算法.种群中每个个体对应一个解向量,通过不同的突变策略产生新的个体,交叉算子根据个体与目标个体进行混合,生成实验个体;选择算子根据实验个体的适应度值与目标个体的适应度值相比较,决定下一代个体.在算法终止前,变异、交叉和选择构成了DE 的主循环.

1.1.1 初始化种群

在解空间中随机均匀生成NP个个体:

式(1)与式(2)中NP代表种群的大小,D表示解空间的维度,表示种群中第i个“个体”的第j个“基因”的下界,表示种群中第i个“个体”的第j个“基因”的上界,xj,i(0) 表示第0 代中第i个“个体”的第j个“基因”,rand(0,1)表示在(0,1)区间内均匀分布的随机数.

1.1.2 变异

初始化种群后,DE 算法通过变异算子从种群中随机选取两个个体作差,所得的差向量加权后与第三个个体求和产生变异个体;其中,针对不同的问题有不同的变异策略,这些变异策略影响着种群的进化.下面列出了5 种常用的变异策略:

1) DE/rand/1

式(3)～ 式(7)中,r1,r2,r3,r4,r5 是在[1,N]中随机选取的5 个整数且r5,xi(g) 表示第g代种群中第i个个体,xj,best(g)表示第g代种群中最好的个体,vj,i(g+1) 表示变异个体.参数F是缩放因子,F值的大小直接影响算法的全局寻优能力.F越小,算法对覆盖问题空间精细搜索能力更好,但收敛速度会变慢.F越大,收敛速度更快,算法能够跳出局部最优,但可能出现丢解的情况;同时F值的大小影响种群的多样性[17].

1.1.3 交叉

在变异之后,DE 通常执行二项式交叉操作,交叉是由交叉率CR决定,其从xj,i(g) 和vj,i(g+1) 进行部分交换以形成新的试验向量uj,i(g+1) :

式(8)中,CR是交叉率,决定子代、父代与中间变异体之间交换个体基因大小程度.CR的值越大,种群的多样性随之增加;CR的值越小,种群的多样性也会减少,不利于全局寻优.

1.1.4 选择

DE 采用贪婪算法来选择进入下一代种群的个体,该算子从试验向量uj,i(g+1) 和原始向量xj,i(g)中选择更好的个体进入下一代:

式(9)中,f(x) 是根据具体问题构建的适应度函数.例如,构建目标函数,对于求最大化问题时,具有较高适应值的向量被选择到下一代.

1.2 MUCTAOP

多无人机协同目标分配最优问题,旨在多任务分配过程中求解最小的航程代价.文献[18]指出多机协同目标分配是一个多模式、多约束、计算难度大,杂度呈几何级增长的最优化NP 问题.这就要求必须对目标分配问题进行统一建模,明确飞行器执行的层次和阶段,才能获得较好的分配结果.

Ramirez 等[2]提出了加权随机策略生成突变的新个体,该策略将搜索的重点放在找到解空间中最好的解,虽然提高了收敛速度,但忽略了种群的多样性.Ramirez-Atencia 等[19]提出多目标遗传算法解决协同分配问题,该方法通过变量两两组合(飞行距离、飞行时间、飞行数量、燃料消耗),根据评级的方式,获得了较好的分配方案.Wang 等[20]以智能体加速度作为控制输入,考虑了限制加速度和速度的物理约束,提出了基于梯度的算法以最小化性能度量并确定最佳轨迹.魏政磊等[21]采用了灰狼优化(GWO)算法对多无人机任务分配模型进行求解,该方法在二维仿真场景中取得了较好的效果,但未考虑三维复杂场景.Zhao 等[22]研究了三维环境中多机协同统一分配方法.建立仿真战场环境,在研究三维环境中多无人机协同目标分配具有较好的指导作用;因此本文在该建模的基础上进行扩展,加入了无人机载弹约束,即限定了无人机可执行目标点的个数.

MUCTAOP 的场景具体描述为在复杂的三维环境中攻击一组目标的一组无人机N={U1,U2,···,Un}.该问题的目的是找到一组分配序列M={T1,T2,···,Tm},其具有最短的估计航程代价、最短的飞行时间和最小的约束违背.其典型的场景和仿真环境如图1 所示.

图1 中三维仿真场景包含10 架UAVs 和10 个目标点,圆圈代表无人机的位置坐标,五角星代表目标点的位置坐标,威胁障碍物包括山地形与雷达辐射区(半球型)的结合.无人机与目标点的对应关系由垂直切面与山地形的交线和可飞行航迹组成,即为图中显示的实线部分.

图1 MUCTA 在三维任务环境中的场景Fig.1 Simulation diagram of MUCTA in a three-dimensional environment

2 AC-DSDE For MUCTAOP

2.1 随机分组和自选分组

在解决多机协同目标分配时,种群中的个体即为备选解,备选解的优劣直接影响搜索算法寻优效率的高低.因此在进化之前需要对种群进行有效地划分.划分方法有两种:随机分组和自选分组;种群中个体随机分组,旨在种群中的个体尽可能探索到种群的未知区域,对空间有较大的覆盖性.但是该方法不能快速搜索到最优解,甚至出现不收敛的现象.例如Crowding 聚类小生境方法[24],该方法引入了新的参数CS(聚类大小),设置参考点R,在种群中找到最近的个体X到R,X及其最近的CS−1 个体形成新的子种群,流程如算法2 所示:

自选分组方法如Speciation 聚类小生境方法[24−25].本文结合该方法引入父代种群的适应度值,从每一代中,选取整数作为聚类大小CS,小生境数为NP/CS.将父代种群适应度值进行排序,最好的个体定义为参考点,参考点及其近邻CS−1 个个体形成新的子种群,流程如算法3 所示:

从“探索性”子种群中挑选个体可以帮助保持种群的多样性,从“开发性”子种群中选择个体可以帮助快速收敛到最优个体.具体操作方法如下:将整个种群划分为若干个子种群,然后根据个体的适应度将每个子种群细分为数量相等的部分.如图2 所示,父代种群中包含“探索性个体”和“开发性个体”,首先将父代种群进行排序,设定聚类大小为CS=2,形成两个子种群.

2.2 动态混合进化策略

上节已经将种群划分成“探索性”与“开发性”两种不同的子种群.探索初期,随机搜索的探索性应该比精细化搜索的开发性比重大,选用DE/rand/2 快速识别空间中最优解的区域,然后选用DE/best/2 优化收敛的速度,确保在搜索的最后阶段,精细搜索趋于主导地位.因此,探索性与开发性得到了平衡,算法的整体性能得到了提高.混合策略产生新个体如式(10)所示:

此外,之前曾分析过缩放因子F值的大小直接影响算法的全局寻优能力.F越小,算法对覆盖问题空间精细搜索能力更好,但收敛速度会变慢.F越大,收敛速度更快,算法能够跳出局部最优;因此,在产生新个体的过程中,设定动态缩放因子Fd代替静态缩放因子F非常重要.Fd设置如式(11)所示:

图2 个体分组Fig.2 Individual grouping

2.3 归档技术

本节结合了代间变异率与归档技术取代了原先的随机重置,以增加搜索范围的可控性.在进化过程中,最优解在整个种群中反映的信息量较低,随着迭代次数的增加而极可能被覆盖,使之前的搜索变得无效,导致信息的不连贯和资源浪费.因此在世代间灭绝操作时,建立合理的选择算子概率模型与使用归档技术非常有必要.在存档中保存当前种群中一定数量的较优个体,将其它的普通个体全部重置,直到搜索结束.保存收敛的个体和代间变异可能找到的最优解,避免种群突变带来的资源浪费.

选择算子概率如式(12)所示,适应度越大的个体被选中的概率越大,同时设置代间变异率(Intergenerational mutation rate,IGMR)为0.3.该方法能避免进化过程中优秀个体的彻底消亡,在保持种群多样性的同时,也加速了收敛速度.

图3 (a)表示每代计算的个体适应度值,经过选择算子计算后得出较好的收敛个体存储在归档库图3 (b)中.

2.4 完整AC-DSDE 算法框架如下:

图3 个体分组Fig.3 Individual grouping

2.5 目标分配模式

多机协同目标分配可按UAVs 和目标点对应数量进行分类.本文中取N,M分别代表无人机的数量与目标点的数量,按数量对应关系可分成以下三种不同的模式[22]:

1) 模式1:当N=M时,该模式任务分配关系较为简单,每架UAV 分配一个目标点,每个目标点分配一架UAV,UAV 与目标点是一一对应的关系;该模式计算复杂度较低,求解的关键在于分配过程中如何避免目标竞争引发的冲突,如何利用协同降低毁伤概率,使总的适应度值最大.

2) 模式2:当N>M时,该模式任务分配关系较为复杂,每一个目标点可以分配多架无人机,每架无人必须执行一个目标点,UAVs 与目标点是多对一的关系;该模式对应关系不平衡,导致计算复杂度较高,问题求解的关键在于严格的时间约束导致多机协同困难.

3) 模式3:当N

2.5.1 分配模式统一建模

多机协同目标分配等同于运筹学中的指派问题.现假设有N架无人机,打击M个分布在不同位置的目标.要求构建目标函数考虑航程距离最短、总飞行时间最少和约束违背最小,并且能够统一处理N=M、N>M和N

其中,d(i,j)是无人机i到目标点j的距离,该距离利用垂直切面法估算航程代替直线,该方法虽然不是最短的航程,但是充分考虑了三维地形信息,比直线距离更接近最优航程;wj是目标j的权重且0

2.5.2 协同约束函数及协调关系:

1) UAV 与目标点决策变量约束:当N ≥M时,UAVs 数量大于等于目标点的数量,此时任务决策为:每架UAV 必须执行一个目标点,每个目标点必须被一架UAV 执行;当N

式(15)和式(16)分别表示了两种不同决策对应的关系.

2) 最大航程约束D(km) :不同的模式下,最大航程代价指所有分配关系的估计航程代价的总和;该约束体现了各UAVs 自身性能,比如油耗、有效通信等.

式(17) 中d(i,j) 表示估计航程代价,Di表示各UAVs 的限定的最大航程距离;式(18)表示无人机i执行任务j,若无人机i超出其自身限定的最大航程距离将对其进行惩罚.

3) UAVs 最小/最大速度约束V(km/h) :

式(19) 中V(i)min表示无人机i的最小速度,V(i)max表示无人机i的最大速度;式(20)表示若无人机i超出限定的最小速度或者最大速度将对其进行惩罚.

4) 最大航行时间约束T(h) :表示协同分配结果中执行目标耗费时间最长的无人机,最大航行时间也是规划完成的标志.

根据式(17)最大航程约束与式(19)最大、最小速度约束,可以计算出最大航行时间;式(22)表示若无人机i实际航行时间超出其限定的最大航行时间将对其进行惩罚.

5) UAVs 最大载弹量约束Umissile:该约束体现了UAVs 最大载弹量.即在模式3)中,单架无人机在巡游过程中执行任务数量不可以超过其有效地载荷量.

式(23)表示无人机i的载弹量应小于其最大的载弹量;式(24)表示若无人机i的载弹量超过其最大载弹量将对其进行惩罚.

6) 目标点之间的时序约束Tsort:该约束体现了目标点之间的执行顺序,重要的目标点必须优先执行,其他目标点根据其约束依次执行;

式(25)表示目标点j必须晚于目标点j+τ执行,τ为正整数.式(26)表示若目标点Tj,Tj+τ不符合限定执行次序则进行惩罚.

7) 等待时间约束Twait:为了确保模式一与模式二中部分UAVs 同时到达指定目标,允许部分UAVs 等待一段时间后再出发.

式(27) 限定各无人机到达目标的等待时间;式(28)表示各目标点被攻击时间的交集不可超过时间段σ,通常σ时间段认为是极小的,可根据真实战场势态进行调整.

该模型针对三种不同分配模式建立了统一的分配关系.将航程代价、时间代价与约束违背量之和作为适应度函数.在进化前,建立UAVs 与目标点的估计航程代价库,进化时通过查找估计航程代价矩阵,可以大幅提高计算效率.

3 实验结果和分析

为验证改进后的AC-DSDE 算法处理MUCTAOP 有效性,本文在Matlab R2016a 进行多组仿真实验.实验包括以下部分:1) 选取数量较少的UAVs 和目标点验证改进算法的有效性;2) 选取数量较多的UAVs 和目标点验证改进算法能够有效处理复杂环境下目标分配;3) 将改进的AC-DSDE与同类算法进行比较.

表1 中“Upos”、“Tpos”、“Rpos”分别表示无人机、目标点和雷达的坐标;“W”表示各目标点的权重;

表2 设定了两组不同实验参数.“Un”表示UAVs 的数量,“Tn”表示目标点的数量,“Pn”表示种群的规模,“Gen”代表进化迭代次数.因为差分进化算法是随机搜索算法,为了验证解的一致性,本文设置“Num”参数对同一情境下进行多次实验.

3.1 验证改进算法的有效性

图4 显示了实验1 分配结果,其中圆圈代表UAVs 的三维坐标,星形代表目标点三维坐标;同时,本文将每个坐标进行编号,以便后续统计分配数据.从图中看出基于AC-DSDE 算法的多机协同分配能够在多雷达区域和目标点随机分布的三维环境中,充分结合了整体山地形,有效地处理三种不同模式下的分配问题.

表3 表示实验1 中三种不同模式下无人机与目标点最优分配的结果;其中UAV 表示UAVs 分配序列,Target 表示对应的目标点分配序列,Cost 是UAV 与Target 对应的总航程代价,包含了航行距离、飞行时间等.同时,仿真数据均符合三种模式无人机与目标点之间的对应关系.图4 与表3 表明了改进的AC-DSDE 算法能够有效处理三种不同的模式,并找到相对应的分配方案.

3.2 验证算法处理复杂环境的有效性

为验证算法处理复杂环境的有效性,本节中选取了5 个评价指标对算法的性能进行评价:

表1 实验初始数据Table 1 Initialization of experimental data

表2 两组实验进化参数的设定Table 2 Setting of experimental evolution parameters of two groups

3) 最优代价Cbest:多组实验中最小代价值;

4) 约束违背:最优解中约束违背量总和占最优代价的百分比,该评价指标衡量了算法的协同性能.

5)“优解”表示陷入局部最优的次数和当前优于平均代价的次数占实验总次数的百分比.

其中,平均代价和最优代价都是综合了航程代价、时间代价和各种约束违背量的适应度值.

表4 分别统计了实验1 与实验2 的数据,可以得出以下结论:

图4 三维环境中实验1 的仿真结果Fig.4 Simulation results of Experiment 1 in a three-dimensional environment

图5 三维环境中实验2 的仿真结果Fig.5 Simulation results of Experiment 2 in a three-dimensional environment

表3 实验1 的分配结果Table 3 Assignment results of Experiment 1

图6 实验1 分配结果的单条收敛曲线Fig.6 Single convergence curve of Experiment 1 assignment results

1) 实验1 算法运行时间较短,且能得到较好的分配结果,数据表明所提出的AC-DSDE 算法能够有效地处理不同模式下的多无人机协同目标分配问题;

表4 两组实验分配结果的统计数据Table 4 Statistics of the results of the two groups of experimental assignments

图7 实验1 分配结果的单条和平均收敛曲线对比Fig.7 Comparison of the single and average convergence curves of the results of Experiment 1

2) 实验2 尽管增加了UAVs 与目标点的数量,算法中的执行效率有所降低,但是AC-DSDE 在有效的时间内搜索到最优解.

3) 各模式中平均代价值与最优代价值接近,表明改进算法搜索的结果接近全局最优解.

4) 较小的协同违背率证明改进算法协同能力较强.较高的优解率说明了实验发现最优解的可能性较大.

3.3 AC-DSDE 算法的性能

表5 AC-DSDE 与其他算法之间的比较Table 5 Comparison between AC-DSDE and other algorithms

图8 不同算法的平均收敛曲线Fig.8 Average convergence curve of different algorithms

本节将从单次实验收敛曲线与多组实验平均收敛曲线进一步研究AC-DSDE 算法处理多无人机协同目标分配的性能.

1) 单次实验收敛曲线与多组实验平均收敛曲线

图6 中实线表示单次实验的收敛曲线,并且显示改进算法进化迭代过程中的最优解以及代间变异随机搜索到的最优解,分别用圆圈与星号表示.从收敛曲线可以看出代间变异不仅增加了种群的多样性,而且找到了更多的优解.图7 是单收敛曲线与平均收敛曲线的对比,单收敛曲线和平均收敛曲线具有相似的收敛趋势,搜索前期能够快速收敛到优解区域,后期能够很快地收敛到最优解.因此ACDSDE 具有较好的收敛性能.

2) AC-DSDE 与同类目标分配算法之间的比较

本节将改进后的AC-DSDE 算法、DMDE 算法[22]与APC-DE 算法[26]进行比较.实验所采用的进化参数、种群规模、迭代次数相同.表5 中,变量CR表示交叉率,变量MR 表示变异率,变量IGMR 为DE 算法的代间变异率.图8 是不同算法的平均收敛曲线,表5 和图8 显示,AC-DSDE 算法总的航程代价值最小,收敛速度最快,执行时间最短.尽管其他两种算法都能在一定的时间内找到最优解,但总的航程代价值较高且需要更长的执行时间.

4 总结

本文提出了基于AC-DSDE 混合双策略差分进化算法以解决无人机协同目标优化分配.首先,为了提高算法的性能,提出了混合双策略动态变异的方法.该方法根据不同类型的个体选用不同的变异策略,同时构建动态缩放因子Fd,解决目前进化过程中存在的探索性和开发性平衡的问题.然后结合归档技术与代间变异方法,在增加了种群的多样性的同时,也保证了收敛个体不会随着迭代次数消亡.最后扩展原有的约束条件,增加了UAVs 的载弹量约束,限制UAVs 可执行的目标个数.仿真实验表明,该方法能够有效快速地解决多无人机协同目标分配问题,且协同能力强.

对于下一步工作,将着重考虑差分进化算法在多无人机协同航迹规划方法的研究,如何有效降低三维空间复杂度,获得关键路径点的集合,保证最终航迹是安全且可行.