A Theoretical Correction for the Properties of NK Fitness Landscapes and Extension of the Model to K Random Interactions
ISEF · 2025 Mathematics
Overview
How likely is it that we are one of the luckiest among many evolutionary possibilities? The NK model, a mathematical exemplar describing Wright's fitness landscapes, has provided great insights into such questions. However, a version developed by one of its early inventors contains an inaccuracy in estimating the number of local optima. Researching its correct properties is crucial for understanding the distribution of local optima in genetic networks, energy states in spin glasses, or solutions in the NP-complete combinatorial optimization like the traveling salesman problem. In this work, a closed-form formula is developed to improve upon the estimate of the probability of a random sequence being at a local optimum, along with the expected number of local optima in an NK fitness landscape. A multivariable approach is used to examine this probability. The problem is then reformulated into estimating a target function, mapping the K adjacent-neighbor interactions to a Hessian matrix, proving its positive definiteness, and solving for its eigenvalues. This framework also allows us to further extend the model to K random-neighbor interactions. To validate the new estimates, a simulation program is developed and run in parallel on a computing cluster, generating random fitness landscapes with fixed K, varying N, and vice versa. Each landscape is exhaustively searched for all the local optima. Comparative simulations between adjacent and random-neighbor models are also performed. The old model underestimates the actual number of local optima. The new estimate achieves an MAPE below 10% in most of the tests and outperforms the old model's MAPE of 40%. The presence of more local optima in fitness landscapes suggests that we are luckier than previously believed.
Competition history
- ISEF 2025
Resources
Related projects
ISEF · 2018
Modeling the Emergence of Epistatic Gene Combinations as a Phenotypic Function of Evolution
ISEF · 2018
A Characterization of n-way Fitness Graphs that Imply n-way Epistasis
ISEF · 2021
Entropy in Evolutionary Algorithms - Statistical Mechanics Bearing Insight into Evolution
CWSF · 2026
EvoNash: Accelerating Convergence to Nash Equilibrium
Closest projects by meaning, across every fair and year in the corpus.
Source: Regeneron International Science and Engineering Fair