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

• tunnelling-crossover-networks (4).pdf