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

  • 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
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. International Journal of Smart Home. 9. 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. (2013). Discrete cat swarm optimization to resolve the traveling salesman problem. International Journal of Computer Science and Software Engineering. 3. 13-18.

Bouzidi, M. & Riffi, M. (2014). Discrete novel hybrid particle swarm optimization to solve travelling salesman problem. 17-20. 10.1109/WCCCS.2014.7107912.

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

Fang, L., Chen, P., & Liu, S. (2007, February). 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. (2018, July). Elephants herding optimization for solving the travelling salesman problem. In International Conference on Advanced Intelligent Systems for Sustainable Development (pp. 122-130). Springer, Cham. https://doi.org/10.1007/978-3-030-12065-8_12 .

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. 10.1287/opre.37.6.865.

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.

Mzili, I & Riffi, M. (2015). 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. (2015, November). 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.

Pintea, C-M & Pop, P & Chira, C. (2017). The Generalized Traveling Salesman Problem solved with Ant Algorithms. Complex Adaptive Systems Modeling, 13(7), 2015-2031. https://doi.org/10.1186/s40294-017-0048-9.

Rybickova, A., Denisa Mockova, I. & AdelaKaraskova, I. (2012). Application of Genetic Algorithm to The TsP Problem. Paripex - Indian Journal of Research. 3. 1-3. 10.15373/22501991/July2014/35.

Tanaev, V.S., Gordon, V.S., Shafransky, Y.M. (1994). NP-Hard Problems. In: Scheduling Theory. Single-Stage Systems. Mathematics and Its Applications, vol 284. Springer, Dordrecht. https://doi.org/10.1007/978-94-011-1190-4_5.

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, Xiang & Xu, Guoyi. (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, Z., Bai, Y., & Yue, L. (2012). An improved ant colony algorithm for solving TSP problems. Mathematics in Practice and Theory. 4(1), 16-28.

Published
2022-06-18
How to Cite
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. https://doi.org/10.31181/dmame0318062022m