Constrained multi-objective weapon-target assignment problem

doi:10.11772/j.issn.1001-9081.2019071274

Abstract

Abstract: The traditional point-to-point saturation attack is not ideal choice facing high-density and multi-azimuth swarming intelligence targets. The maximum killing effect with weapon number less than target number can be achieved by selecting the appropriate types of weapons and the location of aiming points to realize the fire coverage. Considering the operational requirements of security targets, damage threshold and preference assignment, the Constrained Multi-objective Weapon-Target Assignment (CMWTA) mathematical model was established at first. Then, the calculation method of the constraint violation value was designed, and the individual coding, detection and repair as well as constraint domination were fused to deal with multiple constraints. Finally, the convergence metric for multi-objective weapon-target assignment model was designed, and the approaches were verified by the frameworks of Multi-Objective Evolutionary Algorithm (MOEA). In the comparison of three MOEA frameworks, the capacity of the Pareto sets of SPEA2 (Strength Pareto Evolutionary Algorithm Ⅱ) is mainly distributed in [21,25], that of NSGA-Ⅱ (Non-dominated Sorting Genetic Algorithm Ⅱ) is mainly distributed in [16,20], and that of MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition) is less than 16. In the verification of the repair algorithm, the algorithm makes the convergence metrics of three MOEA frameworks increased by 20 %, and the proportion of infeasible non-dominated solutions in Pareto solution set of 0%. The experimental results show that SPEA2 outperforms NSGA-Ⅱ and MOEA/D on distribution and convergence metric in solving CMWTA model, and the proposed repair algorithm improves the efficiency of solving feasible non-dominated solutions.

Key words: Weapon-Target Assignment （WTA）, decision support, target grouping, multi-objective optimization, constraint handling

摘要： 面对未来作战中高密度、多方位的集群智能体，传统点对点饱和攻击已不是最佳策略，可通过选择合适的武器类型和作用点实现火力覆盖，达到武器数量小于目标数量的最大杀伤效果。综合考虑安全目标、毁伤门限、偏好指派等作战需求，首先，建立了多约束多目标武器-目标分配（CMWTA）数学模型；其次，设计了约束违反值的计算方法，并采用个体编码、检测修复和约束支配相结合的方式处理多约束；最后，设计了针对多目标武器-目标分配模型的收敛性度量指标，并基于多目标进化算法（MOEA）框架进行了仿真分析。其中在进化算法框架对比中，SPEA2下的Pareto集合容量主要分布于[21，25]区间内，NSGA-Ⅱ下的Pareto集合容量主要分布于[16，20]，而MOEA/D下的Pareto集合容量均小于16；在修复算法验证中，修复算法将三种进化算法框架的Convergence指标提升了20%以上，且可将Pareto解集中不可行解的比例保持在0%。实验结果表明，在求解CMWTA模型中，SPEA2算法框架在分布性和收敛性上优于NSGA-Ⅱ和MOEA/D算法框架，且所提修复算法有效地提高了进化算法对非支配可行解的求解效率。

关键词: 武器-目标分配, 决策支持, 目标分群, 多目标优化, 约束处理

CLC Number:

TP391.7

ZHANG Kai, ZHOU Deyun, YANG Zhen, PAN Qian. Constrained multi-objective weapon-target assignment problem[J]. Journal of Computer Applications, 2020, 40(3): 902-911.

张凯, 周德云, 杨振, 潘潜. 多约束集群目标下武器-目标分配问题[J]. 计算机应用, 2020, 40(3): 902-911.

References

[1] United States Air Force. Unmanned aircraft systems flight plan 2009-2047[R]. Washington,DC:Headquarters of United States Air Force,2009.
[2] DEN BROEDER G G ELLISON,,EMERLING L. On optimum target assignments[J]. Operations Research,1959,7(3):322-326.
[3] ŞAHİN M A,LEBLEBİCİOĞLU K. Approximating the optimal mapping for weapon target assignment by fuzzy reasoning[J]. Information Sciences,2014,255:30-44.
[4] CHANG T,KONG D,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.
[5] 张先剑. 空陆攻防博弈的动态武器目标分配[J]. 国防科技大学学报,2019,41(2):185-190. (ZHANG X J. Land defense weapon versus target assignment against air attack[J]. Journal of National University of Defense Technology,2019,41(2):185-190.)
[6] VOLLE K,ROGERS J. Weapon-target assignment algorithm for simultaneous and sequenced arrival[J]. Journal of Guidance,Control,and Dynamics,2018,41(11):2361-2373.
[7] XIN B,WANG Y,CHEN J. An efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems,2019,49(12):2536-2547.
[8] LI Y,KOU Y,LI Z,et al. A modified pareto ant colony optimization approach to solve biobjective weapon-target assignment problem[J]. International Journal of Aerospace Engineering,2017,2017:No. 1746124.
[9] LI Y,KOU Y,LI Z. An improved nondominated sorting genetic algorithm Ⅲ method for solving multiobjective weapon-target assignment part I:the value of fighter combat[J]. International Journal of Aerospace Engineering,2018,2018:No. 8302324.
[10] 褚骁庚, 马政伟, 陈行军. 面向多目标优化火力目标分配问题的前瞻式边际贪婪算法[J]. 系统工程与电子技术,2019,41(10):2252-2259. (CHU X G,MA Z W,CHEN X J. 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.)
[11] PHAM L V,DICKERSON B,SANDERS J,et al. UAV swarm attack protection system alternatives for destroyers[D]. Monterey, CA:Naval Postgraduate School,2012.
[12] 李廷杰. 导弹武器系统的效能及其分析[M]. 北京:国防工业出版社,2000:13-16. (LI T J. Effectiveness Analysis for Missile Weapon Systems[M]. Beijing:National Defense Industry Press, 2000:13-16.)
[13] BOGDANOWICZ Z R,PATEL K. Quick collateral damage estimation based on weapons assigned to targets[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(5):762-769.
[14] LEE M Z. Constrained weapon-target assignment:enhanced very large scale neighborhood search algorithm[J]. IEEE Transactions on Systems Man and Cybernetics-Part A:Systems and Humans, 2009,40(1):198-204.
[15] MA J. Constrained target clustering for military targeting process[J]. Defense Science Journal,2017,67(5):523-528.
[16] GONG M,JIAO L,DU H,et al. Multiobjective immune algorithm with nondominated neighbor-based selection[J]. Evolutionary Computation,2014,16(2):225-255.
[17] 张安. 综合航空武器系统分析[M]. 西安:西北工业大学出版社, 2014:75-77. (ZHANG A. Aviation Weapon System Analysis[M]. Xi'an:Northwestern Polytechnical University Press, 2014:75-77.)
[18] KLINE A,AHNER D,HILL R. The weapon target assignment problem[J]. Computers and Operations Research,2019,105:226-236.
[19] DEB K,AGRAWAL R B. Simulated binary crossover for continuous search space[J]. Complex Systems,1995,9(2):115-148.
[20] DEB K,GOYAL M. A combined genetic adaptive search(GeneAS)for engineering design[J]. Computer Science and Informatics,1996,26:30-45.
[21] FONSECA C M,FLEMING P J. Multiobjective optimization and multiple constraint handling with evolutionary algorithms. I. A unified formulation[J]. IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,1998,28(1):26-37.
[22] DEB K,JAIN S. Running performance metrics for evolutionary multi-objective optimization[R]. Kanpur:Indian Institute of Technology Kanpur,Kanpur Genetic Algorithms Laboratory,2002.
[23] SCHOTT J R. Fault tolerant design using single and multicriteria genetic algorithm optimization[J]. Cellular Immunology,1995,37(1):1-13.
[24] ZITZLER E,THIELE L. Multiobjective optimization using evolutionary algorithms-a comparative case study[C]//Proceedings of the 1998 International Conference on Parallel Problem Solving from Nature,LNCS 1498. Berlin:Springer,1998:292-301.
[25] DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[26] ZITZLER E,LAUMANNS M,THIELE L. SPEA2:improving the strength Pareto evolutionary algorithm[R]. Zurich:Swiss Federal Institute of Technology(ETH)Zurich,2001.
[27] ZHANG Q,LI H. MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.