Understanding TSP difficulty by learning from evolved instances

Kate Amanda Smith-Miles, Jano van Hemert, Xin Yu Lim

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

83 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationLearning and Intelligent Optimization
EditorsC Blum, R Battiti
Place of PublicationGermany
PublisherSpringer-Verlag London Ltd.
Pages266 - 280
Number of pages15
ISBN (Print)9783642137990
Publication statusPublished - 2010
EventInternational Conference on Learning and Intelligent OptimizatioN (LION) 2010 - Venice Italy, Venice, Italy
Duration: 8 Jan 201022 Jan 2010
Conference number: 4th


ConferenceInternational Conference on Learning and Intelligent OptimizatioN (LION) 2010
Abbreviated titleLION 4
Internet address

Cite this