TY  - CONF
T1  - Understanding TSP Difficulty by Learning from Evolved Instances
T2  - Lecture Notes in Computer Science
Y1  - 2010
A1  - Smith-Miles, Kate
A1  - van Hemert, Jano
A1  - Lim, Xin
ED  - Blum, Christian
ED  - Battiti, Roberto
AB  - Whether the goal is performance prediction, or insights into the relationships between algorithm performance and instance characteristics, a comprehensive set of meta-data from which relationships can be learned is needed. This paper provides a methodology to determine if the meta-data is sufficient, and demonstrates the critical role played by instance generation methods. Instances of the Travelling Salesman Problem (TSP) are evolved using an evolutionary algorithm to produce distinct classes of instances that are intentionally easy or hard for certain algorithms. A comprehensive set of features is used to characterise instances of the TSP, and the impact of these features on difficulty for each algorithm is analysed. Finally, performance predictions are achieved with high accuracy on unseen instances for predicting search effort as well as identifying the algorithm likely to perform best.
JF  - Lecture Notes in Computer Science
PB  - Springer Berlin / Heidelberg
VL  - 6073
UR  - http://dx.doi.org/10.1007/978-3-642-13800-3_29
N1  - 10.1007/978-3-642-13800-3_29
ER  -