A novel discrete Rat swarm optimization (DRSO) algorithm for solving the traveling salesman problem

Toufik Mzili; Mohammed Essaid Riffi; Ilyass Mzili; Gaurav Dhiman

doi:10.31181/dmame0318062022m

Authors

Toufik Mzili Department of Computer Science, Laboratory LAROSERI, Faculty of Science, Chouaib Doukkali University, Morocco
Mohammed Essaid Riffi Department of Computer Science, Laboratory LAROSERI, Faculty of Science, Chouaib Doukkali University, Morocco
Ilyass Mzili Department of Computer Science, Laboratory LAROSERI, Faculty of Science, Chouaib Doukkali University, Morocco
Gaurav Dhiman Department of Computer Science, Government Bikram College of Commerce, Punjab, India

DOI:

https://doi.org/10.31181/dmame0318062022m

Keywords:

Travelling Salesman Problem, Rat swarm Optimization, Combinatorial optimization, Metaheuristic, Nature-inspired, PSO

Abstract

Metaheuristics are often used to find solutions to real and complex problems. These algorithms can solve optimization problems and provide solutions close to the global optimum in an acceptable and reasonable time. In this paper, we will present a new bio-inspired metaheuristic based on the natural chasing and attacking behaviors of rats in nature, called Rat swarm optimizer. Which has given good results in solving several continuous optimization problems, and adapted it to solve a discrete, NP-hard, and classical optimization problem that is the traveling salesman problem (TSP) while respecting the natural behavior of rats. To test the efficiency of the adaptation of our proposal, we applied the adapted rat swarm optimization (RSO) algorithm on some reference instances of TSPLIB. The obtained results show the performance of the proposed method in solving the traveling salesman problem (TSP).

Downloads

Download data is not yet available.

References

Bao, H. (2015). A two-phase hybrid optimization algorithm for solving complex optimization problems. Int J Smart Home, 9(10), 27-36.

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.

Bouzidi, A., & Riffi, M. E. (2013). Discrete cat swarm optimization to resolve the traveling salesman problem. International Journal of Computer Science and Software Engineering, 3(9), 13-18.

Bouzidi, M., & Riffi, M. E. (2014). Discrete novel hybrid particle swarm optimization to solve travelling salesman problem. In 2014 5th Workshop on Codes, Cryptography and Communication Systems (WCCCS) (pp. 17-20). IEEE.

Dhiman, G., Garg, M., Nagar, A., Kumar, V., & Dehghani, M. (2021). A novel algorithm for global optimization: rat swarm optimizer. Journal of Ambient Intelligence and Humanized Computing, 12, 8457-8482.

Fang, L., Chen, P., & Liu, S. (2007). Particle swarm optimization with simulated annealing for TSP. In Proceedings of the 6th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases (pp. 206-210).

Glover, F. (1989). Tabu Search—Part I. ORSA Journal on Computing 1(3), 190-206.

Gündüz, M., Kiran, M. S., & Özceylan, E. (2015). A hierarchic approach based on swarm intelligence to solve the traveling salesman problem. Turkish Journal of Electrical Engineering and Computer Sciences, 23(1), 103-117.

Hossam, A., Bouzidi, A., & Riffi, M. E. (2019). Elephants herding optimization for solving the travelling salesman problem. In Advanced Intelligent Systems for Sustainable Development (AI2SD’2018) Vol 2: Advanced Intelligent Systems Applied to Energy (pp. 122-130). Springer International Publishing.

Mzili, I & Riffi, M. (2015a). Discrete Penguins search optimization algorithm to solve the traveling salesman problem. Journal of Theoretical and Applied Information Technology. 72(3), 331-336.

Mzili, I., Bouzidi, M., & Riffi, M. E. (2015b). A novel hybrid penguins search optimization algorithm to solve travelling salesman problem. In 2015 Third World Conference on Complex Systems (WCCS) (pp. 1-5). IEEE.

Korupolu, M. R., Plaxton, C. G., & Rajaraman, R. (2000). Analysis of a local search heuristic for facility location problems. Journal of algorithms, 37(1), 146-188.

Pintea, C. M., Pop, P. C., & Chira, C. (2017). The generalized traveling salesman problem solved with ant algorithms. Complex Adaptive Systems Modeling, 5(1), 1-9.

Johnson, D., Aragon, C., McGeoch, L., & Schevon, C. (1989). Optimization by Simulated Annealing: An Experimental Evaluation. Part I, Graph Partitioning. Operations Research. 37, 865-892.

Rybickova, A., Mockova, D., & Karaskova, A. (2014). Application of Genetic Algorithm to The TsP Problem. Paripex - Indian Journal Of Research. 3(7), 105-107.

Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1994). NP-Hard Problems. Scheduling Theory. Single-Stage Systems, 253-311.

Wang, X., & Xu, G. (2011). Hybrid differential evolution algorithm for traveling salesman problem. Procedia Engineering, 15, 2716-2720. https://doi.org/10.1016/j.proeng.2011.08.511.

Wang, K., Huang, L., Zhou, C., & Pang, W. (2003). Particle swarm optimization for traveling salesman problem. In 2003 International Conference on Machine Learning and Cybernetics (Vol. 3, pp. 1583-1585). IEEE Press. https://doi.org/10.1109/ICMLC.2003.1259748.

Wang, Z. Y. (2012). An improved ant colony algorithm for solving TSP problems. Mathematics in Practice and Theory, 24(4), 133-140.