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

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Parallel Implementation of Ant Colony Optimization for TSP based on MapReduce Framework

by Anuraj Mohan, Remya G
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 88 - Number 8
Year of Publication: 2014
Authors: Anuraj Mohan, Remya G
10.5120/15371-3900

Anuraj Mohan, Remya G . A Parallel Implementation of Ant Colony Optimization for TSP based on MapReduce Framework. International Journal of Computer Applications. 88, 8 ( February 2014), 9-12. DOI=10.5120/15371-3900

@article{ 10.5120/15371-3900,
author = { Anuraj Mohan, Remya G },
title = { A Parallel Implementation of Ant Colony Optimization for TSP based on MapReduce Framework },
journal = { International Journal of Computer Applications },
issue_date = { February 2014 },
volume = { 88 },
number = { 8 },
month = { February },
year = { 2014 },
issn = { 0975-8887 },
pages = { 9-12 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume88/number8/15371-3900/ },
doi = { 10.5120/15371-3900 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:07:05.136005+05:30
%A Anuraj Mohan
%A Remya G
%T A Parallel Implementation of Ant Colony Optimization for TSP based on MapReduce Framework
%J International Journal of Computer Applications
%@ 0975-8887
%V 88
%N 8
%P 9-12
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Travelling Salesman Problem (TSP) is one of the most widely and deeply studied problems in optimization. It belongs to the category of NP Complete problems in which no polynomial time solution is possible unless P=NP. Various researches are done on finding efficient heuristics to get provably optimal and near to optimal results to TSP. Having the push towards grid and cloud computing, it will become more necessary to adopt existing algorithms to distributed computing frameworks like MapReduce. The aim is to parallelize the ant colony optimization algorithm for solving TSP over the Apache Hadoop MapReduce framework. The paper also compares the results of the parallel implementation with the performance of the serial version of the ACO algorithm.

References
  1. M. Dorigo and G. Di Caro, "The Ant Colony Optimization meta-heuristic," in New Ideas in Optimization, D. Corne et al. , Eds. , McGraw Hill, London, UK, pp. 11–32, 1999.
  2. M. Dorigo, G. Di Caro, and L. M. Gambardella, "Ant algorithms for discrete optimization," Artificial Life, vol. 5, no. 2, pp. 137–172, 1999. W. Tsai and F. Tsai, "A New Approach for Solving Large Traveling Salesman Problem Using Evolutionary Ant Rules," IJCNN 2002,IEEE.
  3. W. Tsai and F. Tsai, "A New Approach for Solving Large Traveling Salesman Problem Using Evolutionary Ant Rules," IJCNN 2002,IEEE.
  4. H. Md. Rais, Z. A. Othman, and A. R. Hamdan, "Improved dynamic ant colony system (DACS) on symmetric Traveling Salesman Problem(TSP) ," International Conference on Intelligence and Advanced Systems, IEEE, 2007.
  5. J. Han and Y. Tian, "An improved ant colony optimization algorithm based on dynamic control of solution construction and mergence of local search solutions," Fourth International Conference on Natural Computation, IEEE, 2008.
  6. M. Colpan, "Solving geometric tsp with ants," the pennsylvania state university, 2005
  7. T. Stutzle and H. H. Hoos. "MAX-MIN ant system and local search for the traveling salesman problem," in IEEE Int'l Conf on Evolutionary Computation. Indianapolis: IEEE Press, 1997. 309~314.
  8. R. Gan, Q. Guo, H. Chang, and Y. Yi, "Improved ant colony optimization algorithm for the traveling salesman problems," Journal of Systems Engineering and Electronics, April 2010
  9. Siddhartha Jain Matthew Mallozzi "Parallel Heuristics for TSP on MapReduce" Brown University – CSCI 2950-u – Fall 2010
  10. Qing Tan, Qing He, and Zhongzhi Shi "Parallel Max-Min Ant System Using MapReduce" ICSI 2012, Part I, LNCS 7331, pp. 182–189, 2012.
  11. Sanjeev Arora. "Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems". Journal of the ACM 45(5), 753–782, 1998.
  12. . http://hadoop. apache. org/. docs/r1. 2. 1/mapred_tutorial. html
  13. TSPLIB: A Library of Sample Instances for the TSP http://comopt. i?. uni-heidelberg. de/software/TSPLIB/
Index Terms

Computer Science
Information Sciences

Keywords

MapReduce Ant Colony Optimization Parallel Computing

Powered by PhDFocusTM