An Analysis of NK Landscapes: Interaction Structure, Statistical Properties, and Expected Number of Local Optima
Authors:
- 18 October 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 18 (6) , 807-818
Abstract
Simulated landscapes have been used for decades to evaluate search strategies whose goal is to find the landscape location with maximum fitness. Understanding properties of landscapes is important for understanding search difficulty. This paper presents a novel and transparent characterization of NK landscapes and derives an analytic expression representing the expected number of local optima. We prove that NK landscapes can be represented by parametric linear interaction models where model coefficients have meaningful interpretations. We derive the statistical properties of the model coefficients, providing insight into how the NK algorithm parses importance to main effects and interactions. An important insight derived from the linear model representation is that the rank of the linear model defined by the NK algorithm is correlated with the number of local optima, a strong determinant of landscape complexity, and search difficulty. We show that the maximal rank for an NK landscape is achieved through epistatic interactions that form partially balanced incomplete block designs. Finally, an analytic expression representing the expected number of local optima on the landscape is derived, providing a way to quickly compute the expected number of local optima for very large landscapes.Keywords
This publication has 18 references indexed in Scilit:
- Searching the Clinical Fitness LandscapePLOS ONE, 2012
- Global optima results for the Kauffman NK modelMathematical Programming, 2005
- On Confidence Intervals for the Number of Local OptimaLecture Notes in Computer Science, 2003
- Estimating some features of $NK$ fitness landscapesThe Annals of Applied Probability, 2002
- Combinatorial LandscapesSIAM Review, 2002
- Properties of Fitness Functions and Search Landscapes2001
- A comparison of predictive measures of problem difficulty in evolutionary algorithmsIEEE Transactions on Evolutionary Computation, 2000
- Experiments with Tuneable Fitness LandscapesLecture Notes in Computer Science, 2000
- An Experimental Design Perspective on Genetic Algorithms1995
- The NK model of rugged fitness landscapes and its application to maturation of the immune responseJournal of Theoretical Biology, 1989