Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators
Artificial Intelligence ReviewPublished 1 April 1999
Pedro Larrañaga, C.M.H. Kuijpers, R.H. Murga, Iñaki Inza, S. Dizdarevic
Citations820
SJR quartileQ1
SJR score3.01
SNIP5.11
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
This paper presents crossover and mutation operators, developed to tackle the Travelling Salesman Problem with Genetic Algorithms with different representations such as: binary representation, path representation, adjacency representation, ordinal representation and matrix representation.
Abstract
This paper is the result of a literature study carried out by the authors. It is a review of the different attempts made to solve the Travelling Salesman Problem with Genetic Algorithms. We present crossover and mutation operators, developed to tackle the Travelling Salesman Problem with Genetic Algorithms with different representations such as: binary representation, path representation, adjacency representation, ordinal representation and matrix representation. Likewise, we show the experimental results obtained with different standard examples using combination of crossover and mutation operators in relation with path representation.
Keywords
Computer ScienceDecision SciencesEngineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
Medical Entomology and ZoologyGenetic Programming: On the Programming of Computers by Means of Natural Selection
13,257 Citations1992John R. Koza
This book discusses the evolution of architecture, primitive functions, terminals, sufficiency, and closure, and the role of representation and the lens effect in genetic programming.
Artificial intelligenceGenetic Algorithms + Data Structures = Evolution Programs
11,598 Citations1992Zbigniew Michalewicz
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
Journal of the Royal Statistical Society Series B (Statistical Methodology)Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems
3,970 Citations1988Steffen L. Lauritzen, David J. Spiegelhalter
This work exploits a range of local representations for the joint probability distribution, combined with topological changes to the original network termed 'marrying' and 'filling-in', which allows efficient algorithms for transfer between representations, providing rapid absorption and propagation of evidence.
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.
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.
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.
IEEE Signal Processing MagazineGenetic algorithms and their applications
1,093 Citations1996K.S. Tang, K.F. Man +2 more
The genetic algorithm is introduced as an emerging optimization algorithm for signal processing and a number of applications, such as IIR adaptive filtering, time delay estimation, active noise control, and speech processing, that are being successfully implemented are described.
international conference on Genetic algorithmsA study of permutation crossover operators on the traveling salesman problem
892 Citations1987I. M. Oliver, David J. Smith +1 more
Kluwer international series in engineering and computer scienceA Connectionist Machine for Genetic Hillclimbing
717 Citations1987David H. Ackley
This dissertation focuses on the development of a heuristic search algorithm that automates the very labor-intensive and therefore time-heavy and expensive process of manually cataloging discrete-time components of a genealogy tree.
Springer eBooksGenetic algorithms + data structures = evolution programs (2nd, extended ed.)
666 Citations1994Zbigniew Michalewicz
International Joint Conference on Artificial IntelligenceApplying adaptive algorithms to epistatic domains
646 Citations1985Lawrence Davis
New techniques for applying adaptive algorithms to epistatic domains, while retaining some of the strength of Holland's convergence proof are described, for two-dimensional bin-packing problems and graph coloring problems.
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.
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.
international conference on Genetic algorithmsA Comparison of Genetic Sequencing Operators.
367 Citations1991Timothy Starkweather, Susan E. McDaniel +3 more
This work compares six sequencing operators that have been developed for use with genetic algorithms and indicates that the eeective-ness of diierent operators is dependent on the problem domain.
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.
Biological CyberneticsAn evolutionary approach to the traveling salesman problem
290 Citations1988David B. Fogel
A simulation of natural evolution is conducted using the traveling salesman problem as an artificial environment and evolutionary adaptation is demonstrated to be worthwhile in a variety of contexts.
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansLearning Bayesian network structures by searching for the best ordering with genetic algorithms
268 Citations1996Pedro Larrañaga, C.M.H. Kuijpers +2 more
A new methodology for inducing Bayesian network structures from a database of cases based on searching for the best ordering of the system variables by means of genetic algorithms using genetic operators developed for the traveling salesman problem.
IEEE Transactions on Systems Man and CyberneticsApplying the genetic approach to simulated annealing in solving some NP-hard problems
253 Citations1993Feng‐Tse Lin, Cheng‐Yan Kao +1 more
The authors' approach can be viewed as a simulated annealing algorithm with population-based state transition and with genetic-operator-based quasi-equilibrium control and as a genetic algorithm with the Boltzmann-type selection operator.
Fraunhofer-Publica (Fraunhofer-Gesellschaft)ASPARAGOS An Asynchronous Parallel Genetic Optimization Strategy
241 Citations1989M. Gorges-Schleuter
Cybernetics & SystemsAPPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS
231 Citations1993David B. Fogel
The present paper relates the use of evolutionary programming on selected traveling salesman problems and finds solutions that are equal to or better than previously known best routings were discovered.
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.
NatureOptimization strategies gleaned from biological evolution
186 Citations1985R. M. Brady
Computer algorithms are used to investigate new strategies for the 64-city travelling salesman problem, which combine conventional optimization or ‘quenching’ with biological elements, namely having a population of trial solutions, helping weaker individuals to survive, and an analogue of sexual crossing-over of genes.
Foundations of genetic algorithmsGenetic Operators for Sequencing Problems
169 Citations1991B. R. Fox, Mary Beth Mcmahon
A thorough understanding of recombination operators for sequences will open up the possibility of applying genetic algorithms to a wide variety of problem domains, including scheduling.
Biological CyberneticsThe “molecular” traveling salesman
150 Citations1990Wolfgang Banzhaf
A method for optimization of NP-problems motivated by natural evolution is considered and the concept of isolated evolution is introduced to maintain a certain degree of variance in the population.
CryptologiaUSE OF A GENETIC ALGORITHM IN THE CRYPTANALYSIS OF SIMPLE SUBSTITUTION CIPHERS
133 Citations1993Richard Spillman, Mark Janssen +2 more
It is shown that such a algorithm could be used to discover the key for a simple substitution cipher using a directed random search algorithm called a genetic algorithm.
CryptologiaTHE USE OF GENETIC ALGORITHMS IN CRYPTANALYSIS
93 Citations1993Robert Matthews
It is shown that GAs can greatly facilitate cryptanalysis by efficiently searching large keyspaces, and their use with GENALYST, an order-based GA for breaking a classic cryptographic system is demonstrated.
Statistics and ComputingDecomposing Bayesian networks: triangulation of the moral graph with genetic algorithms
86 Citations1997PEDRO LARRAN ̃AGA, C.M.H. Kuijpers +2 more
The optimal decomposition of Bayesian networks is considered and the applicability of genetic algorithms to the problem of the triangulation of moral graphs is examined empirically.
Parallel ComputingNew solutions to the mapping problem of parallel systems: The evolution approach
79 Citations1987Heinz Mühlenbein, M. Gorges-Schleuter +1 more
It is shown that the mapping problem—assigning processes to processors—can be reduced to the graph partitioning problem and an evolution method derived from biology is applied to the travelling salesman problem.
Biological CyberneticsHeuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman Problem
48 Citations1991Balamurali K. Ambati, Jayakrishna Ambati +1 more
A genetic algorithm simulating Darwinian evolution is proposed to yield near-optimal solutions to the Traveling Salesman Problem and can be adapted to tackle a host of other combinatorial problems.
VNU Journal of Science: Natural Sciences and Technology (Vietnam National University)Genetic Algorithm to Traveling Salesman Problem
30 Citations2016Afshan butt, Vanita Ben Dhagat +1 more
A new structure of chromosome for TSP is proposed, since in TSP, a tour must pass through edges in E' at least once, it is necessary to involve E' and the information of direction in the chromosome.
Artificial Neural Nets and Genetic AlgorithmsHybrid Genetic Algorithms for the Traveling Salesman Problem
19 Citations1993P. Prinetto, Maurizio Rebaudengo +1 more
A new operator is proposed, whose goal is to include in the genetic mechanism some heuristic knowledge drawn from the already proposed local-optimization techniques, to exploit the benefits of the different operators.
Genetic algorithms and simulated annealing for gene mapping
10 Citations2002John A. Gunnels, Paul Cull +1 more
It is found that the GA method always converges to a good solution more quickly than the SA method, and the best solution produced by the GA method is always superior to the best solution produced by the SA method.
Studies in classification, data analysis, and knowledge organizationPartitional Cluster Analysis with Genetic Algorithms: Searching for the Number of Clusters
9 Citations1998José A. Lozano, Pedro Larrañaga +1 more
This article sets up the problem of searching for the number of clusters in partitional clustering in R 2.0 as an optimization problem by giving a real function on the different partitions that is optimized when theNumber of clusters and the classes are the most natural.