Conference Proceeding

Tunnelling Crossover Networks for the Asymmetric TSP

Citation

Veerapen N, Ochoa G, Tinós R & Whitley D (2016) Tunnelling Crossover Networks for the Asymmetric TSP. In: Handl J, Hart E, Lewis P, Lopez-Ibanez M, Ochoa G & Paechter B (eds.) Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings. Lecture Notes in Computer Science, 9921. PPSN2016 - 14th International Conference on Parallel Problem Solving from Nature, Edinburgh, 17.09.2016-21.09.2016. Cham, Switzerland: Springer, pp. 994-1003. https://doi.org/10.1007/978-3-319-45823-6_93

Abstract
Local optima networks are a compact representation of fitness landscapes that can be used for analysis and visualisation. This paper provides the first analysis of the Asymmetric Travelling Salesman Problem using local optima networks. These are generated by sampling the search space by recording the progress of an existing evolutionary algorithm based on the Generalised Asymmetric Partition Crossover. They are compared to networks sampled through the Chained Lin-Kernighan heuristic across 25 instances. Structural differences and similarities are identified, as well as examples where crossover smooths the landscape.

Keywords
Fitness Landscape; Local Optima Network; Asymmetric Travelling Salesman Problem; Evolutionary Algorithm; Partition Crossover; Local Search

StatusPublished
FundersThe Leverhulme Trust and Engineering and Physical Sciences Research Council
Title of seriesLecture Notes in Computer Science
Number in series9921
Publication date31/08/2016
Publication date online30/09/2016
URLhttp://hdl.handle.net/1893/24061
Related URLshttp://hdl.handle.net/11667/75;
PublisherSpringer
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN978-3-319-45822-9
eISBN978-3-319-45823-6
ConferencePPSN2016 - 14th International Conference on Parallel Problem Solving from Nature
Conference locationEdinburgh
Dates

Research centres/groups