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

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

Abstract

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

CLC Number:

E91
N945

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.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Table 2

Table 3

Table 4

Fig.5

Fig.6

Table 5

Table 6

References 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

Improved differential evolution algorithm for solving weapon-targetassignment problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 27

Related Articles 15

Recommended Articles

Metrics

Comments

算法	校正p值
RNADE vs DE	0
RNADE vs JADE	0.082 352
RNADE vs SaDE	0.067 807
RNADE vs MGBDE	0.000 153
RNADE vs DADDE	0.000 001

[1]	Mulai TAN, Dali DING, Lei XIE, Wei DING, Chenghui LYU. UCAV escape maneuvering decision based on fuzzy expert system and IDE algorithm [J]. Systems Engineering and Electronics, 2022, 44(6): 1984-1993.
[2]	Yunxiang CHEN, Yi RAO, Zhongyi CAI, Zezhou WANG. Remaining useful lifetime prediction and economic reserve strategy of equipment components based on improved similarity [J]. Systems Engineering and Electronics, 2021, 43(9): 2688-2696.
[3]	Wenhai WU, Xiaofeng GUO, Siyu ZHOU, Li GAO. Self-adaptive differential evolution algorithm with random neighborhood-based strategy and generalized opposition-based learning [J]. Systems Engineering and Electronics, 2021, 43(7): 1928-1942.
[4]	Jun LUO, Jianqiang LIU, Yanan PANG. Multi-threshold image segmentation of 2D Otsu based on neighborhood search JADE [J]. Systems Engineering and Electronics, 2020, 42(10): 2164-2171.
[5]	LI Shihao, DING Yong, GAO Zhenlong. UAV air combat maneuvering decision based on intuitionistic fuzzy game theory [J]. Systems Engineering and Electronics, 2019, 41(5): 1063-1070.
[6]	WANG Yi, SUN Jin-biao, XIAO Ming-qing, LUO Ji-xun. Research of dynamic weapon-target assignment problem based on type-2 interval fuzzy K-nearest neighbors classifier [J]. Systems Engineering and Electronics, 2016, 38(6): 1314-1319.
[7]	CHEN Jun-wei, CHANG Tian-qing, ZHANG Lei, YANG Guo-zhen, MA Dian-zhe. Two-stage model of WTA oriented armored unit combat method [J]. Systems Engineering and Electronics, 2016, 38(6): 1326-1331.
[8]	LIU Han, YIN Cheng-you, LIU Wei. Optimization and design of wideband antenna with adaptive differential evolution algorithm based on hybrid coding method [J]. Systems Engineering and Electronics, 2016, 38(4): 773-777.
[9]	HAN Wei, SU Xi-chao, CHEN Jun-feng. Integrated maintenance support scheduling method of multi carrier aircrafts [J]. Systems Engineering and Electronics, 2015, 37(4): 809-816.
[10]	CHANG Tian-qing, CHEN Jun-wei, HAO Na, MA Dian-zhe. Terminating control of ant colony algorithm for armored unit dynamic weapon-target assignment [J]. Systems Engineering and Electronics, 2015, 37(2): 343-347.
[11]	XU Ke-hu， HUANG Da-shan， WANG Tian-zhao. Improved artificial immune algorithm for solving weapon-target assignment problems [J]. Systems Engineering and Electronics, 2013, 35(10): 2121-2127.
[12]	WANG Shao-lei， CHEN Wei-yi， GU Xue-feng. Solving weapon-target assignment problems based on self-adaptive differential evolution algorithm [J]. Systems Engineering and Electronics, 2013, 35(10): 2115-2120.
[13]	ZHANG Rui, GAO Hui, ZHANG Tao. Hybird optimization algorithm based on quantum and differential evolution for continuous space optimization [J]. Journal of Systems Engineering and Electronics, 2012, 34(6): 1288-1292.
[14]	LIN Lian-lei, YAN Fang, YANG Jing-li. Use of nested differential evolution algorithm to select microburst model’s parameters [J]. Journal of Systems Engineering and Electronics, 2012, 34(11): 2379-2383.
[15]	BAO Zi-yang, CHEN Ke-song, HE Zi-shu, HAN Chun-lin. Sparse circular arrays method based on modified DE algorithm [J]. Journal of Systems Engineering and Electronics, 2009, 31(3): 497-499.