NK-Landscapes

Kauffman ([kauffSO], [kauffOOa]) has introduced a class of parametrizable fitness landscapes called NK-landscapes, that provide a formalism for studying the efficacy of GA evolution as a function of certain statistical properties of the landscape. Given N binary variables Xi = 1, so that x = (xi, X2, , Xjv) represents a vertex of an A -dimensional hypercube, an NK-landscape is defined by a fitness function, JF, of the form 

As K increases from 0 (where T x) = fi xi)) to N — 1 (where F becomes the sum of N independent random numbers), the NK-landscape goes from having a single maximum to having more and more maxima that become less and less correlated to, finally, being essentially totally random. The parameter K can therefore be used to tune the degree of ruggedness of the landscape. 

Some preliminary suggestions of how NK-landscapes can be used to predict GA performance are discussed by Kauffman [kauff89] and Manderick, de Weger and Spiessens [mand91]. 

---

Fig. 18. Distribution of fitnesses as a function of mutant Hamming distance from current position on the landscape for an initial fitness of (a) 0.5 and (b) 0.543. Simulations were carried out on NK landscapes with N= 100 and K = 2, yielding the high nearest neighbor correlation of 0.97 and a correlation length of 33.3. Vertical bars show +1 and -1 standard deviation from the mean of fitnesses found at each search distance. If the best of six mutants at each distance is chosen, then the best mutant can be found at Hamming distance 33 from the fitness 0.5 point and at decreasing distances as the initial fitness increases. (From Ref. 119.)...

Fig. 19. Distributions offitnesses of the best pool during successive cycles (iterations) ofa pooling strategy. Simulations are on an NK landscape with N= 6 and 20 monomers per site, corresponding to a hexapeptide. The initial 400 pools are fixed at sites 3 and 4. The second pools are fixed at sites 2 and 5, and the third pools are fixed at sites 1 and 6. (a) K=0 (b) K=3. (From Ref. 65.)...

NK model The NK model is a simple landscape model that allows arbitrary degrees of correlation between 0 and 1 [4,92,93], The sequence space is an N-dimensional space... 

Fig. 15. Example of frustration in an NK fitness landscape model. The tables list the fitness contributions for sites 3 and 4 as a function of their K = 2 epistatic inputs and their own values. The highest fitness contribution for fi requires [a2.a,.a4] =[1,0,0], while for f4 it requires [a3,a4,a5]= [1,0,1]. These two constraints cannot be mutually satisfied, leading to frustration. As K increases, the number of such conflicts rises and results in an increasingly rugged landscape whose peaks are of increasingly lower average fitness.

The NK, p-spin and other models described above all assign fitnesses directly to sequences. In contrast, the secondary structure landscapes are best thought of in two parts ... 

Kauffman and Macready [65] examined pooling strategies on NK fitness landscapes. They simulated two pooling strategies that differed in the order in which amino acid sites were used to partition the best pool each cycle (order of unrandomization) and the number of subpools they were partitioned into. Results were qualitatively the same for both. A pool s fitness was defined as the average fitness of its members. 

The REM, NK and p-spin models all are attempts to capture the important statistical properties of true molecular landscapes in a simple model. Because they contain no biophysical information, they are limited in how well they can achieve this. The block model is an important step in removing some of the simplifications in these models, as it allows for nonstationary properties that can be matched to different regions of molecules. Ideally, landscape models can be based on experimental data. Unfortunately, despite the tremendous interest in molecular optimization, there is still relatively little data that can be used this way. As more data are collected on the effects of substitutions in protein structural and loop regions, antibody CDRs and framework regions, etc., a block or other type of model can be developed that uses appropriate fitness functions for each block. Combined efforts by theoreticians and experimentalists may also help devise experiments that measure key true affinity landscape properties without excessive laboratory effort. 

To summarize this section we have developed a simple dynamical model for a genetic algorithm that predicts the time evolution of the fitness distribution of a population. As basis for its prediction, it uses the parent-child fitness correlation of the genetic operators with respect to the specific fitness function. What has been demonstrated here for the simplest fitness function, a random field paramagnet, has also been generalized and applied to more rugged landscapes in [47], e.g., the spin glass motivated NK model. 

---