APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS
- 1 January 1993
- journal article
- research article
- Published by Taylor & Francis Ltd in Cybernetics and Systems
- Vol. 24 (1), 27-36
- https://doi.org/10.1080/01969729308961697
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
This publication has 9 references indexed in Scilit:
- Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman ProblemBiological Cybernetics, 1991
- The “molecular” traveling salesmanBiological Cybernetics, 1990
- Comparing genetic operators with gaussian mutations in simulated evolutionary processes using linear systemsBiological Cybernetics, 1990
- An evolutionary approach to the traveling salesman problemBiological Cybernetics, 1988
- Using simulated annealing to solve routing and location problemsNaval Research Logistics Quarterly, 1986
- The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis AlgorithmSIAM Review, 1984
- Optimization by Simulated AnnealingScience, 1983
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the PlaneMathematics of Operations Research, 1977
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973