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

Autor: Tinós R; Department of Computing and Mathematics, University of São Paulo, Ribeirão Preto, SP, Brazil rtinos@ffclrp.usp.br., Whitley D; Department of Computer Science, Colorado State University, Fort Collins, CO, USA whitley@cs.colostate.edu., Ochoa G; Department of Computing Science and Mathematics, University of Stirling, Stirling, FK9 4LA, Scotland gabriela.ochoa@cs.stir.ac.uk.
Jazyk: angličtina
Zdroj: Evolutionary computation [Evol Comput] 2020 Summer; Vol. 28 (2), pp. 255-288. Date of Electronic Publication: 2019 Mar 22.
DOI: 10.1162/evco_a_00254
Abstrakt: 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 article 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 the multitrial 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.
Databáze: MEDLINE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje