How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes

Citation

McMenemy P, Veerapen N & Ochoa G (2018) How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes. In: Liefooghe A & López-Ibáñez M (eds.) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2018. Lecture Notes in Computer Science, 10782. EvoCOP 2018 - The 18th European Conference on Evolutionary Computation in Combinatorial Optimisation, Parma, Italy, 04.04.2018-06.04.2018. Cham, Switzerland: Springer, pp. 34-49. https://doi.org/10.1007/978-3-319-77449-7_3

Abstract
Local optima networks are a valuable tool used to analyse and visualise the global structure of combinatorial search spaces; in particular, the existence and distribution of multiple funnels in the landscape. We extract and analyse the networks induced by Chained-LK, a powerful iterated local search for the TSP, on a large set of randomly generated (Uniform and Clustered) instances. Results indicate that increasing the perturbation strength employed by Chained-LK modifies the landscape's global structure, with the effect being markedly different for the two classes of instances. Our quantitative analysis shows that several funnel metrics have stronger correlations with Chained-LK success rate than the number of local optima, indicating that global structure clearly impacts search performance.

Keywords
Fitness landscape; Local Search; Local Optima Networks; Travelling Salesman Problem

People

Dr Paul McMenemy

Lect in Pure Math/Mathematical Mod, Mathematics

Professor Gabriela Ochoa

Professor, Computing Science