Booth Id:
MATH027
Category:
Mathematics
Year:
2025
Finalist Names:
Liu, Dale (School: Lynbrook High School)
Abstract:
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.
Awards Won: