Conference Proceeding

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

StatusPublished
FundersThe Leverhulme Trust and Engineering and Physical Sciences Research Council
Title of seriesLecture Notes in Computer Science
Number in series10782
Publication date31/12/2018
Publication date online03/03/2018
URLhttp://hdl.handle.net/1893/26546
Related URLshttp://hdl.handle.net/…8/cfp_evocop.php
PublisherSpringer
Place of publicationCham, Switzerland
eISSN1611-3349
ISSN of series0302-9743
ISBN9783319774480; 9783319774497
eISBN978-3-319-77449-7
ConferenceEvoCOP 2018 - The 18th European Conference on Evolutionary Computation in Combinatorial Optimisation
Conference locationParma, Italy
Dates

Research centres/groups