Conference Proceeding

Tunnelling Crossover Networks for the Asymmetric TSP



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.

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.

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

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
Related URLs;
Place of publicationCham, Switzerland
ISSN of series0302-9743
ConferencePPSN2016 - 14th International Conference on Parallel Problem Solving from Nature
Conference locationEdinburgh

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups