![]() | ||
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,
Contents
An early version of the model, which considered only the smoothest (
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.
Mathematical details
The NK model defines a combinatorial phase space, consisting of every string (chosen from a given alphabet) of length
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
and the contribution from each locus in general depends on the value of
where
Hence, the fitness function
In 1991, Weinberger published a detailed analysis of the case in which
and a variance of approximately
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
Tunable topology
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.
Variations with neutral spaces
The bare NK model does not support the phenomenon of neutral space -- that is, sets of genomes connected by single mutations that have the same fitness value. Two adaptations have been proposed to include this biologically important structure. The NKP model introduces a parameter
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.