CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU

by Gaurav Bhardwaj, Manish Pandey
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 99 - Number 16
Year of Publication: 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 },
issue_date = { August 2014 },
volume = { 99 },
number = { 16 },
month = { August },
year = { 2014 },
issn = { 0975-8887 },
pages = { 9-13 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume99/number16/17455-7406/ },
doi = { 10.5120/17455-7406 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:28:21.418283+05:30
%A Gaurav Bhardwaj
%A Manish Pandey
%T Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU
%J International Journal of Computer Applications
%@ 0975-8887
%V 99
%N 16
%P 9-13
%D 2014
%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
  1. E. Lawler, J. Lenstra, A. Kan, and D. Shomsys Wiley New York, 1987 The Travelling Salesman Problem
  2. M. Dorigo and T. Stizzle : Bradford Company 2004. Ant Colony Optimization.
  3. C. Blum. Physics of life reviews, vol. 2, no. 4, pp. 353-373, 2005. Ant colony optimization: Introduction and recent trends.
  4. Y-S. You. Genetic and Evolutionary computation, 2009. Parallel ant system for Travelling Salesman Problem.
  5. 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.
  6. M. Dorigo. PhD thesis, Politecnico di Milano, 1992. Optimization, Learning, and Natural Algorithms
  7. T. Stizzle and H. H. Hoos. Future Generation Computer Systems, vol. 16, no8, pp. 889–914, 2000. MAX–MIN ant system
  8. M. Dorigo and T. Stizzle, A Bradford Book,2004. Ant Colony Optimization.
  9. Ying Zhang. PHD Thesis 2006. Performance and power comparisons between fermi and cypress GPUs.
  10. A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, Addison-Wesley pub. , 2011. OpenCL Programming Guide.
  11. ] G. Reinelt, ORSA Journal on Computing, vol. 3, pp. 376–384, 1991. Tsplib–a traveling salesman problem library.
  12. 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.
  13. T. Stizzle, H. Hoos MAX-MIN ant system and local search for the Travelling salesman problem
  14. A. Colorni, M. Dorigo, V. Manniezo. Distributed Optimization by ant colonies. ECAL-91 European conference of Artificial Life.
  15. T. Stizzle, H. Hoos. MAX-MIN Ant System. IRIDIA
  16. M. Midderndorf, F. rieschle, H. Schmeck . Multi Colony Ant Algorithms. Journal of heuristics, 8:305-320,2002
Index Terms

Computer Science
Information Sciences

Keywords

Parallel Implementation

Powered by PhDFocusTM