NK model

The NK model is a mathematical model described by its primary inventor Stuart Kauffman as a "tunably rugged" fitness landscape. "tunable ruggedness" captures the intuition that both the overall size of the landscape and the number of its local "hills and valleys" can be adjusted via changes to its two parameters, N and K, defined below. The NK model has found application in a wide variety of fields, most notably the theoretical study of evolutionary biology, immunology, optimisation and complex systems.

An early version of the model, which considered only the smoothest (K = 0) and most rugged (K = N) landscapes, was presented in Kauffman and Levin (1987)^[1]. The model as it is currently known first appeared in Kauffman and Weinberger (1989)^[2].

One of the reasons why the model has attracted wide attention in optimisation is that it is a particularly simple instance of a so-called Np-complete problem^[3]

Mathematical Detail

The NK model defines a combinatorial search space, consisting of every string (chosen from a given alphabet) of length N. For each string in this search space, a scalar value (called the fitness) is defined. If a distance metric is defined between strings, the resulting structure is a landscape.

Fitness values are defined according to the specific incarnation of the model, but the key feature of the NK model is that the fitness of a given string S is the sum of contributions from each locus S_i in the string:

F(S) =	∑	f(Si),
	i

and the contribution from each locus in general depends on the value of K other loci:

$f(S_i) = f(S_i, S^i_1, \dots, S^i_K), \,$

where $S^i_j$ are the other loci upon which the fitness of S_i depends.

Hence, the fitness function $f(S_i, S^i_1, \dots, S^i_K)$ is a mapping between strings of length K + 1 and scalar values. In a particular implementation of the NK model, the scalar values corresponding to each string are often chosen randomly.

Example

For simplicity, we will work with binary strings. Consider an NK model with N = 5, K = 1. Here, the fitness of a string is given by the sum of individual fitness contributions from each of 5 loci. Each fitness contribution depends on the local locus value and one other. We will employ the convention that f(S_i) = f(S_i,S_{i + 1}), so that each locus is affected by its neighbour, and f(S₅) = f(S₅,S₁) for cyclicity. If we choose, for example, the fitness function f(0, 0) = 0; f(0, 1) = 1; f(1, 0) = 2; f(1, 1) = 0, the fitness values of two example strings are:

$F(00101) = f(0,0) + f(0,1) + f(1,0) + f(0, 1) + f(1, 0) = 0 + 1 + 2 + 1 + 2 = 6. \,$

$F(11100) = f(1,1) + f(1,1) + f(1,0) + f(0, 0) + f(0, 1) = 0 + 0 + 2 + 0 + 1 = 3. \,$

Tunable topology

Illustration of tunable topology in the NK model. Nodes are individual binary strings, edges connect strings with a Hamming distance of exactly one. (left) N = 5, K = 0. (centre) N = 5, K = 1. (right) N = 5, K = 2. The colour of a node denotes its fitness, with redder values having higher fitness. The embedding of the hypercube is chosen so that the fitness maximum is at the centre. Notice that the K = 0 landscape appears smoother than the higher-K cases.

The value of K controls the degree of epistasis in the NK model, or how much other loci affect the fitness contribution of a given locus. With K = 0, the fitness of a given string is a simple sum of individual contributions of loci: for nontrivial fitness functions, a global optimum is present and easy to locate (the genome of all 0s if f(0) > f(1), or all 1s if f(1) > f(0)). For nonzero K, the fitness of a string is a sum of fitnesses of substrings, which may interact to frustrate the system (consider how to achieve optimal fitness in the example above). Increasing K thus increases the ruggedness of the fitness landscape.

Applications

The NK model has found use in many fields, including in the study of spin glasses, epistasis and pleiotropy in evolutionary biology, and combinatorial optimisation.

References

1. ^ Kauffman, S. and Levin, S. (1987), "Towards a general theory of adaptive walks on rugged landscapes", J. Theor. Biol 128 (1) 11–45
2. ^ Kauffman, S. and Weinberger, E. (1989), "The N-k Model of the application to the maturation of the immune response," Journal of Theoretical Biology, Vol. 141, No. 2, 211-245
3. ^ Weinberger, E. (1996), "Np-completeness of Kauffman's N-k model, a Tuneably Rugged Fitness Landscape", Santa Fe Institute Working Paper, 96-02-003.