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
Travelling salesman problemComputer scienceGenetic programmingMathematical optimization2-optCombinatorial optimizationEvolutionary programmingEvolutionary algorithmGenetic algorithmRouting (electronic design automation)Artificial intelligenceMathematicsAlgorithmMachine learning
Affiliated Institutions
Related Publications
Ant colony system: a cooperative learning approach to the traveling salesman problem
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...
Fast Algorithms for Geometric Traveling Salesman Problems
This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heur...
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is base...
Applying the genetic approach to simulated annealing in solving some NP-hard problems
A stochastic approach called the annealing-genetic algorithm is presented for solving some well-known combinatorial optimization problems. This approach incorporates genetic alg...
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple cons...
Publication Info
- Year
- 1993
- Type
- article
- Volume
- 24
- Issue
- 1
- Pages
- 27-36
- Citations
- 231
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
231
OpenAlex
Cite This
David B. Fogel
(1993).
APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS.
Cybernetics & Systems
, 24
(1)
, 27-36.
https://doi.org/10.1080/01969729308961697
Identifiers
- DOI
- 10.1080/01969729308961697