Extended Empirical Analysis: An analysis of communication policies for homogeneous multi-colony ACO algorithms through experimental design

by Max Manfrin, Thomas Stützle, Mauro Birattari, and Marco Dorigo
March 2008

Abstract:

The increasing availability of parallel hardware encourages the design and the adoption of parallel algorithms. Maximizing the degree to which a parallel platform is capable of efficiently utilizing increased computing resources is the challenge to be faced. In this article, we present a study in which, by means of a design of experiments approach, we analyze the impact that communication policies have on the solution quality reached by a parallel homogeneous multi-colony ACO algorithm for the traveling salesman problem. We adopt a full factorial design, empirically testing the treatments on a distributed-memory parallel architecture, and analyzing the results with a multi-factor analysis of variance. We consider several factors that influence the performance of a multi-colony ACO algorithm: the number of colonies, migration frequency schedules, communication strategies on different interconnection topologies, and the usage of local search. Conclustions are drawn about the performance of the different policies. It is shown that the adopted policy 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, preserving, at the same time, the tendency of each colony to explore the search space differently. 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 frequency schedules (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 schedule (f for the fixed one, i for the increasing one); finally 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 a treatmnet with 4 identical colonies, a replace-worst strategy on a fully-connected topology, adopting fixed-frequency migration schedule 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 a treatment with 1 colony that runs for 4 times the number of iterations of the parallel treatments and no local search.

Preliminary experiments:

To assess the impact of the local search component on the final solution quality in our implementationof MMAS, we compare SEQ0, SEQ2, and SEQ3 on four TSPLIB instances: lin318, rat783, nrw1379, and pr2392. In order to obtain enough statistical evidence, 30 runs are performed for each algorithm on each instance. To conduct a fair comparison, due to the different time complexities of the three algorithms, we use a stopping criterion based on maximum CPU time, instead of a maximum number of iterations. The output of all the experiments for each algorithm is available in the following table:

[1] "Instance lin318"

Pairwise comparisons using Wilcoxon rank sum test

SEQ0 SEQ2
SEQ2 3.6e-12 -
SEQ3 3.6e-12 0.33

P value adjustment method: holm

[1] "Instance rat783"

Pairwise comparisons using Wilcoxon rank sum test

SEQ0 SEQ2
SEQ2 3.0e-11 -
SEQ3 2.8e-11 2.8e-11

P value adjustment method: holm

[1] "Instance nrw1379"

Pairwise comparisons using Wilcoxon rank sum test

SEQ0 SEQ2
SEQ2 9e-11 -
SEQ3 9e-11 9e-11

P value adjustment method: holm

[1] "Instance pr2392"

Pairwise comparisons using Wilcoxon rank sum test

SEQ0 SEQ2
SEQ2 <2e-16 -
SEQ3 <2e-16 <2e-16

P value adjustment method: holm

TSPLIB Instance	Boxplot of normalized results (click to download eps format)
lin318
rat783
nrw1379
pr2392

Treatments with no local search:

In a first set of experiments, we compare those treatments with the local search factor set to no local search. The experiments are carried out on 7 TSPLIB instances: kroA100, eil101, kroA200, lin318, pcb442, att532, and rat783. In order to We use a stopping criterion based on a maximum number of iterations: 10000. The output of all the experiments for each algorithm is available in the following table:

TSPLIB Instance	Boxplot of normalized results	Boxplot of normalized results
kroA100
eil101
kroA200
lin318
pcb442
att532
rat783

Treatments with 2-opt local search:

In a second set of experiments, we compare those treatments with the local search factor set to 2-opt local search. The experiments are carried out on 7 TSPLIB instances: pcb442, att532, rat783, u1060, d1655, and pr2392. We use a stopping criterion based on a maximum number of iterations: 10000. The output of all the experiments for each algorithm is available in the following table:

TSPLIB Instance	Boxplot of normalized results	Boxplot of normalized results
pcb442
att532
rat783
u1060
nrw1379
d1655
pr2392

Treatments with 3-opt local search:

In a third set of experiments, we compare those treatments with the local search factor set to 3-opt local search. The experiments are carried out on 7 TSPLIB instances: rat783, u1060, nrw1379, d1655, pr2392, fnl4461, and rl5915. We use a stopping criterion based on a maximum number of iterations: 10000. The output of all the experiments for each algorithm is available in the following table:

TSPLIB Instance	Boxplot of normalized results	Boxplot of normalized results
rat783
u1060
nrw1379
d1655
pr2392
fnl4461
rl5915

Scalability test:

In a fourth set of experiments, the most successful policies identified previously are tested with three more levels for the factor number of colonies: 16, 32, and 64, respectively.
From the previous analyses we concluded that the overall better communication strategies are the replace-worst and the unidirectional ring, in both the cases with and without local search component. We found also that the increasing-frequency schedule has beneficial effects that tend to grow with increasing number of colonies. This fourth set of experiments is carried out on 3 TSPLIB instances: nrw1379, pr2392, and rl5915, performing 20 runs of 10000 iterations each. The output of all the experiments for each algorithm is available in the following table:

No local search

CPUs	TSPLIB instance	Algorithms
		xRi0	xRWi0	xPIR0	xSEQ0
16	nrw1379	6.83 MB	5.91 MB	5.83 MB	570 KB
	pr2392	5.3 MB	3.25 MB	1.92 MB	825 KB
	rl5915	2.09 MB	1.48 MB	1.5 MB	286 KB
32	nrw1379	13.62 MB	11.9 MB	12.15 MB	N.A.
	pr2392	10.64 MB	5.12 MB	3.88 MB	N.A.
	rl5915	4.34 MB	2.99 MB	2.98 MB	N.A.
64	nrw1379	27.89 MB	25.63 MB	24.22 MB	N.A.
	pr2392	21.9 MB	9.96 MB	7.9 MB	N.A.
	rl5915	8.44 MB	6 MB	5.94 MB	N.A.

local search	CPUs	TSPLIB instance	Boxplot of normalized results (click to download eps format)
no local search	16	nrw1379
		pr2392
		rl5915
no local search	32	nrw1379
		pr2392
		rl5915
no local search	64	nrw1379
		pr2392
		rl5915

2-opt local search

CPUs	TSPLIB instance	Algorithms
		xRi2	xRWi2	xPIR2	xSEQ2
16	nrw1379	3.15 MB	3.1 MB	2.65 MB	198 KB
	pr2392	4.35 MB	4.47 MB	4 MB	306 KB
	rl5915	2.95 MB	2.62 MB	2.95 MB	295 KB
32	nrw1379	6.36 MB	6.22 MB	5.31 MB	N.A.
	pr2392	8.79 MB	9.11 MB	8.1 MB	N.A.
	rl5915	5.83 MB	5.57 MB	5.98 MB	N.A.
64	nrw1379	12.74 MB	12.71 MB	10.65 MB	N.A.
	pr2392	17.74 MB	18.65 MB	16.22 MB	N.A.
	rl5915	11.75 MB	11.91 MB	11.82 MB	N.A.

local search	CPUs	TSPLIB instance	Boxplot of normalized results (click to download eps format)
2-opt	16	nrw1379
		pr2392
		rl5915
2-opt	32	nrw1379
		pr2392
		rl5915
2-opt	64	nrw1379
		pr2392
		rl5915

3-opt local search

CPUs	TSPLIB instance	Algorithms
		xRi3	xRWi3	xPIR3	xSEQ3
16	nrw1379	1.71 MB	1.74 MB	1.46 MB	108 KB
	pr2392	2.05 MB	2.12 MB	1.89 MB	141 KB
	rl5915	1.75 MB	1.63 MB	1.62 MB	128 KB
32	nrw1379	3.51 MB	3.51 MB	2.94 MB	N.A.
	pr2392	4.14 MB	4.34 MB	3.83 MB	N.A.
	rl5915	3.59 MB	3.33 MB	3.28 MB	N.A.
64	nrw1379	6.98 MB	7.08 MB	5.96 MB	N.A.
	pr2392	8.35 MB	8.86 MB	7.66 MB	N.A.
	rl5915	7.16 MB	7.02 MB	6.57 MB	N.A.

local search	CPUs	TSPLIB instance	Boxplot of normalized results (click to download eps format)
3-opt	16	nrw1379
		pr2392
		rl5915
3-opt	32	nrw1379
		pr2392
		rl5915
3-opt	64	nrw1379
		pr2392
		rl5915

Results of the two-sided pairwise Wilcoxon rank sum test for all the scalability tests can be found clicking here.

 

Test on unseen instances:

In this last test, we perform some experiments on randomly generated instances to verify our conjecture with unseen instances. We generated several instances of different sizes where cities are distributed uniformly in a square: 30 instances of size 316, 30 instances of size 1000, and 30 instances of size 3162. On each instance, 1 run of 10000 iterations is performed. The results are grouped by instance size and analyzed as if they were multiple runs of a single instance. To assess the statistical significance of the differences in solution costs obtained by the algorithms under analysis, we rely on a two-sided pairwise Wilcoxon rank sum test with p-values adjusted by Holm's method. (To find the optimal value, instances has been solved to the optimum using CONCORDE, and for the few ones for which the optimal solution was not found after 24 hours we took the best solution found by a publicly availabe implementation of the Iterated Lin-Kernigham Helsgaun algorithm)

To contain the computational budget, we limited our test to the treatments 8RWf2 and 8Rf2 versus 8PIR2 and 8SEQ2.

The output of all the experiments for each algorithm is available in the following table:

TSP Instance	Algorithms
unif316	8RWf2, 8Rf2, 8PIR2, 8SEQ2
unif1000	8RWf2, 8Rf2, 8PIR2, 8SEQ2
unif3162	8RWf2, 8Rf2, 8PIR2, 8SEQ2

 

TSPB Instance	Boxplot of normalized results (click to download eps format)
unif316
unif1000
unif3162

Two-sided pairwise Wilcoxon rank sum test with p-values adjusted by Holm's method

[1] "Instance unif3162 - 2-opt local search"
RWs2 Rs2 SEQ2
0 0 0

[1] "Instance unif1000 - 2-opt local search"
RWs2 Rs2 SEQ2
0.065 0.584 0.032

[1] "Instance unif316 - 2-opt local search"
RWs2 Rs2 SEQ2
0.227 0.227 0.227