Combinatorial Optimization and Simulation for Weapon System Portfolio using Self-adaptive Memetic Algorithm

  • shanliang yang National University of Defense Technology
  • Kedi Huang
Keywords: weapon system portfolio, combinatorial optimization, self-adaptive Memetic algorithm, genetic algorithm, local search method


The weapon system portfolio problem is considered as a typical constrained combinatorial optimization problem with the purpose of maximizing the expected damage of hostile targets. Considering the computation complexity and the strict time constraints, a decision-making methodology based on self-adaptive Memetic algorithm is proposed as an alternative to help military commanders in making appropriate decisions. In this framework, self-adaptive genetic algorithm performs global search to prevent trapping into the local optima, in which the crossover probability and mutation probability could be adjusted dynamically according to the prematurity degree of evolving population. Furthermore, the problem-specific heuristics are utilized to conduct local search and fine-tuning in the solution space. A case study is given to illustrate the entire procedure and verify the performance of our proposed algorithm. Comparative experiments show that our algorithm outperforms its competitors with regard to solution quality and computation time. In addition, very large-scale scenarios are also simulated to demonstrate the scalability of our algorithm.


Lee J., Kang S.H., Jay R. & Kim S.B. 2010. A hybrid approach of goal programming for weapon systems selection, Computers & Industrial Engineering, vol.58, pp. 521-527.

Bogdanowicz R.Z. & Patel K. 2015. Quick Collateral Damage Estimation Based on Weapons Assigned to Targets, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol.45, pp. 762-769.

Lee Z.J., Su S.F. & Lee C.Y. 2002. A genetic algorithm with domain knowledge for weapon-target assignment problems, Journal of the Chinese Institute of Engineers, vol.25, pp.287-295.

Bogdanowicz R.Z. 2009. A new efficient algorithm for optimal assignment of smart weapons to targets, Computers and Mathematics with Applications, vol. 58, pp. 1965-1969.

Lee M.Z. 2010. Constrained Weapon-Target Assignment: Enhanced Very Large Scale Neighborhood Search Algorithm, IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, vol.40, pp. 198-204.

Silven S. 1992. A neural approach to the assignment algorithm for multiple-target tracking, IEEE Journal of Oceanic Engineering, vol.17, pp. 326-332.

Bogdanowicz R.Z., Antony T., Patel K. & Coleman P. 2013. Optimization of Weapon-Target Pairings Based on Kill Probabilities, IEEE Transactions on Cybernetics, vol.43, pp. 1835-1844.

Lee Z.J., Su S.F. & Lee C.Y. 2003. Efficiently Solving General Weapon-Target Assignment Problem by Genetic Algorithms With Greedy Eugenics, IEEE Transactions on Systems, Man, And Cybernetics-Part B: Cybernetics, vol.33, pp. 113-120.

Wang W., Cheng S. & Zhang Y. 2008. Research on Approach for a Type of Weapon Target Assignment Problem Solving by Genetic Algorithm, Systems Engineering and Electronics, vol.30, pp. 1708-1711.

Wang Y., Qian L., Guo Z. & Ma L. 2008. Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm, Journal of Systems Engineering and Electronics, vol.19, pp. 939-944.

Mehmet A.S. & Kemal L. 2014. Approximating the optimal mapping for weapon target assignment by fuzzy reasoning, Information Sciences, vol.255, pp. 30-44.

Xue X. & Wang Y. 2015. Optimizing ontology alignments through a Memetic Algorithm using both MatchFmeasure and Unanimous Improvement Ratio, Artificial Intelligence, vol.223, pp. 65-81.

Fraser G., Arcuri A. & McMinn P. 2015. A Memetic Algorithm for Whole Test Suite Generation, The Journal of Systems and Software, vol.103, pp. 311-327.

Zhao H., Xu W. & Jiang R. 2015. The Memetic Algorithm for the Optimization of Urban Transit Network, Expert Systems with Applications, vol.42, pp. 3760-3773.

Zhang Z., Liu M. & Lim A. 2015. A Memetic Algorithm for the Patient Transportation Problem, Omega, vol.54, pp. 60-71.

Zhu Z., Wang F., He S. & Sun Y. 2015. Global Path Planning of Mobile Robots using a Memetic Algorithm, International Journal of Systems Science, vol.46, pp. 1982-1993.

Day R.H. 1966. Allocating weapons to target complexes by means of non-linear programming. Operations Research, vol.14, pp. 992–1013.

Chen J., Xin B., Peng Z., Dou L. & Zhang J. 2009. Evolutionary decision-makings for the dynamic weapon-target assignment problem. Science in China Series F:Information Sciences. vol.52(11), pp. 2006–2018.

Ni M., Yu Z., Ma F. & Wu X. 2011. A Lagrange Relaxation Method for Solving Weapon-Target Assignment Problem, Mathematical Problems in Engineering, vol.1, pp. 1-10.

Gallardo J. & Carlos C. 2015. A GRASP-based Memetic Algorithm with Path Relinking for the Far from Most String Problem, Engineering Applications of Artificial Intelligence, vol.41, pp. 183-194.

He C., Xing J., Li J., Yang Q., Wang R. & Zhang X. 2015. A New Optimal Sensor Placement Strategy Based on Modified Modal Assurance Criterion and Improved Adaptive Genetic Algorithm for Structural Health Monitoring, Mathematical Problems in Engineering, vol.10, pp. 1-10.

Lu H., Wen X., Lan L., An Y. & Li X. 2015. A Self-adaptive Genetic Algorithm to Estimate JA Model Parameters Considering Minor Loops, Journal of Magnetism and Magnetic Materials, vol.374, pp. 502-507.

Mahdavi I., Movahednejad M. & Adbesh F. 2011. Designing Customer-oriented Catalogs in E-CRM using an Effective Self-adaptive Genetic Algorithm, Expert Systems with Applications, vol.38, pp. 631-639.

Srinivasa K.G., Venugopal K.R. & Patnaik L.M. 2007. A Self-adaptive Migration Model Genetic Algorithm for Data Mining Applications, Information Sciences, vol.177, pp. 4295-4313.

Industrial Engineering