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.
