THE MOLECULAR TRAVELING SALESMAN

被引：103

作者：

BANZHAF, W

机构：

[1] Central Research Laboratory, Mitsubishi Electric Corporation, Hyogo, 661, 1-1, Tsukaguchi Honmachi 8-chome, Amagasaki

来源：

BIOLOGICAL CYBERNETICS | 1990年 / 64卷 / 01期

关键词：

D O I：

10.1007/BF00203625

中图分类号：

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

学科分类号：

0812 ;

摘要：

We consider a method for optimization of NP-problems motivated by natural evolution. The basic entity is a population of individuals searching in state space defined by the problem. A message exchange mechanism between individuals enables the system to proceed fast and to avoid local optima. We introduce the concept of isolated evolution to maintain a certain degree of variance in the population. The global optimum can be approached to an arbitrary degree. The method is applied to the TSP and its behavior is shown in a couple of simulations. © 1990 Springer-Verlag.

引用

页码：7 / 14

页数：8

共 16 条

[1] THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM
BONOMI, E
LUTTON, JL
[J]. SIAM REVIEW, 1984, 26 (04) : 551 - 568
[2] BOLTZMANN AND DARWIN STRATEGIES IN COMPLEX OPTIMIZATION
BOSENIUK, T
EBELING, W
ENGEL, A
[J]. PHYSICS LETTERS A, 1987, 125 (6-7) : 307 - 310
[3] OPTIMIZATION STRATEGIES GLEANED FROM BIOLOGICAL EVOLUTION
BRADY, RM
[J]. NATURE, 1985, 317 (6040) : 804 - 806
[4] Bremermann H. J., 1965, BIOPHYSICS CYBERNETI, P157
[5] FOGEL DB, 1989, BIOL CYBERN, V60, P139
[6] A COMPUTER-MODEL OF EVOLUTIONARY OPTIMIZATION
FONTANA, W
SCHUSTER, P
[J]. BIOPHYSICAL CHEMISTRY, 1987, 26 (2-3) : 123 - 147
[7] Grefenstette J., 1985, P 1 INT C GENETIC AL, P160
[8] HOLLAND JH, 1975, ADAPTATION NATURAL A
[9] OPTIMIZATION BY SIMULATED ANNEALING
KIRKPATRICK, S
GELATT, CD
VECCHI, MP
[J]. SCIENCE, 1983, 220 (4598) : 671 - 680
[10] Lawler E. L., 1985, WILEY INTERSCIENCE S

← 1 2 →