Artificial rat optimization with decision-making: A bio-inspired metaheuristic algorithm for solving the traveling salesman problem
DOI:
https://doi.org/10.31181/dmame622023644Keywords:
Bio-inspired; Metaheuristics; Rat Swarm Optimizer (RSO); Combinatorial optimization; TSP; Artificial intelligence (AI); Swarm intelligence (SI); Modeling systems.Abstract
In this paper, we present the Rat Swarm Optimization with Decision Making (HDRSO), a hybrid metaheuristic algorithm inspired by the hunting behavior of rats, for solving the Traveling Salesman Problem (TSP). The TSP is a well-known NP-hard combinatorial optimization problem with important applications in transportation, logistics, and manufacturing systems. To improve the search process and avoid getting stuck in local minima, we added a natural mechanism to HDRSO through the incorporation of crossover and selection operators. In addition, we applied 2-opt and 3-opt heuristics to the best solution found by HDRSO. The performance of HDRSO was evaluated on a set of symmetric instances from the TSPLIB library and the results demonstrated that HDRSO is a competitive and robust method for solving the TSP, achieving better results than the best-known solutions in some cases.
Downloads
References
Abualigah, L., Elaziz, M. A., Sumari, P., Khasawneh, A. M., Alshinwan, M., Mirjalili, S., Shehab, M., Abuaddous, H. Y., & Gandomi, A. H. (2022). Black hole algorithm: A comprehensive survey. Applied Intelligence, 52(10), 11892–11915.
Anuar, S., Selamat, A., & Sallehuddin, R. (2016). A modified scout bee for artificial bee colony algorithm and its performance on optimization problems. Journal of King Saud University - Computer and Information Sciences, 28(4), 395–406.
Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition. 2007 IEEE Congress on Evolutionary Computation, 4661–4667. https://doi.org/10.1109/CEC.2007.4425083
Barbarosoglu, G., & Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26(3), 255–270.
BAŞ, E., & ÜLKER, E. (2021). Dıscrete socıal spıder algorıthm for the travelıng salesman problem. Artificial Intelligence Review, 54(2), 1063–1085.
Chung, S. W., & Freund, J. B. (2022). An optimization method for chaotic turbulent flow. Journal of Computational Physics, 457, 111077. https://doi.org/10.1016/j.jcp.2022.111077
Cinar, A. C., Korkmaz, S., & Kiran, M. S. (2020). A discrete tree-seed algorithm for solving symmetric traveling salesman problem. Engineering Science and Technology, an International Journal, 23(4), 879–890.
Cotta, C., Mathieson, L., & Moscato, P. (2018). Memetic Algorithms. In Handbook of Heuristics (pp. 607–638). Springer International Publishing. https://doi.org/10.1007/978-3-319-07124-4_29
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.
Ezugwu, A. E.-S., & Adewumi, A. O. (2017). Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems with Applications, 87, 70–78.
Ezugwu, A. E., Shukla, A. K., Nath, R., Akinyelu, A. A., Agushaka, J. O., Chiroma, H., & Muhuri, P. K. (2021). Metaheuristics: a comprehensive overview and classification along with bibliometric analysis. Artificial Intelligence Review, 54(6), 4237–4316.
Ginidi, A., Ghoneim, S. M., Elsayed, A., El-Sehiemy, R., Shaheen, A., & El-Fergany, A. (2021). Gorilla Troops Optimizer for Electrically Based Single and Double-Diode Models of Solar Photovoltaic Systems. Sustainability, 13(16), 9459. https://doi.org/10.3390/su13169459
Gunduz, M., & Aslan, M. (2021). DJAYA: A discrete Jaya algorithm for solving traveling salesman problem. Applied Soft Computing, 105, 107275. https://doi.org/10.1016/j.asoc.2021.107275
Kaveh, A., & Dadras, A. (2017). A novel meta-heuristic optimization algorithm: Thermal exchange optimization. Advances in Engineering Software, 110, 69–84.
Kennedy, J., & Eberhart, R. (n.d.). Particle swarm optimization. Proceedings of ICNN’95 - International Conference on Neural Networks, 1942–1948. https://doi.org/10.1109/ICNN.1995.488968
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1987). Optimization by Simulated Annealing. In Readings in Computer Vision (pp. 606–615). Elsevier. https://doi.org/10.1016/B978-0-08-051581-6.50059-3
Koza, J. R., & Poli, R. (2005). Genetic Programming. In E. K. Burke & G. Kendall (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (pp. 127–164). Springer US. https://doi.org/10.1007/0-387-28356-0_5
Kumar, A., Vohra, M., Pant, S., & Singh, S. K. (2021). Optimization techniques for petroleum engineering: A brief review. International Journal of Modelling and Simulation, 41(5), 326–334.
Kumar, J., Kumar Singh, A., Mohan, A., & Buyya, R. (2021). Metaheuristic Optimization Algorithms. In Machine Learning for Cloud Management (pp. 59–74). Chapman and Hall/CRC. https://doi.org/10.1201/9781003110101-4
Lee, K. S., & Geem, Z. W. (2004). A new structural optimization method based on the harmony search algorithm. Computers & Structures, 82(9–10), 781–798.
Lourenço, H. R., Martin, O. C., & Stützle, T. (2010). Iterated Local Search: Framework and Applications (pp. 363–397). https://doi.org/10.1007/978-1-4419-1665-5_12
Medjahed, S. A., Ait Saadi, T., Benyettou, A., & Ouali, M. (2016). Gray Wolf Optimizer for hyperspectral band selection. Applied Soft Computing, 40, 178–186.
Mirjalili, S., Gandomi, A. H., Mirjalili, S. Z., Saremi, S., Faris, H., & Mirjalili, S. M. (2017). Salp Swarm Algorithm: A bio-inspired optimizer for engineering design problems. Advances in Engineering Software, 114, 163–191.
Mirjalili, S. Z., Mirjalili, S., Saremi, S., Faris, H., & Aljarah, I. (2018). Grasshopper optimization algorithm for multi-objective optimization problems. Applied Intelligence, 48(4), 805–820.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100.
Mzili, T., Riffi, M. E., Mzili, I., & Dhiman, G. (2022). A novel discrete Rat swarm optimization (DRSO) algorithm for solving the traveling salesman problem. Decision Making: Applications in Management and Engineering, 5(2), 287–299.
Opara, K. R., & Arabas, J. (2019). Differential Evolution: A survey of theoretical analyses. Swarm and Evolutionary Computation, 44, 546–558.
Osaba, E., Yang, X.-S., & Del Ser, J. (2020). Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics. In Nature-Inspired Computation and Swarm Intelligence (pp. 135–164). Elsevier. https://doi.org/10.1016/B978-0-12-819714-1.00020-8
Pereira, J. L. J., Francisco, M. B., Diniz, C. A., Antônio Oliver, G., Cunha, S. S., & Gomes, G. F. (2021). Lichtenberg algorithm: A novel hybrid physics-based meta-heuristic for global optimization. Expert Systems with Applications, 170, 114522. https://doi.org/10.1016/j.eswa.2020.114522
Peres, F., & Castelli, M. (2021). Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development. Applied Sciences, 11(14), 6449. https://doi.org/10.3390/app11146449
Prajapati, V. K., Jain, M., & Chouhan, L. (2020). Tabu Search Algorithm (TSA): A Comprehensive Survey. 2020 3rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE), 1–8. https://doi.org/10.1109/ICETCE48199.2020.9091743
Rahman, Md. A., & Parvez, H. (2021). Repetitive Nearest Neighbor Based Simulated Annealing Search Optimization Algorithm for Traveling Salesman Problem. OALib, 08(06), 1–17. https://doi.org/10.4236/oalib.1107520
Rashedi, E., Nezamabadi-pour, H., & Saryazdi, S. (2009). GSA: A Gravitational Search Algorithm. Information Sciences, 179(13), 2232–2248.
Rawat, S. S., Pant, S., Kumar, A., Ram, M., Sharma, H. K., & Kumar, A. (2022). A State-of-the-Art Survey on Analytical Hierarchy Process Applications in Sustainable Development. International Journal of Mathematical, Engineering and Management Sciences, 7(6), 883–917.
Saji, Y., & Riffi, M. E. (2016). A novel discrete bat algorithm for solving the travelling salesman problem. Neural Computing and Applications, 27(7), 1853–1866.
Simon, D. (2008). Biogeography-Based Optimization. IEEE Transactions on Evolutionary Computation, 12(6), 702–713.
Slowik, A., & Kwasnicka, H. (2020). Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications, 32(16), 12363–12379.
Sun, L. (2015). Genetic Algorithm for TSP Problem. https://doi.org/10.2991/iiicec-15.2015.319
Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1994). NP-Hard Problems. In Scheduling Theory. Single-Stage Systems (pp. 253–311). Springer Netherlands. https://doi.org/10.1007/978-94-011-1190-4_5
Uniyal, N., Pant, S., Kumar, A., & Pant, P. (2022). Nature-inspired metaheuristic algorithms for optimization. In Meta-heuristic Optimization Techniques (pp. 1–10). De Gruyter. https://doi.org/10.1515/9783110716214-001
Wu, C., Fu, X., Pei, J., & Dong, Z. (2021). A Novel Sparrow Search Algorithm for the Traveling Salesman Problem. IEEE Access, 9, 153456–153471.
Xu, G.-H., Zhang, T.-W., & Lai, Q. (2022). A new firefly algorithm with mean condition partial attraction. Applied Intelligence, 52(4), 4418–4431.
Yang, X.-S. (2009a). Firefly Algorithms for Multimodal Optimization (pp. 169–178). https://doi.org/10.1007/978-3-642-04944-6_14
Yang, X.-S. (2009b). Firefly Algorithms for Multimodal Optimization (pp. 169–178). https://doi.org/10.1007/978-3-642-04944-6_14
Yang, X.-S. (2010). A New Metaheuristic Bat-Inspired Algorithm (pp. 65–74). https://doi.org/10.1007/978-3-642-12538-6_6
Yang, X.-S., & Deb, S. (2009). Cuckoo Search via Lévy flights. 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 210–214. https://doi.org/10.1109/NABIC.2009.5393690
Zhong, X. (2021). On the approximation ratio of the 3-Opt algorithm for the (1,2)-TSP. Operations Research Letters, 49(4), 515–521.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Decision Making: Applications in Management and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
