Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment

doi:10.23919/JSEE.2023.000102

Journal of Systems Engineering and Electronics ›› 2023, Vol. 34 ›› Issue (4): 1007-1019.doi: 10.23919/JSEE.2023.000102

• CONTROL THEORY AND APPLICATION • Previous Articles

Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment

Yang ZHAO(), Jicheng LIU(), Ju JIANG(), Ziyang ZHEN()

¹ College of Automation Engineering, Nanjing University of Aeronautics and Astronauts, Nanjing 211106, China

Received:2021-03-07 Online:2023-08-18 Published:2023-08-28
Contact: Yang ZHAO E-mail:zy@nuaa.edu.cn;ljc_uav@nuaa.edu.com;jiangju@nuaa.edu.cn;zhenziyang@nuaa.edu.cn
About author:
ZHAO Yang was born in 1987. He received his M.S. degree in the College of Automation Engineering from Nanjing University of Aeronautics and Astronautics, Nanjing, China, in 2013. He is pursuing his Ph.D. degree in the College of Automation Engineering, Nanjing University of Aeronautics and Astronautics. His research interests include advanced aircraft flight control and intelligent decision-making for modern air combat. E-mail: zy@nuaa.edu.cn

LIU Jicheng was born in 1996. He received his B.S. degree in the College of Automation Engineering from Nanjing University of Aeronautics and Astronautics, Nanjing, China, in 2019. He is pursuing his M.S. degree in the College of Automation Engineering from Nanjing University of Aeronautics and Astronautics. His main research interests include advanced flight control theory and its application to multi-unmanned aerial vehicle flight control systems. E-mail: ljc_uav@nuaa.edu.com

JIANG Ju was born in 1963. He received his M.S. and Ph.D. degrees in navigation, guidance and control from Beijing University of Aeronautics and Astronautics, Beijing, China, in 1988 and 2007. He is a professor at Nanjing University of Aeronautics and Astronautics. His research interest includes navigation and flight control of aircraft systems. E-mail: jiangju@nuaa.edu.cn

ZHEN Ziyang was born in 1981. He received his M.S. and Ph.D. degrees in control theory and control engineering from Nanjing University of Aeronautics and Astronautics, Nanjing, China, in 2007 and 2010. He is a professor at Nanjing University of Aeronautics and Astronautics. His research interests include advanced aircraft flight control, unmanned aerial vehicle swarm cooperative control, and artificial intelligence. E-mail: zhenziyang@nuaa.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (61673209; 71971115)

Abstract

Abstract:

The dynamic weapon target assignment (DWTA) problem is of great significance in modern air combat. However, DWTA is a highly complex constrained multi-objective combinatorial optimization problem. An improved elitist non-dominated sorting genetic algorithm-II (NSGA-II) called the non-dominated shuffled frog leaping algorithm (NSFLA) is proposed to maximize damage to enemy targets and minimize the self-threat in air combat constraints. In NSFLA, the shuffled frog leaping algorithm (SFLA) is introduced to NSGA-II to replace the inside evolutionary scheme of the genetic algorithm (GA), displaying low optimization speed and heterogeneous space search defects. Two improvements have also been raised to promote the internal optimization performance of SFLA. Firstly, the local evolution scheme, a novel crossover mechanism, ensures that each individual participates in updating instead of only the worst ones, which can expand the diversity of the population. Secondly, a discrete adaptive mutation algorithm based on the function change rate is applied to balance the global and local search. Finally, the scheme is verified in various air combat scenarios. The results show that the proposed NSFLA has apparent advantages in solution quality and efficiency, especially in many aircraft and the dynamic air combat environment.

Key words: dynamic weapon-target assignment (DWTA) problem, shuffled frog leaping algorithm (SFLA), air combat research

Yang ZHAO, Jicheng LIU, Ju JIANG, Ziyang ZHEN. Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment[J]. Journal of Systems Engineering and Electronics, 2023, 34(4): 1007-1019.

Figures/Tables 16

Fig 1

Fig 2

Table 1

Table 2

Table 3

Table 4

Fig 3

Table 5

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

References 33

1	KLINE A, AHNER D, HILL R The weapon-target assignment problem. Computers & Operations Research, 2019, 105 (1): 226- 236.
2	LEE Z J, LEE C Y, SU S F An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem. Applied Soft Computing, 2002, 2 (1): 39- 47. doi: 10.1016/S1568-4946(02)00027-3
3	XIN B, CHEN J, ZHANG J, et al Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics. IEEE Trans. on Systems Man and Cybernetics Part C-Applications and Reviews, 2010, 40 (6): 649- 662. doi: 10.1109/TSMCC.2010.2049261
4	ZHANG Y, YANG R N, ZUO J L, et al Weapon-target assignment based on decomposition-based evolutionary multi-objective optimization algorithms. Systems Engineering and Electronics, 2014, 36 (12): 2435- 2441.
5	LI N, HUAI W Q, WANG S D The solution of target assignment problem in command and control decision-making behaviour simulation. Enterprise Information Systems, 2016, 11 (7): 1059- 1077.
6	AHUJA R K, KUMAR A, JHA K C, et al Exact and heuristic algorithms for the weapon-target assignment problem. Operations Research, 2007, 55 (6): 1136- 1146. doi: 10.1287/opre.1070.0440
7	KARASAKAL O, OZDEMIREL NE, KANDILLER L Anti-ship missile defense for a naval task group. Naval Research Logistics, 2011, 58 (3): 305- 322.
8	KORSAH G A, STENTZ A, DIAS M B A comprehensive taxonomy for multi-robot task allocation. International Journal of Robotics Research, 2013, 32 (12): 1495- 1512. doi: 10.1177/0278364913496484
9	LUO L, CHAKRABORTY N, SYCARA K Provably-good distributed algorithm for constrained multi-robot task assignment for grouped tasks. IEEE Trans. on Robotics, 2015, 31 (1): 19- 30. doi: 10.1109/TRO.2014.2370831
10	LLOYD S P, WITSENHAUSEN H S. Weapons allocation is NP-complete. Proc. of the Summer Computer Simulation Conference, 1986: 1054−1061.
11	SAHIN M A, LEBLEBICIOGLU K Approximating the optimal mapping for weapon target assignment by fuzzy reasoning. Information Sciences, 2014, 255 (1): 30- 44.
12	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. Applied Soft Computing, 2018, 70 (1): 845- 863.
13	ZHAO Y, CHEN Y F, ZHEN Z Y, et al Multi-weapon multi-target assignment based on hybrid genetic algorithm in uncertain environment. International Journal of Advanced Robotic Systems, 2020, 17 (2): 1054- 1058.
14	LI X, LUO J, CHEN M R, et al An improved shuffled frog-leaping algorithm with extremal optimization for continuous optimization. Information Sciences, 2012, 192 (1): 143- 151.
15	CAI H P, LIU J X, CHEN Y W, et al Survey of the research on dynamic weapon-target assignment problem. Journal of Systems Engineering and Electronics, 2006, 17 (3): 559- 565. doi: 10.1016/S1004-4132(06)60097-2
16	NI M F, YU Z K, MA F, et al A Lagrange relaxation method for solving weapon-target assignment problem. Mathematical Problems in Engineering, 2011, 4 (1): 264- 265.
17	SAHIN M, LEBLEBICIOGLU K. Rule-based weapon target assignment on the battlefield. Proc. of the 18th IFAC World Congress, 2011: 13600−13605.
18	DAVIS M T, ROBBINS M J, LUNDAY B J Approximate dynamic programming for missile defense interceptor fire control. European Journal of Operational Research, 2017, 259 (3): 873- 886. doi: 10.1016/j.ejor.2016.11.023
19	BOARDMAN N T, LUNDAY B J, ROBBINS M J Heterogeneous surface-to-air missile defense battery location: a game theoretic approach. Journal of Heuristics, 2017, 23 (6): 417- 447. doi: 10.1007/s10732-017-9350-0
20	WANG S H, YANG Q S, WANG R H, et al Particle swarm optimization based weapon-target assignment for attacking ground targets. Electronics Optics & Control, 2017, 24 (3): 36- 40.
21	MEI Z J, PENG Z H, ZHANG X L. Optimal dynamic weapon-target assignment based on receding horizon control heuristic. Proc. of the 13th IEEE International Conference on Control & Automation, 2017: 876−881.
22	GAO C Q, KOU Y X, LI Y, et al. Multi-objective weapon target assignment based on D-NSGA-III-A. IEEE Access, 2019, 7: 50240−50254.
23	STEUER R E. Multiple criteria optimization: theory, computation, and application. Malabar: Krieger, 1988.
24	ZHA W Z, CHEN J, PENG Z H Dynamic multi-team antagonistic games model with incomplete information and its application to multi-UAV. IEEE/CAA Journal of Automatica Sinica, 2015, 2 (1): 74- 84. doi: 10.1109/JAS.2015.7032908
25	WANG Y, GARCIA E, CASBEER D, et al. Cooperative control of multi-agent systems: theory and applications. New York: John Wiley & Sons, 2017.
26	OSYCZKA A An approach to multicriterion optimization problems for engineering design. Computer Methods in Applied Mechanics and Engineering, 1978, 15 (3): 309- 333. doi: 10.1016/0045-7825(78)90046-4
27	SARABI J A, ARAABI B N How to decide when the sources of evidence are unreliable: a multi-criteria discounting approach in the Dempster-Shafer theory. Information Sciences, 2018, 448 (1): 233- 248.
28	ZHOU D Y, PAN Q, ZHANG K. An improved discrete shuffled frog leaping algorithm for cooperative multi-target assignment of BVR air combat. Proc. of the IEEE International Conference on Signal Processing, Communications and Computing, 2014: 686−691.
29	LAI C M, WU T H Simplified swarm optimization with initialization scheme for dynamic weapon-target assignment problem. Applied Soft Computing, 2019, 82, 105542.
30	EUSUFF M, LANSEY K Optimization of water distribution network design using the shuffled frog leaping algorithm. Journal of Water Resources Planning and Management, 2003, 129 (3): 210- 225. doi: 10.1061/(ASCE)0733-9496(2003)129:3(210)
31	EUSUFF M, LANSEY E, PASHA F Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Engineering Optimization, 2006, 38 (2): 129- 154. doi: 10.1080/03052150500384759
32	ROY P, CHAKRABARTI A Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect. Applied Soft Computing, 2013, 13 (11): 4244- 4252. doi: 10.1016/j.asoc.2013.07.006
33	FETTAKA S, THIBAULT J, GUPTA Y A new algorithm using front prediction and NSGA-II for solving two and three-objective optimization problems. Optimization and Engineering, 2015, 16 (4): 713- 736. doi: 10.1007/s11081-014-9271-9

Parameter	Value	Type
$ m $	$\{\text{ {4}，\text{6}，\text{12}，\text{18} } \}$	Integer
$ r $	$\{ {2}\times m,2\times m,2\times m,2\times m{} \}$	Integer
$ n $	$\{\text{ {6}，10，\text{20}，\text{36} } \}$	Integer
$ v $	$\{\text{ {2}，\text{2}，\text{3}，\text{3} } \}$	Integer
$ n_k^h $	1	Integer
$ m_j^h $	$\{ \text{ {2}，\text{2}，\text{3}，\text{3} }\}$	Integer
$ {a_k} $	$\{ \text{ {2}，\text{2}，\text{2}，\text{2} }\}$	Integer
$ f_{kj}^h $	$\left\{\begin{aligned}&1,\;\;\rho \lt \theta \\ &0,\;\;\text{otherwise}\end{aligned}\right.$ where $\theta {\text{ = } }0.8 - 0.1 h$	Float

$({\rm{Nmp}},{\rm{Nem}})$	$({F_{{\rm{avg}}} },{E_{{\rm{avg}}} })$	$({F_{{\rm{std}}} },{E_{{\rm{std}}} })$	${T_{{\rm{avg}}} }$	${T_{{\rm{std}}} }$	${N_{{\rm{avg}}} }$	${\rm{Ind}}$
(5,60)	(38.24,10.27)	(0.00531,0.00507)	16.2931	1.4682	63.0241	0.3184
(10,30)	(37.37,11.51)	(0.00406,0.00401)	15.6742	0.9257	58.2852	0.7627
(15,20)	(37.12,12.01)	(0.00352,0.00337)	14.7203	0.5060	52.7503	1.9241
(20,15)	(37.13,11.79)	(0.00347,0.00364)	14.9268	0.7401	58.9511	1.7956
(30,10)	(37.45,11.23)	(0.00509,0.00498)	15.6472	0.8364	60.2047	0.6507
(60,5)	(38.03,11.02)	(0.00646,0.00632)	15.9356	1.2679	62.6059	0.3166

P=150		P=200		P=500
$({\rm{Nmp}},{\rm{Nem}})$	${\rm{Ind}}$	$({\rm{Nmp}},{\rm{Nem}})$	${\rm{Ind}}$	$({\rm{Nmp}},{\rm{Nem}})$	${\rm{Ind}}$
(5,30)	0.2668	(5,40)	1.4502	(10,50)	4.9341
(10,15)	0.2955	(10,20)	1.5884	(20,25)	5.1755
(15,10)	0.3031	(20,10)	1.6032	(25,20)	5.3022
(30,5)	0.2764	(40,5)	1.4794	(50,10)	4.9816

Case	Criteria	$ \varepsilon $
		${p_{{\rm{cross}}} } = 0.2$			${p_{{\rm{cross}}} } = 0.5$			${p_{{\rm{cross}}} } = 0.8$
		2.0	6.0	10.0	2.0	6.0	10.0	2.0	6.0	10.0
II	${F_{{\rm{avg}}} }$	8.2473	8.2472	8.2473	8.2461	8.2458	8.2460	8.2470	8.2472	8.2472
	${E_{{\rm{avg}}} }$	4.8051	4.8050	4.8055	4.8079	4.8082	4.8068	4.8081	4.8112	4.8078
	${T_{{\rm{avg}}} }$	9.6005	9.1317	8.9053	9.5224	9.0127	8.9050	9.6732	9.1260	9.1071
	${N_{{\rm{avg}}} }$	18.5207	15.3214	15.8553	17.0524	13.3285	16.5227	14.0952	13.4100	16.2571
	${\rm{Ind}}$	13.4931	18.4212	19.3138	11.7050	21.5326	16.6947	15.4371	19.0545	18.9267
III	${F_{{\rm{avg}}} }$	37.2723	37.2715	37.2771	37.1365	37.1361	37.1473	37.1642	37.1637	37.1810
	${E_{{\rm{avg}}} }$	12.0548	12.1036	12.0872	12.1429	12.2550	12.2546	12.2510	12.2649	12.2588
	${T_{{\rm{avg}}} }$	14.3106	13.5501	13.1864	13.3601	12.9197	13.0985	14.6062	13.0089	13.4272
	${N_{{\rm{avg}}} }$	65	59	61	62	55	56	66	62	62
	${\rm{Ind}}$	0.4060	0.5009	0.4978	0.5329	0.6220	0.6212	0.4576	0.0538	0.5296

Parameter	Binh1		Fonseca2		Poloni
Parameter	NSFLA	NSGA-II	NSFLA	NSGA-II	NSFLA	NSGA-II
${C_{{\rm{avg}}} }$	0.00015	0.00020	0.00012	0.00077	0.00038	0.00170
${N_{{\rm{avg}}} }$	6.68508	7.00131	5.24771	5.78068	6.52404	7.13399
${C_{{\rm{std}}} }$	0.02091	0.02417	0.00096	0.00154	0.11474	0.13550

Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 16

References 33

Related Articles 1

Recommended Articles

Metrics

Comments