Rugged NK landscapes contain the highest peaks

NK models provide a family of tunably rugged fitness landscapes used in a wide range of evolutionary computation studies. It is well known that the average height of local optima regresses to the mean of the landscape with increasing ruggedness, K. This fact has been confirmed with both theoretical studies of landscape structure and empirical studies of evolutionary search. However, we show mathematically that the global optimum behaves quite differently: the expected value of the global optimum is highest in the maximally rugged case. Furthermore, we demonstrate that this expected value increases with K, despite the fact that the average fitness of the local optima decreases. We find the asymptotic value of the global optimum as N approaches infinity for both the smooth and maximally rugged cases. We interpret these results in the context of evolutionary search, and describe the relationship between the global optimum, local optima and found optima as search effort is geometrically increased