An Analysis of Problem Difficulty for a Class of Optimisation Heuristics

Enda Ridge; Daniel Kudenko

doi:10.1007/978-3-540-71615-0_18

An Analysis of Problem Difficulty for a Class of Optimisation Heuristics

Enda Ridge, Daniel Kudenko

Computer Science

Research output: Contribution to conference › Paper › peer-review

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	Undefined/Unknown
Pages	198-209
DOIs	https://doi.org/10.1007/978-3-540-71615-0_18
Publication status	Published - 2007

Access to Document

10.1007/978-3-540-71615-0_18

http://dx.doi.org/10.1007/978-3-540-71615-0_18

Cite this

@conference{5fd4df8abb6f4ed4b0686a82d5dca5a5,

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",

doi = "10.1007/978-3-540-71615-0_18",

language = "Undefined/Unknown",

pages = "198--209",

}

TY - CONF

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.

U2 - 10.1007/978-3-540-71615-0_18

DO - 10.1007/978-3-540-71615-0_18

M3 - Paper

SP - 198

EP - 209

ER -