NK model

This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (April 2021) (Learn how and when to remove this message)

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, ${\displaystyle N}$ and ${\displaystyle K}$, with ${\displaystyle N}$ being the length of a string of evolution and ${\displaystyle K}$ 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, 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 (${\displaystyle K=0}$) and most rugged (${\displaystyle K=N-1}$) landscapes, was presented in Kauffman and Levin (1987).^[3] The model as it is currently known first appeared in Kauffman and Weinberger (1989).^[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. This has consequences for the study of open-ended evolution.