An analysis of problem difficulty for a class of optimisation heuristics

Enda Ridge; Daniel Kudenko

An analysis of problem difficulty for a class of optimisation heuristics

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper investigates the effect of the cost matrix standard deviation of Travelling Salesman Problem (TSP) instances on the performance of a class of combinatorial optimisation heuristics. Ant Colony Optimisation (ACO) is the class of heuristic investigated. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these algorithms on the TSP.

Original language	English
Title of host publication	Evolutionary Computation in Combinatorial Optimization, Proceedings
Editors	C Cotta, J VanHemert
Place of Publication	BERLIN
Publisher	Springer
Pages	198-209
Number of pages	12
ISBN (Print)	978-3-540-71614-3
Publication status	Published - 2007
Event	7th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2007) - Valencia Duration: 11 Apr 2007 → 13 Apr 2007

Conference

Conference	7th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2007)
City	Valencia
Period	11/04/07 → 13/04/07

Cite this

@inproceedings{f10d49e68c1d427b91fc0b2c07e5cbe7,

title = "An analysis of problem difficulty for a class of optimisation heuristics",

abstract = "This paper investigates the effect of the cost matrix standard deviation of Travelling Salesman Problem (TSP) instances on the performance of a class of combinatorial optimisation heuristics. Ant Colony Optimisation (ACO) is the class of heuristic investigated. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these algorithms on the TSP.",

author = "Enda Ridge and Daniel Kudenko",

year = "2007",

language = "English",

isbn = "978-3-540-71614-3",

pages = "198--209",

editor = "C Cotta and J VanHemert",

booktitle = "Evolutionary Computation in Combinatorial Optimization, Proceedings",

publisher = "Springer",

address = "Germany",

note = "7th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2007) ; Conference date: 11-04-2007 Through 13-04-2007",

}

TY - GEN

T1 - An analysis of problem difficulty for a class of optimisation heuristics

AU - Ridge, Enda

AU - Kudenko, Daniel

PY - 2007

Y1 - 2007

N2 - This paper investigates the effect of the cost matrix standard deviation of Travelling Salesman Problem (TSP) instances on the performance of a class of combinatorial optimisation heuristics. Ant Colony Optimisation (ACO) is the class of heuristic investigated. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these algorithms on the TSP.

AB - This paper investigates the effect of the cost matrix standard deviation of Travelling Salesman Problem (TSP) instances on the performance of a class of combinatorial optimisation heuristics. Ant Colony Optimisation (ACO) is the class of heuristic investigated. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these algorithms on the TSP.

M3 - Conference contribution

SN - 978-3-540-71614-3

SP - 198

EP - 209

BT - Evolutionary Computation in Combinatorial Optimization, Proceedings

A2 - Cotta, C

A2 - VanHemert, J

PB - Springer

CY - BERLIN

T2 - 7th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2007)

Y2 - 11 April 2007 through 13 April 2007

ER -