APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS
Cybernetics & SystemsPublished 1 January 1993
David B. Fogel
Citations231
SJR quartileQ3
SJR score0.42
SNIP0.69
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
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.
Abstract
Natural evolution provides a paradigm for the design of stochastic-search optimization algorithms. Various forms of simulated evolution, such as genetic algorithms and evolutionary programming techniques, have been used to generate machine learning through automated discovery. These methods have been applied to complex combinatorial optimization problems with varied degrees of success. The present paper relates the use of evolutionary programming on selected traveling salesman problems. In three test cases, solutions that are equal to or better than previously known best routings were discovered. In a 1000-city problem, the best evolved routing is about 5% longer than the expected optimum.
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.
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.
BiometricsPrinciples of Population Genetics.
5,349 Citations1990R. M. Cormack, Daniel L. Hartl +1 more
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.
Distributed Optimization by Ant Colonies
2,580 Citations1992Alberto Colorni, Marco Dorigo +3 more
A distributed problem solving environment is introduced and its use to search for a solution to the travelling salesman problem is proposed.
international conference on Genetic algorithmsA study of permutation crossover operators on the traveling salesman problem
892 Citations1987I. M. Oliver, David J. Smith +1 more
A Survey of Evolution Strategies.
746 Citations1991Thomas Bäck, Frank Hoffmeister +1 more
Evolution Strategies are algorithms which imitate the principles of natural evolution as a method to solve parameter optimization problems and adaptation of the strategy parameters for the mutation variances as well as their covariances are described.
Mathematics of Operations ResearchProbabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
443 Citations1977Richard M. Karp
This work considers partitioning algorithms for the approximate solution of large instances of the traveling-salesman problem in the plane, in which partitioning is used in conjunction with existing heuristic algorithms.
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.
Evolving artificial intelligence
285 Citations1992David B. Fogel
It is argued that all three forms of intelligence are equivalent in process and that all intelligent systems are inherently evolutionary in nature.
SIAM ReviewThe <i>N</i>-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
251 Citations1984Ernesto Bonomi, Jean‐Luc Lutton
The Metropolis algorithm is used to generate a sequence of tours that may be viewed as the random evolution of a physical system in contact with a heat-bath, and it appears that for large N one arrives within a few percent of the optimal solution in better than quadratic time.
Deep Blue (University of Michigan)Computer-Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning.
248 Citations1983David E. Goldberg
Biological CyberneticsComparing genetic operators with gaussian mutations in simulated evolutionary processes using linear systems
242 Citations1990David B. Fogel, J. W. Atmar
The results indicate that specific genetic operations to mutate the structure that encodes expressed behavior do not compare favorably with more simple random mutation.
Naval Research Logistics QuarterlyUsing simulated annealing to solve routing and location problems
206 Citations1986Bruce Golden, Christopher C. Skiścim
This paper implements the analogy between the statistical mechanics of large multivariate physical systems and combinatorial optimization, applies it to the traveling salesman problem and the p‐median location problem, and test the approach extensively.
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.
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.
Transportation Research Part A GeneralScheduling dial-a-ride transportation systems: An asymptotic approach
21 Citations1979
There has been some recent interest in the Dial-a-Ride proposal for innovative public transportation systems, which ideally provide large numbers of passengers with personalized service and the central mathematical problem is one of scheduling.
international conference on Genetic algorithmsParallelisation of probabilistic sequential search algorithms
19 Citations1987Prasanna Jog, Dirk Van Gucht
This work compares some strategies of parallelization of Lin and Kernighan's 2-opt operator for the Traveling Salesman Problem and explores the quick approximate evaluation of tour lengths to determine the fitness of each tour for information exchange.
Natural processes which accelerate the evolutionary search
4 Citations2005Wirt Atmar
Sufficient experience has now been garnered to suggest that all strongly-determined numerical optimization methods tend to work acceptably well on some adaptive surfaces, but exhibit a pronounced tendency to stall in indefinite oscillation, fail to converge, or become entrapped in local optima on others.