Research on Solving Travelling Salesman Problem using Rank Based Ant System on GPU
Keywords:
Ant Colony Optimization, Rank Based Ant System, TSP, GPU, CUDA ArchitectureAbstract
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
How to Cite
Issue
Section
License
Copyright (c) 2015 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.
