File(s) not publicly available

Solving traveling salesman problems with ant colony optimization algorithms in sequential and parallel computing environments: A normalized comparison

journal contribution
posted on 23.04.2019, 00:00 by G Dong, Wei Li, J Shen, Yucang Wang, X Fu, Wanwu Guo
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. © 2018, International Association of Computer Science and Information Technology.

History

Volume

8

Issue

2

Start Page

98

End Page

103

Number of Pages

6

ISSN

2010-3700

Publisher

International Association of Computer Science and Information Technology (I A C S I T), Singapore

Peer Reviewed

Yes

Open Access

No

External Author Affiliations

University of Wollongong; Inner Mongolia Agricultural University, China

Author Research Institute

Centre for Intelligent Systems

Era Eligible

Yes

Journal

International Journal of Machine Learning and Computing

Exports