HYBRID NEWTON-RAPHSON GENETIC ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM

被引：30

作者：

LIN, W ^{[1
]}

DELGADOFRIAS, JG ^{[1
]}

GAUSE, DC ^{[1
]}

VASSILIADIS, S ^{[1
]}

机构：

[1] SUNY BINGHAMTON,DEPT ELECT ENGN,BINGHAMTON,NY 13902

来源：

CYBERNETICS AND SYSTEMS | 1995年 / 26卷 / 04期

关键词：

D O I：

10.1080/01969729508927504

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper presents a novel genetic algorithm to solve the traveling salesman problem. The proposed method combines the Newton-Raphson numerical method with an inversion genetic algorithm; the method is called inversion with embedded Newton-Raphson Search. Different benchmark problems, including 10-, 30-, 50-, 75-, 105-, and 318-city topologies, are used to evaluate the approach. The best-known solutions have been produced by this hybrid genetic algorithm. In this paper we also report other results, such as the average tour distance, distribution of the results, and average number of generations. The proposed approach has been shown to outperform other genetic operators. An analysis based on the survival rate of the o-schemata and Holland's fundamental theory is included.

引用

页码：387 / 412

页数：26

共 13 条

[1]

Eilon S., Christofides N., Distribution management: Mathematical modeling and practical analysis, Operational Research Quarterly, 20, (1969)

[2]

Fogel D.B., Applying evolutionary programming to selected traveling salesman problems, Cybernet. Syst, 24, pp. 27-36, (1993)

[3]

Fogel D.B., An introduction to simulated evolutionary optimization, IEEE Trans. Neural Networks, 5, 1, pp. 3-14, (1994)

[4]

Goldberg D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, (1989)

[5]

Homaifar A., Guan S., Liepins G.E., A new approach on the traveling salesman problem by genetic algorithms. Genetic algorithms and their applications, Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 460-466, (1993)

[6]

Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B., The Traveling Salesman Problem, (1985)

[7]

Lin S., Kemighan B.W., An effective heuristic algorithm for the traveling salesman problem, Operational Research, 21, pp. 498-516, (1976)

[8]

Lin W., Delgado-Frias J.G., Pechanek G.G., Vassiliadis S., An evaluation of energy function for a neural network model for optimization problems, IEEE International Joint Conference on Neural Networks, pp. 4518-4522, (1994)

[9]

Michalewicz Z., Genetic Algorithms + Data Structures — Evolution Programs, (1992)

[10]

Oliver I.M., Smith D.J., Holland J.R.C., A study of permutation crossover operators on the traveling salesman problem. Genetic algorithms and their applications, Proceedings of the Second International Conference on Genetic Algorithms, pp. 224-230, (1987)

← 1 2 →