Solution bias in ant colony optimisation: Lessons for selecting pheromone models

James Montgomery, Marcus Randall, Tim Hendtlass

Research output: Contribution to journalArticleResearchpeer-review

17 Citations (Scopus)

Abstract

Ant colony optimisation is a constructive metaheuristic in which solutions are built probabilistically influenced by the parameters of a pheromone model-an analogue of the trail pheromones used by real ants when foraging for food. Recent studies have uncovered the presence of biases in the solution construction process, the existence and nature of which depend on the characteristics of the problem being solved. The presence of these solution construction biases induces biases in the pheromone model used, so selecting an appropriate model is highly important. The first part of this paper presents new findings bridging biases due to construction with biases in pheromone models. Novel approaches to the prediction of this bias are developed and used with the knapsack and generalised assignment problems. The second part of the paper deals with the selection of appropriate pheromone models when detailed knowledge of their biases is not available. Pheromone models may be derived either from characteristics of the way solutions are represented by the algorithm or characteristics of the solutions represented, which are often quite different. Recently it has been suggested that the latter is more appropriate. The relative performance of a number of alternative pheromone models for six well-known combinatorial optimisation problems is examined to test this hypothesis. Results suggest that, in general, modelling characteristics of solutions (rather than their representations) does lead to the best performance in ACO algorithms. Consequently, this principle may be used to guide the selection of appropriate pheromone models in problems to which ACO has not yet been applied.

Original languageEnglish
Pages (from-to)2728-2749
Number of pages22
JournalComputers and Operations Research
Volume35
Issue number9
DOIs
Publication statusPublished - Sep 2008

Fingerprint

Ant colony optimization
Pheromone
pheromone
ant
trend
Model
Generalized Assignment Problem
analog model
Knapsack
Foraging
Combinatorial optimization
Combinatorial Optimization Problem
Metaheuristics
performance
food
Analogue
Prediction
Alternatives
prediction
Modeling

Cite this

@article{492a4ffd74604696bfc9b4ee12193140,
title = "Solution bias in ant colony optimisation: Lessons for selecting pheromone models",
abstract = "Ant colony optimisation is a constructive metaheuristic in which solutions are built probabilistically influenced by the parameters of a pheromone model-an analogue of the trail pheromones used by real ants when foraging for food. Recent studies have uncovered the presence of biases in the solution construction process, the existence and nature of which depend on the characteristics of the problem being solved. The presence of these solution construction biases induces biases in the pheromone model used, so selecting an appropriate model is highly important. The first part of this paper presents new findings bridging biases due to construction with biases in pheromone models. Novel approaches to the prediction of this bias are developed and used with the knapsack and generalised assignment problems. The second part of the paper deals with the selection of appropriate pheromone models when detailed knowledge of their biases is not available. Pheromone models may be derived either from characteristics of the way solutions are represented by the algorithm or characteristics of the solutions represented, which are often quite different. Recently it has been suggested that the latter is more appropriate. The relative performance of a number of alternative pheromone models for six well-known combinatorial optimisation problems is examined to test this hypothesis. Results suggest that, in general, modelling characteristics of solutions (rather than their representations) does lead to the best performance in ACO algorithms. Consequently, this principle may be used to guide the selection of appropriate pheromone models in problems to which ACO has not yet been applied.",
author = "James Montgomery and Marcus Randall and Tim Hendtlass",
year = "2008",
month = "9",
doi = "10.1016/j.cor.2006.12.014",
language = "English",
volume = "35",
pages = "2728--2749",
journal = "Location Science",
issn = "0305-0548",
publisher = "Elsevier",
number = "9",

}

Solution bias in ant colony optimisation : Lessons for selecting pheromone models. / Montgomery, James; Randall, Marcus; Hendtlass, Tim.

In: Computers and Operations Research, Vol. 35, No. 9, 09.2008, p. 2728-2749.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Solution bias in ant colony optimisation

T2 - Lessons for selecting pheromone models

AU - Montgomery, James

AU - Randall, Marcus

AU - Hendtlass, Tim

PY - 2008/9

Y1 - 2008/9

N2 - Ant colony optimisation is a constructive metaheuristic in which solutions are built probabilistically influenced by the parameters of a pheromone model-an analogue of the trail pheromones used by real ants when foraging for food. Recent studies have uncovered the presence of biases in the solution construction process, the existence and nature of which depend on the characteristics of the problem being solved. The presence of these solution construction biases induces biases in the pheromone model used, so selecting an appropriate model is highly important. The first part of this paper presents new findings bridging biases due to construction with biases in pheromone models. Novel approaches to the prediction of this bias are developed and used with the knapsack and generalised assignment problems. The second part of the paper deals with the selection of appropriate pheromone models when detailed knowledge of their biases is not available. Pheromone models may be derived either from characteristics of the way solutions are represented by the algorithm or characteristics of the solutions represented, which are often quite different. Recently it has been suggested that the latter is more appropriate. The relative performance of a number of alternative pheromone models for six well-known combinatorial optimisation problems is examined to test this hypothesis. Results suggest that, in general, modelling characteristics of solutions (rather than their representations) does lead to the best performance in ACO algorithms. Consequently, this principle may be used to guide the selection of appropriate pheromone models in problems to which ACO has not yet been applied.

AB - Ant colony optimisation is a constructive metaheuristic in which solutions are built probabilistically influenced by the parameters of a pheromone model-an analogue of the trail pheromones used by real ants when foraging for food. Recent studies have uncovered the presence of biases in the solution construction process, the existence and nature of which depend on the characteristics of the problem being solved. The presence of these solution construction biases induces biases in the pheromone model used, so selecting an appropriate model is highly important. The first part of this paper presents new findings bridging biases due to construction with biases in pheromone models. Novel approaches to the prediction of this bias are developed and used with the knapsack and generalised assignment problems. The second part of the paper deals with the selection of appropriate pheromone models when detailed knowledge of their biases is not available. Pheromone models may be derived either from characteristics of the way solutions are represented by the algorithm or characteristics of the solutions represented, which are often quite different. Recently it has been suggested that the latter is more appropriate. The relative performance of a number of alternative pheromone models for six well-known combinatorial optimisation problems is examined to test this hypothesis. Results suggest that, in general, modelling characteristics of solutions (rather than their representations) does lead to the best performance in ACO algorithms. Consequently, this principle may be used to guide the selection of appropriate pheromone models in problems to which ACO has not yet been applied.

UR - http://www.scopus.com/inward/record.url?scp=38749091758&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2006.12.014

DO - 10.1016/j.cor.2006.12.014

M3 - Article

VL - 35

SP - 2728

EP - 2749

JO - Location Science

JF - Location Science

SN - 0305-0548

IS - 9

ER -