Research on Solving Travelling Salesman Problem using Rank Based Ant System on GPU

Authors

  • Khatri K Student in ME (CSE) at Hasmukh Goswami College Of Engineering, Ahmedabad, India
  • Gupta VK Professor Computer Dept, Hasmukh Goswami College Of Engineering, Ahmedabad, India

Keywords:

Ant Colony Optimization, Rank Based Ant System, TSP, GPU, CUDA Architecture

Abstract

Ant Colony Optimization (ACO) is meta-heuristic algorithm inspired from nature to solve many combinatorial optimization problems such as Travelling Salesman Problem (TSP). There are many versions of ACO used to solve TSP like, Ant System, Elitist Ant System, Max-Min Ant System, Rank based Ant System algorithm. For improved performance, these methods can be implemented in parallel architecture like GPU, CUDA architecture. Graphics Processing Unit (GPU) provides highly parallel and fully programmable platform. GPUs which have many processing units with an off-chip global memory can be used for general purpose parallel computation. This paper presents a parallel Rank Based Ant System algorithm to solve TSP by use of Pre Roulette Wheel Selection Method.

References

Wikipedia, “Travelling Salesman Problem [Online]”,http://en.wikipedia.org/wiki/Travelling_salesman problem

M. Dorigo, “Optimization, learning and natural algorithms,” Ph.D. dissertation, Dipartimento di Elettronica, Politecnico di Milano, 1992.

M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of 11cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics–Part B, vol. 26, no. 1, pp. 29–41, 1996.

M. Dorigo and T. St¨utzle, Ant Colony Optimization. MIT Press, 2004.

G. Gutin, A. Yeo, and A. Zverovich, “Traveling salesman shoud notbe greedy: domination analysis of greedy-type heuristics for the tsp,”Discrete Applied Mathematics, vol. 117, pp. 81–86, 2002.

Nvidia,C., “ABOUT GPU COMPUTING [Online]” ,http://www.nvidia.com/object/what-is-gpucomputing.html#sthash.VTFrtzbE.dpuf

Wikipedia, “Graphics Processing Unit [Online]”, http://en.wikipedia.org/wiki/Graphics_processing_unit

Ling Lin, Huailin Dong, Qingfeng Wu, “Research and Improvement of Ant Colony Algorithm based on TSP”, IEEE, 978-1-4244-8625-0/11/ - 2011

TSPLIB WebPage August 2008, http://comopt.ifi.uniheidelberg.de/software/TSPLIB95

Dorigo,M., et al., “Ant Colony Optimization ”, A Bradford Book, The MIT Press, Cambridge, Massachusetts, London, England, 2004.

Jie Fu, Lin Lei Guphuo Zhou, “A Parallel Ant Colony Optimization Algorithm with GPU-Acceleration based on All-In-Roulette Selection” Third International Workshop on Advanced Computational Intelligence August 25-27, 2010 - Suzhou, Jiangsu, China.

Laurence Dawson, Iain Stewart, “Improving Ant Colony Optimization performance On the GPU using CUDA” IEEE Congress on Evolutionary Computation, Cancún, México, June 2013.

Kai-Cheng Wei, Chao-chin Wu, Chien-Ju Wu, “Using CUDA GPU to Accelerate the Ant Colony Optimization Algorithm” IEEE International

Conference on Parallel and Distributed Computing, Applications and Technologies- 2013

KamilRocki, RejiSuda , “High Performance GPU Accelerated Local Optimization in TSP “, IEEE 27th International Symposium on Parallel & Distributed Processing Workshops and PhD Forum- 2013

GauravBhardwaj, Manish Pandey, “Parallel Implemetation of Travillening Salesman Problem using ACO”, International Journal of Computer Applications Technology and Research Volume 3–Issue 6, 385 - 389, 2014

UgurCekmez, MustufaOzsiginan, “A UAV Path planning with parallel ACO algorithm on CUDA platform”, IEEEUnmanned Aircraft Systems (ICUAS), 2014

DewenZeng, Qing He, Binheng, “Improving Ant Colony Optimization algorithm based on Dynamically Adjusting Ant Number”, IEEE International Conference on Robotics and Biomimetics December 11-14, 2012, Guangzhou, China

Maida Arnoutoive, Maida Cunic, “Parallelization of Ant Colony Optimization for the shortest path problem using OpenMP and CUDA”, IEEE MIPRO 2013, MAY 20-24, Opatija.

Ling Lin, Huailin Dong, Qingfeng Wu, “Research and Improvement of Ant Colony Algorithm based on TSP”, IEEE, 978-1-4244-8625-0/11/ - 2011

Downloads

Published

2024-02-26

How to Cite

Khatri, K., & Gupta, V. K. (2024). Research on Solving Travelling Salesman Problem using Rank Based Ant System on GPU. COMPUSOFT: An International Journal of Advanced Computer Technology, 4(05), 1778–1783. Retrieved from https://ijact.in/index.php/j/article/view/312

Issue

Section

Original Research Article

Similar Articles

<< < 10 11 12 13 14 15 16 17 18 19 > >> 

You may also start an advanced similarity search for this article.