改进差分进化算法求解武器目标分配问题

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

摘要/Abstract

摘要：

针对武器目标分配问题求解收敛速度慢、搜索效率低、寻优精度差的问题, 提出一种基于改进差分进化算法的武器目标分配方法。首先, 建立多约束条件下武器目标分配优化模型, 将动态武器目标分配问题离散为静态武器目标分配问题处理。其次, 采用随机邻域变异策略平衡差分进化算法全局探索和局部开发能力, 采用基于历史存档的自适应参数整定方法, 根据“精英”信息动态更新算法参数。最后, 通过与5种变种差分进化算法的对比实验, 验证了所提方法寻优精度高、收敛速度快、鲁棒性强的优点。

关键词: 武器目标分配, 差分进化算法, 随机邻域, 自适应参数

Abstract:

To solve the problems of the slow convergence rate and the low search efficiency in solving weapon-target assignment (WTA), an improved differential evolution (DE) algorithm is proposed. Firstly, the WTA model is established under the multi-constraint condition, and the dynamic WTA (DWTA) problem is discretized into the static WTA (SWTA) problem. Secondly, the exploration and exploitation capabilities of DE algorithm gorithm are slightly balanced by the random neighborhood-based mutation strategy, and the adaptive parameter setting method based on historical archive is adopted to dynamically update parameters based on "elite" information. Finally, through the comparative experiments with five kinds of variant DE algorithms, the present algorithm is proved to have a high searching accuracy, a fast convergence speed and a strong robustness.

Key words: weapon-target assignment (WTA), differential evolution algorithm, random neighbourhood, self-adaptation parameter

中图分类号:

E91
N945

吴文海, 郭晓峰, 周思羽, 高丽. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43(4): 1012-1021.

Wenhai WU, Xiaofeng GUO, Siyu ZHOU, Li GAO. Improved differential evolution algorithm for solving weapon-targetassignment problem[J]. Systems Engineering and Electronics, 2021, 43(4): 1012-1021.

图/表 12

图1

图2

图3

图4

表1

表2

表3

表4

图5

图6

表5

表6

参考文献 27

1	LEE M Z . Constrained weapon-target assignment: enhanced very large scale neighborhood search algorithm[J]. IEEE Trans.on Systems Man & Cybernetics Part A Systems & Humans, 2010, 40 (1): 198- 204.
2	KLINE A , AHNER D , HILL R . The weapon-target assignment problem[J]. Computers & Operations Research, 2019, 105, 226- 236.
3	HOSEIN P A, ATHANS M. Some analytical results for the dynamic weapon-target allocation problem, LIPS-P-1944[R]. Cambridge UK: MIT, 1990.
4	LLOYD S P, WITSENHAUSDEN H S. Weapon allocation is NP-complete[C]//Proc. of the IEEE Summer Simulation Conference, 1986: 1054-1058.
5	HOCAOGLU M F . Weapon target assignment optimization for land based multi-air defense systems: a goal programming approach[J]. Computers & Industrial Engineering, 2019, 128, 681- 689.
6	YAO Z X , LI M , CHEN Z J , et al. Mission decision-making method of multi-aircraft cooperatively attacking multi-target based on game theoretic framework[J]. Chinese Journal of Aeronautics, 2016, 29 (6): 1685- 1694. doi: 10.1016/j.cja.2016.09.006
7	KLINE A G , AHNER D K , LUNDAY B J . Real-time heuristic algorithms for the static weapon target assignment problem[J]. Journal of Heuristics, 2019, 25, 377- 397. doi: 10.1007/s10732-018-9401-1
8	NI M F , YU Z K , MA F , et al. A Lagrange relaxation method for solving weapon-target assignment problem[J]. Mathematical Problems in Engineering, 2011, 4, 1- 10.
9	ZHOU Y L, LI X B, ZHU Y F, et al. A discrete particle swarm optimization algorithm applied in constrained static weapon-target assignment problem[C]//Proc. of the 12th World Congress on Intelligent Control and Automation, 2016: 3118-3123.
10	SONUC E , SEN B , BAYIR S . A parallel simulated annealing algorithm for weapon-target assignment problem[J]. International Journal of Advanced Computer Science & Applications, 2017, 8 (4): 87- 92.
11	CHEN J , XIN B , PENG Z , et al. Evolutionary decision-makings for the dynamic weapon-target assignment problem[J]. Science in China Series F: Information Sciences, 2009, 52 (11): 2006- 2018. doi: 10.1007/s11432-009-0190-x
12	LI X Y , ZHOU D Y , PAN Q , et al. Weapon-target assignment problem by multiobjective evolutionary algorithm based on decomposition[J]. Complexity, 2018,
13	HU X , LUO P , ZHANG X , et al. Improved ant colony optimization for weapon-target assignment[J]. Mathematical Problems in Engineering, 2018,
14	STORN R , PRICE K . Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11 (4): 341- 359. doi: 10.1023/A:1008202821328
15	閤大海. 差分进化算法的改进及在约束优化中的应用[D]. 武汉: 武汉大学, 2017.
	HE D H. The improvement of differential evolution algorithm and its application in constrained optimization[D]. Wuhan: Wuhan University, 2017.
16	DENG C, ZHAO B, DENG A Y, et al. Differential evolution with dual population for static weapon-target assignment problem[C]//Proc. of the 6th International Conference on Natural Computation, 2010: 3910-3913.
17	王少蕾, 陈维义, 顾雪峰. 自适应差分进化算法求解多平台多武器-目标分配问题[J]. 系统工程与电子技术, 2013, 35 (10): 2115- 2120. doi: 10.3969/j.issn.1001-506X.2013.10.16
	WANG S L , CHEN W Y , GU X F . Solving weapon-target assignment problems based on self-adaptive differential evolution algorithm[J]. Systems Engineering and Electronics, 2013, 35 (10): 2115- 2120. doi: 10.3969/j.issn.1001-506X.2013.10.16
18	LI N , HUAI W , WANG S . The solution of target assignment problem in command and control decision-making behaviour simulation[J]. Enterprise Information Systems, 2016, 11 (31): 1- 19.
19	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, 845- 863. doi: 10.1016/j.asoc.2018.06.014
20	PHAM H A, VU T C, NGUYEN B D, et al. Engineering optimization using an improved epsilon differential evolution with directional mutation and nearest neighbor comparison[C]//Proc. of the International Conference on Advances in Computational Mechanics, 2017: 201-216.
21	ZHANG X , ZHANG X . Improving differential evolution by differential vector archive and hybrid repair method for global optimization[J]. Soft Computing, 2016, 21 (23): 7107- 7116.
22	STANOVOV V , AKHMEDOVA S , SEMENKIN E . Selective pressure strategy in differential evolution: exploitation improvement in solving global optimization problems[J]. Swarm and Evolutionary Computation, 2019, 50, 1- 41.
23	CAI Y , WANG J , JIAN Y . Learning-enhanced differential evolution for numerical optimization[J]. Soft Computing, 2012, 16 (2): 303- 330. doi: 10.1007/s00500-011-0744-x
24	ZHANG J , SANDERSON A C . JADE: adaptive differential evolution with optional external archive[J]. IEEE Trans.on Evolutionary Computation, 2009, 13 (5): 945- 948. doi: 10.1109/TEVC.2009.2014613
25	QIN A K , HUANG V L , SUGANTHAN P N . Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Trans.on Evolutionary Computation, 2009, 13 (2): 398- 417. doi: 10.1109/TEVC.2008.927706
26	WANG H , RAHNAMAYAN S , SUN H , et al. Gaussian bare-bones differential evolution[J]. IEEE Trans.on Cybernet, 2013, 43 (2): 634- 647. doi: 10.1109/TSMCB.2012.2213808
27	LIU J, YIN X, GU X. Differential evolution improved with adaptive control parameters and double mutation strategies[C]// Proc. of the Asian Simulation Conference, 2016: 186-198.

小规模NP=50			中规模NP=80			大规模NP=100
m>n	m=n	m＜n	m>n	m=n	m＜n	m>n	m=n	m＜n
5W-3T	5W-5T	3W-5T	16W-10T	16W-16T	10W-16T	50W-30T	50W-50T	30W-50T
8W-5T	8W-8T	5W-8T	24W-15T	24W-24T	15W-24T	70W-40T	70W-70T	40W-70T

武器目标	算法
武器目标	DE	JADE	SaDE	MGBDE	DADDE	RNADE
5W-3T	1.53E-01±2.82E-17≈	1.54E-01±9.51E-04+	1.53E-01±2.82E-17≈	1.54E-01±1.08E-03+	1.53E-01±2.82E-17≈	1.53E-01±2.82E-17
8W-5T	2.57E-01±3.47E-03+	2.57E-01±0.00E+00≈	2.57E-01±0.00E+00≈	2.59E-01±4.53E-03+	2.57E-01±0.00E+00≈	2.57E-01±0.00E+00
16W-10T	6.51E-01±4.04E-02+	4.81E-01±8.91E-03+	4.78E-01±9.84E-03+	5.04E-01±2.07E-02+	6.27E-01±6.93E-02+	4.66E-01±3.13E-03
24W-15T	1.26E+00±9.04E-02+	6.23E-01±2.88E-02+	6.38E-01±3.17E-02+	6.01E-01±4.90E-02+	1.23E+00±6.36E-02+	5.19E-01±1.80E-02
50W-30T	3.05E+00±9.23E-02+	1.57E+00±5.58E-02+	1.83E+00±5.99E-02+	2.51E+00±2.06E-01+	3.03E+00±9.53E-02+	1.37E+00±3.63E-02
70W-40T	4.22E+00±6.00E-02+	2.41E+00±8.50E-02+	2.88E+00±1.11E-01+	3.83E+00±3.96E-01+	4.23E+00±1.80E-15+	2.18E+00±8.28E-02

武器目标	算法
武器目标	DE	JADE	SaDE	MGBDE	DADDE	RNADE
5W-5T	5.63E-01±1.26E-01+	5.64E-01±1.84-02+	5.59E-01±0.00E+00≈	5.71E-01±2.74E-02+	5.59E-01±0.00E+00≈	5.59E-01±0.00E+00
8W-8T	1.21E+00±2.64E-02+	1.19E+00±1.06E-02+	1.20E+00±1.01E-02+	1.23E+00±2.71E-02+	1.23E+00±5.25E-02+	1.18E+00±1.19E-02
16W-16T	3.25E+00±8.02E-03+	2.08E+00±1.41E-01+	2.19E+00±8.88E-02+	1.96E+00±1.47E-01+	3.25E+00±1.70E-02+	1.81E+00±8.75E-02
24W-24T	4.41E+00±1.80E-15+	3.33E+00±1.58E-01+	3.65E+00±1.98-01+	3.89E+00±2.49E-01+	4.41E+00±1.80E-15+	2.98E+00±9.49E-02
50W-50T	9.85E+00±5.42E-15+	9.83E+00±9.46E-02+	9.80E+00±1.26E-01+	9.80E+00±6.55E-02+	9.85E+00±5.42E-15+	9.30E+00±5.83E-01
70W-70T	1.44E+01±9.03E-15+	1.43E+01±7.60E-02+	1.43E+01±3.94E-02+	1.43E+01±5.83E-02+	1.44E+01±9.03E-15+	1.42E+01±1.79E-01

武器目标	算法
武器目标	DE	JADE	SaDE	MGBDE	DADDE	RNADE
3W-5T	1.21E+00±6.77E-16≈	1.21E+00±6.77E-16≈	1.21E+00±6.77E-16≈	1.26E+00±6.77E-16≈	1.21E+00±6.77E-16≈	1.21E+00±6.77E-16
5W-8T	2.29E+00±2.13E-02+	2.29E+00±1.03E-02+	2.29E+00±9.03E-16≈	2.29E+00±9.03E-16≈	2.29E+00±1.03E-02+	2.29E+00±9.03E-16
10W-16T	4.95E+00±1.39E-01+	4.60E+00±2.35E-02+	4.60E+00±2.89E-02+	4.67E+00±5.83E-02+	5.04E+00±1.28E-01+	4.58E±00±1.77E-02
15W-24T	7.86E+00±5.95E-02+	6.80E+00±5.93E-02+	6.85E+00±6.52E-02+	6.96E+00±1.14E-01+	7.88E+00±2.23E-02+	6.63E+00±2.99E-02
30W-50T	1.94E+01±8.23E-02+	1.58E+01±1.62E-02+	1.63E+01±2.12E-01+	1.76E+01±8.00E-01+	1.93E+01±1.65E-01+	1.51E+01±1.52E-01
40W-70T	2.90E+01±1.79E-01+	2.44E+01±3.38E-01+	2.53E+01±5.23E-01+	2.79E+01±8.00E-01+	2.90E+01±2.20E-01+	2.36E+01±2.37E-01

算法	平均排序值
RNADE	1.666 7
DE	5.055 6
JADE	2.750 0
SaDE	2.805 6
MGBDE	4.027 8
DADDE	4.694 4