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

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.