An analysis of communication policies for homogeneous multi-colony ACO algorithms

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.