An Improved Particle Swarm Optimization Algorithm For A Variant of TSP

International Journal of Computer Science and Engineering

© 2020 by SSRG - IJCSE Journal

Volume 7 Issue 5

Year of Publication : 2020

Authors : Dr. Nitesh M Sureja, Dr. Sanjay P Patel

10.14445/23488387/IJCSE-V7I5P105

How to Cite?

Dr. Nitesh M Sureja, Dr. Sanjay P Patel, "An Improved Particle Swarm Optimization Algorithm For A Variant of TSP," SSRG International Journal of Computer Science and Engineering , vol. 7,  no. 5, pp. 16-20, 2020. Crossref, https://doi.org/10.14445/23488387/IJCSE-V7I5P105

Abstract:

Particle swarm optimization algorithm is one of the nature inspired algorithms based on the flocking behaviour of a swarm of the birds. The standard Particle swarm optimization algorithm has been successfully used to solve many engineering problems. Each and every algorithm has its own merits and demerits like stagnation and fall in premature convergence in searching space. It is always necessary to handle the issues of exploitation and exploration of the search space. Excessive exploitation leads to premature convergence, while excessive exploration slows down the convergence. In
this paper, an improved particle swarm optimization algorithm is proposed to solve the Random Traveling Salesman Problem. Random TSP is a type of the TSP where the TSP problems are defined randomly. The results obtained from this algorithm are compared with the results obtained with other optimization algorithms like GA, MA and ACO. Results shows that the Particle swarm optimization (PSO) algorithm performs very well to solve most of TSP problems, but it can be trapped into local optimum solutions for some of the problems.

Keywords:

Particle Swarm Optimization, Nature Inspired Algorithms, Random Traveling Salesman, Optimization Introduction

References:

[1] M. M. Flood, ―The Traveling Salesman Problem, Operations Research, 1956
[2] Gerhard Reinelt. “The Traveling Salesman: Computational Solutions for TSP Applications.”, Springer-Verlag, (1994),Berlin, Heidelberg .
[3] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large- Scale Traveling Salesman Problem, J. Oper. Res. Soc. 2 (1954) 393–410.
[4] G. Laporte, The vehicle routing problem: an overview of exact and approximate algorithms, Eur. J. Oper. Res. 59 (1992) 345–358.
[5] D. Bookstaber, “Simulated Annealing for Traveling Salesman Problem”, Spring, 1997.
[6] S. M. Abdel-Moetty, “Traveling salesman problem using neural network techniques”, IEEE The 7th International Conference on Informatics and Systems (INFOS), 2010, Cairo, Egypt.
[7] Budinich, M.: A Self-Organizing Neural Network for the Traveling Salesman Problem That Is Competitive with Simulated Annealing. Neural Computing 8, 416–424 (1996).
[8] Abid Hussain, Yousaf Shad Muhammad, M. Nauman Sajid, Ijaz Hussain, Alaa Mohamd Shoukry, and Showkat Gani, “Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator,” Computational Intelligence and Neuroscience, vol. 2017, Article ID 7430125, 7 pages.
[9] Yong Deng, Yang Liu, and Deyun Zhou, “An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP,” Mathematical Problems in Engineering, vol. 2015, Article ID 212794, 6 pages, 2015.
[10] Adewole, Philip & Taofiki, Akinwale & Otunbanowo, Kehinde. (2011). A Genetic Algorithm for Solving Travelling Salesman Problem. International Journal of Advanced Computer Sciences and Applications. 2. 10.14569/IJACSA.2011.020104.
[11] Gutin, G., & Karapetyan, D. (2009). A memetic algorithm for the generalized traveling salesman problem. Natural Computing, 9(1), 47–60.
[12] Arango Serna, M. D., & Serna Uran, C. A. (2015). A Memetic Algorithm for the Traveling Salesman Problem. IEEE Latin America Transactions, 13(8), 2674–2679.
[13] M. Dorigo, T. Stutzle, “Ant Colony optimization”, A Bradford book, MIT Press Cambridge, Massachucetts,london, England (2004) .
[14] M. Dorigo, L. Gambardella, “Ant colonies for the Traveling salesman problem.” Biosystems, 43 (1997): (73-81).
[15] Jiang, H., “Solving Traveling Salesman Problem Using Artificial Bee Colony Algorithm.”, Computer Science and Technology. (2016) : (989-995)
[16] Li, L., Cheng, Y., Tan, L., & Niu, B. (2012). A Discrete Artificial Bee Colony Algorithm for TSP Problem. Lecture Notes in Computer Science, 566–573
[17] Wong, L.-P., Low, M. Y. H., & Chong, C. S. (2008). A Bee Colony Optimization Algorithm for Traveling Salesman Problem. 2008 Second Asia International Conference on Modelling & Simulation (AMS). doi:10.1109/ams.2008.27
[18] Ayon, S. I., Akhand, M. A. H., Shahriyar, S. A., & Siddique, N. (2019). “Spider Monkey Optimization to Solve Traveling Salesman Problem.”, 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE).