A Survey Paper on Solving TSP using Ant Colony Optimization on GPU
Keywords:
Ant Colony Optimization, TSP, GPU, CUDA Architecture, Parallel ImplementationAbstract
Ant Colony Optimization (ACO) is meta-heuristic algorithm inspired from nature to solve many combinatorial optimization problem 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 survey on different solving TSP using ACO on GPU.
References
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 anType equation here.t 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 not be greedy: domination analysis of greedy-type heuristics for the tsp,”Discrete Applied Mathematics, vol. 117, pp. 81–86, 2002.
Jie Fu, Lin Lei Guphuo Zhou, “A Parallel Ant Colony Optimization Algorithm with GPUAcceleration 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
Kamil Rocki, Reji Suda , “High Performance GPU Accelerated Local Optimization in TSP “, IEEE 27th International Symposium on Parallel & Distributed Processing Workshops and PhD Forum- 2013
Jose M. Cecilla, Jose M. Garcia, Manuel Ujaldon, Andy Nisbt, Martyn Amos, “Parallel Strategies Ant Colony Optimization on GPUs”, Elsevier, J. Parallel Distrib. Comput. 73 (2013) 42–51
Gaurav Bhardwaj, 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, Mustufa Ozsiginan, “A UAV Path planning with parallel ACO algorithm on CUDA platform”, IEEE Unmanned Aircraft Systems (ICUAS), 2014
Dewen Zeng, 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
http://www.nvidia.com/object/what-is-gpucomputing.html#sthash. VTFrtzbE.dpuf
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2014 COMPUSOFT: An International Journal of Advanced Computer Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
©2023. COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY by COMPUSOFT PUBLICATION is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY. Permissions beyond the scope of this license may be available at Creative Commons Attribution 4.0 International Public License.
