SOLVING STATIC WEAPON-TARGET ASSIGNMENT PROBLEM USING MULTI-START LATE ACCEPTANCE HILL CLIMBING

Yıl 2024, Cilt: 2 Sayı: 1, 23 - 35

Selin Alparslan Emrullah Sonuç

Öz

A challenging methodology predicted in modern military strategies is the unprotected Weapon-Target Assignment (WTA) problem, where weapons under consideration must be assigned to targets in order to minimize the expected survivability attribute against the targets. In this case, this study is interested in the static WTA (SWTA) scenario, where the assignments are made on a one-time basis. Since the SWTA problem has been found to be of NP-complete nature, the more accurate solution techniques can be considered infeasible due to the escalating complexity. In this paper, it is proposed to extend the library of new methods by implementing the multi-start method and the technique called Late Acceptance Hill Climbing (LAHC). Performance comparisons between the Multi-Start Late Acceptance Hill Climbing (MLAHC) and LAHC algorithms, derived from different examples and problem sizes, prove that the MLAHC algorithm yields better quality solutions and higher reliability than the traditional LAHC algorithm for large problems. This strategy can be seen as a revolution in the process of analyzing military resource allocation towards the optimal level.

Anahtar Kelimeler

Combitonarial Optimization, Late Acceptance Hill Climbing, Weapon-Target Assignment Problem

Kaynakça

• R. K. Ahuja, A. Kumar, K. C. Jha, J. B. Orlin, Exact and heuristic algorithms for the weapon-target assignment problem, Operations research 55 (6) (2007) 1136–1146.
• A. Kline, D. Ahner, R. Hill, The weapon-target assignment problem, Computers & Operations Research 105 (2019) 226–236.
• S. P. Lloyd, H. S. Witsenhausen, Weapons allocation is np-complete., in: 1986 summer computer simulation conference, 1986, pp. 1054–1058.
• E. Sonuc, B. Sen, S. Bayir, A cooperative gpu-based parallel multistart simulated annealing algorithm for quadratic assignment problem, Engineering Science and Technology, an International Journal 21 (5) (2018) 843–849.
• Ö. Tolga, E. BOZKAYA, An evaluation on weapon target assignment problem, Journal of Naval Sciences and Engineer- ing 18 (2) (2022) 305–332.
• H. Xing, Q. Xing, An air defense weapon target assignment method based on multi-objective artificial bee colony algorithm., Computers, Materials & Continua 76 (3) (2023).
• E. Sonuc, B. Sen, S. Bayir, A parallel simulated annealing algorithm for weapon-target assignment problem, Interna- tional Journal of Advanced Computer Science and Applications 8 (4) (2017) 87–92.
• B. Chopard, M. Tomassini, An introduction to metaheuristics for optimization, Springer, 2018.
• A. Toet, H. de Waard, The Weapon-Target Assignment Problem, Citeseer, 1995.
• C. Wang, G. Fu, D. Zhang, H. Wang, J. Zhao, et al., Genetic algorithm-based variable value control method for solving the ground target attacking weapon-target allocation problem, Mathematical Problems in Engineering 2019 (2019).
• D. Guo, Z. Liang, P. Jiang, X. Dong, Q. Li, Z. Ren, Weapon-target assignment for multi-to-multi interception with grouping constraint, IEEE Access 7 (2019) 34838–34849.
• M. D. Rezende, B. S. P. De Lima, S. Guimara˜es, A greedy ant colony system for defensive resource assignment problems, Applied Artificial Intelligence 32 (2) (2018) 138–152.
• Exact and heuristic algorithms for the weapon-target assignment problem (2007). doi:10.1287/OPRE.1070.0440.
• A new exact algorithm for the weapon-target assignment problem (2021). doi:10.1016/J.OMEGA.2019.102138.
• A. C. Andersen, K. Pavlikov, T. A. Toffolo, Weapon-target assignment problem: Exact and approximate solution algo- rithms, Annals of Operations Research 312 (2) (2022) 581–606.
• E. Sonuc¸, A modified crow search algorithm for the weapon-target assignment problem, An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 10 (2) (2020) 188–197.
• S. Zou, X. Shi, S. Song, Moea with adaptive operator based on reinforcement learning for weapon target assignment, Electronic Research Archive 32 (3) (2024) 1498–1532.
• E. K. Burke, Y. Bykov, The late acceptance hill-climbing heuristic, European Journal of Operational Research 258 (1) (2017) 70–78.
• M. Terzi, T. Arbaoui, F. Yalaoui, K. Benatchba, Solving the unrelated parallel machine scheduling problem with setups using late acceptance hill climbing, in: Asian Conference on Intelligent Information and Database Systems, Springer, 2020, pp. 249–258.
• A. Goerler, E. Lalla-Ruiz, S. Voß, Late acceptance hill-climbing matheuristic for the general lot sizing and scheduling problem with rich constraints, Algorithms 13 (6) (2020) 138.
• S. Clay, L. Mousin, N. Veerapen, L. Jourdan, Clahc-custom late acceptance hill climbing: First results on tsp, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2021, pp. 1970–1973.
• B. S. Shihab, H. N. Abdullah, L. A. Hassnawi, Improved artificial bee colony algorithm-based path planning of un- manned aerial vehicle using late acceptance hill climbing., International Journal of Intelligent Engineering & Systems 15 (6) (2022).
• B. Chatterjee, T. Bhattacharyya, K. K. Ghosh, P. K. Singh, Z. W. Geem, R. Sarkar, Late acceptance hill climbing based social ski driver algorithm for feature selection, IEEE Access 8 (2020) 75393–75408.