Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic

Renato Tinós, Keld Helsgaun, Darrell Whitley

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Resumé

The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.
OriginalsprogEngelsk
TitelParallel Problem Solving from Nature – PPSN XV : 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
RedaktørerA. Auger, C.M. Fonseca, N. Lourenco, P. Machado, L. Paquete, D. Whitley
Antal sider13
Vol/bind1
ForlagSpringer
Publikationsdato2018
Sider95-107
ISBN (Trykt)978-3-319-99252-5
ISBN (Elektronisk)978-3-319-99253-2
DOI
StatusUdgivet - 2018
Begivenhed15th International Conference on Parallel Problem Solving from Nature - University of Coimbra, Coimbra, Portugal
Varighed: 8 sep. 201812 sep. 2018
Konferencens nummer: 15
http://ppsn2018.dei.uc.pt

Konference

Konference15th International Conference on Parallel Problem Solving from Nature
Nummer15
LokationUniversity of Coimbra
LandPortugal
ByCoimbra
Periode08/09/201812/09/2018
AndetThe Fifteenth International Conference on Parallel Problem Solving from Nature (PPSN XV) will be held in Coimbra, Portugal on 8-12 September 2018. The conference will take place at the Campus of the University of Coimbra, recognised by UNESCO as world heritage site, due to its relevance in the dissemination of knowledge throughout the fields of arts, sciences, law, architecture, urban planning and landscape. The venue includes a set of buildings and rooms of historical relevance, thus giving the participants the opportunity to visit the different areas of the university and experience the feeling of studying and working in Coimbra.<br/><br/>This biennial meeting brings together researchers and practitioners in the field of Natural Computing. Natural Computing is the study of computational systems which use ideas and get inspiration from natural systems, including biological, ecological, physical, chemical, and social systems. It is a fast-growing interdisciplinary field in which a range of techniques and methods are studied for dealing with large, complex, and dynamic problems with various sources of potential uncertainties.<br/><br/>PPSN XV will showcase a wide range of topics in Natural Computing including, but not restricted to, Evolutionary Computation, Artificial Neural Networks, Artificial Life, Swarm Intelligence, Artificial Immune Systems, Self-Organising Systems, Emergent Behaviour, Molecular Computing, Evolutionary Robotics, Evolvable Hardware, Parallel Implementations and Applications to Real-World Problems. PPSN XV will also feature workshops and tutorials covering advanced and fundamental topics in the field of Natural Computing.<br/><br/>Following the PPSN tradition, all accepted papers will be presented during poster sessions and will be included in the proceedings, to be published in the Series Lecture Notes in Computer Science (LNCS) by Springer. Prospective authors are invited to contribute their high-quality original results in the field of Natural Computing.
Internetadresse
NavnTheoretical Computer Science and General Issues
Vol/bind11101
NavnLecture Notes in Computer Science
Vol/bind11101
ISSN0302-9743

Emneord

  • Traveling Salesman Problem
  • Recombination operator
  • Heuristic search
  • Evolutionary combinatorial optimization

Citer dette

Tinós, R., Helsgaun, K., & Whitley, D. (2018). Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. I A. Auger, C. M. Fonseca, N. Lourenco, P. Machado, L. Paquete, & D. Whitley (red.), Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I (Bind 1, s. 95-107). Springer. Theoretical Computer Science and General Issues, Bind. 11101, Lecture Notes in Computer Science, Bind. 11101 https://doi.org/10.1007/978-3-319-99253-2_8
Tinós, Renato ; Helsgaun, Keld ; Whitley, Darrell. / Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. red. / A. Auger ; C.M. Fonseca ; N. Lourenco ; P. Machado ; L. Paquete ; D. Whitley. Bind 1 Springer, 2018. s. 95-107 (Theoretical Computer Science and General Issues, Bind 11101). (Lecture Notes in Computer Science, Bind 11101).
@inproceedings{28b39dae1cf246f58052bab46f0bed0d,
title = "Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic",
abstract = "The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.",
keywords = "Traveling Salesman Problem, Recombination operator, Heuristic search, Evolutionary combinatorial optimization, Traveling Salesman Problem, Recombination operator, Heuristic search, Evolutionary combinatorial optimization",
author = "Renato Tin{\'o}s and Keld Helsgaun and Darrell Whitley",
year = "2018",
doi = "10.1007/978-3-319-99253-2_8",
language = "English",
isbn = "978-3-319-99252-5",
volume = "1",
pages = "95--107",
editor = "A. Auger and C.M. Fonseca and N. Lourenco and P. Machado and L. Paquete and D. Whitley",
booktitle = "Parallel Problem Solving from Nature – PPSN XV",
publisher = "Springer",

}

Tinós, R, Helsgaun, K & Whitley, D 2018, Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. i A Auger, CM Fonseca, N Lourenco, P Machado, L Paquete & D Whitley (red), Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. bind 1, Springer, Theoretical Computer Science and General Issues, bind 11101, Lecture Notes in Computer Science, bind 11101, s. 95-107, 15th International Conference on Parallel Problem Solving from Nature, Coimbra, Portugal, 08/09/2018. https://doi.org/10.1007/978-3-319-99253-2_8

Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. / Tinós, Renato; Helsgaun, Keld; Whitley, Darrell.

Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. red. / A. Auger; C.M. Fonseca; N. Lourenco; P. Machado; L. Paquete; D. Whitley. Bind 1 Springer, 2018. s. 95-107.

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

TY - GEN

T1 - Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic

AU - Tinós, Renato

AU - Helsgaun, Keld

AU - Whitley, Darrell

PY - 2018

Y1 - 2018

N2 - The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.

AB - The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the most successful search algorithms for the Traveling Salesman Problem (TSP). The core of LKH is a variable depth local search heuristic developed by Lin and Kernighan (LK). Several improvements have been incorporated to LKH along the years. The best results reported in the literature were obtained by an iterative local search version known as multi-trial LKH. In multi-trial LKH, solutions generated by soft restarts of the LK heuristic are recombined using Iterative Partial Transcription (IPT). We show that IPT can be classified as a partition crossover. Partition crossovers use the features common to the parents to decompose the evaluation function. Recently, a new generalized partition crossover, known as GPX2, was proposed for the TSP. We investigate the use of GPX2 in multi-trial LKH and compare it to multi-trial LKH using IPT. Results of experiments with 11 large instances of the TSP indicate that LKH with GPX2 outperforms LKH with IPT in most of the instances, but not in all of them.

KW - Traveling Salesman Problem

KW - Recombination operator

KW - Heuristic search

KW - Evolutionary combinatorial optimization

KW - Traveling Salesman Problem

KW - Recombination operator

KW - Heuristic search

KW - Evolutionary combinatorial optimization

UR - https://www.springer.com/us/book/9783319992525

U2 - 10.1007/978-3-319-99253-2_8

DO - 10.1007/978-3-319-99253-2_8

M3 - Article in proceedings

SN - 978-3-319-99252-5

VL - 1

SP - 95

EP - 107

BT - Parallel Problem Solving from Nature – PPSN XV

A2 - Auger, A.

A2 - Fonseca, C.M.

A2 - Lourenco, N.

A2 - Machado, P.

A2 - Paquete, L.

A2 - Whitley, D.

PB - Springer

ER -

Tinós R, Helsgaun K, Whitley D. Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. I Auger A, Fonseca CM, Lourenco N, Machado P, Paquete L, Whitley D, red., Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. Bind 1. Springer. 2018. s. 95-107. (Theoretical Computer Science and General Issues, Bind 11101). (Lecture Notes in Computer Science, Bind 11101). https://doi.org/10.1007/978-3-319-99253-2_8