Artificial rat optimization with decision-making: A bio-inspired metaheuristic algorithm for solving the traveling salesman problem

Toufik Mzili; Ilyass  Mzili; Mohammed Essaid  Riffi

doi:10.31181/dmame622023644

Authors

Toufik Mzili Department of Computer Science, Faculty of Science, Chouaib Doukkali, University, EI Jadida , Morocco https://orcid.org/0000-0002-5733-3119
Ilyass Mzili Department of Management, Faculty of Economics and Management, Hassan First University, Settat, Morocco https://orcid.org/0000-0002-9096-8271
Mohammed Essaid Riffi Department of Computer Science, Faculty of Science, Chouaib Doukkali, University, EI Jadida , Morocco https://orcid.org/0000-0003-1576-2174

DOI:

https://doi.org/10.31181/dmame622023644

Keywords:

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. DOI: https://doi.org/10.1016/j.jksuci.2016.03.001

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 DOI: 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. DOI: https://doi.org/10.1016/S0305-0548(98)00047-1

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. DOI: https://doi.org/10.1007/s10462-020-09869-8

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. DOI: https://doi.org/10.1109/4235.585892

Ezugwu, A. E.-S., & Adewumi, A. O. (2017). Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems with Applications, 87, 70–78. DOI: https://doi.org/10.1016/j.eswa.2017.06.007

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. DOI: https://doi.org/10.1016/j.advengsoft.2017.03.014

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 DOI: 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 DOI: 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 DOI: 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. DOI: https://doi.org/10.1016/j.compstruc.2004.01.002

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 DOI: 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. DOI: https://doi.org/10.1016/j.asoc.2015.09.045

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. DOI: https://doi.org/10.1016/j.advengsoft.2017.07.002

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. DOI: https://doi.org/10.1007/s10489-017-1019-8

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100. DOI: https://doi.org/10.1016/S0305-0548(97)00031-2

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. DOI: https://doi.org/10.31181/dmame0318062022m

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. DOI: https://doi.org/10.1016/j.ins.2009.03.004

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. DOI: https://doi.org/10.1007/s00521-015-1978-9

Simon, D. (2008). Biogeography-Based Optimization. IEEE Transactions on Evolutionary Computation, 12(6), 702–713. DOI: https://doi.org/10.1109/TEVC.2008.919004

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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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.