基于归纳法的同构资源目标分配算法
|
摘要
针对传统目标分配算法不能求解大规模资源目标分配的组合规划难题,提出了一种基于数学归纳法的资源目标分配算法。建立了资源相同条件下的目标分配数学模型。通过逐步增加资源和资源预分配的方法,不断从每次迭代的预分配方案中选择最优的分配方案,极大地降低了分配问题的搜索解空间和计算复杂度。以无人机协同区域搜索为典型应用案例,分别设计了对比实验和性能实验。仿真实验结果表明,该算法可以保证得到目标分配问题的全局最优解,并且在大规模资源分配中具有很好的实时性。
Aiming at the problem that the traditional target assignment algorithm cannot solve the portfolio planning problem of large-scale resource-target assignment,a new algorithm based on mathematical induction is proposed.Firstly,the mathematical model of target assignment under the same resource condition is established.Then,the optimal assignment scheme is selected from the pre-assignment scheme of each iteration.The search space and computational complexity are greatly reduced by means of pre-assignment of resources.In order to verify the collaborative area search of unmanned aircraft vehicles,comparative experiments and performance experiments are designed respectively.The experimental results demonstrate that the new algorithm can obtain a global optimal solution and solve large-scale assignment in real-time.
Aiming at the problem that the traditional target assignment algorithm cannot solve the portfolio planning problem of large-scale resource-target assignment,a new algorithm based on mathematical induction is proposed.Firstly,the mathematical model of target assignment under the same resource condition is established.Then,the optimal assignment scheme is selected from the pre-assignment scheme of each iteration.The search space and computational complexity are greatly reduced by means of pre-assignment of resources.In order to verify the collaborative area search of unmanned aircraft vehicles,comparative experiments and performance experiments are designed respectively.The experimental results demonstrate that the new algorithm can obtain a global optimal solution and solve large-scale assignment in real-time.
引文
[1]MURPHEY R A.Target-based weapon target assignment problems[M]∥Nonlinear assignment problems.New York:Springer US,2000:39-53.
[2]NASEEM A,SHAH S T H,KHAN S A,et al.Decision support system for optimum decision making process in threat evaluation and weapon assignment:current status,challenges and future directions[J].Annual Reviews in Control,2017,43:169-187.
[3]于连飞,刘进,张维明,等.武器-目标分配问题算法研究综述[J].数学的实践与认识,2016,46(2):26-32.YU L F,LIU J,ZHANG W M,et al.A survey of algorithms for weapon-objective assignment problem[J].Journal of Mathematics in Practice and Theory,2016,46(2):26-32.
[4]LEBOUCHER C,SHIN H S,SIARRY P,et al.A two-step optimization method for dynamic weapon target assignment problem[M]∥Recent advances on meta-heuristics and their application to real scenarios.Croatia:InTech,2013:109-129.
[5]陈思,胡涛.基于多目标优化遗传算法的武器-目标分配[J].舰船电子工程,2015,35(7):54-57,100.CHEN S,HU T.Weapon-target assignment with multi-objective non-dominated set ran-king genetic algorithm[J].2015,35(7):54-57,100.
[6]朱卫宵,祝前旺,陈康.一种基于遗传算法的多传感器目标分配方法[J].电子信息对抗技术,2015,30(3):30-34.ZHU W X,ZHU Q W,CHEN K.A multi-sensor target allocation method based on genetic algorithm[J].Electronic Information Warfare Technology,2015,30(3):30-34.
[7]YANG J,LI J,WANG Y,et al.Optimization of weapon-target assignment problem by intuitionistic fuzzy genetic algorithm[J].Application Research of Computers,2018,128(2):1-5.
[8]王顺宏,杨奇松,王然辉,等.对地打击武器-目标分配问题的粒子群算法[J].电光与控制,2017,24(3):36-40.WANG S H,YANG Q S,WANG R H,et al.Particle swarm optimization based weapon-target assignment for attacking ground targets[J].Electronics Optics&Control,2017,24(3):36-40.
[9]段修生,徐公国,单甘霖.基于协同Memetic自适应QPSO算法的传感器目标分配问题求解[J].系统工程与电子技术,2016,38(12):2769-2776.DUAN X S,XU G G,SHAN G L.Solution to sensor-target assignment problem based on cooperative memetic adaptive QPSO algorithm[J].Systems Engineering and Electronics,2016,38(12):2769-2776.
[10]LEBOUCHER C.A Swarm Intelligence method combined to evolutionary game theory applied to resources allocation problem[C]∥Proc.of the International Conference on Swarm Intelligence,2012:20-38.
[11]XU G.An adaptive parameter tuning of particle swarm optimization algorithm[J].Applied Mathematics&Computation,2013,219(9):4560-4569.
[12]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.
[13]ZHOU Y,LI X,ZHU Y,et al.A discrete particle swarm optimization algorithm applied in constrained static weapon-target assignment problem[C]∥Proc.of the IEEE Intelligent Control and Automation,2016:3118-3123.
[14]常天庆,陈军伟,郝娜,等.装甲分队动态武器目标分配中蚁群算法终止控制[J].系统工程与电子技术,2015,37(2):343-347.CHANG T Q,CHEN J W,HAO N,et al.Terminating control of ant colony algorithm for armored unit dynamic weapon-target assignment[J].Systems Engineering and Electronics,2015,37(2):343-347.
[15]LI Y,KOU Y,LI Z,et al.A modified pareto ant colony optimization approach to solve bi-objective weapon-target assignment problem[J].International Journal of Aerospace Engineering,2017,2017(8):1-14.
[16]麻士东,龚光红,韩亮,等.目标分配的蚁群-模拟退火算法及其改进[J].系统工程与电子技术,2011,33(5):1182-1186.MA S D,GONG G H,HAN,L,et al.Hybrid strategy with ant colony and simulated annealing algorithm and its improvement in target assignment[J].Systems Engineering and Electronics,2011,33(5):1182-1186.
[17]DURGUT R,KUTUCU H,AKLEYLEK S.An artificial bee colony algorithm for solving the weapon target assignment problem[C]∥Proc.of the International Conference on Information Communication and Management,2017.
[18]陈军伟,常天庆,张雷,等.面向装甲分队战法运用的两阶段WTA模型[J].系统工程与电子技术,2016,38(6):1326-1331.CHEN J W,CHANG T Q,ZHANG L,et al.Two-stage model of WTA oriented armored unit combat method[J].Systems Engineering and Electronics,2016,38(6):1326-1331.
[19]ZHOU D,LI X,PAN Q,et al.Multiobjective weapon-target assignment problem by two-stage evolutionary multiobjective particle swarm optimization[C]∥Proc.of the IEEE International Conference on Information and Automation,2017:921-926.
[20]张滢,杨任农,左家亮,等.基于分解进化多目标优化算法的火力分配问题[J].系统工程与电子技术,2014,36(12):2435-2441.ZHANG Y,YANG R N,ZUO J L,et al.Weapon-target assignment based on decomposition-based evolutionary multi-objective optimization algorithms[J].Systems Engineering and Electronics,2014,36(12):2435-2441.
[21]ZHAO M,ZHAO L,SU X,et al.Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multi-targets assignment under unified model[J].International Journal of Machine Learning&Cybernetics,2017,8(3):765-780.
[22]张春美,陈杰,辛斌.武器目标分配问题的离散差分进化算法[J].北京理工大学学报,2014,34(3):289-293.ZHANG C M,CHEN J,XIN B.A discrete differential evolution algorithm for the weapon target assignment problem[J].Transactions of Beijing Institute of Technology,2014,34(3):289-293.
[23]XIN B,CHEN J,ZHANG J,et al.Efficient decision makings for dynamic weapon-target assignment by virtual permutation and Tabu search heuristics[J].IEEE Trans.on Systems,Man,and Cybernetics,Part C(Applications and Reviews),2010,40(6):649-662.
[24]MU L,QU X,WANG P.Application of sensor/weapon-target assignment based on multi-scale quantum harmonic oscillator algorithm[C]∥Proc.of the International Conference on Image,Vision and Computing,2017:1147-1151.
[25]WANG Y,ZHANG W,LI Y.An efficient clonal selection algorithm to solve dynamic weapon-target assignment game model in UAV cooperative aerial combat[C]∥Proc.of the IEEE Control Conference,2016:9578-9581.
[26]谢俊洁,穆富岭,王骏,等.ABMS中基于Q学习算法的空战目标分配方法[J].系统工程与电子技术,2017,39(3):557-561.XIE J,LUO P,MU F,et al.Air combat target assignment in ABMS based on Q-learning algorithm[J].Systems Engineering and Electronics,2017,39(3):557-561.
[27]MEI Z,PENG Z,ZHANG X.Optimal dynamic weapon-target assignment based on receding horizon control heuristic[C]∥Proc.of the IEEE International Conference on Control&Automation,2017:876-881.
[28]AHNER D K,PARSON C R.Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming[J].Optimization Letters,2015,9(8):1689-1701.
[29]王邑,孙金标,肖明清,等.基于类型2区间模糊K近邻分类器的动态武器目标分配方法研究[J].系统工程与电子技术,2016,38(6):1314-1319.WANG Y,SUN J B,XIAO M Q,et al.Research of dynamic weapon-target assignment problem based on type-2interval fuzzy K-nearest neighbors classifier[J].Systems Engineering and Electronics,2016,38(6):1314-1319.
[30]高坚,佟明安.编队协同对空目标探测及搜索力的最优分配[J].系统工程与电子技术,2004,26(3):350-352.GAO J,TONG M A.Cooperative target detection in team air combat and optimal allocation of search capability[J].Systems Engineering and Electronics,2004,26(3):350-352.
[2]NASEEM A,SHAH S T H,KHAN S A,et al.Decision support system for optimum decision making process in threat evaluation and weapon assignment:current status,challenges and future directions[J].Annual Reviews in Control,2017,43:169-187.
[3]于连飞,刘进,张维明,等.武器-目标分配问题算法研究综述[J].数学的实践与认识,2016,46(2):26-32.YU L F,LIU J,ZHANG W M,et al.A survey of algorithms for weapon-objective assignment problem[J].Journal of Mathematics in Practice and Theory,2016,46(2):26-32.
[4]LEBOUCHER C,SHIN H S,SIARRY P,et al.A two-step optimization method for dynamic weapon target assignment problem[M]∥Recent advances on meta-heuristics and their application to real scenarios.Croatia:InTech,2013:109-129.
[5]陈思,胡涛.基于多目标优化遗传算法的武器-目标分配[J].舰船电子工程,2015,35(7):54-57,100.CHEN S,HU T.Weapon-target assignment with multi-objective non-dominated set ran-king genetic algorithm[J].2015,35(7):54-57,100.
[6]朱卫宵,祝前旺,陈康.一种基于遗传算法的多传感器目标分配方法[J].电子信息对抗技术,2015,30(3):30-34.ZHU W X,ZHU Q W,CHEN K.A multi-sensor target allocation method based on genetic algorithm[J].Electronic Information Warfare Technology,2015,30(3):30-34.
[7]YANG J,LI J,WANG Y,et al.Optimization of weapon-target assignment problem by intuitionistic fuzzy genetic algorithm[J].Application Research of Computers,2018,128(2):1-5.
[8]王顺宏,杨奇松,王然辉,等.对地打击武器-目标分配问题的粒子群算法[J].电光与控制,2017,24(3):36-40.WANG S H,YANG Q S,WANG R H,et al.Particle swarm optimization based weapon-target assignment for attacking ground targets[J].Electronics Optics&Control,2017,24(3):36-40.
[9]段修生,徐公国,单甘霖.基于协同Memetic自适应QPSO算法的传感器目标分配问题求解[J].系统工程与电子技术,2016,38(12):2769-2776.DUAN X S,XU G G,SHAN G L.Solution to sensor-target assignment problem based on cooperative memetic adaptive QPSO algorithm[J].Systems Engineering and Electronics,2016,38(12):2769-2776.
[10]LEBOUCHER C.A Swarm Intelligence method combined to evolutionary game theory applied to resources allocation problem[C]∥Proc.of the International Conference on Swarm Intelligence,2012:20-38.
[11]XU G.An adaptive parameter tuning of particle swarm optimization algorithm[J].Applied Mathematics&Computation,2013,219(9):4560-4569.
[12]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.
[13]ZHOU Y,LI X,ZHU Y,et al.A discrete particle swarm optimization algorithm applied in constrained static weapon-target assignment problem[C]∥Proc.of the IEEE Intelligent Control and Automation,2016:3118-3123.
[14]常天庆,陈军伟,郝娜,等.装甲分队动态武器目标分配中蚁群算法终止控制[J].系统工程与电子技术,2015,37(2):343-347.CHANG T Q,CHEN J W,HAO N,et al.Terminating control of ant colony algorithm for armored unit dynamic weapon-target assignment[J].Systems Engineering and Electronics,2015,37(2):343-347.
[15]LI Y,KOU Y,LI Z,et al.A modified pareto ant colony optimization approach to solve bi-objective weapon-target assignment problem[J].International Journal of Aerospace Engineering,2017,2017(8):1-14.
[16]麻士东,龚光红,韩亮,等.目标分配的蚁群-模拟退火算法及其改进[J].系统工程与电子技术,2011,33(5):1182-1186.MA S D,GONG G H,HAN,L,et al.Hybrid strategy with ant colony and simulated annealing algorithm and its improvement in target assignment[J].Systems Engineering and Electronics,2011,33(5):1182-1186.
[17]DURGUT R,KUTUCU H,AKLEYLEK S.An artificial bee colony algorithm for solving the weapon target assignment problem[C]∥Proc.of the International Conference on Information Communication and Management,2017.
[18]陈军伟,常天庆,张雷,等.面向装甲分队战法运用的两阶段WTA模型[J].系统工程与电子技术,2016,38(6):1326-1331.CHEN J W,CHANG T Q,ZHANG L,et al.Two-stage model of WTA oriented armored unit combat method[J].Systems Engineering and Electronics,2016,38(6):1326-1331.
[19]ZHOU D,LI X,PAN Q,et al.Multiobjective weapon-target assignment problem by two-stage evolutionary multiobjective particle swarm optimization[C]∥Proc.of the IEEE International Conference on Information and Automation,2017:921-926.
[20]张滢,杨任农,左家亮,等.基于分解进化多目标优化算法的火力分配问题[J].系统工程与电子技术,2014,36(12):2435-2441.ZHANG Y,YANG R N,ZUO J L,et al.Weapon-target assignment based on decomposition-based evolutionary multi-objective optimization algorithms[J].Systems Engineering and Electronics,2014,36(12):2435-2441.
[21]ZHAO M,ZHAO L,SU X,et al.Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multi-targets assignment under unified model[J].International Journal of Machine Learning&Cybernetics,2017,8(3):765-780.
[22]张春美,陈杰,辛斌.武器目标分配问题的离散差分进化算法[J].北京理工大学学报,2014,34(3):289-293.ZHANG C M,CHEN J,XIN B.A discrete differential evolution algorithm for the weapon target assignment problem[J].Transactions of Beijing Institute of Technology,2014,34(3):289-293.
[23]XIN B,CHEN J,ZHANG J,et al.Efficient decision makings for dynamic weapon-target assignment by virtual permutation and Tabu search heuristics[J].IEEE Trans.on Systems,Man,and Cybernetics,Part C(Applications and Reviews),2010,40(6):649-662.
[24]MU L,QU X,WANG P.Application of sensor/weapon-target assignment based on multi-scale quantum harmonic oscillator algorithm[C]∥Proc.of the International Conference on Image,Vision and Computing,2017:1147-1151.
[25]WANG Y,ZHANG W,LI Y.An efficient clonal selection algorithm to solve dynamic weapon-target assignment game model in UAV cooperative aerial combat[C]∥Proc.of the IEEE Control Conference,2016:9578-9581.
[26]谢俊洁,穆富岭,王骏,等.ABMS中基于Q学习算法的空战目标分配方法[J].系统工程与电子技术,2017,39(3):557-561.XIE J,LUO P,MU F,et al.Air combat target assignment in ABMS based on Q-learning algorithm[J].Systems Engineering and Electronics,2017,39(3):557-561.
[27]MEI Z,PENG Z,ZHANG X.Optimal dynamic weapon-target assignment based on receding horizon control heuristic[C]∥Proc.of the IEEE International Conference on Control&Automation,2017:876-881.
[28]AHNER D K,PARSON C R.Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming[J].Optimization Letters,2015,9(8):1689-1701.
[29]王邑,孙金标,肖明清,等.基于类型2区间模糊K近邻分类器的动态武器目标分配方法研究[J].系统工程与电子技术,2016,38(6):1314-1319.WANG Y,SUN J B,XIAO M Q,et al.Research of dynamic weapon-target assignment problem based on type-2interval fuzzy K-nearest neighbors classifier[J].Systems Engineering and Electronics,2016,38(6):1314-1319.
[30]高坚,佟明安.编队协同对空目标探测及搜索力的最优分配[J].系统工程与电子技术,2004,26(3):350-352.GAO J,TONG M A.Cooperative target detection in team air combat and optimal allocation of search capability[J].Systems Engineering and Electronics,2004,26(3):350-352.