APPLYING EVOLUTIONARY PROGRAMMING TO SELECTED TRAVELING SALESMAN PROBLEMS

被引：178

作者：

FOGEL, DB

机构：

[1] ORINCON Corporation, San Diego, CA, 92121

来源：

CYBERNETICS AND SYSTEMS | 1993年 / 24卷 / 01期

关键词：

D O I：

10.1080/01969729308961697

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：27 / 36

页数：10

共 34 条

[1]

Ambati B.K., Ambati J., Mokhtar M.M., Heuristic Combinatorial Optimization by Simulated Darwinian Evolution: A Polynomial Time Algorithm for the Traveling Salesman Problem, Biol. Cybernet, 65, pp. 31-35, (1991)

[2]

Ambati B.K., Ambati J., Mokhtar M.M., An O (N log n)-Time Genetic Algorithm for the Traveling Salesman Problem, Proc First Armu Conf on Evolutionary Programming, pp. 134-140, (1992)

[3]

Atmar J.W., Speculation on the Evolution of Intelligence and Its Possible Realization in Machine Form, Doctoral Dissertation, (1976)

[4]

Atmar W., Natural Processes Which Accelerate the Evolutionary Search Proc 24Th Asilomar Conf on Signals Systems and Computers, pp. 1030-1035, (1990)

[5]

Back T., Hoffmeister F., Schwefel H.-P., A Survey of Evolution Strategies Proc Fourth Int Conf on Genetic Algorithms and Their Applications, pp. 2-9, (1991)

[6]

Banzhaf W., The “Molecular" Traveling Salesman. Biol, Cybernet, 64, pp. 7-14, (1990)

[7]

Belew R.K., Booker L.B., Proc. Fourth International Conference on Genetic Algorithms and Their Applications, (1991)

[8]

Bonomi E., Lutton J.-L., The City Traveling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm, SIAM Rev, 26, 4, pp. 551-569, (1984)

[9]

Christofides N., Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem Report 388, (1976)

[10]

Colomi A., Dorigo M., Maniezzo V., Distributed Optimization by Ant Colonies, Proc. Conference on Artificial Life, (1991)

← 1 2 3 4 →