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

Download data is not yet available.

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.