The Origins of Order: Self-Organization and Selection in Evolution
The following sections are included:
Introduction
Fitness Landscapes in Sequence Space
The NK Model of Rugged Fitness Landscapes
The NK Model of Random Epistatic Interactions
The Rank Order Statistics on K = N − 1 Random Landscapes
The number of local optima is very large
The expected fraction of fitter 1-mutant neighbors dwindles by 1/2 on each improvement step
Walks to local optima are short and vary as a logarithmic function of N
The expected time to reach an optimum is proportional to the dimensionality of the space
The ratio of accepted to tried mutations scales as lnN/N
Any genotype can only climb to a small fraction of the local optima
A small fraction of the genotypes can climb to any one optimum
Conflicting constraints cause a “complexity catastrophe”: as complexity increase accessible adaptive peaks fall toward the mean fitness
The “Tunable” NK Family of Correlated Landscapes
Other Combinatorial Optimization Problems and Their Landscapes
Summary
References