Research Article
Multi Colony Ant System based Solution to Travelling Salesman Problem using OpenCL
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 118 - Issue 23 |
| Published: May 2015 |
| Authors: Shobhit N Sharma, Vikram Garg |
10.5120/20882-3637
|
Shobhit N Sharma, Vikram Garg . Multi Colony Ant System based Solution to Travelling Salesman Problem using OpenCL. International Journal of Computer Applications. 118, 23 (May 2015), 1-3. DOI=10.5120/20882-3637
@article{ 10.5120/20882-3637,
author = { Shobhit N Sharma,Vikram Garg },
title = { Multi Colony Ant System based Solution to Travelling Salesman Problem using OpenCL },
journal = { International Journal of Computer Applications },
year = { 2015 },
volume = { 118 },
number = { 23 },
pages = { 1-3 },
doi = { 10.5120/20882-3637 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%A Shobhit N Sharma
%A Vikram Garg
%T Multi Colony Ant System based Solution to Travelling Salesman Problem using OpenCL%T
%J International Journal of Computer Applications
%V 118
%N 23
%P 1-3
%R 10.5120/20882-3637
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Travelling salesman problem (TSP) finds applications in wide domains. It is a well known NP Hard problem. In this paper we have proposed GPU based implementation for TSP using OpenCL based on Multi colony Ant System. A comparative analysis is done among the standard travelling salesman problem, multi colony based implementation of travelling salesman problem and GPU based implementation. It is found that GPU based implementation is most efficient in terms of execution time and average tour length.
References
- Laurence Dawson, Iain Stewart "Improving Ant Colony Optimization performance on the GPU using CUDA" in 2013 IEEE Congress on Evolutionary Computation June 20-23, Cancún, México
- Elmedina Fejzagi?, Adna Oputi? "Performance Comparison of Sequential and Parallel Execution of the Ant Colony Optimization Algorithm for Solving the Traveling Salesman Problem" in MIPRO 2013.
- Yuet Ming Lam, Shuang Ying Yu, Peng Wang "A Parallel Threads Coordination Scheme for Solving Combinatorial Optimization Problems" in IEEE 2013.
- YingLi , Kai Ma, Jiong Zhang "An Efficient Multicore based Parallel Computing Approach for TSP Problems" in 2013 Ninth International Conference on Semantics, Knowledge and Grids
- Wang Jiening, Dong Jiankang, Zhang Chunfeng "Implementation of Ant Colony Algorithm based on GPU" in 2009 Sixth International Conference on Computer Graphics, Imaging and Visualization.
- Akihiro Uchida, Yasuaki Ito, Koji Nakano "An Efficient GPU Implementation of Ant Colony Optimization for the Traveling Salesman Problem" in 2012 Third International Conference on Networking and Computing.
- Kamil Rocki, Reiji Suda "High Performance GPU Accelerated Local Optimization in TSP" in 2013 IEEE 27th International Symposium on Parallel & Distributed Processing Workshops and PhD Forum.
- Murilo Zangari de Souza, Aurora Trinidad Ramirez Pozo "A GPU Implementation of MOEA/D-ACO for the Multiobjective Traveling Salesman Problem" in 2014 Brazilian Conference on Intelligent Systems.
- A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, "OpenCL Programming Guide", Addison Wesley pub. , 2011.
Index Terms
Keywords