Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Tinos, Renato [1] ; Whitley, Darrell [2] ; Ochoa, Gabriela [3]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Dept Comp & Math, Ribeirao Preto, SP - Brazil
[2] Colorado State Univ, Dept Comp Sci, Ft Collins, CO 80523 - USA
[3] Univ Stirling, Dept Comp Sci & Math, Stirling FK9 4LA - Scotland
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: EVOLUTIONARY COMPUTATION; v. 28, n. 2, p. 255-288, JUN 2020.
Citações Web of Science: 0
Resumo

Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of 2k 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. (AU)

Processo FAPESP: 16/18615-0 - Aprendizado de máquina avançado
Beneficiário:André Carlos Ponce de Leon Ferreira de Carvalho
Linha de fomento: Auxílio à Pesquisa - Parceria para Inovação Tecnológica - PITE
Processo FAPESP: 15/06462-1 - Recombinação por decomposição em computação evolutiva
Beneficiário:Renato Tinós
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
Beneficiário:José Alberto Cuminato
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs