Determining Whether a Problem Characteristic Affects Heuristic Performance

Enda Ridge; Daniel Kudenko; Carlos Cotta; Jano I. van Hemert

doi:10.1007/978-3-540-70807-0_2

Determining Whether a Problem Characteristic Affects Heuristic Performance

Enda Ridge, Daniel Kudenko, Carlos Cotta (Editor), Jano I. van Hemert (Editor)

Computer Science

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

Abstract

This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. 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 heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics.

Original language	English
Title of host publication	Recent Advances in Evolutionary Computation for Combinatorial Optimization
Publisher	Springer
Pages	21-35
Number of pages	15
Volume	153
DOIs	https://doi.org/10.1007/978-3-540-70807-0_2
Publication status	Published - 2008

Publication series

Name	Studies in Computational Intelligence
Publisher	Springer

Access to Document

10.1007/978-3-540-70807-0_2

http://dx.doi.org/10.1007/978-3-540-70807-0_2

Cite this

@inproceedings{c2d3fa288f5f4a4e837406ea3b2cd736,

title = "Determining Whether a Problem Characteristic Affects Heuristic Performance",

abstract = "This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. 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 heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics.",

author = "Enda Ridge and Daniel Kudenko and Carlos Cotta and Hemert, {Jano I. van}",

year = "2008",

doi = "10.1007/978-3-540-70807-0_2",

language = "English",

volume = "153",

series = "Studies in Computational Intelligence",

publisher = "Springer",

pages = "21--35",

booktitle = "Recent Advances in Evolutionary Computation for Combinatorial Optimization",

address = "Germany",

}

Determining Whether a Problem Characteristic Affects Heuristic Performance. / Ridge, Enda; Kudenko, Daniel; Cotta, Carlos (Editor) et al.

Recent Advances in Evolutionary Computation for Combinatorial Optimization. Vol. 153 Springer, 2008. p. 21-35 (Studies in Computational Intelligence).

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

TY - GEN

T1 - Determining Whether a Problem Characteristic Affects Heuristic Performance

AU - Ridge, Enda

AU - Kudenko, Daniel

A2 - Cotta, Carlos

A2 - Hemert, Jano I. van

PY - 2008

Y1 - 2008

N2 - This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. 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 heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics.

AB - This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. 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 heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics.

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

U2 - 10.1007/978-3-540-70807-0_2

DO - 10.1007/978-3-540-70807-0_2

M3 - Conference contribution

VL - 153

T3 - Studies in Computational Intelligence

SP - 21

EP - 35

BT - Recent Advances in Evolutionary Computation for Combinatorial Optimization

PB - Springer

ER -

Determining Whether a Problem Characteristic Affects Heuristic Performance

Abstract

Publication series

Access to Document

Other files and links

Cite this