EVOLUTION IN A RUGGED FITNESS LANDSCAPE

Kauffman's NK model for genetic evolution and adaption is analyzed for K = N - 1. In this case it describes adaptive walks on random fitness landscapes, and its dynamics is equivalent to the Metropolis algorithm for Derrida's random-energy model at zero temperature. We derive analytical expressions for the average length and duration of adaptive walks, and for the variance about these averages. The results are exact to leading order in N, the number of genes. We also find that the lengths of walks are Poisson distributed to leading order in 1/ln N, and that the duration of walks essentially is exponentially distributed to leading order in l/N.