THE MOLECULAR TRAVELING SALESMAN

被引：104
作者：
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 [J].
BONOMI, E ;
LUTTON, JL .
SIAM REVIEW, 1984, 26 (04) :551-568
[2]   BOLTZMANN AND DARWIN STRATEGIES IN COMPLEX OPTIMIZATION [J].
BOSENIUK, T ;
EBELING, W ;
ENGEL, A .
PHYSICS LETTERS A, 1987, 125 (6-7) :307-310
[3]   OPTIMIZATION STRATEGIES GLEANED FROM BIOLOGICAL EVOLUTION [J].
BRADY, RM .
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 [J].
FONTANA, W ;
SCHUSTER, P .
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 [J].
KIRKPATRICK, S ;
GELATT, CD ;
VECCHI, MP .
SCIENCE, 1983, 220 (4598) :671-680
[10]  
Lawler E. L., 1985, WILEY INTERSCIENCE S
12