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

Publication Type:
Journal Article
International Journal of Machine Learning and Computing, 2018, 8 (2), pp. 98 - 103
Issue Date:
Filename Description Size
670-L0121F (2).pdfPublished Version728.68 kB
Adobe PDF
Full metadata record
© 2018, International Association of Computer Science and Information Technology. 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.
Please use this identifier to cite or link to this item: