Random field models for fitness landscapes

被引:38
作者
Stadler, PF
Happel, R
机构
[1] Univ Vienna, Inst Theoret Chem, A-1090 Vienna, Austria
[2] Santa Fe Inst, Santa Fe, NM 87501 USA
关键词
combinatorial optimization problems; correlation function; evolutionary optimization; fitness landscapes; Fourier series; random fields;
D O I
10.1007/s002850050156
中图分类号
Q [生物科学];
学科分类号
07 ; 0710 ; 09 ;
摘要
In many cases fitness landscapes are obtained as particular instances of random fields by randomly assigning a large number of parameters. Models of this type are often characterized reasonably well by their covariance matrices. We characterize isotropic random fields on finite graphs in terms of their Fourier series expansions and investigate the relation between the covariance matrix of the random field model and the correlation structure of the individual landscapes constructed from this random field. Correlation measures are a good characteristic of "rugged landscapes" models as they are closely related to quantities like the number of local optima or the length of adaptive walks. Our formalism suggests to approximate landscape with known autocorrelation function by a random field model that has the same correlation structure.
引用
收藏
页码:435 / 478
页数:44
相关论文
共 97 条
[1]  
Alavi Y., 1991, Graph theory, combinatorics, and applications, V2, P871
[2]   POPULATION-DYNAMICS IN A SPIN-GLASS MODEL OF CHEMICAL EVOLUTION [J].
AMITRANO, C ;
PELITI, L ;
SABER, M .
JOURNAL OF MOLECULAR EVOLUTION, 1989, 29 (06) :513-525
[3]  
[Anonymous], 1980, SPECTRA GRAPHS THEOR
[4]  
[Anonymous], 1994, LECT NOTES MATH
[5]  
[Anonymous], 1994, ALGEBRAIC GRAPH THEO
[6]  
[Anonymous], ORIGIN ORDER
[7]  
[Anonymous], 1979, GRAPH THEORY INTRO C, DOI DOI 10.1007/978-1-4612-9967-7
[8]   COEVOLUTION IN A RUGGED FITNESS LANDSCAPE [J].
BAK, P ;
FLYVBJERG, H ;
LAUTRUP, B .
PHYSICAL REVIEW A, 1992, 46 (10) :6724-6730
[9]   GRAPH BIPARTITIONING AND STATISTICAL-MECHANICS [J].
BANAVAR, JR ;
SHERRINGTON, D ;
SOURLAS, N .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1987, 20 (01) :L1-L8
[10]  
BESAG J, 1974, AM MATH MONTHLY, V81, P192