Hierarchical Distribution of Ascending Slopes, Nearly Neutral Networks, Highlands, and Local Optima at the d-th order in an NK Fitness Landscape

We obtained several structural features of an NK fitness landscape by analytical approach. Particularly, we focused on spatial distributions of "ascending slopes", "highlands", "nearly neutral networks", and "local optima" along the fitness coordinate W, from the viewpoint of adaptive walks with step-width d, where d is the number of mutated sites (Hamming distance) after a generation. The parameter k governs the degree of the ruggedness on the NK landscape, and we handled cases where k is moderate against the sequence length. From the foot LIP to the middle region on the landscape, many ascending slopes exist (high evolvability) and these slopes extend up near the "highland", which is mathematically defined as the specific region W = W-d* where the expectation of the fitness increment becomes zero. Denoting the standard deviation of the fitness change at W = W-d*; by SD*, we considered the existence of "nearly neutral networks", which percolate in the fitness band between W - SD* and W + SD*. Our results suggest that the highland corresponds to a phase-transition threshold of the formation of the nearly neutral networks. Near or over the highland, "local optima at the dth order" appear drastically (low evolvability), where d means the radius of their basins. The value of W-d* increases with d increasing. Then, as the fitness ( altitude) becomes higher, the basin size of the local optima increases. This leads to a conclusion that it is very hard or impossible for walkers with step-width d to reach near the global peak when d is a realistic large value: d = 1-6, and suggests that the region over the middle in real landscapes may be considerably smooth with small k-values to maintain high evolvability. (C) 2008 Elsevier Ltd. All rights reserved