TY - GEN
T1 - Optimisation and generalisation
T2 - 11th International Conference on Parallel Problem Solving from Nature
AU - Corne, David W.
AU - Reynolds, Alan P.
PY - 2010
Y1 - 2010
N2 - The chief purpose of research in optimisation is to understand how to design (or choose) the most suitable algorithm for a given distribution of problem instances. Ideally, when an algorithm is developed for specific problems, the boundaries of its performance should be clear, and we expect estimates of reasonably good performance within and (at least modestly) outside its 'seen' instance distribution. However, we show that these ideals are highly over-optimistic, and suggest that standard algorithm-choice scenarios will rarely lead to the best algorithm for individual instances in the space of interest. We do this by examining algorithm 'footprints', indicating how performance generalises in instance space. We find much evidence that typical ways of choosing the 'best' algorithm, via tests over a distribution of instances, are seriously flawed. Also, understanding how footprints in instance spaces vary between algorithms and across instance space dimensions, may lead to a future platform for wiser algorithm-choice decisions. © 2010 Springer-Verlag.
AB - The chief purpose of research in optimisation is to understand how to design (or choose) the most suitable algorithm for a given distribution of problem instances. Ideally, when an algorithm is developed for specific problems, the boundaries of its performance should be clear, and we expect estimates of reasonably good performance within and (at least modestly) outside its 'seen' instance distribution. However, we show that these ideals are highly over-optimistic, and suggest that standard algorithm-choice scenarios will rarely lead to the best algorithm for individual instances in the space of interest. We do this by examining algorithm 'footprints', indicating how performance generalises in instance space. We find much evidence that typical ways of choosing the 'best' algorithm, via tests over a distribution of instances, are seriously flawed. Also, understanding how footprints in instance spaces vary between algorithms and across instance space dimensions, may lead to a future platform for wiser algorithm-choice decisions. © 2010 Springer-Verlag.
U2 - 10.1007/978-3-642-15844-5_3
DO - 10.1007/978-3-642-15844-5_3
M3 - Conference contribution
SN - 3642158439
SN - 9783642158438
VL - 6238 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 22
EP - 31
BT - Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings
Y2 - 11 September 2010 through 15 September 2010
ER -