Adaptive walks

Random energy model The random energy model (REM) results from using a fitness distribution p(f) to assign fitnesses randomly to points in the landscape [ 14,59,60,70,71,81, 91,92], p(f) is the probability that a point in the sequence space has fitness fand is exactly analogous to affinity distribution p(Ka). Such landscapes have zero correlation (are very rugged), have many local fitness peaks, and result in very short adaptive walks. Very few of the local peaks are accessible by adaptive walks from any particular point. 

The limited space for this review precludes a proper review of the extensive literature on this subject. I will confine this section to results concerning setting selection stringency and mutation rate, as these issues are critical to any laboratory implementation of search. There are four relevant bodies of literature adaptive walk studies, theoretical immune system studies, formal spin glass studies, and theoretical genetic algorithm studies. Much of the adaptive walk literature has already been discussed above. 

The simulations also show that pooling generally does not result in local peaks. Adaptive walks via point mutations from pool optima found local peaks of higher fitness. Interestingly, if the best two pools in each cycle were retained, recombination between the 2c (c cycles) resulting pool optima generally only found points of lower fitness than the pool optima. But when the recombinants were then used as the start for adaptive walks... 

Fig. 4. The role of neutral networks in evolutionary optimization through adaptive walks and random drift. Adaptive walks allow to choose the next step arbitrarily from all directions where fitness is (locally) nondecreasing. Populations can bridge over narrow valleys with widths of a few point mutations. In the absence of selective neutrality (upper part) they are, however, unable to span larger Hamming distances and thus will approach only the next major fitness peak. Populations on rugged landscapes with extended neutral networks evolve along the network by a combination of adaptive walks and random drift at constant fitness (lower part). In this manner, populations bridge over large valleys and may eventually reach the global maximum ofthe fitness landscape.

Therefore, the walk length before a local optimum is reached will be longer for an adaptive walk than a steepest ascent walk. The walk length R for an adaptive and steepest ascent walk has been estimated using the NK-model ... 

Macken et al. (1991) identified two behaviors of an adaptive walk as it ascends the fitness landscape that are separated by a distinct phase transition. As a sequence becomes more optimized, the number of fitter mutants decreases. At some point, it becomes difficult to sample a fitter mutant given the number that can be screened. The probability of a sequence with fitness I having a single-mutant neighbor with lower fitness is G(F). The probability that a sequence with D single-mutant neighbors is at a local optimum 1 (F) is approximately... 

Kauffman S, Levin S. Towards a general theory of adaptive walks on mgged landscapes. 1. Theor. Biol. 1987 128 11-45. 

---