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,
The NK model has found application in a wide variety of fields, including the theoretical study of evolutionary biology, immunology, optimisation, technological evolution, team science,[1] and complex systems.
The model was also adopted in organizational theory, where it is used to describe the way an agent may search a landscape by manipulating various characteristics of itself.
For example, an agent can be an organization, the hills and valleys represent profit (or changes thereof), and movement on the landscape necessitates organizational decisions (such as adding product lines or altering the organizational structure), which tend to interact with each other and affect profit in a complex fashion.
[2] An early version of the model, which considered only the smoothest (
[4] 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[5] which means it is difficult to find global optima.
Recently, it was shown that the NK model for K > 1 is also PLS-complete[6] which means than, in general, it is difficult to find even local fitness optima.
Then the plasmid is modelled by a binary string with length N, and so the fitness function is
The simplest model would have the genes not interacting with each other, and so we obtain
It is reasonable to assume that on a plasmid, two genes interact if they are adjacent, thus giving
For example, when K = 1, and N = 5, The NK model generalizes this by allowing arbitrary finite K, N, as well as allowing arbitrary definition of adjacency of genes (the genes do not necessarily lie on a circle or a line segment).
The NK model defines a combinatorial phase space, consisting of every string (chosen from a given alphabet) of length
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
is a mapping between strings of length K + 1 and scalars, which Weinberger's later work calls "fitness contributions".
Such fitness contributions are often chosen randomly from some specified probability distribution.
The 1D Ising model of spin glass is usually written as
We can reformulate it as a special case of the NK model with K=1:
In general, the m-dimensional Ising model on a square grid
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)).
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.
possible values, again introducing degeneracy in the contributions from some genetic motifs [citation needed].
In 1991, Weinberger published a detailed analysis[7] of the case in which
His analytical estimate of the number of local optima was later shown to be flawed [citation needed].
However, numerical experiments included in Weinberger's analysis support his analytical result that the expected fitness of a string is normally distributed with a mean of approximately
The NK model has found use in many fields, including in the study of spin glasses, collective problem solving,[8] epistasis and pleiotropy in evolutionary biology, and combinatorial optimisation.
