• Aug 09, 2018 News! Vol. 6, No. 4-No. 7, No. 3 has been indexed by EI(Inspec)!   [Click]
  • Aug 09, 2018 News!Good News! All papers from Volume 8, Number 3 have been indexed by Scopus!   [Click]
  • May 23, 2018 News![CFP] 2018 the annual meeting of IJMLC Editorial Board, ACMLC 2018, will be held in Ho Chi Minh, Vietnam, December 7-9, 2018   [Click]
Search
General Information
Editor-in-chief
Dr. Lin Huang
Metropolitan State University of Denver, USA
It's my honor to take on the position of editor in chief of IJMLC. We encourage authors to submit papers concerning any branch of machine learning and computing.
IJMLC 2018 Vol.8(2): 98-103 ISSN: 2010-3700
DOI: 10.18178/ijmlc.2018.8.2.670

Solving Traveling Salesman Problems with Ant Colony Optimization Algorithms in Sequential and Parallel Computing Environments: A Normalized Comparison

G. Dong, W. Li, J. Shen, Y. Wang, X. Fu, and W. W. Guo
Abstract—In recent years some comparative studies have explored the use of parallel ant colony optimization (ACO) algorithms over the traditionally sequential ACOs to solve the traveling salesman problem (TSP). However, these studies did not take a systematical approach to assess the performance of both algorithms on a comparable ground. In this paper, we aim to make a comparison of both the quality of the solutions and the running time as a result of the application of a sequential ACO and a parallel ACO to Eil51, Eil76 and KroA100 on a normalized and thus, comparable ground. Our study reaffirmed that the parallel algorithm is superior in computing efficiency over the sequential algorithm, particularly for larger TSPs. We also found that such a comparison could be meaningless if the size of the TSPs keeps increasing. We revealed that the worst solution among 10 repeated runs obtained from the parallel ACO was still better than the best solution among 10 repeated runs obtained from the sequential ACO, though both did not reach the global optimal solution within 300 iterations. The proposed parallel ACO has a very high consistency because at least one best solution was found within an error of 0.5% to the global optimal solution in every three repeats for all three cases.

Index Terms—Ant colony optimization, traveling salesman problem, parallel computing, sequential computing.

G. Dong is with College of Computer and Information Engineering Computing Science, Inner Mongolia Agricultural University, Hohhot, China (e-mail: donggf@imau.edu.cn).
W. Li, Y. Wang, W. W. Guo are with School of Engineering and Technology, Central Queensland University, North Rockhampton QLD 4702, Australia (e-mail: w.li@cqu.edu.au, y.wang2@cqu.edu.au, w.guo@cqu.edu.au).
J. Shen is with School of Information Systems and Technology, University of Wollongong, Wollongong, NSW 2522, Australia (e-mail: jshen@uow.edu.au).

[PDF]

Cite: G. Dong, W. Li, J. Shen, Y. Wang, X. Fu, and W. W. Guo, "Solving Traveling Salesman Problems with Ant Colony Optimization Algorithms in Sequential and Parallel Computing Environments: A Normalized Comparison," International Journal of Machine Learning and Computing vol. 8, no. 2, pp. 98-103, 2018.

Copyright © 2008-2018. International Journal of Machine Learning and Computing. All rights reserved.
E-mail: ijmlc@ejournal.net