Accelerating ant colony optimisation for the travelling salesman problem on the GPU

REFERENCES

• J.M.Cecilia, J.M.Garca, A.Nisbet, M.Amos, and M.Ujaldón, Enhancing data parallelism for ant colony optimization on GPUs, J. Parallel Distrib. Comput.73 (2013), pp. 42–51.
   Web of Science ®Google Scholar
• T.H.Cormen, C.E.Leiserson, R.L.Rivest, and C.Stein, Introduction to Algorithms, 2nd ed., The MIT Press, Cambridge, USA, 2001.
   Google Scholar
• A.Delévacq, P.Delisle, M.Gravel, and M.Krahecki, Parallel ant colony optimization on graphics processing units, in Proceedings of the International Conference on Parallel Distributed Processing Techniques and Applications, 2010, pp. 196–202.
   Google Scholar
• P.Delisle, M.Krahecki, M.Gravel, and C.Gagné, Parrallel implementation of an ant colony optimization metaheuristic with OpenMP, in Proceedings of the 3rd European Workshop on OpenMP, Barcelona, Spain, 2001.
   Google Scholar
• M. Dorigo, Optimization, learning and natural algorithms, Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.
   Google Scholar
• M.Dorigo and T.Stützle, Ant Colony Optimization, A Bradford Book, Scituate, USA, 2004.
   Google Scholar
• M.Dorigo and L.M.Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput.1 (1997), Los Alamitos, USA, pp. 53–66.
   Google Scholar
• M.Dorigo, V.Maniezzo, and A.Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Trans. Syst. Man Cybernet. B26 (1996), pp. 29–41.
   PubMed Web of Science ®Google Scholar
• G.Gutin, A.Yeo, and A.Zverovich, Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP, Discrete Appl. Math.117 (2002), pp. 81–86.
   Web of Science ®Google Scholar
• Y.Ito, K.Ogawa, and K.Nakano, Fast ellipse detection algorithm using hough transform on the GPU, in Proceedings of International Workshop on Challenges on Massively Parallel Processors (CMPP), December, 2011, pp. 313–319.
   Google Scholar
• D.S.Johnson and M.R.Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness, WH Freeman & Co., New York, USA, 1979.
   Google Scholar
• K.Kobashi, A.Fujii, T.Tanaka, and K.Miyoshi, Acceleration of ant colony optimization for the traveling salesman problem on a GPU, in Proceedings of the IASTED International Conference Parallel and Distributed Computing and Systems, December, ACTA Press, Calgary, Canada, 2011, pp. 108–115.
   Google Scholar
• A.Lipowski and D.Lipowska, Roulette-wheel selection via stochastic acceptance, Physica A: Stat. Mech. Appl.391 (2011), pp. 2193–2196.
   Web of Science ®Google Scholar
• D.Man, K.Uda, H.Ueyama, Y.Ito, and K.Nakano, Implementations of parallel computation of Euclidean distance map in multicore processors and GPUs, in Proceedings of the International Conference on Networking and Computing, 2010, pp. 120–127.
   Google Scholar
• D.Man, K.Uda, H.Ueyama, Y.Ito, and K.Nakano, Implementations of a parallel algorithm for computing Euclidean distance map in multicore processors and GPUs, Int. J. Network. Comput.1 (2011), pp. 260–276.
   Google Scholar
• M.Manfrin, M.Birattari, T.Stützle, and M.Dorigo, Parallel ant colony optimization for the traveling salesman problem, in Proceedings of the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, Lecture Notes on Computer ScienceVol. 4150, Springer-Verlag, Berlin, Germany, 2006, pp. 224–234.
   Google Scholar
• K.Nakano, An optimal parallel prefix-sums algorithm on the memory machine models for GPUs, in Proceedings of International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP), September, 2012, Lecture Notes on Computer ScienceVol. 7439, 2012, pp. 99–113.
   Google Scholar
• H.Nguyen, GPU Gems 3, Addison-Wesley Professional, Boston, USA, 2007.
   Google Scholar
• K.Nishida, Y.Ito, and K.Nakano, Accelerating the dynamic programming for the matrix chain product on the GPU, in Proceedings of the International Workshop on Challenges on Massively Parallel Processors, IEEE Computer Society, Los Alamitos, USA, 2011, pp. 320–326.
   Google Scholar
• NVIDIA Corp, CUDA C Best Practice Guide Version 5.0, 2012. Available at www.nividia.com.
   Google Scholar
• NVIDIA Corp, CUDA Toolkit 5.0 CURAND Guide, 2012. Available at www.nvidia.com.
   Google Scholar
• NVIDIA Corp, CUDA Zone. Available at http://developer.nvidia.com/category/zone/cuda-zone.
   Google Scholar
• NVIDIA Corp, NVIDIA CUDA C Programming Guide Version 5.0, 2012. Available at www.nvidia.com.
   Google Scholar
• K.Ogawa, Y.Ito, and K.Nakano, Efficient Canny edge detection using a GPU, in Proceedings of the International Workshop on Advances in Networking and Computing, IEEE Computer Society, Los Alamitos, USA, 2010, pp. 279–280.
   Google Scholar
• G.Reinelt, TSPLIB – A traveling salesman problem library, ORSA J. Comput.3 (1991), pp. 376–384.
   Google Scholar
• B.Schlegel, R.Gemulla, and W.Lehner, k-Ary search on modern processors, in Proceedings of the Fifth International Workshop on Data Management on New Hardware, ACM, New York, USA, 2009, pp. 52–60.
   Google Scholar
• T.Stützle and H.H.Hoos, MAX–MIN ant system, Future Gener. Comput. Syst.16 (2000), pp. 889–914.
   Web of Science ®Google Scholar