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

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

CLC Number:

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.

Figures/Tables 9

Table 1

Fig.1

Fig.2

Fig.3

Table 2

Table 3

Table 4

Fig.4

Fig.5

References 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]	Mengjie LI, Xuening CHANG, Jianmai SHI, Chao CHEN, Jincai HUANG, Zhong LIU. Developments of weapon target assignment: models, algorithms, and applications [J]. Systems Engineering and Electronics, 2023, 45(4): 1049-1071.
[2]	Wenfei ZHAO, Xiaolei LIU, Cuiling MA, Kenan TENG. DWTA of air defense for strategic location on the sea based on multi-objective fuzzy programming [J]. Systems Engineering and Electronics, 2023, 45(3): 777-784.
[3]	Hongli ZHAO, Tianming CHEN, Nie ZHENG. Engine life prediction based on multi-stage similarity of comprehensive index [J]. Systems Engineering and Electronics, 2021, 43(5): 1430-1436.
[4]	Minggang YU, Ming HE, Dongge ZHANG, Lianxiang JIA. Scheme optimization for network information-centric system-of-systems based on multi-stage Bayesian Stackelberg game [J]. Systems Engineering and Electronics, 2020, 42(6): 1301-1309.
[5]	Jiayi LIU, Gang WANG, Jie ZHANG, Chuang WANG, Xituan SONG. Target optimal assignment model based on improved AGD-distributed multi-Agent system [J]. Systems Engineering and Electronics, 2020, 42(4): 863-870.
[6]	Yue LIU, Xiaoqing ZHONG, Jinyu FU, Xiang LI. Stereo matching algorithm based on hybrid optimization method [J]. Systems Engineering and Electronics, 2020, 42(12): 2692-2699.
[7]	CHU Xiaogeng, MA Zhengwei, CHEN Xingjun. Look-ahead margin-greedy constructive algorithm for the multi-objective optimization of the weapon target assignment problem [J]. Systems Engineering and Electronics, 2019, 41(10): 2252-2259.
[8]	XU Hao, XING Qinghua, WANG Wei. WTA for air and missile defense based on fuzzy multi-objective programming [J]. Systems Engineering and Electronics, 2018, 40(3): 563-570.
[9]	HUANG Liang, LIU Junqiang, GONG Yingjie. Residual lifetime prediction of aeroengines based on the consistency test [J]. Systems Engineering and Electronics, 2018, 40(12): 2736-2742.
[10]	HUANG Jin-bo, KONG De-jing, CUI Li-rong. Degradation modeling and reliability assessment of multi-stage system with calibrations [J]. Systems Engineering and Electronics, 2016, 38(4): 965-969.
[11]	LI An-da, HE Zhen, HE Shu-guang. Critical to quality characteristics identification for complex products using GSA [J]. Systems Engineering and Electronics, 2015, 37(9): 2073-2079.
[12]	YAN Qing-qing, SHEN Huai-rong, SHAO Qiong-ling. Space object ground-based surveillance scheduling based on genetic-simulated annealing algorithm [J]. Systems Engineering and Electronics, 2015, 37(12): 2764-2771.
[13]	XU Xuanhua, CAI Chenguang, LIANG Dong. Complex multi-stage decision making method based on#br# mixed multi-attribute information [J]. Systems Engineering and Electronics, 2015, 37(10): 2315-2321.
[14]	HAN Ping，XU Jian-sa，ZHAO Ai-jun. PolSAR image runways detection based on multi-stage classification [J]. Systems Engineering and Electronics, 2014, 36(5): 866-871.
[15]	GONG Shu-feng，BEN De，PAN Ming-hai. Discrete frequency code waveform design for OAR based on HGSAA [J]. Systems Engineering and Electronics, 2013, 35(9): 1854-1860.

Multi-stage weapon target assignment method based on Hungarian simulated annealing algorithms

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 33

Related Articles 15

Recommended Articles

Metrics

Comments