基于匈牙利-模拟退火算法的多阶段武器目标分配方法

doi:10.12305/j.issn.1001-506X.2023.11.18

摘要/Abstract

摘要：

针对现代化战争中远程精确制导武器成本高昂以及武器发射平台数量有限的问题, 研究了多阶段武器目标分配问题, 以最小化武器成本为优化目标, 建立了混合整数非线性规划模型。设计了一种集成匈牙利和模拟退火的混合智能搜索算法, 首先根据待攻击目标的时空状态与毁伤特性确定打击阶段、标记可松弛性。在模拟退火的框架下, 基于目标的松弛性调整攻击阶段, 再通过匈牙利算法计算每个阶段武器和目标的精确匹配方案。通过启发式算法和精确求解技术的结合, 在保证求解质量的前提下, 极大减少了计算时间。通过计算实验, 与变邻域搜索算法进行了对比分析, 验证了该算法在求解多阶段武器目标分配问题的有效性。仿真结果表明, 所提算法在计算时间和求解效果上优于变邻域搜索算法。

关键词: 武器目标分配, 多阶段, 匈牙利算法, 模拟退火算法

Abstract:

Aimed at the high cost of long-range precision-guided weapons and the limited number of weapon launch platforms in modern warfare, the multi-stage weapon target assignment(MS-WTA) problem is studied, and a mixed-integer nonlinear programming model is established to minimize the cost of weapons. A hybrid intelligent search algorithm integrating Hungarian and simulated annealing(HSA) is designed. Firstly, the hit stage and mark relaxation are determined according to the spatio-temporal state and damage characteristics of the target to be attacked. Under the framework of simulated annealing, the attack stage is adjusted based on the target's relaxation, and then the accurate matching scheme of weapons and targets in each stage is calculated by Hungarian algorithm. By combining heuristic algorithms and precise solving techniques, the calculation time is greatly reduced while ensuring the quality of the solution. Through computational experiments and comparative analysis with the variable neighborhood search algorithm, the effectiveness of this algorithm in solving MS-WTA problems is verified. The simulation results show that the proposed algorithm outperforms the variable neighborhood search algorithm in terms of computational time and solution performance.

Key words: weapon target assignment (WTA), multi-stage, Hungarian algorithm, simulated annealing algorithm

中图分类号:

常雪凝, 石建迈, 陈超, 黄金才. 基于匈牙利-模拟退火算法的多阶段武器目标分配方法[J]. 系统工程与电子技术, 2023, 45(11): 3516-3523.

Xuening CHANG, Jianmai SHI, Chao CHEN, Jincai HUANG. Multi-stage weapon target assignment method based on Hungarian simulated annealing algorithms[J]. Systems Engineering and Electronics, 2023, 45(11): 3516-3523.

图/表 9

表1

图1

图2

图3

表2

表3

表4

图4

图5

参考文献 33

1	程进, 齐航, 袁健全, 等. 关于导弹武器智能化发展的思考[J]. 航空兵器, 2019, 26 (1): 20- 24.
	CHENG J , QI H , YUAN J Q , et al. Discussion on the development of intelligent missile technology[J]. Aero Weaponry, 2019, 26 (1): 20- 24.
2	ELRAN M, PADAN C, DOLEV A, et al. Emergency, resilience, and the big city[C]//Proc. of the Research Forum, 2020.
3	付蒙, 纪永强, 陈超, 等. 2020年精确制导武器动力技术发展综述[J]. 飞航导弹, 2021, (2): 7- 13. doi: 10.16338/j.issn.1009-1319.20210804
	FU M , JI Y Q , CHEN C , et al. Review of power technology development of precision-guided weapons in 2020[J]. Aerodynamic Missile Journal, 2021, (2): 7- 13. doi: 10.16338/j.issn.1009-1319.20210804
4	DAVIS M T , ROBBINS M J , LUNDAY B J . Approximate dynamic programming for missile defense interceptor fire control[J]. European Journal of Operational Research, 2016, 259 (3): 873- 886.
5	ANDERSEN A C , PAVLIKOV K , TOFFOLO T . Weapon-target assignment problem: exact and approximate solution algorithms[J]. Annals of Operations Research, 2022, 312 (2): 581- 606. doi: 10.1007/s10479-022-04525-6
6	夏博远, 赵青松, 张骁雄, 等. 基于动态能力需求的鲁棒性武器系统组合决策[J]. 系统工程与电子技术, 2017, 39 (6): 1280- 1286.
	XIA B Y , ZHAO Q S , ZHANG X X , et al. Robust weapon system portfolio decision based on dynamic capability requirements[J]. Systems Engineering and Electronics, 2017, 39 (6): 1280- 1286.
7	FLOOD M. Target-assignment model[C]//Proc. of the Princeton University Conference on Linear Programming, 1957.
8	MANNE A S . A target-assignment problem[J]. Operations Research, 1958, 3 (6): 346- 357.
9	LLOYD S P, WITSENHAUSEN H S. Weapons allocation is NP-complete[C]//Proc. of the Summer Computer Simulation Conference, 1986: 1054-1058.
10	DIRIK N , HALL S N , MOORE J T . Maximizing strike aircraft planning efficiency for a given class of ground targets[J]. Optimization Letters, 2015, 9 (8): 1729- 1748. doi: 10.1007/s11590-014-0844-5
11	HAN C Y , LUNDAY B J , ROBBINS M J . A game theoretic model for the optimal location of integrated air defense system missile batteries[J]. Informs Journal on Computing, 2016, 28 (3): 405- 416. doi: 10.1287/ijoc.2016.0690
12	PENG G , FANG Y W , CHEN S H , et al. A hybrid multi objective discrete particle swarm optimization algorithm for cooperative air combat DWTA[J]. Journal of Optimization, 2017, doi: 10.1155/2017/8063767
13	陆一平, 李慧慧. 静态武器目标分配问题的攻击界整数规划求解方法[J]. 系统工程理论与实践, 2019, 39 (3): 783- 789.
	LU Y P , LI H H . An attack-number bounded integer programming method for the static WTA problem[J]. Systems Engineering-Theory & Practice, 2019, 39 (3): 783- 789.
14	STIEBER A , FVGENSCHUH A , EPP M , et al. The multiple traveling salesmen problem with moving targets[J]. Optimization Letters, 2015, 9 (8): 1569- 1583. doi: 10.1007/s11590-014-0835-6
15	GUO D , LIANG Z X , JIANG P , et al. Weapon-target assignment for multi-to-multi interception with grouping constraint[J]. IEEE Access, 2019, 7, 34838- 34849. doi: 10.1109/ACCESS.2019.2898874
16	LU Y P , CHEN D Z . A new exact algorithm for the weapon-target assignment problem[J]. Omega, 2021, 98 (1): 102138.
17	XIN B , WANG Y P , CHEN J . An efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem[J]. IEEE Trans.on Systems, Man, and Cybernetics: Systems, 2019, 49 (12): 2536- 2547. doi: 10.1109/TSMC.2017.2784187
18	LI X Y , ZHOU D Y , YANG Z , et al. A novel genetic algorithm for the synthetical sensor-weapon-target assignment problem[J]. Applied Sciences, 2019, 9 (18): 3803- 3830. doi: 10.3390/app9183803
19	ZHANG K , ZHOU D Y , YANG Z , et al. A novel heterogeneous sensor-weapon-target cooperative assignment for ground-to-air defense by efficient evolutionary approaches[J]. IEEE Access, 2020, 8, 227373- 227398. doi: 10.1109/ACCESS.2020.3043667
20	LI J, CHEN J, XIN B, et al. Solving multi-objective multi-stage weapon target assignment problem via adaptive NSGA-Ⅱ and adaptive MOEA/D: a comparison study[C]//Proc. of the IEEE Congress on Evolutionary Computation, 2015: 3132-3139.
21	ZHANG K , ZHOU D Y , YANG Z , et al. Constrained multi-objective weapon target assignment for area targets by efficient evolutionary algorithm[J]. IEEE Access, 2019, 7, 176339- 176360. doi: 10.1109/ACCESS.2019.2955482
22	AHUJA R K , KUMAR A , JHA K C , et al. Exact and heuristic algorithms for the weapon-target assignment problem[J]. Operations Research, 2007, 55 (6): 1136- 1146. doi: 10.1287/opre.1070.0440
23	KLINE A G , AHNER D K , LUNDAY B J , et al. Real-time heuristic algorithms for the static weapon target assignment problem[J]. Journal of Heuristics, 2019, 25 (3): 377- 397. doi: 10.1007/s10732-018-9401-1
24	NI M F , YU Z K , FENG M , et al. A lagrange relaxation method for solving weapon-target assignment problem[J]. Mathematical Problems in Engineering, 2011, 2011 (PT.4): 264- 265.
25	CHOPRA S , NOTARSTEFANO G , RICE M , et al. A distributed version of the hungarian method for multirobot assignment[J]. IEEE Trans.on Robotics, 2017, 33 (4): 932- 947. doi: 10.1109/TRO.2017.2693377
26	张进, 郭浩, 陈统. 基于可适应匈牙利算法的武器-目标分配问题[J]. 兵工学报, 2021, 42 (6): 1339- 1344. doi: 10.3969/j.issn.1000-1093.2021.06.025
	ZHANG J , GUO H , CHEN T . Weapon-target assignment based on adaptable hungarian algorithm[J]. Acta Armamentarii, 2021, 42 (6): 1339- 1344. doi: 10.3969/j.issn.1000-1093.2021.06.025
27	郭斐然, 于剑桥, 宋豹. 基于指派模型的导弹装备体系弹种优化设计[J]. 系统工程与电子技术, 2022, 44 (3): 850- 862.
	GUO F R , YU J Q , SONG B . Optimal design of missile types in missile equipment system based on assignment model[J]. Systems Engineering and Electronics, 2022, 44 (3): 850- 862.
28	LEE Z J , SU S F , LEE C Y . A genetic algorithm with domain knowledge for weapon-target assignment problems[J]. Journal of the Chinese Institute of Engineers, 2002, 25 (3): 287- 295. doi: 10.1080/02533839.2002.9670703
29	XIN B , CHEN J , PENG Z H , et al. An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem[J]. IEEE Trans.on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2011, 41 (3): 598- 606. doi: 10.1109/TSMCA.2010.2089511
30	LIANG H T , KANG F J . Adaptive chaos parallel clonal selection algorithm for objective optimization in WTA application[J]. Optik, 2016, 127 (6): 3459- 3465. doi: 10.1016/j.ijleo.2015.12.122
31	SONUC E , SEN B , BAYIR S . A parallel simulated annealing algorithm for weapon-target assignment problem[J]. International Journal of Advanced Computer Science and Applications, 2017, 8 (4): 87- 92.
32	KLINE A , AHNER D , HILL R . The weapon-target assignment problem[J]. Computers & Operations Research, 2019, 105 (3): 226- 236.
33	GELATT M P , VECCHI S , KIRKPATRICK C D . Optimization by simulated annealing[J]. Science, 1983, 220 (4598): 671- 680. doi: 10.1126/science.220.4598.671

参数	说明
V_j	目标初始威胁值
P_ij	武器i对目标j的毁伤能力
r_j	目标的松弛系数, r_j=0代表目标亟待打击, 不可调整攻击阶段; r_j=1代表目标处于松弛状态, 可以调整攻击阶段
N={1, 2, ⋯, n}	目标标号集合, 对任意目标j∈N
W={1, 2, ⋯, w}	武器标号集合, 对任意武器i∈W
S={1, 2, ⋯, s}	阶段标号集合, 对任意阶段t∈S
N_t	t阶段准备打击的目标集合, 满足N_t$\subseteq $N
W_t	t阶段可以使用的武器集合, 满足W_t$ \subseteq$W
X=[x_tij]_s×m×n	x_tij=1时, 表示第t个阶段武器i攻击目标j; 反之, x_tij=0代表不攻击
x_tij	0-1决策变量, 当武器i在t阶段分配给目标j时, 取值为1;否则为0

算例	算例规模(S, W, T)
1	(3, 4, 12)
2	(3, 10, 30)
3	(3, 20, 60)
4	(4, 15, 60)
5	(3, 40, 120)
6	(4, 30, 120)
7	(3, 50, 150)
8	(3, 80, 240)
9	(4, 60, 240)
10	(3, 100, 300)

参数名称	取值
初始温度T₀/℃	100 000
冷却系数Δd	0.95
内部迭代系数ψ/次	100
终止温度T_f/℃	0.1
外部停止系数Ω/次	300

算例	平均目标函数值		平均运行时间/s
算例	HSA	VNS	HSA	VNS
1	100.82	103.45	0.396	1.697
2	170.15	173.28	5.045	61.204
3	335.77	344.05	8.729	1 042.645
4	355.22	372.05	12.204	398.575
5	741.31	767.83	23.487	2 447.96
6	759.28	792.82	14.76	5 193.81
7	873.39	889.23	34.163	8 007.56
8	1 423.25	1 599.12	86.18	-
9	1 449.23	1 609.56	87.856	-
10	1 753.43	1 730.22	255.945	-

[1]	李翔宇, 黄洪钟, 熊晓燕. 考虑冲击与阶段备份的多阶段任务系统可靠性建模[J]. 系统工程与电子技术, 2023, 45(7): 2280-2286.
[2]	李梦杰, 常雪凝, 石建迈, 陈超, 黄金才, 刘忠. 武器目标分配问题研究进展: 模型、算法与应用[J]. 系统工程与电子技术, 2023, 45(4): 1049-1071.
[3]	朱晓雯, 范成礼, 卢盈齐, 朱文正, 吴暄. 基于改进BBO算法和模糊期望效果的反导武器目标分配建模与实现[J]. 系统工程与电子技术, 2023, 45(11): 3544-3554.
[4]	余婧, 雍恩米, 陈汉洋, 郝东, 张显才. 面向多无人机协同对地攻击的双层任务规划方法[J]. 系统工程与电子技术, 2022, 44(9): 2849-2857.
[5]	张彦, 叶春茂, 李璋峰, 鲁耀兵. 多种转发干扰下的脉内脉间波形综合优化设计[J]. 系统工程与电子技术, 2022, 44(5): 1495-1501.
[6]	王鹏, 孙紫荆, 张帆, 肖国松. 考虑概率型共因失效的多阶段任务系统可靠性分析模型[J]. 系统工程与电子技术, 2022, 44(12): 3887-3898.
[7]	赵洪利, 陈天铭, 郑涅. 基于综合指标多阶段相似的发动机寿命预测[J]. 系统工程与电子技术, 2021, 43(5): 1430-1436.
[8]	吴文海, 郭晓峰, 周思羽, 高丽. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43(4): 1012-1021.
[9]	禹明刚, 何明, 张东戈, 贾连祥. 基于Bayesian Stackelberg多阶段博弈的网络信息体系方案优选[J]. 系统工程与电子技术, 2020, 42(6): 1301-1309.
[10]	刘家义, 王刚, 张杰, 王闯, 宋喜团. 基于改进AGD-分布式多智能体系统的目标优化分配模型[J]. 系统工程与电子技术, 2020, 42(4): 863-870.
[11]	张奡, 王治华, 赵振平, 秦续国, 吴琼, 刘成瑞. 两阶段非线性Wiener过程退化建模与可靠性分析[J]. 系统工程与电子技术, 2020, 42(4): 954-959.
[12]	刘越, 仲小清, 付金宇, 李想. 基于混合优化方法的立体匹配算法[J]. 系统工程与电子技术, 2020, 42(12): 2692-2699.
[13]	弋佳东, 杨洁. 基于IFOA-SA-BP神经网络的雷达信号识别[J]. 系统工程与电子技术, 2020, 42(12): 2735-2741.
[14]	李孝鹏, 黄洪钟, 李福秋. 基于PRA的复杂航天多阶段任务系统可靠性分析[J]. 系统工程与电子技术, 2019, 41(9): 2141-2147.
[15]	闫华, 汪贻生, 王锐淇, 刘波, 郭立卿, 肖骅. 基于GPU的大规模多阶段任务系统可靠性并行计算方法[J]. 系统工程与电子技术, 2019, 41(1): 215-222.