二分图匹配模型下的武器目标分配问题

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

摘要/Abstract

摘要：

武器目标分配问题是研究双方交战时, 按照一定分配原则将武器分配给多个能造成威胁的对方目标, 从而达到最佳打击效果的问题, 也是军事运筹学领域经典的组合优化问题。提出了二分图匹配模型下的武器目标分配问题, 并建立了相关的数学模型, 最后运用结合了贪心策略的Kuhn-Munkres算法对模型进行求解。通过使用随机生成的20个规模不同的实例来测试所提模型与算法的有效性。计算实验结果表明, 提出的模型与算法求解精度高、求解速度快, 可以满足武器目标分配问题快速做出最优决策的要求。

关键词: 武器目标分配问题, 加权二分图, 贪心策略, Kuhn-Munkres算法

Abstract:

The problem of weapon target allocation is a study of how to allocate weapons to multiple targets that can pose a threat when two sides engage in combat according to certain distribution rules, with the aim of achieving the best strike effect. It is also a classic combinatorial optimization problem in the field of military operations research. This article proposes the problem of weapon target allocation under the bipartite graph matching model and establishes a relevant mathematical model. Finally, the Kuhn-Munkres algorithm combined with greedy strategy is used to solve the model. The effectiveness of the proposed model and algorithm is tested by using 20 randomly generated instances of different sizes. The computational experiments result show that the proposed model and algorithm have high solving accuracy and fast solving speed, and can meet the requirements for fast solution of optimal decisions for weapon target allocation problems.

Key words: weapon target allocation problem, weighted bipartite graph, greedy strategy, Kuhn-Munkres algorithm

中图分类号:

吕娜, 王茂桓, 钟元芾, 张英朝, 孙蕾. 二分图匹配模型下的武器目标分配问题[J]. 系统工程与电子技术, 2024, 46(2): 549-560.

Na LYU, Maohuan WANG, Yuanfu ZHONG, Yingchao ZHANG, Lei SUN. Weapon target allocation problem based on matching model of bipartite graphs[J]. Systems Engineering and Electronics, 2024, 46(2): 549-560.

图/表 13

图1

图2

表1

图3

图4

图5

表2

表3

表4

多种算法实验结果对比"

问题	武器数	目标数	算法	最优值	平均值	中位数	标准差	运行时间/s
WTA1	5	5	KM-WTA	48.364 0	-	-	-	0.005
			FMINCON	48.364 0	-	-	-	0.820
			KM	48.364 0	-	-	-	0.140
			PSA^[25]	48.364 0	48.364 0	48.364 0	0.00	19.280
			PSA	48.364 0	48.364 0	48.364 0	0.00	27.300
			MCSA^[26]	48.364 0	48.364 0	48.364 0	0.00	4.420
			MCSA	48.364 0	48.364 0	48.364 0	0.00	11.420
WTA2	10	10	KM-WTA	96.312 3	-	-	-	0.007
			FMINCON	120.118 5	-	-	-	1.280
			KM	96.312 3	-	-	-	3.660
			PSA^[25]	96.312 3	96.312 3	96.312 3	0.00	30.940
			PSA	96.312 3	100.137 1	101.028 8	3.06	42.720
			MCSA^[26]	96.312 3	96.312 3	96.312 3	0.00	5.390
			MCSA	96.312 3	96.843 7	96.312 3	1.12	12.540
WTA3	20	20	KM-WTA	142.107 0	-	-	-	0.060
			FMINCON	189.080 9	-	-	-	69.850
			KM	142.107 0	-	-	-	8.200
			PSA^[25]	142.107 0	142.107 0	142.107 0	0.00	17.560
			PSA	169.145 1	193.787 5	194.323 8	4.71	42.390
			MCSA^[26]	142.107 0	142.107 0	142.107 0	0.00	7.560
			MCSA	178.132 3	183.981 1	184.695 5	2.48	13.060
WTA4	30	30	KM-WTA	247.167 9	-	-	-	0.160
			FMINCON	304.319 5	-	-	-	34.870
			KM	247.167 9	-	-	-	17.850
			PSA^[25]	248.028 5	248.028 5	248.028 5	0.00	11.230
			PSA	343.677 1	377.720 6	378.685 2	8.28	78.030
			MCSA^[26]	248.028 5	248.078 1	248.028 5	0.10	9.860
			MCSA	350.101 4	357.944 5	358.235 2	5.204 2	13.660
WTA5	40	40	KM-WTA	303.534 5	-	-	-	0.290
			FMINCON	368.337 5	-	-	-	40.240
			KM	303.534 5	-	-	-	23.090
			PSA^[25]	305.501 6	305.501 6	305.501 6	0.00	12.150
			PSA	474.890 3	520.943 6	522.207 0	10.46	82.810
			MCSA^[26]	305.501 6	305.604 6	305.501 6	0.15	12.700
			MCSA	484.390 3	495.208 7	494.979 7	6.48	14.050
WTA6	50	50	KM-WTA	354.865 7	-	-	-	0.770
			FMINCON	409.938 0	-	-	-	210.130
			KM	354.865 7	-	-	-	54.580
			PSA^[25]	353.076 7	353.311 2	353.261 0	0.14	11.170
			PSA	575.185 7	629.167 8	630.491 7	10.89	81.110
			MCSA^[26]	353.010 2	353.410 4	353.489 3	0.26	14.860
			MCSA	592.395 8	606.195 2	607.581 4	7.427 9	14.930
WTA7	60	60	KM-WTA	416.389 3	-	-	-	0.530
			FMINCON	504.111 8	-	-	-	297.120
			KM	416.389 3	-	-	-	45.920
			PSA^[25]	415.052 8	415.406 8	415.437 1	0.21	14.090
			PSA	702.694 5	776.700 7	777.976 5	12.32	82.980
			MCSA^[26]	414.222 2	415.401 7	415.383 8	0.82	17.480
			MCSA	721.075 9	742.163 8	746.450 9	7.43	15.300
WTA8	70	70	KM-WTA	497.586 6	-	-	-	0.720
			FMINCON	581.537 8	-	-	-	469.930
			KM	497.586 6	-	-	-	67.660
			PSA^[25]	498.104 9	498.591 8	498.586 0	0.30	15.730
			PSA	898.514 7	958.680 1	960.763 0	14.26	84.060
			MCSA^[26]	496.309 5	497.101 2	497.129 7	0.55	19.840
			MCSA	906.679 3	918.006 1	918.063 6	9.13	15.600
WTA9	80	80	KM-WTA	530.931 2	-	-	-	1.340
			FMINCON	-	-	-	-	> 3 600.000
			KM	530.931 2	-	-	-	80.490
			PSA^[25]	534.440 8	535.455 9	535.593 7	0.57	18.120
			PSA	966.850 6	1 040.6	1 043.1	15.44	86.740
			MCSA^[26]	531.159 2	533.264 7	532.978 2	1.46	22.260
			MCSA	979.834 2	998.234 9	998.904 6	12.02	15.860
WTA10	90	90	KM-WTA	588.149 1	-	-	-	2.070
			FMINCON	-	-	-	-	> 3 600.000
			KM	588.149 1	-	-	-	125.900
			PSA^[25]	594.063 9	595.327 7	595.646 6	0.72	19.900
			PSA	1 114.0	1 188.9	1 190.9	15.95	89.000
			MCSA^[26]	589.320 9	592.504 2	592.372 5	1.52	24.370
			MCSA	1 127.4	1 150.6	1 153.7	13.85	16.520
WTA11	100	100	KM-WTA	690.379 7	-	-	-	1.070
			FMINCON	-	-	-	-	> 3 600.000
			KM	690.379 7	-	-	-	93.530
			PSA^[25]	699.835 7	701.005 4	701.249 5	0.75	20.600
			PSA	1 338.5	1 402.9	1 405.0	17.51	90.000
			MCSA^[26]	694.500 9	696.729 9	696.723 5	1.34	29.080
			MCSA	1 349.6	1 362.8	1 363.0	9.44	17.120
WTA12	200	200	KM-WTA	1 274.1	-	-	-	18.590
			FMINCON	-	-	-	-	> 3 600.000
			KM	1 274.1	-	-	-	248.400
			PSA^[25]	1 306.912 6	1 308.338 2	1 308.518 7	0.86	27.570
			PSA	2 711.5	2 813.0	2 817.7	26.00	112.400
			MCSA^[26]	1 290.271 2	1 294.494 3	1 294.858 3	1.66	55.720
			MCSA	2 699.0	2 731.4	2 735.9	19.896 5	23.620
WTA13	10	5	KM-WTA	36.092 5	-	-	-	0.020
			FMINCON	36.092 5	-	-	-	2.370
			KM	36.092 5	-	-	-	4.130
			PSA	36.092 5	36.095 2	36.095 2	0.00	40.390
			MCSA	36.092 5	36.095 2	36.095 2	0.00	20.560
WTA14	5	10	KM-WTA	330.815 8	-	-	-	0.020
			FMINCON	414.145 3	-	-	-	3.660
			KM	330.815 8	-	-	-	4.190
			PSA	330.815 8	330.815 8	330.815 8	0.00	44.500
			MCSA	330.815 8	330.815 8	330.815 8	0.00	20.550
WTA15	10	20	KM-WTA	585.064 5	-	-	-	0.030
			FMINCON	689.055 4	-	-	-	126.530
			KM	585.064 5	-	-	-	8.310
			PSA	609.248 7	645.344 1	646.466 8	8.86	47.030
			MCSA	591.111 7	620.861 4	623.042 2	11.87	39.540
WTA16	20	10	KM-WTA	65.473 9	-	-	-	0.030
			FMINCON	78.294 2	-	-	-	9.240
			KM	65.473 9	-	-	-	8.220
			PSA	71.242 5	84.707 4	84.575 2	4.73	46.360
			MCSA	74.074 9	76.847 3	77.130 0	1.51	39.330
WTA17	20	40	KM-WTA	1 043.5	-	-	-	0.080
			FMINCON	1 202.7	-	-	-	3 431.000
			KM	1 043.5	-	-	-	10.460
			PSA	1 197.8	1 293.5	1 295.3	14.75	50.350
			MCSA	1 226.3	1 251.5	1 253.7	12.50	111.400
WTA18	20	80	KM-WTA	3 264.2	-	-	-	0.330
			FMINCON	-	-	-	-	> 3 600.000
			KM	3 264.2	-	-	-	14.320
			PSA	3 556.5	3 643.8	3 646.3	18.81	59.720
			MCSA	3 566.7	3 585.6	3 586.2	12.04	402.000
WTA19	40	20	KM-WTA	152.172 1	-	-	-	0.180
			FMINCON	160.417 9	-	-	-	19.140
			KM	152.172 1	-	-	-	13.510
			PSA	209.540 3	242.607 7	242.895 0	7.81	50.400
			MCSA	251.369 5	227.254 3	229.094 0	6.65	1 120.000
WTA20	80	20	KM-WTA	140.556 4	-	-	-	0.870
			FMINCON	-	-	-	-	> 3 600.000
			KM	140.556 4	-	-	-	67.010
			PSA	196.682 9	225.269 8	225.812 9	7.74	55.760
			MCSA	204.432 2	212.706 9	213.461 1	4.61	401.000

表4

表5

表6

图6

图7

参考文献 26

1	LLOYD S P, WITSENHAUSE H S. Weapon allocation is NP-Complete[C]//Proc. of the IEEE Summer Simulation Conference, 1986: 1054-1058.
2	MANNE A S . A target-assignment problem[J]. Operations Research, 1985, 6 (3): 346- 351.
3	李梦杰, 常雪凝, 石建迈, 等. 武器目标分配问题研究进展: 模型、算法与应用[J]. 系统工程与电子技术, 2023, 45 (4): 1049- 1071.
	LI M J , CHANG X N , SHI J M , et al. Developments of weapon target assignment problem: models, algorithms, and applications[J]. Systems Engineering and Electronics, 2023, 45 (4): 1049- 1071.
4	SOLAND R M . Optimal defensive missile allocation: a discrete min-max problem[J]. Operations Research, 1973, 21 (2): 590- 596. doi: 10.1287/opre.21.2.590
5	SIKANEN T. Solving weapon target assignment problem with dynamic programming[R]. Helsinki, Finland: Aalto University, 2008.
6	KIM Y , CHO J , HAN S , et al. Weapon target assignment model for small unit ground combat using mixed Integer nonli-near program and Lagrangian relaxation[J]. Mathematical Problems in Engineering, 2022, 12, 9228993.
7	LU Y P , CHEN D Z . A new exact algorithm for the weapon-target assignment problem[J]. Omega, 2021, 2021 (98): 102138.
8	WANG J , LUO P C , HU X W , et al. A hybrid discrete grey optimizer to solve weapon target assignment problems[J]. Discrete Dynamics in Nature and Society, 2018, (4): 1- 17.
9	CHANG T Q , KONG D P , HAO N , et al. Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization[J]. Applied Soft Computing, 2018, 70 (9): 845- 863.
10	KONG L R , WANG J Z , ZHAO P . Dynamic weapon target assignment problem by an improved multiobjective particle swarm optimization algorithm[J]. Applied Sciences, 2021, 11 (19): 9254. doi: 10.3390/app11199254
11	HUANGFU Y L , FAN Y H , LI G F , et al. Adaptive grouping weapon-target assignment with field-of-view angle constraint[J]. International Federation of Automatic Control-Papers Online, 2022, 55 (3): 190- 195.
12	AHUJA R K , KUMAR A , ORLIN J . Exact and heuristic algorithms for the weapon-target assignment problem[J]. Operations Research, 2007, 55 (6): 1136- 1146. doi: 10.1287/opre.1070.0440
13	常雪凝, 石建迈, 陈超, 等. 基于匈牙利-模拟退火算法的多阶段武器目标分配方法[J]. 系统工程与电子技术, 2023, 45 (11): 3516- 3523.
	CHANG X N , SHI J M , CHEN C , et al. Multi-stage weapon target assignment method based on the integrating of hungarian and simulated annealing algorithms[J]. Systems Engineering and Electronics, 2023, 45 (11): 3516- 3523.
14	LEBOUCHER C , SHIN H S , SIARRY P , et al. A two-step optimisation method for dynamic weapon target assignment problem[M]. London: Intech Open, 2013.
15	KLINE A , AHNER D , HILL R . The weapon-target assignment problem[J]. Computers & Operations Research, 2019, 105 (10): 226- 236.
16	HUO Y L , XIONG J , GUO Z X , et al. A collaboration approach for cloud factories based on Kuhn-Munkras algorithm[J]. International Journal of Computer Integrated Manufacturing, 2022, 35 (9): 972- 988. doi: 10.1080/0951192X.2022.2027021
17	WANG H C , LI H F , ZHOU H , et al. Low-altitude infrared small target detection based on fully convolutional regression network and graph matching[J]. Infrared Physics and Techno-logy, 2021, 115 (7): 103738.
18	MAN J F , ZHAO L Q , LIU M , et al. A bipartite graph ma-tching algorithm in human-computer collaboration[J]. International Journal of Performability Engineering, 2018, 14 (10): 2384- 2392.
19	CHEN K , KUANG C P . Web service discovery based on maximum weighted bipartite graphs[J]. Computer Communications, 2021, 171 (4): 54- 60.
20	MA J T , QIAO Y Q , HU G W , et al. Socialaccount linking via weighted bipartite graph matching[J]. International Journal of Communication Systems, 2018, 31 (7): e3471. doi: 10.1002/dac.3471
21	SUN S L , LI Y , XIE Y F , et al. 3D model retrieval using bipartite graph matching based on attention[J]. Neural Processing Letters, 2022, 52 (1): 1043- 1055.
22	HASHEMI A , DOWLATSHAHI M B , NEZAMABADI-POUR H . A bipartite matching-based feature selection for multi-label learning[J]. International Journal of Machine Learning and Cybernetics, 2021, 12 (2): 459- 475. doi: 10.1007/s13042-020-01180-w
23	BEIRANVAND F , MEHRDAD V , DOWLATSHAHI M B . Unsupervised feature selection for image classification: a bipartite matching-based principal component analysis approach[J]. Know-ledge-Based Systems, 2022, 250 (8): 109085.
24	李明哲, 金俊, 石端银. 图论及其算法[M]. 北京: 机械工业出版社, 2010.
	LI M Z , JIN J , SHI D Y . Graph theory and algorithms[M]. Beijing: China Machine Press, 2010.
25	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.
26	SONUC E . A modified crow search algorithm for the weapon-target assignment problem[J]. An International Journal of Optimization and Control: Theories & Applications, 2020, 10 (2): 188- 197.

符号	符号含义
X	作战时己方武器集合
x_i	第i个武器, x_i∈X
Y	作战时对方目标集合
y_j	第j个目标, y_j∈Y
M	确定有打击关系的边组成的集合
m	作战时己方武器数量
n	作战时对方目标数量
P_ij	武器i对目标j的毁伤概率, x_i∈X, y_j∈Y
v_j	目标j的威胁程度, y_j∈Y
x_iy_j	第i个武器与第j个目标之间的边
w_ij	边x_iy_j的权重, 也是目标j被武器i打击后的威胁程度
X_ij	0-1决策变量, 当武器i分配给目标j时取值为1;否则为0

算法	参数	取值
PSA	初始温度/(°)	1 000
	最终温度/(°)	0.1
	冷却因子	0.999 9
MCSA	最大迭代次数	200 000
	种群大小	40
	感知概率	0.2
	飞行距离/km	2
	限制次数	10 m