蜂群作战的启发式目标分配方法

源自：现代防御技术

作者：魏喜庆, 杜厦

摘要：

由于低成本和智能化技术的发展，蜂群作战正在成为现在的研究热点。随着蜂群规模的增加，高效的目标分配算法成为其中的一个重要研究方向。为了提高目标分配的计算效率，利用目标集群的剩余价值作为优化目标，使用贪婪算法分步选取局部最优解，最终获取目标分配的近似全局最优解。通过对典型目标分配问题的仿真，验证了提出算法的有效性。

关键词: 蜂群, 无人系统, 目标分配, 启发式, 贪婪算法

引言

随着机器人技术、人工智能和通信技术的发展，多智能体的自主编队技术已经成为现实。卫星编队、无人机编队、临近空间飞行器编队、无人舰艇、无人车辆以及混合编队的研究和应用不断涌现^［1-5］。更大规模的蜂群编队已经出现，并在智能化无人系统中取得了发展和应用。2016年，美国国防部战略能力办公室首次进行空射无人机蜂群演示验证，使用3架F/A-18战斗机一次性释放出103架“山鹑”微型无人机，无人机蜂群在空中自主编队飞行，展示了良好的自主决策、轨迹修正和自适应编队的能力^［6］。无人系统的编队作战已经具备了基本的作战能力，而蜂群数量的增加彻底改变了战场作战样式，预计可自主执行攻防任务的高达数万架规模的“超级蜂群”将在不久的将来出现。

面对高复杂性和强对抗性的战场环境，需要充分利用蜂群自主态势感知、信息融合和自主决策能力，其中的目标分配是自主决策能力的一项核心能力。事实上，武器目标分配（weapon target assignment，WTA）问题，较早地被用于解决导弹防御问题，来最大化地实现对来袭导弹的拦截。

李梦杰等^［7］对武器目标分配问题的建模方法、求解算法和实验验证等方面近年来取得的成果做了全面的综述。MANNE^［8］第1个提出了武器目标分配问题的数学模型，在武器对任何一个目标都具有相同杀伤概率的假设条件下，给出了该问题的最优解。随着武器目标分配问题的技术发展，研究者在考虑的问题规模和模型假设简化方面都有所扩展。文献［9］开发了一种非线性分枝定界算法优化武器分配问题，减少目标函数的线性近似所导致求解误差，并使用分枝定界算法来求解非线性问题中较大规模的目标分配问题。文献［10］通过分段线性凸函数逼近WTA问题的非线性项，引入额外变量和约束作为代价，提出了一种称为分支和调整的精确求解方法。该算法建立在现有的分支切割或分支定界算法之上，并且可以使用现有的混合整数线性规划工具来实现。

武器目标分配问题已经被证明是一种N-P完全问题，随着“蜂群”规模的增加，导致目标分配计算量随之指数增加。针对大规模的武器目标分配问题，许多启发式算法被用于快速寻找次优解。文献［11-12］提出了一种超大规模邻域（very large-scale neighborhood，VLSN）搜索算法，使用隐式枚举算法来改进邻域搜索，可以较好地解决大规模实例问题。其他包括神经网络^［13-14］、遗传算法^［15］、蚁群算法^［16］和粒子群算法^［17］在内的多种智能算法，也被应用于武器目标分配问题的启发式求解。文献［9］还创建和测试了一种新的能够实时进行高质量求解的启发式算法。这种启发式方法，在0.01 s内找到大型实例（近百个目标）的解，但通常不能保证最优解。验证发现启发式算法对于较小的实例（10个目标）的解，与原问题的全局最优解相比具有较小的平均误差。针对空间飞行器集群对抗中的多目标分配问题，对可达性、燃料消耗和拦截概率多级指标综合优化，文献［18］提出了采用目标分配指导表构建集群对抗目标分配的决策树，进行遍历搜索得出综合收益最优的目标分配方案。但对于规模更大的实例，其算法的实时性仍需要提升。

本文综合考虑了对目标打击的有效性和提高效率，以武器打击后的目标集群剩余价值作为优化指标，通过贪婪算法构建一种启发式多约束目标分配算法。有效实现对近似最优解搜索的同时，保证在大规模实例应用时良好的实时性。

1 目标分配模型

1.1 目标约束条件

武器目标分配问题可以分为静态目标分配问题和动态目标分配问题。静态目标分配问题指的是单回合作战的情况下，一次性地实现武器目标分配，而动态目标分配问题涉及多回合作战情况下目标分配。因为大多数的实际问题都属于静态目标分配问题，多数动态目标分配可以分解为多个静态目标分配问题，所以本文重点考虑静态武器目标分配问题，具体将其描述为找到一组不同类型武器（拥有不同战斗部的同一种武器可以认为是不同类型的武器）对一组目标的最佳分配，最大限度地提高对目标总的预期杀伤效应。对于m种类型的武器，n个目标分配问题需要考虑下面约束：

1.2 目标优化模型

2 目标分配算法

结束

3 计算复杂度

对于启发式分配算法，在每一次迭代计算时，需要遍历计算每种类型武器对目标的收益值。不考虑武器耗尽的情况，在最严苛的情况要计算m种类型武器对n个目标的收益值，执行O（mn）次计算。而对比经典的算法VLSN 搜索启发式算法，当对目标集合中的k个目标进行交换寻优，过程中采用动态规划，每次迭代需要进行O（m² ×2^k ）计算^［19］。经过对比，在m×2^k >n的情况下本算法的计算量将小于VLSN算法。

4 仿真验证

下面以对飞行器集群目标打击分配问题为例，分配方案的优化指标为目标剩余价值最低，采用文中提出的目标分配算法进行验证。

例1： 假定初始时刻拦截飞行器为3种（其中第1和第3种数目为2），目标飞行器的数目为3。表1中给出仿真算例1的参数，其中包含武器类型、数量、目标价值和武器杀伤概率。

5 结束语

本文针对蜂群飞行器集群对抗目标分配问题，利用目标集群的剩余价值作为优化目标，使用贪婪算法分步选取局部最优解，最终获取目标分配的近似全局最优解。通过仿真算例详细说明了启发式目标分配算法武器收益迭代计算和寻优的步骤，验证了蜂群作战情况下所提出方法解决大规模实例的有效性。

声明:公众号转载的文章及图片出于非商业性的教育和科研目的供大家参考和探讨，并不意味着支持其观点或证实其内容的真实性。版权归原作者所有，如转载稿涉及版权等问题，请立即联系我们删除。