Research Article
Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 99 - Issue 16 |
| Published: August 2014 |
| Authors: Gaurav Bhardwaj, Manish Pandey |
10.5120/17455-7406
|
Gaurav Bhardwaj, Manish Pandey . Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU. International Journal of Computer Applications. 99, 16 (August 2014), 9-13. DOI=10.5120/17455-7406
@article{ 10.5120/17455-7406,
author = { Gaurav Bhardwaj,Manish Pandey },
title = { Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU },
journal = { International Journal of Computer Applications },
year = { 2014 },
volume = { 99 },
number = { 16 },
pages = { 9-13 },
doi = { 10.5120/17455-7406 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Gaurav Bhardwaj
%A Manish Pandey
%T Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU%T
%J International Journal of Computer Applications
%V 99
%N 16
%P 9-13
%R 10.5120/17455-7406
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In this paper, we have proposed an approach to implement Ant colony optimization algorithm especially Max-Min Ant System for solving Travelling Salesman problem on GPU. GPUs are specially designed microprocessor for graphical operation and can be used for general purpose operations. ACO is a nature based inspired algorithm based on heuristics to find the solution for combinatorial optimization problems such as TSP. In this paper we have discussed many different programming issues of GPUs using OpenCL such synchronized memory access and barriers. We have used a partial solution for the stochastic probability function used in ACO for the tour construction to increase the speed-up. Thus with this implementation we are able to gain a speedup of 4. 01x in CPU parallel and up to 11. 29x speedup in GPU parallel.
References
- E. Lawler, J. Lenstra, A. Kan, and D. Shomsys Wiley New York, 1987 The Travelling Salesman Problem
- M. Dorigo and T. Stizzle : Bradford Company 2004. Ant Colony Optimization.
- C. Blum. Physics of life reviews, vol. 2, no. 4, pp. 353-373, 2005. Ant colony optimization: Introduction and recent trends.
- Y-S. You. Genetic and Evolutionary computation, 2009. Parallel ant system for Travelling Salesman Problem.
- K. D. boese , A. B. Kahng, and S. Muddu . Operations Research letters ,16:101-113,1994. A new adaptive multistart technique for combinatorial global optimization.
- M. Dorigo. PhD thesis, Politecnico di Milano, 1992. Optimization, Learning, and Natural Algorithms
- T. Stizzle and H. H. Hoos. Future Generation Computer Systems, vol. 16, no8, pp. 889–914, 2000. MAX–MIN ant system
- M. Dorigo and T. Stizzle, A Bradford Book,2004. Ant Colony Optimization.
- Ying Zhang. PHD Thesis 2006. Performance and power comparisons between fermi and cypress GPUs.
- A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, Addison-Wesley pub. , 2011. OpenCL Programming Guide.
- ] G. Reinelt, ORSA Journal on Computing, vol. 3, pp. 376–384, 1991. Tsplib–a traveling salesman problem library.
- M. Manfrin, M. Birattari, T. Stizzle, and M. Dorigo. 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, vol. LNCS 4150. Springer-Verlag, 2006, pp. 224–234. Parallel ant colony optimization for the traveling salesman problem.
- T. Stizzle, H. Hoos MAX-MIN ant system and local search for the Travelling salesman problem
- A. Colorni, M. Dorigo, V. Manniezo. Distributed Optimization by ant colonies. ECAL-91 European conference of Artificial Life.
- T. Stizzle, H. Hoos. MAX-MIN Ant System. IRIDIA
- M. Midderndorf, F. rieschle, H. Schmeck . Multi Colony Ant Algorithms. Journal of heuristics, 8:305-320,2002
Index Terms
Keywords