Research output

Article in Journal

Mapping the Global Structure of TSP Fitness Landscapes (Forthcoming/Available Online)

Citation
Ochoa G & Veerapen N (2017) Mapping the Global Structure of TSP Fitness Landscapes (Forthcoming/Available Online), Journal of Heuristics.

Abstract
The global structure of combinatorial landscapes is not fully understood, yet it is known to impact the performance of heuristic search methods. We use a so-called local optima network model to characterise and visualise the global structure of travelling salesperson fitness landscapes of different classes, including random and structured real-world instances of realistic size. Our study brings rigour to the characterisation of so-called funnels, and proposes an intensive and effective sampling procedure for extracting the networks. We propose enhanced visualisation techniques, including 3D plots and the incorporation of colour, sizes and widths, to reflect relevant aspects of the search process. This brings an almost tangible new perspective to the landscape and funnel metaphors. Our results reveal a much richer global structure than the suggestion of a 'big-valley' structure. Most landscapes of the tested instances have multiple valleys or funnels; and the number, disposition and interaction of these funnels seem to relate to search difficulty on the studied landscapes. We also find that the structured TSP instances feature high levels of neutrality, an observation not previously reported in the literature. We then propose ways of analysing and visualising these neutral landscapes.

Keywords
Fitness landscapes; Local optima network; Funnels; Global structure; Neutrality; Travelling salesman problem; Lin-Kernighan heuristic; Iterated local search; Visualisation

Related dataset
http://hdl.handle.net/11667/91

StatusIn press
AuthorsOchoa Gabriela, Veerapen Nadarajen
Publication date online29/05/2017
Date accepted by journal03/05/2017
URLhttp://rdcu.be/s50z
PublisherSpringer
ISSN 1381-1231
LanguageEnglish

Journal
Journal of Heuristics

© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
My Portal