COMPARATIVE STUDY OF SOME SOLUTION METHODS FOR TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHMS

被引：13

作者：

Bhattacharyya, Malay ^{[1
]}

Bandyopadhyay, Anup Kumar ^{[2
]}

机构：

[1] Indian Stat Inst, Machine Intelligence Unit, Kolkata 700108, India

[2] Jadavpur Univ Kolkata, Dept ETCE, Kolkata, India

来源：

CYBERNETICS AND SYSTEMS | 2009年 / 40卷 / 01期

关键词：

Genetic algorithms; Network; Traveling salesman problem;

D O I：

10.1080/01969720802492967

中图分类号：

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

学科分类号：

0812 ;

摘要：

Despite the existence of a number of variations of genetic algorithms for the traveling salesman problem in literature, no efforts have been made to the best of our knowledge to characterize their performance. This paper presents a detailed comparative study on some of the solution methods for the traveling salesman problem using genetic algorithms. All the operators of genetic algorithms have been given equal emphasis in the analysis. The complete simulation has been done using a number of C programs written by us for this purpose. A permanent network has been particularly considered for this task. The results shed insight on the best solution method for the problem. However, we cannot conclude how the behavior of those algorithms depends on network topology.

引用

页码：1 / 24

页数：24

共 20 条

[11]

Goldberg DavidE., 2005, Genetic Algorithms in Search, Optimization, and Machine Learning

[12]

Grefenstette J.J., 1985, P 1 INT C GENETIC AL, P160

[13]

Holland J.H., 1975, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, DOI 10.7551/mitpress/1090.001.0001

[14]

Hong S., 1972, THESIS J HOPKINS U B

[15]

Konar A., 2005, COMPUTATIONAL INTELL

[16] EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM [J].

LIN, S ;

KERNIGHAN, BW .

OPERATIONS RESEARCH, 1973, 21 (02) :498-516

[17] INTEGER PROGRAMMING FORMULATION OF TRAVELING SALESMAN PROBLEMS [J].

MILLER, CE ;

TUCKER, AW ;

ZEMLIN, RA .

JOURNAL OF THE ACM, 1960, 7 (04) :326-329

[18]

SENGOKU H, 1998, FAST TSP SOLVER USIN, P283

[19]

SENGOKU H, 1993, INF PROC SOC JAP 47

[20]

SYSWERDA G, 1990, P WORKSH FDN GEN ALG

← 1 2 →