基于可适应匈牙利算法的武器-目标分配问题

doi:10.3969/j.issn.1000-1093.2021.06.025

摘要/Abstract

摘要： 当前各类智能优化算法求解武器-目标分配问题时，存在耗时长、优化结果不唯一等缺陷，而匈牙利算法具有耗时短、求解结果稳定的优势，但其适应性较差，目前尚未见二者的对比分析文献。针对此现象，对比分析传统匈牙利算法与智能优化算法的耗时性与稳定性，展现了匈牙利算法的优势；提出统一效率矩阵，创建可适用于所有类型目标分配问题的可适应匈牙利算法；通过实例应用验证了可适应匈牙利算法的正确性。

关键词: 武器-目标分配, 匈牙利算法, 整数规划, 智能优化算法

Abstract: When various intelligent optimization algorithms are used to solve the weapon-target assignment problem, they have the disadvantages of long time-consuming and non-unique optimization results. Hungary algorithm has the advantages of short time-consuming and stable optimization results, but its adaptability is poor. Currently, the comparison and analysis of intelligent optimization algorithms and Hungarian algorithm has not been reported. For this phenomenon, the time-consuming and stability of traditional Hungarian algorithm and intelligent optimization algorithms are compared, which shows the advantages of Hungarian algorithm. An adaptable Hungarian algorithm that can be applied to all types of weapon-target assignment problems is established by proposing a unified efficiency matrix. And then some examples are used to verify the correctness of the adaptable Hungarian algorithm.

Key words: weapon-targetassignment, Hungarianalgorithm, integerprogramming, intelligentoptimizationalgorithm

中图分类号:

E911

张进，郭浩，陈统. 基于可适应匈牙利算法的武器-目标分配问题[J]. 兵工学报, 2021, 42(6): 1339-1344.

ZHANG Jin， GUO Hao， CHEN Tong. Weapon-target Assignment Based on Adaptable Hungarian Algorithm[J]. Acta Armamentarii, 2021, 42(6): 1339-1344.

参考文献

［1］陈曼, 周凤星. 改进粒子群算法的舰载武器目标分配[J]. 火力与指挥控制, 2018, 43(11):72-76.
CHEN M, ZHOU F X. Shipborne weapon-target assignment based on improved particle swarm optimization[J]. Fire Control & Command Control, 2018, 43(11):72-76. (in Chinese)
[2］黄大山, 徐克虎, 王天召. 求解WTA问题的智能算法评价准则[J]. 火力与指挥控制, 2013, 38(8):43-46.
HUANG D S, XU K H, WANG T Z. An evaluation criteria for intelligent algorithm in solving weapon target assignment problem [J]. Fire Control & Command Control, 2013, 38(8):43-46. (in Chinese)
[3］杨飞, 王青, 侯砚泽. 基于整数域改进粒子群优化算法的多平台武器目标分配[J]. 兵工学报, 2011, 32(7):906-912.
YANG F, WANG Q, HOU Y Z. Weapon-target assignment in multi-launcher system based on improved integer field particle swarm optimization algorithm[J]. Acta Armamentarii, 2011, 32(7): 906-912. (in Chinese)
[4］董朝阳, 路遥, 王青. 改进的遗传算法求解火力分配优化问题[J]. 兵工学报, 2016, 37(1):97-102.
DONG C Y, LU Y, WANG Q. Improved genetic algorithm for solving firepower distribution[J]. Acta Armamentarii, 2016, 37(1): 97-102. (in Chinese)
[5］刘家义, 王刚, 张杰, 等. 基于改进AGD-分布式多智能体系统的目标优化分配模型[J]. 系统工程与电子技术, 2020, 42(4): 863-870.
LIU J Y, WANG G, ZHANG J, et al. Target optimal assignment model based on improved AGD-distributed multi-agent system[J]. Systems Engineering and Electronics, 2020, 42(4):863-870. (in Chinese)
[6］杨进帅, 李进, 王毅. 武器-目标分配问题研究[J]. 火力与指挥控制, 2019, 44(5):6-11.
YANG J S, LI J, WANG Y. Study of weapon target assignment problem[J]. Fire Control & Command Control, 2019, 44(5):6-11. (in Chinese)
[7］李廷鹏, 钱彦岭, 李岳. 基于改进匈牙利算法的多技能人员调度方法[J]. 国防科技大学学报, 2016, 38(2):144-149.
LI T P, QIAN Y L, LI Y. Multi-skilled labor allocating method based on improved Hungary algorithm[J]. Journal of National University of Defense Technology, 2016, 38(2):144-149. (in Chinese)
[8］ ZHU H B, LIU D N, ZHANG S Q, et al. Solving the many to many assignment problem by improving the Kuhn-Munkres algorithm with backtracking[J]. Theoretical Computer Science, 2016, 618:30-41.
[9］ CHOPRA S, NOTARSTEFANO G, RICE M, et al. A distributed version of the Hungarian method for multirobot assignment[J]. IEEE Transactions on Robotics, 2017, 33(4):932-947.
[10］柳毅, 佟明安. 匈牙利算法在多目标分配中的应用[J]. 火力与指挥控制, 2002, 27(4):34-37.
LIU Y, TONG M A. An application of Hungarian algorithm to the multi-target assignment[J]. Fire Control & Command Control, 2002, 27(4):34-37. (in Chinese)
[11］谷稳. 基于进化匈牙利算法的目标分配问题研究及应用[D]. 西安：西安电子科技大学, 2013.
GU W. Study and application of target allocation based on evolution Hungarian algorithm[J]. Xi'an: Xi'an University of Electronic Science and Technology, 2013. (in Chinese)
[12］李元左, 杨晓段. 炮兵火力分配建模及优化方法[J]. 指挥控制与仿真, 2015, 37(2):48-52.
LI Y Z, YANG X D. Optimal assignment model of artillery firepower[J]. Command Control & Simulation, 2015, 37(2):48-52. (in Chinese)
[13］ KUHN H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics Quarterly, 1955, 2(1):83-97.
[14］ BOURGEOIS F, LASSALLE J. An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J]. Communications of the ACM, 1971, 14(12):802-804.
[15］陈彬, 韩林, 余旺盛, 等. 基于改进遗传算法的装备调配[J]. 系统工程, 2010, 28(9):98-102.
CHEN B, HAN L, YU W S, et al. Equipment distribution based on modified genetic algorithm[J]. Systems Engineering, 2010, 28(9):98-102. (in Chinese)
[16］孙晓雅, 林焰. 一种新的离散粒子群算法在指派问题中的应用[J]. 计算机应用研究, 2009, 26(11):4091-4093,4097.
SUN X Y, LIN Y. Using new DPSO algorithm to solve assignment problem[J]. Application Research of Computers, 2019, 26(11): 4091-4093,4097. (in Chinese)



下3篇留版，1篇重排

[1]	薛辉，王源，张天鹏，刘铁林. 随机组合约束下的联合火力打击弹药需求预测模型[J]. 兵工学报, 2019, 40(8): 1716-1724.
[2]	夏维，刘新学，范阳涛，元锋刚. 基于改进型多目标粒子群优化算法的武器-目标分配[J]. 兵工学报, 2016, 37(11): 2085-2093.
[3]	王然辉，王超. 面向对地打击武器-目标分配问题的遗传算法变量取值控制技术[J]. 兵工学报, 2016, 37(10): 1889-1895.
[4]	董朝阳，路遥，王青. 改进的遗传算法求解火力分配优化问题[J]. 兵工学报, 2016, 37(1): 97-102.
[5]	郭业才，张苗青. 基于混合蛙跳算法的多模盲均衡算法[J]. 兵工学报, 2015, 36(7): 1280-1287.
[6]	张蛟，王中许，陈黎，武兆斌，陆建锋. 具有多次拦截时机的防空火力分配建模及其优化方法研究[J]. 兵工学报, 2014, 35(10): 1644-1650.
[7]	1:王国平，芮筱亭,陆毓琪;2:陈卫东;3:贠来峰. 减少多管火箭武器试验用弹量仿真技术[J]. 兵工学报, 2004, 25(6): 786-789.