静态武器目标分配问题的攻击界整数规划求解方法
|
摘要
静态武器目标分配(weapon-target assignment, WTA)问题的直接表现形态是非线性.在不丧失模型最优解的前提下,本文把WTA问题建模为整数线性规划(ILP)模型,并提出在最优武器分配方案中攻击特定目标的武器数量存在上界(攻击界).在采用启发式方法限定攻击界后,WTA问题的ILP模型的维数被大规模降低,使得求解能够在短时间内完成.与近年来发表于国内外期刊上的算例进行试算比较,结果显示本文提出的方法在求解速度和求解优化程度方面具有明显的优势.
The weapon-target assignment(WTA) problem is intuitively non-linear. In this paper the WTA problem is modelled as an integer linear program(ILP) without lose the problem's exact optimality, and it is proposed that there exists an upper bound of the number of attacking weapons for a specific target(the attack-number bound) providing the solution is optimal. By limiting the attack-number bound, the dimension of the ILP model of the WTA problem can be drastically decreased, and this enables the ILP of the WTA problem can be solved in short time. Computational experiments have been done on data provided by literature published in recent years, and the results show that the method proposed by this paper has clear advances over the traditional methods in both better optimality and faster computational speed.
The weapon-target assignment(WTA) problem is intuitively non-linear. In this paper the WTA problem is modelled as an integer linear program(ILP) without lose the problem's exact optimality, and it is proposed that there exists an upper bound of the number of attacking weapons for a specific target(the attack-number bound) providing the solution is optimal. By limiting the attack-number bound, the dimension of the ILP model of the WTA problem can be drastically decreased, and this enables the ILP of the WTA problem can be solved in short time. Computational experiments have been done on data provided by literature published in recent years, and the results show that the method proposed by this paper has clear advances over the traditional methods in both better optimality and faster computational speed.
引文
[1]蔡怀平,陈英武.武器-目标分配(WTA)问题研究进展[J].火力与指挥控制,2006, 31(12):11-15.Cai H P, Chen Y W. The development of the research on weapon-target assignment(WTA)problem[J]. Fire Control and Command Control, 2006, 31(12):11-15.
[2]王玮,刘兴林,王军,等.信息化条件下海上编队区域防空目标分配方法[J].系统工程理论与实践,2015, 35(4):1011-1018.Wang W, Liu X L, Wang J, et al. Method of area antiaircraft weapon target assignment for the warship formation under informationized conditions[J]. Systems Engineering—Theory&Practice, 2015, 35(4):1011-1018.
[3] Ahuja R K, Kumar A, Jha K C, et al. Exact and heuristic algorithms for the weapon-target assignment problem[J]. Operations Research, 2007, 55(6):1136-1146.
[4]常天庆,陈军伟,张雷,等.坦克分队WTA问题的改进人工蜂群算法[J]·装甲兵工程学院学报,2015(5):69-76.Chang T Q, Chen J W, Zhang L, et al. An improved artificial bee colony algorithm for tank unit WTA problem[J].Journal of Academy of Armored Force Engineering, 2015(5):69-76.
[5] Sonuc E, Sen B, Bayir S. A parallel simulated annealing algorithm for weapon-target assignment problem[J].International Journal of Advanced Computer Science and Applications, 2017, 8(4):87-92.
[6]毛艺帆,张多林.改进的人工蜂群算法求解武器目标分配问题[J].军事运筹与系统工程,2015(1):30-33.Mao Y F, Zhang D L. An improved artificial bee colony algorithm for the WTA problem[J]. Military Operations Research and Systems Engineering, 2015(1):30-33.
[7]陶德进,王军,朱凯,等,高炮武器系统毁伤概率计算的蒙特卡罗法[J]·系统工程理论与实践,2014, 34(1):268-272.Tao D J, Wang J, Zhu K, et al. Damage probability calculation of antiaircraft gun weapon system by Monte Carlo method[J]. Systems Engineering—Theory Practice, 2014, 34(1):268-272.
[8]程呈,高敏,程旭德,等.基于组合赋权的反坦克导弹武器系统作战效能评估研究[J].系统工程理论与实践,2018, 38(1):241-251.Cheng C, Gao M, Cheng X D, et al. Research on operational efficiency evaluation of anti-tank missile weapon system based on combination weighting[J]. Systems Engineering—Theory&Practice, 2018, 38(1):241-251.
[9] Lloyd S P, Witsenhausen H S. Weapon allocation is NP-complete[C]//IEEE Summer Simulation Conference,Reno, NV, 1986.
[10] Liang H, Kang F. Adaptive chaos parallel colnal selection algorithm for objective optimization in WTA application[J]. Optik, 2016, 127:3459-3465.
[11]杨奇松,王顺宏,王然辉,等.分阶段对地打击武器-目标分配建模与决策[J].弹道学报,2017,29(2):90-96.Yang Q S, Wang S H, Wang R H, et al. Modeling and decision-making of ground attack weapon-target assignment[J]. Journal of Ballistics, 2017, 29(2):90-96.
[12]刘蜀.舰艇编队防空火力分配方案生成及优选方法研究[J]·舰船电子工程,2017, 37(1):14-17.Liu S. Weapon-target assignment projects creation and selection method for fleet air defense battle[J]. Ship Electronic Engineering, 2017, 37(1):14-17.
[13] Wang Y, Li J, Huang W, et al. Dynamic weapon target assignment based on intuitionistic fuzzy entropy of discrete particle swarm[J]. China Communications, 2017, 14(1):169-179.
[14] Nickolls J, Dally W J. The GPU computing era[J]. IEEE Micro, 2010, 30(2):56-69.
[2]王玮,刘兴林,王军,等.信息化条件下海上编队区域防空目标分配方法[J].系统工程理论与实践,2015, 35(4):1011-1018.Wang W, Liu X L, Wang J, et al. Method of area antiaircraft weapon target assignment for the warship formation under informationized conditions[J]. Systems Engineering—Theory&Practice, 2015, 35(4):1011-1018.
[3] Ahuja R K, Kumar A, Jha K C, et al. Exact and heuristic algorithms for the weapon-target assignment problem[J]. Operations Research, 2007, 55(6):1136-1146.
[4]常天庆,陈军伟,张雷,等.坦克分队WTA问题的改进人工蜂群算法[J]·装甲兵工程学院学报,2015(5):69-76.Chang T Q, Chen J W, Zhang L, et al. An improved artificial bee colony algorithm for tank unit WTA problem[J].Journal of Academy of Armored Force Engineering, 2015(5):69-76.
[5] Sonuc E, Sen B, Bayir S. A parallel simulated annealing algorithm for weapon-target assignment problem[J].International Journal of Advanced Computer Science and Applications, 2017, 8(4):87-92.
[6]毛艺帆,张多林.改进的人工蜂群算法求解武器目标分配问题[J].军事运筹与系统工程,2015(1):30-33.Mao Y F, Zhang D L. An improved artificial bee colony algorithm for the WTA problem[J]. Military Operations Research and Systems Engineering, 2015(1):30-33.
[7]陶德进,王军,朱凯,等,高炮武器系统毁伤概率计算的蒙特卡罗法[J]·系统工程理论与实践,2014, 34(1):268-272.Tao D J, Wang J, Zhu K, et al. Damage probability calculation of antiaircraft gun weapon system by Monte Carlo method[J]. Systems Engineering—Theory Practice, 2014, 34(1):268-272.
[8]程呈,高敏,程旭德,等.基于组合赋权的反坦克导弹武器系统作战效能评估研究[J].系统工程理论与实践,2018, 38(1):241-251.Cheng C, Gao M, Cheng X D, et al. Research on operational efficiency evaluation of anti-tank missile weapon system based on combination weighting[J]. Systems Engineering—Theory&Practice, 2018, 38(1):241-251.
[9] Lloyd S P, Witsenhausen H S. Weapon allocation is NP-complete[C]//IEEE Summer Simulation Conference,Reno, NV, 1986.
[10] Liang H, Kang F. Adaptive chaos parallel colnal selection algorithm for objective optimization in WTA application[J]. Optik, 2016, 127:3459-3465.
[11]杨奇松,王顺宏,王然辉,等.分阶段对地打击武器-目标分配建模与决策[J].弹道学报,2017,29(2):90-96.Yang Q S, Wang S H, Wang R H, et al. Modeling and decision-making of ground attack weapon-target assignment[J]. Journal of Ballistics, 2017, 29(2):90-96.
[12]刘蜀.舰艇编队防空火力分配方案生成及优选方法研究[J]·舰船电子工程,2017, 37(1):14-17.Liu S. Weapon-target assignment projects creation and selection method for fleet air defense battle[J]. Ship Electronic Engineering, 2017, 37(1):14-17.
[13] Wang Y, Li J, Huang W, et al. Dynamic weapon target assignment based on intuitionistic fuzzy entropy of discrete particle swarm[J]. China Communications, 2017, 14(1):169-179.
[14] Nickolls J, Dally W J. The GPU computing era[J]. IEEE Micro, 2010, 30(2):56-69.