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

Multi Colony Ant System based Solution to Travelling Salesman Problem using OpenCL

by Shobhit N Sharma, Vikram Garg
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 118 - Number 23
Year of Publication: 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 },
issue_date = { May 2015 },
volume = { 118 },
number = { 23 },
month = { May },
year = { 2015 },
issn = { 0975-8887 },
pages = { 1-3 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume118/number23/20882-3637/ },
doi = { 10.5120/20882-3637 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:02:29.258959+05:30
%A Shobhit N Sharma
%A Vikram Garg
%T Multi Colony Ant System based Solution to Travelling Salesman Problem using OpenCL
%J International Journal of Computer Applications
%@ 0975-8887
%V 118
%N 23
%P 1-3
%D 2015
%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
  1. 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
  2. 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.
  3. Yuet Ming Lam, Shuang Ying Yu, Peng Wang "A Parallel Threads Coordination Scheme for Solving Combinatorial Optimization Problems" in IEEE 2013.
  4. 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
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, "OpenCL Programming Guide", Addison Wesley pub. , 2011.
Index Terms

Computer Science
Information Sciences

Keywords

Travelling salesman problem OpenCL Graphical processing unit(GPU) Ant colony optimization.

Powered by PhDFocusTM