You are here

Understanding TSP Difficulty by Learning from Evolved Instances

TitleUnderstanding TSP Difficulty by Learning from Evolved Instances
Publication TypeConference Paper
Year of Publication2010
AuthorsSmith-Miles, K, van Hemert, J, Lim, X
Conference NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
EditorBlum, C, Battiti, R

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.

Full Text