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

• DOI: 10.1162/evco_a_00254
• Publication Date: 2019-03-22T14:37:34Z
• Authors: Renato Tinós; Darrell Whitley; Gabriela Ochoa
• Keywords: Operator (biology)

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