Kauffman NK Model - A Stochastic Combinatorial Optimization Model for Complex Systems

Abstract

Many scenarios in theoretical biology, physics, and management science can be modeled as discrete complex systems with several interacting components that can be in various states.  The aim is to maximize a performance measure involving contributions from each component.  This measure may depend on both the state of each component and on interactions between components. In 1987, Kauffman and Levin introduced a combinatorial optimization model for such systems, called the Kauffman NK model, where N is the number of components of the system and K measures the interaction between the components.  This was proposed to model the evolution of genomes in theoretical biology but has since been applied in other areas as listed above.
Previous research on the NK model has emphasized simulations and analysis of local optima.  Here we focus on rigorous results for global optima. We describe a computational setup using a stochastic network model, which leads to applicable strategies for computing bounds on global optima. Recent papers used tools from analysis and probability to obtain bounds on the expected value of the global optima for fixed K and large N. We present bounds when K grows with N, using ideas from graph theory, probabilistic combinatorics and order statistics. These general ideas are then applied to the analysis of the cases when underlying distributions are uniform and normal distributions.