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, and, with being the length of a string of evolution and determining the level of landscape ruggedness. The NK model has found application in a wide variety of fields, including the theoretical study of evolutionary biology, immunology, optimisation, technological evolution, 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, and movement on the landscape necessitates organizational decisions, which tend to interact with each other and affect profit in a complex fashion. An early version of the model, which considered only the smoothest and most rugged landscapes, was presented in Kauffman and Levin. The model as it is currently known first appeared in Kauffman and Weinberger. 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 which means it is difficult to find global optima. Recently, it was shown that the NK model for K > 1 is also PLS-complete which means than, in general, it is difficult to find even local fitness optima. This has consequences for the study of open-ended evolution.
Mathematical details
The NK model defines a combinatorialphase space, consisting of every string of length. For each string in this search space, a scalar value 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 the sum of contributions from each locus in the string: and the contribution from each locus in general depends on its state and the state of other loci,: where is the index of the th neighbor of locus. Hence, the fitness function 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. In 1991, Weinberger published a detailed analysis of the case in which and the fitness contributions are chosen randomly. His analytical estimate of the number of local optima was later shown to be flawed. 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 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, so that each locus is affected by its neighbour, and for cyclicity. If we choose, for example, the fitness function f = 0; f = 1; f = 2; f = 0, the fitness values of two example strings are:
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 > f, or all 1s if f > f). For nonzero K, the fitness of a string is a sum of fitnesses of substrings, which may interact to frustratethe system. 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 : a proportion of the fitness contributions is set to zero, so that the contributions of several genetic motifs are degenerate. The NKQ model introduces a parameter and enforces a discretisation on the possible fitness contribution values so that each contribution takes one of possible values, again introducing degeneracy in the contributions from some genetic motifs. The bare NK model corresponds to the and cases under these parameterisations.
