On the Fitness Landscape in the NK Model

The NK model, introduced by Kauffman, Levin, and Weinberger, is a random field used to describe the fitness landscape of certain species with N genetic loci, each interacting with K others. The model has wide applications in understanding evolutionary and natural selection as it captures ruggedness feature of the fitness landscape. Earlier literature has been focused on the case K being a fixed positive integer and used tools from Ergodic and Markov theory. In this paper, by viewing it as a statistical physics object, we investigate the NK model in the regime K/Nα (0, 1] via the spin glass methodologies. Our main result identifies the exact limits for the free energy at any temperature and the maximum fitness. Moreover, we show that the NK model exhibits a multiple-peak structure, namely, the number of near-fittest genomes that are asymptotically orthogonal to each other is exponentially large. Based on establishing the overlap gap properties, we obtain quantitative descriptions for the geometry of the fitness landscape and deduce that, in particular, near-fittest evolutionary paths become impossible as the fitness levels of the genomes approach the global maximum for any α (0, 1]. Nevertheless, we also show that by choosing α sufficiently small, an evolutionary path maintained at a given fitness level can be constructed with high probability.