Adaptive Walks by the Fittest among Finite Random Mutants on a Mt. Fuji-type Fitness Landscape.
Based on the theory of fitness distributions on a Mt. Fuji-type fitness landscape in a multivalued sequence space (Aita & Husimi, 1996 J. theor. Biol. 182, 469-485), we investigated the properties of adaptive walks on the ideal landscape in the case of a cloning-screening-type evolution experiment. We modeled that an adaptive walk is performed by repetition of the evolution cycle composed of the mutagenesis process generating random d-fold point mutants of population size N and the selection process looking for the fittest mutant among them. While an adaptive walk is described in a sequence space, we simplified the description as follows. We mapped the landscape in an x-y plane, where x and y represent a normalized Hamming distance from the global peak and a scaled fitness, respectively. An adaptive walk is described as a trajectory in the plane. The most certain step for a walker to move in a single evolution cycle is represented by a vector in the plane. Then, a walker moves along the streams in the vector field determined by d and N. The walker performs fast hill-climbing until a "trap-line", which traverses the plane. Subsequently, the walker is likely to get trapped in an "apparent local optimum". To continue the walk, apparent local optima must be eliminated by resetting d and N larger. Therefore, for the fastest walk, the optimal schedule of the d-values (initially large d, then small d) is effective, although the economical walk with high cost-performance is different. If a real landscape is just of the Mt. Fuji-type, the walk with the highest cost-performance will be performed by scanning site-directed optimization through all sites. However, in the case of the rough Mt. Fuji-type, which seems to be more realistic, the walking method we have examined will be effective for a walker to sidestep true local optima.Copyright 1998 Academic Press
Aita
T
Department of Functional Materials Science, Saitama University, Urawa 338, Japan
Husimi
Y