New genetic local search operators for the traveling salesman problem
Lecture notes in computer sciencePublished 1 January 1996
Bernd Freisleben, Peter Merz
Citations168
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An approach is presented to incorporate problem specific knowledge into a genetic algorithm which is used to compute near-optimum solutions to traveling salesman problems (TSP).
Abstract
In this paper, an approach is presented to incorporate problem specific knowledge into a genetic algorithm which is used to compute near-optimum solutions to traveling salesman problems (TSP). The approach is based on using a tour construction heuristic for generating the initial population, a tour improvement heuristic for finding local optima in a given TSP search space, and new genetic operators for effectively searching the space of local optima in order to find the global optimum. The quality and efficiency of solutions obtained for a set of TSP instances containing between 318 and 1400 cities are presented.
Keywords
Computer ScienceEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Mathematics and Computers in SimulationSimulated annealing: theory and applications.
3,005 Citations1988
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Simulated Annealing: Theory and Applications
2,372 Citations1987Peter J. M. van Laarhoven, Emile Aarts
Performance of the simulated annealing algorithm and the relation with statistical physics and asymptotic convergence results are presented.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
Journal of the Operational Research SocietyThe Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization
1,701 Citations1986
Parallel ComputingEvolution algorithms in combinatorial optimization
397 Citations1988Heinz Mühlenbein, M. Gorges-Schleuter +1 more
A new genetic algorithm which relies on intelligent evolution of individuals is presented, which is inherently parallel and shows a superlinear speedup in multiprocessor systems.
Operations Research LettersOptimization of a 532-city symmetric traveling salesman problem by branch and cut
392 Citations1987Manfred Padberg, Giovanni Rinaldi
Lecture notes in computer scienceLocal optimization and the Traveling Salesman Problem
376 Citations2005David S. Johnson
This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
Lecture notes in computer scienceParallel genetic algorithms, population genetics and combinatorial optimization
369 Citations1991Heinz Mühlenbein
This paper has applied ASPARAGOS to an important combinatorial optimization problem, the quadratic assignment problem, and found a new optimum for the largest published problem.
Operations Research LettersA new adaptive multi-start technique for combinatorial global optimizations
351 Citations1994Kenneth D. Boese, Andrew B. Kahng +1 more
This work motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima.
Foundations of genetic algorithmsEvolution in Time and Space – The Parallel Genetic Algorithm
326 Citations1991Heinz Mühlenbein
This work investigates the PGA with deceptive problems and the traveling salesman problem, a parallel search with information exchange between the individuals, and shows the correlation for thetraveling salesman problem by a configuration space analysis.
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
280 Citations2002Bernd Freisleben, P. Merz
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP) and the results indicate that it is possible to arrive at high quality solutions in reasonable time.
Fraunhofer-Publica (Fraunhofer-Gesellschaft)ASPARAGOS An Asynchronous Parallel Genetic Optimization Strategy
241 Citations1989M. Gorges-Schleuter
Lecture notes in computer scienceGenetic local search algorithms for the traveling salesman problem
220 Citations1991Nico L. J. Ulder, Emile Aarts +3 more
Experimental approaches to Genetic Local Search with 2-Opt neighbourhoods and Lin-Kernighan neighbourhoods are compared with the corresponding classical multi-start Local Search algorithms, as well as with Simulated Annealing and Threshold Accepting.
Lecture notes in computer scienceExplicit parallelism of genetic algorithms through population structures
101 Citations2006M. Gorges-Schleuter
This paper specifies an algorithm which uses only local rules and local data making it massively parallel with an observed linear speedup on a transputer-based parallel system, and shows that both convergence speed and final quality are improved in comparison to a genetic algorithm without population structure.
Genetic Operators, the Fitness Landscape and the Traveling Salesman Problem.
92 Citations1992Keith E. Mathias, L. Darrell Whitley
Lecture notes in computer scienceA modified edge recombination operator for the Travelling Salesman Problem
21 Citations1994Anthony Yiu-Cheung Tang, Kwong‐Sak Leung
A modified version of the crossover operator developed to preserve edge information for the Travelling Salesman Problem is described, which converges significantly faster for all the benchmark problems tested.