A comprehensive review of metaheuristic algorithms for combinatorial optimization problems
Abstract
Metaheuristic algorithms are essential for handling difficult combinatorial optimization issues that arise in a variety of domains such as engi-neering, logistics, and operations research. These algorithms, based on natural, social, and physical events, strike a compromise between computing efficiency and solution quality. This study divides metaheuristic approaches into three categories: evolutionary algorithms, swarm intelligence techniques, and physics-based models, with a focus on current advances like hybrid and AI-driven frameworks. It also examines issues like as standardization, scalability, and practical implementation, including examples such as the Fire Hawk Optimizer to demonstrate its uses. This study intends to lead the development of trustworthy and efficient metaheuristic algorithms to solve increasingly complicated optimization issues in real-world settings, integrating theoretical ideas and practical examples.
About this article
Keywords
- Metaheuristic Algorithms
- Combinatorial Optimization
- Evolutionary Algorithms
- Swarm Intelligence
- Hybrid Optimization Frameworks.
References
Maier H R, Razavi S, Kapelan Z, L. S. E. Kasprzyk, and J. F. Tolson, “Introductory Overview: Optimization using Evolutionary Algorithms and other Metaheuristics,” 2018. https://doi.org/10.1016/j.envsoft.2018.11.018.
H. Shayanfar and F. S. Gharehchopogh, “Farmland fertility: A new metaheuristic algorithm for solving continuous optimization problems,” Applied Soft Computing Journal, vol. 71, pp. 728–746, Oct. 2018, https://doi.org/10.1016/j.asoc.2018.07.033.
M. Azizi, S. Talatahari, and A. H. Gandomi, “Fire Hawk Optimizer: a novel metaheuristic algorithm,” Artif Intell Rev, vol. 56, no. 1, pp. 287–363, Jan. 2023, https://doi.org/10.1007/s10462-022-10173-w.
M. Abdel-Basset, L. Abdel-Fatah, and A. K. Sangaiah, “Metaheuristic algorithms: A comprehensive review,” in Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications, Elsevier, 2018, pp. 185–231. https://doi.org/10.1016/B978-0-12-813314-9.00010-4.
B. Morales-Castañeda, D. Zaldívar, E. Cuevas, F. Fausto, and A. Rodríguez, “A better balance in metaheuristic algorithms: Does it exist?,” Swarm Evol Comput, vol. 54, May 2020, https://doi.org/10.1016/j.swevo.2020.100671.
View more references (39)
V. C. Vinod and A. H. S, “Nature inspired meta heuristic algorithms for optimization problems,” Computing, vol. 104, no. 2, pp. 251–269, Feb. 2022, https://doi.org/10.1007/s00607-021-00955-5.
F. Peres and M. Castelli, “Combinatorial optimization problems and metaheuristics: Review, challenges, design, and development,” Applied Sciences (Switzerland), vol. 11, no. 14, Jul. 2021, https://doi.org/10.3390/app11146449.
V. Sharma and A. K. Tripathi, “A systematic review of meta-heuristic algorithms in IoT based application,” Array, vol. 14, Jul. 2022, https://doi.org/10.1016/j.array.2022.100164.
D. Leiva, B. Ramos-Tapia, B. Crawford, R. Soto, and F. Cisternas-Caneo, “A Novel Approach to Combinatorial Problems: Bina-ry Growth Optimizer Algorithm,” Biomimetics, vol. 9, no. 5, May 2024, https://doi.org/10.3390/biomimetics9050283.
A. I. Garmendia, J. Ceberio, and A. Mendiburu, “Applicability of Neural Combinatorial Optimization: A Critical View,” ACM Transactions on Evolutionary Learning and Optimization, vol. 4, no. 3, Jul. 2024, https://doi.org/10.1145/3647644.
N. T. X. Hoa and V. H. Anh, “BIBLIOMETRIC STUDY OF METAHEURISTICS APPLICATION FOR SOLVING INVEN-TORY ROUTING PROBLEM,” Revista de Gestao Social e Ambiental, vol. 18, no. 2, 2024, https://doi.org/10.24857/rgsa.v18n2-116.
E. H. Houssein, M. K. Saeed, G. Hu, and M. M. Al-Sayed, “Metaheuristics for Solving Global and Engineering Optimization Problems: Review, Applications, Open Issues and Challenges,” Dec. 01, 2024, Springer Science and Business Media B.V. https://doi.org/10.1007/s11831-024-10168-6.
Z. Meng, G. Li, X. Wang, S. M. Sait, and A. R. Yıldız, “A Comparative Study of Metaheuristic Algorithms for Reliability-Based Design Optimization Problems,” Archives of Computational Methods in Engineering, vol. 28, no. 3, pp. 1853–1869, May 2021, https://doi.org/10.1007/s11831-020-09443-z.
B. Chopard and M. Tomassini, “Natural Computing Series an Introduction to Metaheuristics for Optimization.” [Online]. Availa-ble: www.springer.com/series/
M. Abdel-Basset, D. El-Shahat, and A. K. Sangaiah, “A modified nature inspired meta-heuristic whale optimization algorithm for solving 0–1 knapsack problem,” International Journal of Machine Learning and Cybernetics, vol. 10, no. 3, pp. 495–514, Mar. 2019, https://doi.org/10.1007/s13042-017-0731-3.
V. Hayyolalam and A. A. Pourhaji Kazem, “Black Widow Optimization Algorithm: A novel meta-heuristic approach for solving engineering optimization problems,” Eng Appl Artif Intell, vol. 87, Jan. 2020, https://doi.org/10.1016/j.engappai.2019.103249.
P. S. Game and V. Vaze, “Bio-inspired Optimization: metaheuristic algorithms for optimization,” NTCOMIS-2020.
F. A. Hashim, K. Hussain, E. H. Houssein, M. S. Mabrouk, and W. Al-Atabany, “Archimedes optimization algorithm: a new metaheuristic algorithm for solving optimization problems,” Applied Intelligence, vol. 51, no. 3, pp. 1531–1551, Mar. 2021, https://doi.org/10.1007/s10489-020-01893-z.
E. Osaba et al., “A Tutorial on the Design, Experimentation and Application of Metaheuristic Algorithms to Real-World Optimiza-tion Problems.”
A. Seyyedabbasi, R. Aliyev, F. Kiani, M. U. Gulle, H. Basyildiz, and M. A. Shah, “Hybrid algorithms based on combining rein-forcement learning and metaheuristic methods to solve global optimization problems,” Knowl Based Syst, vol. 223, Jul. 2021, https://doi.org/10.1016/j.knosys.2021.107044.
M. Yousefikhoshbakht, “Solving the Traveling Salesman Problem: A Modified Metaheuristic Algorithm,” Complexity, vol. 2021, 2021, https://doi.org/10.1155/2021/6668345.
B. Abdollahzadeh, F. Soleimanian Gharehchopogh, and S. Mirjalili, “Artificial gorilla troops optimizer: A new nature-inspired metaheuristic algorithm for global optimization problems,” International Journal of Intelligent Systems, vol. 36, no. 10, pp. 5887–5958, Oct. 2021, https://doi.org/10.1002/int.22535.
S. Talatahari, M. Azizi, and A. H. Gandomi, “Material generation algorithm: A novel metaheuristic algorithm for optimization of engineering problems,” Processes, vol. 9, no. 5, 2021, https://doi.org/10.3390/pr9050859.
J. S. Pan, L. G. Zhang, R. Bin Wang, V. Snášel, and S. C. Chu, “Gannet optimization algorithm : A new metaheuristic algorithm for solv-ing engineering optimization problems,” Math Comput Simul, vol. 202, pp. 343–373, Dec. 2022, https://doi.org/10.1016/j.matcom.2022.06.007.
M. Braik, M. H. Ryalat, and H. Al-Zoubi, “A novel meta-heuristic algorithm for solving numerical optimization problems: Ali Baba and the forty thieves,” Neural Comput Appl, vol. 34, no. 1, pp. 409–455, Jan. 2022, https://doi.org/10.1007/s00521-021-06392-x.
E. S. M. El-Kenawy et al., “Novel Meta-Heuristic Algorithm for Feature Selection, Unconstrained Functions and Engineering Problems,” IEEE Access, vol. 10, pp. 40536–40555, 2022, https://doi.org/10.1109/ACCESS.2022.3166901.
M. Dehghani, E. Trojovská, and P. Trojovský, “A new human-based metaheuristic algorithm for solving optimization problems on the base of simulation of driving training process,” Sci Rep, vol. 12, no. 1, Dec. 2022, https://doi.org/10.1038/s41598-022-14225-7.
O. N. Oyelade, A. E. S. Ezugwu, T. I. A. Mohamed, and L. Abualigah, “Ebola Optimization Search Algorithm: A New Nature-Inspired Metaheuristic Optimization Algorithm,” IEEE Access, vol. 10, pp. 16150–16177, 2022, https://doi.org/10.1109/ACCESS.2022.3147821.
F. A. Hashim, E. H. Houssein, K. Hussain, M. S. Mabrouk, and W. Al-Atabany, “Honey Badger Algorithm: New metaheuristic algorithm for solving optimization problems,” Math Comput Simul, vol. 192, pp. 84–110, Feb. 2022, https://doi.org/10.1016/j.matcom.2021.08.013.
T. S. L. V. Ayyarao et al., “War Strategy Optimization Algorithm: A New Effective Metaheuristic Algorithm for Global Optimiza-tion,” IEEE Access, vol. 10, pp. 25073–25105, 2022, https://doi.org/10.1109/ACCESS.2022.3153493.
T. Mzili, I. Mzili, and M. E. Riffi, “ARTIFICIAL RAT OPTIMIZATION WITH DECISION-MAKING: A BIO-INSPIRED METAHEURISTIC ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM,” Decision Making: Appli-cations in Management and Engineering, vol. 6, no. 2, pp. 150–176, Oct. 2023, https://doi.org/10.31181/dmame622023644.
M. Dehghani and P. Trojovský, “Osprey optimization algorithm: A new bio-inspired metaheuristic algorithm for solving engineer-ing optimization problems,” Front Mech Eng, vol. 8, Jan. 2023, https://doi.org/10.3389/fmech.2022.1126450.
E. V. Altay, O. Altay, and Y. Özçevik, “A Comparative Study of Metaheuristic Optimization Algorithms for Solving Real-World Engineering Design Problems,” CMES - Computer Modeling in Engineering and Sciences, vol. 139, no. 1, pp. 1039–1094, 2023, https://doi.org/10.32604/cmes.2023.029404.
R. Martín-Santamaría, M. López-Ibáñez, T. Stützle, and J. M. Colmenar, “On the automatic generation of metaheuristic algorithms for combinatorial optimization problems,” Eur J Oper Res, vol. 318, no. 3, pp. 740–751, Nov. 2024, https://doi.org/10.1016/j.ejor.2024.06.001.
M. Abdel-Basset, R. Mohamed, S. Saber, I. M. Hezam, K. M. Sallam, and I. A. Hameed, “Binary metaheuristic algorithms for 0–1 knapsack problems: Performance analysis, hybrid variants, and real-world application,” Journal of King Saud University - Com-puter and Information Sciences, vol. 36, no. 6, Jul. 2024, https://doi.org/10.1016/j.jksuci.2024.102093.
R. Zhong, Y. Xu, C. Zhang, and J. Yu, “Leveraging Large Language Model to Generate a Novel Metaheuristic Algorithm with CRISPE Framework,” Mar. 2024, [Online]. Available: http://arxiv.org/abs/2403.16417
E. H. Houssein, M. A. Mahdy, M. J. Blondin, D. Shebl, and W. M. Mohamed, “Hybrid slime mould algorithm with adaptive guided dif-ferential evolution algorithm for combinatorial and global optimization problems,” Expert Syst Appl, vol. 174, Jul. 2021, https://doi.org/10.1016/j.eswa.2021.114689.
J. Kallestad, R. Hasibi, A. Hemmati, and K. Sörensen, “A general deep reinforcement learning hyperheuristic framework for solv-ing combinatorial optimization problems,” Eur J Oper Res, vol. 309, no. 1, pp. 446–468, Aug. 2023, https://doi.org/10.1016/j.ejor.2023.01.017.
A. Arram, M. Ayob, G. Kendall, and A. Sulaiman, “Bird Mating Optimizer for Combinatorial Optimization Problems,” IEEE Access, vol. 8, pp. 96845–96858, 2020, https://doi.org/10.1109/ACCESS.2020.2993491.
H. R. Boveiri and M. Elhoseny, “A-COA: an adaptive cuckoo optimization algorithm for continuous and combinatorial optimiza-tion,” Feb. 01, 2020, Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/s00521-018-3928-9.
A. G. Hussien, A. E. Hassanien, E. H. Houssein, M. Amin, and A. T. Azar, “New binary whale optimization algorithm for dis-crete op-timization problems,” Engineering Optimization, vol. 52, no. 6, pp. 945–959, Jun. 2020, https://doi.org/10.1080/0305215X.2019.1624740.
N. Benabbou, C. Leroy, and T. Lust, “An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems.” [Online]. Available: www.aaai.org.
V. Santucci, M. Baioletti, and A. Milani, “An Algebraic Framework for Swarm and Evolutionary Algorithms in Combinatorial Optimization.”
M. T. Khumalo, H. A. Chieza, K. Prag, and M. Woolway, “An investigation of IBM Quantum Computing device performance on Combinatorial Optimisation Problems,” Jul. 2021, [Online]. Available: http://arxiv.org/abs/2107.03638.