Supporting material for the article:

The impact of design choices of multiobjective ant colony optimization algorithms on performance: An experimental study on the biobjective TSP

By Manuel López-Ibáñez and Thomas Stützle
March 2010 (last update: July 2010)

Table of Contents
  1. Abstract
  2. MOAQ: β = 0 vs. β = 2
  3. P-ACO: Single vs. multiple heuristic matrices
  4. BicriterionAnt: One vs. three colonies
  5. BicriterionAnt: Weighted product vs. weigthed sum
  6. mACO-1 vs. mACO-2
  7. mACO-3 vs. mACO-4
  8. Comparison of MOACO algorithms vs. BicriterionAnt with 3 colonies

Manuel López-Ibáñez and Thomas Stützle. The impact of design choices of multi-objective ant colony optimization algorithms on performance: An experimental study on the biobjective TSP. In GECCO 2010, pages 71–78. ACM press, New York, NY, 2010.
★ Best paper award
[ bibtex | doi: 10.1145/1830483.1830494 |  supplementary information ]

Abstract:

Over the last few years, there have been a number of proposals of ant colony optimization (ACO) algorithms for tackling multiobjective combinatorial optimization problems. These proposals adapt ACO concepts in various ways, for example, some use multiple pheromone matrices and multiple heuristic matrices and others use multiple ant colonies. In this article, we carefully examine several of the most prominent of these proposals. In particular, we identify commonalities among the approaches by recasting the original formulation of the algorithms in different terms. For example, several proposals described in terms of multiple colonies can be cast equivalently using a single ant colony, where ants use different weights for aggregating the pheromone and/or the heuristic information. We study algorithmic choices for the various proposals and we identify previously undetected trade-offs in their performance.

Keywords: Multiobjective Optimization, Ant Colony Optimization, Travelling Salesman Problem

MOAQ: β = 0 vs. β = 2

These plots illustrate the different behaviour between β = 0 vs. β = 2. Each file contains plots of the output of 15 independent runs with different random seeds. Plots are given for a limit of iterations of 1000, 5000 and 25000, and for a time limit of n/5, n and 5n seconds, where n is the instance size.

ACS MMAS
Instances β = 0 β = 2 β = 0 β = 2
kroAB100.tsp kroAB100.tsp/a24rho05beta0_MOAQ_acs_r15t100.png kroAB100.tsp/a24rho05beta2_MOAQ_acs_r15t100.png kroAB100.tsp/a24rho05beta0_MOAQ_mmas_r15t100.png kroAB100.tsp/a24rho05beta2_MOAQ_mmas_r15t100.png
kroAB100.tsp-MOAQ-beta0-acs.tar.gz kroAB100.tsp-MOAQ-beta2-acs.tar.gz kroAB100.tsp-MOAQ-beta0-mmas.tar.gz kroAB100.tsp-MOAQ-beta2-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a24rho05beta0_MOAQ_acs_r15t200.png kroAB200.tsp/a24rho05beta2_MOAQ_acs_r15t200.png kroAB200.tsp/a24rho05beta0_MOAQ_mmas_r15t200.png kroAB200.tsp/a24rho05beta2_MOAQ_mmas_r15t200.png
kroAB200.tsp-MOAQ-beta0-acs.tar.gz kroAB200.tsp-MOAQ-beta2-acs.tar.gz kroAB200.tsp-MOAQ-beta0-mmas.tar.gz kroAB200.tsp-MOAQ-beta2-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a24rho05beta0_MOAQ_acs_r15t300.png euclidAB300.tsp/a24rho05beta2_MOAQ_acs_r15t300.png euclidAB300.tsp/a24rho05beta0_MOAQ_mmas_r15t300.png euclidAB300.tsp/a24rho05beta2_MOAQ_mmas_r15t300.png
euclidAB300.tsp-MOAQ-beta0-acs.tar.gz euclidAB300.tsp-MOAQ-beta2-acs.tar.gz euclidAB300.tsp-MOAQ-beta0-mmas.tar.gz euclidAB300.tsp-MOAQ-beta2-mmas.tar.gz

P-ACO: Single vs. multiple heuristic matrices

Each plots displays differences in the EAFs of two alternatives. Each EAF is calculated from 15 independent runs with different random seeds. Plots are given for a limit of iterations of 1000, 5000 and 25000, and for a time limit of n/5, n and 5n seconds, where n is the instance size.

Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a24rho05beta2_PACO_acs_singleheu_r15t100-a24rho05beta2_PACO_acs_r15t100.png kroAB100.tsp/a24rho05beta2_PACO_mmas_singleheu_r15t100-a24rho05beta2_PACO_mmas_r15t100.png
kroAB100.tsp-PACO-single-vs-multiple-heu-acs.tar.gz kroAB100.tsp-PACO-single-vs-multiple-heu-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a24rho05beta2_PACO_acs_singleheu_r15t200-a24rho05beta2_PACO_acs_r15t200.png kroAB200.tsp/a24rho05beta2_PACO_mmas_singleheu_r15t200-a24rho05beta2_PACO_mmas_r15t200.png
kroAB200.tsp-PACO-single-vs-multiple-heu-acs.tar.gz kroAB200.tsp-PACO-single-vs-multiple-heu-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a24rho05beta2_PACO_acs_singleheu_r15t300-a24rho05beta2_PACO_acs_r15t300.png euclidAB300.tsp/a24rho05beta2_PACO_mmas_singleheu_r15t300-a24rho05beta2_PACO_mmas_r15t300.png
euclidAB300.tsp-PACO-single-vs-multiple-heu-acs.tar.gz euclidAB300.tsp-PACO-single-vs-multiple-heu-mmas.tar.gz

BicriterionAnt: One vs. three colonies

Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a24c1rho05_BicriterionAnt_acs_dtau_r15t100-a8c3rho05_BicriterionAnt_acs_dtau_r15t100.png kroAB100.tsp/a24c1rho05_BicriterionAnt_mmas_dtau_r15t100-a8c3rho05_BicriterionAnt_mmas_dtau_r15t100.png
kroAB100.tsp-BCAnt-a8c3-vs-a24c1-acs.tar.gz kroAB100.tsp-BCAnt-a8c3-vs-a24c1-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a24c1rho05_BicriterionAnt_acs_dtau_r15t200-a8c3rho05_BicriterionAnt_acs_dtau_r15t200.png kroAB200.tsp/a24c1rho05_BicriterionAnt_mmas_dtau_r15t200-a8c3rho05_BicriterionAnt_mmas_dtau_r15t200.png
kroAB200.tsp-BCAnt-a8c3-vs-a24c1-acs.tar.gz kroAB200.tsp-BCAnt-a8c3-vs-a24c1-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a24c1rho05_BicriterionAnt_acs_dtau_r15t300-a8c3rho05_BicriterionAnt_acs_dtau_r15t300.png euclidAB300.tsp/a24c1rho05_BicriterionAnt_mmas_dtau_r15t300-a8c3rho05_BicriterionAnt_mmas_dtau_r15t300.png
euclidAB300.tsp-BCAnt-a8c3-vs-a24c1-acs.tar.gz euclidAB300.tsp-BCAnt-a8c3-vs-a24c1-mmas.tar.gz

BicriterionAnt: Weighted product vs. weigthed sum

Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a24c1rho05_BicriterionAnt_acs_dtau_r15t100-a24c1rho05_BicriterionAnt_acs_sum_dtau_r15t100.png kroAB100.tsp/a24c1rho05_BicriterionAnt_mmas_dtau_r15t100-a24c1rho05_BicriterionAnt_mmas_sum_dtau_r15t100.png
kroAB100.tsp-BCAnt-sum-vs-product-acs.tar.gz kroAB100.tsp-BCAnt-sum-vs-product-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a24c1rho05_BicriterionAnt_acs_dtau_r15t200-a24c1rho05_BicriterionAnt_acs_sum_dtau_r15t200.png kroAB200.tsp/a24c1rho05_BicriterionAnt_mmas_dtau_r15t200-a24c1rho05_BicriterionAnt_mmas_sum_dtau_r15t200.png
kroAB200.tsp-BCAnt-sum-vs-product-acs.tar.gz kroAB200.tsp-BCAnt-sum-vs-product-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a24c1rho05_BicriterionAnt_acs_dtau_r15t300-a24c1rho05_BicriterionAnt_acs_sum_dtau_r15t300.png euclidAB300.tsp/a24c1rho05_BicriterionAnt_mmas_dtau_r15t300-a24c1rho05_BicriterionAnt_mmas_sum_dtau_r15t300.png
euclidAB300.tsp-BCAnt-sum-vs-product-acs.tar.gz euclidAB300.tsp-BCAnt-sum-vs-product-mmas.tar.gz

mACO-1 vs. mACO-2

Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a24rho05beta2_mACO1_acs_r15t100-a24rho05beta2_mACO2_acs_r15t100.png kroAB100.tsp/a24rho05beta2_mACO1_mmas_r15t100-a24rho05beta2_mACO2_mmas_r15t100.png
kroAB100.tsp-mACO1-vs-mACO2-acs.tar.gz kroAB100.tsp-mACO1-vs-mACO2-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a24rho05beta2_mACO1_acs_r15t200-a24rho05beta2_mACO2_acs_r15t200.png kroAB200.tsp/a24rho05beta2_mACO1_mmas_r15t200-a24rho05beta2_mACO2_mmas_r15t200.png
kroAB200.tsp-mACO1-vs-mACO2-acs.tar.gz kroAB200.tsp-mACO1-vs-mACO2-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a24rho05beta2_mACO1_acs_r15t300-a24rho05beta2_mACO2_acs_r15t300.png euclidAB300.tsp/a24rho05beta2_mACO1_mmas_r15t300-a24rho05beta2_mACO2_mmas_r15t300.png
euclidAB300.tsp-mACO1-vs-mACO2-acs.tar.gz euclidAB300.tsp-mACO1-vs-mACO2-mmas.tar.gz

mACO-3 vs. mACO-4

Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a24rho05beta2_mACO3_acs_r15t100-a24rho05beta2_mACO4_acs_r15t100.png kroAB100.tsp/a24rho05beta2_mACO3_mmas_r15t100-a24rho05beta2_mACO4_mmas_r15t100.png
kroAB100.tsp-mACO3-vs-mACO4-acs.tar.gz kroAB100.tsp-mACO3-vs-mACO4-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a24rho05beta2_mACO3_acs_r15t200-a24rho05beta2_mACO4_acs_r15t200.png kroAB200.tsp/a24rho05beta2_mACO3_mmas_r15t200-a24rho05beta2_mACO4_mmas_r15t200.png
kroAB200.tsp-mACO3-vs-mACO4-acs.tar.gz kroAB200.tsp-mACO3-vs-mACO4-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a24rho05beta2_mACO3_acs_r15t300-a24rho05beta2_mACO4_acs_r15t300.png euclidAB300.tsp/a24rho05beta2_mACO3_mmas_r15t300-a24rho05beta2_mACO4_mmas_r15t300.png
euclidAB300.tsp-mACO3-vs-mACO4-acs.tar.gz euclidAB300.tsp-mACO3-vs-mACO4-mmas.tar.gz

Comparison of MOACO algorithms vs. BicriterionAnt with 3 colonies

Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t100-a24rho05beta2_COMPETants_acs_r15t100.png kroAB100.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t100-a24rho05beta2_COMPETants_mmas_r15t100.png
kroAB100.tsp-BCc3-vs-COMPETants-acs.tar.gz kroAB100.tsp-BCc3-vs-COMPETants-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t200-a24rho05beta2_COMPETants_acs_r15t200.png kroAB200.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t200-a24rho05beta2_COMPETants_mmas_r15t200.png
kroAB200.tsp-BCc3-vs-COMPETants-acs.tar.gz kroAB200.tsp-BCc3-vs-COMPETants-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t300-a24rho05beta2_COMPETants_acs_r15t300.png euclidAB300.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t300-a24rho05beta2_COMPETants_mmas_r15t300.png
euclidAB300.tsp-BCc3-vs-COMPETants-acs.tar.gz euclidAB300.tsp-BCc3-vs-COMPETants-mmas.tar.gz
Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t100-a24rho05beta2_mACO2_acs_r15t100.png kroAB100.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t100-a24rho05beta2_mACO2_mmas_r15t100.png
kroAB100.tsp-BCc3-vs-mACO2-acs.tar.gz kroAB100.tsp-BCc3-vs-mACO2-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t200-a24rho05beta2_mACO2_acs_r15t200.png kroAB200.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t200-a24rho05beta2_mACO2_mmas_r15t200.png
kroAB200.tsp-BCc3-vs-mACO2-acs.tar.gz kroAB200.tsp-BCc3-vs-mACO2-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t300-a24rho05beta2_mACO2_acs_r15t300.png euclidAB300.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t300-a24rho05beta2_mACO2_mmas_r15t300.png
euclidAB300.tsp-BCc3-vs-mACO2-acs.tar.gz euclidAB300.tsp-BCc3-vs-mACO2-mmas.tar.gz
Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t100-a24rho05beta2_mACO4_acs_r15t100.png kroAB100.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t100-a24rho05beta2_mACO4_mmas_r15t100.png
kroAB100.tsp-BCc3-vs-mACO4-acs.tar.gz kroAB100.tsp-BCc3-vs-mACO4-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t200-a24rho05beta2_mACO4_acs_r15t200.png kroAB200.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t200-a24rho05beta2_mACO4_mmas_r15t200.png
kroAB200.tsp-BCc3-vs-mACO4-acs.tar.gz kroAB200.tsp-BCc3-vs-mACO4-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t300-a24rho05beta2_mACO4_acs_r15t300.png euclidAB300.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t300-a24rho05beta2_mACO4_mmas_r15t300.png
euclidAB300.tsp-BCc3-vs-mACO4-acs.tar.gz euclidAB300.tsp-BCc3-vs-mACO4-mmas.tar.gz
Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t100-a24rho05beta2_MACS_acs_r15t100.png kroAB100.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t100-a24rho05beta2_MACS_mmas_r15t100.png
kroAB100.tsp-BCc3-vs-MACS-acs.tar.gz kroAB100.tsp-BCc3-vs-MACS-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t200-a24rho05beta2_MACS_acs_r15t200.png kroAB200.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t200-a24rho05beta2_MACS_mmas_r15t200.png
kroAB200.tsp-BCc3-vs-MACS-acs.tar.gz kroAB200.tsp-BCc3-vs-MACS-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t300-a24rho05beta2_MACS_acs_r15t300.png euclidAB300.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t300-a24rho05beta2_MACS_mmas_r15t300.png
euclidAB300.tsp-BCc3-vs-MACS-acs.tar.gz euclidAB300.tsp-BCc3-vs-MACS-mmas.tar.gz
Instances ACS MMAS
kroAB100.tsp kroAB100.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t100-a24rho05beta2_PACO_acs_singleheu_r15t100.png kroAB100.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t100-a24rho05beta2_PACO_mmas_singleheu_r15t100.png
kroAB100.tsp-BCc3-vs-PACO-acs.tar.gz kroAB100.tsp-BCc3-vs-PACO-mmas.tar.gz
kroAB200.tsp kroAB200.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t200-a24rho05beta2_PACO_acs_singleheu_r15t200.png kroAB200.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t200-a24rho05beta2_PACO_mmas_singleheu_r15t200.png
kroAB200.tsp-BCc3-vs-PACO-acs.tar.gz kroAB200.tsp-BCc3-vs-PACO-mmas.tar.gz
euclidAB300.tsp euclidAB300.tsp/a8c3rho05_BicriterionAnt_acs_dtau_r15t300-a24rho05beta2_PACO_acs_singleheu_r15t300.png euclidAB300.tsp/a8c3rho05_BicriterionAnt_mmas_dtau_r15t300-a24rho05beta2_PACO_mmas_singleheu_r15t300.png
euclidAB300.tsp-BCc3-vs-PACO-acs.tar.gz euclidAB300.tsp-BCc3-vs-PACO-mmas.tar.gz

Valid HTML 4.01 Transitional Valid CSS!