基于改进NSGA-III算法的多无人机协同目标分配

摘 要：武器-目标分配问题是战场环境下无人机对敌方执行打击任务的关键， 其目的是基于目标的威胁、 价值和我方武器的毁伤概率， 寻找合理的武器目标分配方案， 以提高作战效率。 针对当前多目标优化算法解决静态武器-目标分配问题时收敛速度慢、 收敛稳定性差， 难以适应当前战场高度实时性的问题， 提出一种改进的基于参考点的非支配排序遗传算法。 通过二进制编码打击方案并优化初始种群， 引入自适应变异与交叉策略以及种群寻优更新策略， 基于对战场态势进行评估得到的威胁矩阵和优势矩阵， 种群多次迭代后生成目标打击方案。 最后计算满足约束条件的Pareto解集， 并将Pareto前沿中的相对最优解作为多无人机的打击方案。 多次实验证明， 在较好情况下改进算法相比于原始算法的收敛时间减少46.74%， 目标威胁值降低50.5%， 总飞行航程减少26.46%， 杀伤目标数增加11.76%， 证明该算法在解决多无人机空对地打击任务目标分配问题时具有合理性和高效性。

关键词：对地打击； 多无人机； 武器目标分配； 多目标优化； NSGA-III； Pareto解

中图分类号：TJ760； V279

文献标识码：    A

文章编号：1673-5048（2024）04-0100-12

DOI： 10.12132/ISSN.1673-5048.2023.0222

0 引  言

随着无人系统的应用广泛普及， 在当前作战环境下产生了多种新颖的战术样式， 包括多无人机协同作战和跨域无人集群协同作战等。 新战术样式下的武器目标分配（Weapon Target Assignment， WTA）问题是当前多无人机、 无人机集群研究的关键问题， 是单种类任务分配的重要环节。 根据敌我双方态势， 合理为每架无人机分配目标， 以提高多无人机作战效能［1］， 对于无人作战领域来说具有重要意义， 能够通过对无人机有限机载资源的合理分配取得最大化的作战成果。

WTA问题经过几十年的研究， 在算法方面一直快速发展， 大致遵循从单目标优化到多目标优化的趋势［2］。 单目标优化主要求解在给定限制条件下的最优的解决方案， 使目标函数的值达到最优。 李洋等［3］设计了一种基于随机动态规划的动态武器目标分配决策算法， 基于战场态势转移概率采用逆向迭代算法生成序贯拦截方案。 强裕功等［4］建立多约束条件下的武器目标优化分配模型， 基于拍卖算法解决了动态武器目标分配问题。 刘攀等［5］提出一种改进的粒子群优化算法， 引入武器转火时间窗等约束条件， 验证了粒子群算法解决多导弹的武器目标分配问题的有效性。 Kline等［6］针对武器目标分配问题采用实时启发式算法进行求解， 提出一种非线性分支定界算法。 多目标优化需找到一个解决方案使其在多个目标函数下同时达到一个平衡点， 即每个解在所有目标函数下都最优。 吴思聪等［7］构建了UUV集群打击任务分配模型， 引入第3代非支配排序遗传算法求解， 能够更好地为决策提供支撑。 邱少明等［8］针对武器目标分配算法中计算耗时较长、 求解效率低的问题， 提出一种多目标简化群优化算法， 并证明了其较高的计算效率和求解精度。 郑峰婴等［9］提出基于自适应概率引导的多目标粒子群控制分配方法， 根据收敛性指标增加变异因子， 实现操纵面多目标控制分配。

上述文献提出了多种针对WTA问题的优化算法， 但多数只能处理单一目标函数下的优化问题， 而实际的WTA问题往往涉及多个相互冲突的目标， 需要找到一个平衡点。 多目标优化方法存在一定的局限性， 其计算效率和求解质量受限于特定问题的算法和参数设置， 可能无法很好地适应战场环境中的武器目标分配， 导致解决方案的有效性和实用性受到影响。 在本文的WTA问题中， 需考虑最大程度击毁敌方无人机的任务需求， 考虑无人机续航能力、 武器数量等的性能限制， 评估敌方的威胁程度， 包括防空系统潜在的反制措施， 以及考虑地形对任务执行的影响。

遗传算法采取多点并列搜索， 按照适者生存的原理逐代演化产生越来越好的近似解， 因此取得了大量研究成果［10］。 作为遗传算法的衍生方法， 非支配排序遗传算法（Non-Dominated Sorting Genetic Algorithms， NSGA）是一种基于Pareto最优概念的多目标优化算法， 由Srinivas等于1995年提出［11］。 NSGA-III算法［12］由NSGA和NSGA-II［13］发展而来， 能够不受问题性质的限制， 有效地处理复杂问题［14］。

为解决上述问题， 提高战场环境下的多机目标分配问题的求解质量和收敛速率， 本文将WTA问题建模为多目标优化模型， 在NSGA-III算法的基础上， 提出改进ABCSA-NSGA-III（Artificial Bee Colony and Simulated Annealing NSGA-III）算法对其求解， 结合人工蜂群算法和模拟退火算法的优势， 通过算例验证了改进算法的求解质量。

1 多无人机协同目标分配模型

1.1 场景描述

假设当前处于无人机对目标的攻击阶段， 每架无人机需根据战场中的目标信息获取全局的战场态势， 再对所跟踪锁定的目标发射合适的武器以达到摧毁的目的。

为了实现有效的多无人机对地打击协同目标分配， 首先提取出四个关键因素： 目标信息、 武器信息、 无人机性能参数和作战要求。 假设我方拥有n架构型和携带武器类型均相同的无人机， 表示为无人机集合U={u1，  u2，  …，  ui，  …，  un}， U包含n架无人机， 其中无人机载弹集合为W={w1，  w2，  …，  wi，  …，  wnn}， W包含nn枚导弹， n≤nn。 而敌方有m个不同地面目标， 组成目标集合T={t1，  t2，  …，  tj，  …，  tm}， T包含m个不同的目标。 本文的最终目标是将这n架无人机的武器有效地分配给这m个不同的目标， 以执行对地打击任务， 作战想定场景如图1所示， 在目标区域可能存在多个不同类型的敌方目标， 如装甲车、 坦克、 导弹车、 指挥所等， 其具体位置尚未确定， 导弹车应具备雷达和防空导弹， 对我方无人机构成潜在威胁。

1.2 模型约束

根据我方无人机及携带导弹的性能， 在无人机发射导弹时应满足以下条件：

（1） 每架无人机的所有导弹全部被分配给目标。

∑xu，   ij=nn（1）

（2） 一枚导弹只能分配给一个目标。

∑mj=1xu，  ij=1（2）

根据多无人机打击任务的要求， 决策变量xu，  ij存在以下三种分配模型， 如图2所示。

（1） 当我方无人机数量等于敌方目标数量（n=m）时， 在进行分配时需找到一对一的分配关系， 保证每个目标都会被打击。

（2） 当我方无人机数量大于敌方数量（n>m）时， 在进行分配时需为我方多个无人机分配同一目标， 共同执行打击任务。

（3） 当我方无人机数量小于敌方数量（n<m）时， 在进行分配时我方一架无人机可分配多个任务目标， 并按照一定的次序依次打击这些目标， 对无人机的燃油性能要求较高， 但这种情况下完成打击任务所用的无人机数量最少。

综上， 决策变量根据不同的任务模型有

xu，  ij=xu，  i   n=m

xum，  uk，  i n>m

xu，  i，  j n<m（3）

1.3 目标函数

根据1.1节和1.2节对模型的定义和约束， 在本文的WTA问题中， 多无人机的目标分配是指为多无人机组中每架携带导弹的无人机分配一个或多个打击目标， 每架飞机挂载的导弹只能被分配到一个目标， 每个目标可以被一个或多个导弹攻击， 以使整个无人机组的打击效率和资源利用达到最优化。 使用NSGA-III算法对本文的WTA问题进行求解时， 首先需要将目标分配问题转化为一个多目标优化问题。 考虑到打击任务的具体需求， 以最大化我方无人机对敌方目标的伤害、 最小化敌方目标对我方无人机的威胁和最小化总飞行航程为衡量标准， 将目标分配模型定义为

minD=∑nu=1∑mi=1∑mj=1du，  ij·xu， ij

minN=∑nu=1∑mj=1∑mi=1Tu，  i·Psu，  ij

maxF=∑ni=1∑rj=1［1－Psu，  ij］ （4）

式中： minD表示最小化飞行总航程代价； du，  ij为航程代价； xu，  ij为决策变量； minN表示使敌方剩余目标的威胁值最小化； maxF表示最大化对敌方目标的毁伤； Tu，  i为某时刻敌方对我方的威胁矩阵； r为我方无人机携带的导弹数； 目标的生存概率Psu，  ij取决于对目标的攻击情况， 即

Psu，  ij=∏ni=1∏rj=1［1－Ddu，  ij］nmu，  ij（5）

式中： nmu，  ij为目标受到攻击的导弹数量； Ddu，  ij为我方无人机发射导弹对目标的摧毁效果。

Ddu，  ij=ωe·Pdu，  ij·Wsu，  ij， i，  j=1，  2，  …，  m（6）

式中： 0<ωe<1表示环境对导弹杀伤率的影响； Pdu，  ij为无人机u对目标的态势优势； Wsu，  ij为我方无人机携带导弹的理想摧毁概率。

至此， 将目标分配问题转换为多目标优化问题［15］， 下面用NSGA-III算法对问题进行求解。

2 基于ABCSA-NSGA-III算法的目标分配问题求解

2.1 多目标优化问题

将无人机的打击目标分配模型作为多目标优化问题（Multi-Objective Optimization Problem， MOP）研究， 需要同时优化两个不可直接比较且可能相互冲突的目标函数［16］， 意味着要优化一个目标函数的值可能会以牺牲另一个目标为代价。 算法的最优解取决于最后一次迭代中种群的非支配解集， 从而得到Pareto解集［17］， 由于这种相互制约的关系， 通常不存在唯一的最优解， 而是存在一系列权衡不同目标之间权重的解， 称为Pareto前沿。

因此， 本文的目标是寻找Pareto前沿上的目标分配方案， 这些方案在不同程度上优化了多个冲突的目标， 在不大幅度劣化某一目标的前提下改善其余目标。

2.2 标准NSGA-III算法原理

NSGA-III算法的基本思想是通过不断迭代生成一组非支配解集合， 其中每一个非支配解均为最优解的近似。 在每次迭代中， 算法会根据当前解集合中的非支配解生成一组新解， 通过一系列筛选和排序， 生成下一代解集合。 通过这种方式不断同时优化多个目标函数， 最终得到一组最优的目标分配方案。 这样， NSGA-III算法可以在保证种群多样性的同时， 有效地寻找到Pareto最优解集合， 即那些在所有目标函数上都无法被改进的解集合。

标准NSGA-III算法的求解步骤如下：

（1） 随机初始化规模为N的初始种群Pt， 计算种群中每个个体的适应度函数值。

（2） 对初始种群Pt进行非支配排序， 在排序结果中选择较优的个体进行交叉和变异操作， 以产生子代种群Qt。 将两个种群结合， 形成大小为2N的新子代种群Rt。

（3） 进行快速非支配排序， 根据非支配关系保留优良且多样的个体， 组成新的父代种群Pt+1。