Journal
INFORMATION SCIENCES
Volume 180, Issue 12, Pages 2390-2404Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2010.02.017
Keywords
Ant colony optimization; Parallelization; Traveling salesman problem; Communication topologies
Categories
Funding
- European Community [MEST-CT-2004-505079]
- Scientific Research Directorate of the French Community of Belgium
- French Community of Belgium
Ask authors/readers for more resources
The increasing availability of parallel hardware encourages the design and adoption of parallel algorithms. In this article, we present a study in which we analyze the impact that different communication policies have on the solution quality reached by a parallel homogeneous multi-colony ACO algorithm for the traveling salesman problem. We empirically test different configurations of each algorithm on a distributed-memory parallel architecture, and analyze the results with a fixed-effects model of the analysis of variance. We consider several factors that influence the performance of a multi-colony ACO algorithm: the number of colonies, migration schedules, communication strategies on different interconnection topologies, and the use of local search. We show that the importance of the communication strategy employed decreases with increasing search effort and stronger local search, and that the relative effectiveness of one communication strategy versus another changes with the addition of local search. (C) 2010 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available