A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling Between Local Optima

Citation

Tinós R, Whitley D & Ochoa G (2020) A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling Between Local Optima. Evolutionary Computation, 28 (2), pp. 255-288. https://doi.org/10.1162/evco_a_00254

Abstract
Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of 2 k reachable offspring, where k is the number of recombining components. This paper introduces a new GPX2 operator, which finds more recombining components than GPX or Iterative Partial Transcription (IPT). We also show that GPX2 has O(n) runtime complexity, while also introducing new enhancements to reduce the execution time of GPX2. Finally, we experimentally demonstrate the efficiency of GPX2 when it is used to improve solutions found by multi-trial Lin-Kernighan-Helsgaum (LKH) algorithm. Significant improvements in performance are documented on large (n > 5000) and very large (n = 100, 000) instances of the Traveling Salesman Problem.

Keywords
Traveling salesman problem; recombination operator; evolutionary combinatorial op- timization

Journal
Evolutionary Computation: Volume 28, Issue 2

• Gen Partition-crossover-ecj2019