Analysis of adaptive walks on NK fitness landscapes with different interaction schemes

Abstract

Fitness landscapes are genotype to fitness mappings commonly used in evolutionary biology and computer science which are closely related to spin glass models. In this paper, we study the NK model for fitness landscapes where the interaction scheme between genes can be explicitly defined. The focus is on how this scheme influences the overall shape of the landscape. Our main tool for the analysis are adaptive walks, an idealized dynamics by which the population moves uphill in fitness and terminates at a local fitness maximum. We use three different types of walks and investigate how their length (the number of steps required to reach a local peak) and height (the fitness at the endpoint of the walk) depend on the dimensionality and structure of the landscape. We find that the distribution of local maxima over the landscape is particularly sensitive to the choice of interaction pattern. Most quantities that we measure are simply correlated to the rank of the scheme, which is equal to the number of nonzero coefficients in the expansion of the fitness landscape in terms of Walsh functions.

arXiv comment29 pages, 9 figures

References in corpus (12)

• Quantitative analyses of empirical fitness landscapes
• Evolutionary accessibility of mutational pathways
• Adaptation in tunably rugged fitness landscapes: The Rough Mount Fuji Model
• Exact Results for Amplitude Spectra of Fitness Landscapes
• Adaptive walks and extreme value theory
• Evolutionary accessibility of modular fitness landscapes
• Optimal adaptive performance and delocalization in NK fitness landscapes
• Evolutionary accessibility in tunably rugged fitness landscapes
• More rigorous results on the Kauffman-Levin model of evolution
• Accessibility percolation on n-trees
• Number of adaptive steps to a local fitness peak
• Energy-Decreasing Dynamics in Mean-Field Spin Models

Cited by in corpus (7)

• Universality classes of interaction structures for NK fitness landscapes
• Greedy adaptive walks on a correlated fitness landscape
• From Adaptive Dynamics to Adaptive Walks
• Distribution of the number of fitness maxima in Fisher's Geometric Model
• Impact of population size on early adaptation in rugged fitness landscapes
• The surprising little effectiveness of cooperative algorithms in parallel problem solving
• Getting higher on rugged landscapes: Inversion mutations open access to fitter adaptive peaks in NK fitness landscapes