Extended Empirical Analysis: Communication Policies for a Parallel Multi-colony ACO Algorithm with Identical Colonies

by Max Manfrin, Mauro Birattari, Thomas Stützle, and Marco Dorigo
June 2007

Abstract:

In this article, we present a study that analyzes the impact that communication policies have on the solution quality reached by a parallel multi-colony ant colony optimization algorithm for the TRAVELING SALESMAN PROBLEM. We consider several factors of the parallel variants: the number of colonies, migration frequencies, communication strategies on different interconnection topologies, and the usage of k-opt local searches or not. We adopt a full factorial design, empirically testing the parallel variants on a distributed-memory parallel architecture, and we analyze the results with a multi-factor analysis of variance. Conclusions are drawn about the performance of the different policies. It is shown that the parallel variant adopted has a large influence on the actual performance of the algorithm.

Keywords: ant colony optimization, parallel programming, traveling salesman problem, communication policies, message passing

Introduction:

We present a study of various communication policies for a parallel homogeneous multi-colony MAX-MIN Ant System (MMAS) by means of a design of experiment approach. The idea of the multi-colony approach is to have several colonies running in parallel that exchange information to intensify the search for solutions toward promising regions of the search space. At the same time, the tendency of each colony to explore the search space differently must be preserved. We use factorial experiments based on a full factorial design, extensively testing the parallel variants on the TRAVELING SALESMAN PROBLEM (TSP) using message passing libraries and a distributed-memory parallel architecture; we analyze the impact of the factor studied on solution quality with a multi-factor analysisi of variance (ANOVA).

Algorithms:

We modify version 1.0 of ACOTSP, adding the quadrant nearest neighbors heuristic with 20 neighbors and the MPI code to implement the communication among different colonies.
For the policies we consider several factors: the number of colonies (2 levels: 4 and 8 colonies of 25 ants each), migration frequencies (2 levels: fixed and increasing), communication strategies on different interconnection topologies (4 levels: unidirectional ring [R] over the ring topology, hypercube [HC] over the hypercube topology, fully-connected [FC] and replace-worst [RW] over the fully-connected topology), and usage of local search or not (3 levels: no local search, 2-opt local search, and 3-opt local search).

All cited factors result in 2*2*4*3=48 different treatments.

The response variable is the percentage error from the known optimal cost.

To evaluate the quality of the parallel variants we compare them with the parallel independent runs [PIR] approach. Moreover, we also test the single colony MMAS algorithm (SEQ) running for k-times number of iterations as the parallel algorithms, where k=4 or 8 depending on the number of colonies.

The naming convention for the treatments is the following: a number, indicating how many identical colonies are used (4 or 8), is followed by the communication strategy label of the algorithm (PIR, R, RW, HC, FC, SEQ), and then by a letter indicating the adopted migration frequency schema (f for the fixed one, i for the increasing one), and a number indicating the adopted local search (0 for no local search, 2 for the 2-opt local search, and 3 for the 3-opt local search). Please note that the algorithms implementing PIR and SEQ strategies do not have in their names the migration frequency schema's letter. Moreover, the initial number for the algorithms implementing the SEQ strategis, identifies the multiplier factor for the number of iterations. For example the label 4RWf2 identifies an algorithm with 4 identical colonies, a replace-worst strategy on a fully-connected topology, adopting fixed migration frequency and a 2-opt local search; while the label 8PIR3 identifies an algorithm with 8 identical colonies, a parallel independent runs strategy on an isolated topology and 3-opt local search. The label 4SEQ0 identifies an algorithm with no local search and 1 colony that runs 4 times the number of iterations of the parallel algorithms.

Problem instances :

Each treatment has 30 replicates on a number of instances available from TSPLIB, according to the local search adopted (no local search, 2-opt local search, 3-opt local search), as reported in the following tables:

Raw data:

The following table containts the output traces produced by each treatment during the execution of the 30 replicates on the various instances:

ANOVAs:

Results:

Pairwise Wilcoxon rank sum tests :

To assess the statistical significance of the differences in solution costs obtained by the communication policies with respect to the PIR approach we perform a series of Pairwise Wilcoxon rank sum tests with p-values adjusted by Holm's method.

We report the results of the tests in this PDF file.