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

Renato Tinós; Keld Helsgaun; Darrell Whitley

doi:10.1007/978-3-319-99253-2_8

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

Renato Tinós, Keld Helsgaun, Darrell Whitley

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

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.

Originalsprog	Engelsk
Titel	Parallel Problem Solving from Nature – PPSN XV : 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
Redaktører	A. Auger, C.M. Fonseca, N. Lourenco, P. Machado, L. Paquete, D. Whitley
Antal sider	13
Vol/bind	1
Forlag	Springer
Publikationsdato	2018
Sider	95-107
ISBN (Trykt)	978-3-319-99252-5
ISBN (Elektronisk)	978-3-319-99253-2
DOI	https://doi.org/10.1007/978-3-319-99253-2_8
Status	Udgivet - 2018
Begivenhed	15th International Conference on Parallel Problem Solving from Nature - University of Coimbra, Coimbra, Portugal Varighed: 8 sep. 2018 → 12 sep. 2018 Konferencens nummer: 15 http://ppsn2018.dei.uc.pt

Konference

Konference	15th International Conference on Parallel Problem Solving from Nature
Nummer	15
Lokation	University of Coimbra
Land/Område	Portugal
By	Coimbra
Periode	08/09/2018 → 12/09/2018
Andet	The 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	http://ppsn2018.dei.uc.pt

Navn	Theoretical Computer Science and General Issues
Vol/bind	11101

Navn	Lecture Notes in Computer Science
Vol/bind	11101
ISSN	0302-9743

Emneord

Traveling Salesman Problem
Recombination operator
Heuristic search
Evolutionary combinatorial optimization

Link til dokument

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

Andre filer og links

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

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",

series = "Theoretical Computer Science and General Issues",

publisher = "Springer",

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",

note = "15th International Conference on Parallel Problem Solving from Nature, PPSN ; Conference date: 08-09-2018 Through 12-09-2018",

url = "http://ppsn2018.dei.uc.pt",

}

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 (Theoretical Computer Science and General Issues, Bind 11101). (Lecture Notes in Computer Science, Bind 11101).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

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

AU - Tinós, Renato

AU - Helsgaun, Keld

AU - Whitley, Darrell

N1 - Conference code: 15

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

T3 - Theoretical Computer Science and General Issues

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

T2 - 15th International Conference on Parallel Problem Solving from Nature

Y2 - 8 September 2018 through 12 September 2018

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). doi: 10.1007/978-3-319-99253-2_8