APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS

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.