Towards a general theory of adaptive walks on rugged landscapes

Adaptive evolution, to a large extent, is a complex combinatorial optimization process. In this article we take beginning steps towards developing a general theory of adaptive "walks" via fitter variants in such optimization processes. We introduce the basic idea of a space of entities, each a 1-mutant neighbor of many other entities in the space, and the idea of a fitness ascribed to each entity. Adaptive walks proceed from an initial entity, via fitter neighbors, to locally or globally optimal entities that are fitter than their neighbors. We develop a general theory for the number of local optima, lengths of adaptive walks, and the number of alternative local optima accessible from any given initial entity, for the baseline case of an uncorrelated fitness landscape. Most fitness landscapes are correlated, however. Therefore we develop parts of a universal theory of adaptation on correlated landscapes by adaptive processes that have sufficient numbers of mutations per individual to "jump beyond" the correlation lengths in the underlying landscape. In addition, we explore the statistical character of adaptive walks in two independent complex combinatorial optimization problems, that of evolving a specific cell type in model genetic networks, and that of finding good solutions to the traveling salesman problem. Surprisingly, both show similar statistical features, encouraging the hope that a general theory for adaptive walks on correlated and uncorrelated landscapes can be found. In the final section we explore two limits to the efficacy of selection. The first is new, and surprising: for a wide class of systems, as the complexity of the entities under selection increases, the local optima that are attainable fall progressively closer to the mean properties of the underlying space of entities. This may imply that complex biological systems, such as genetic regulatory systems, are "close" to the mean properties of the ensemble of genomic regulatory systems explored by evolution. The second limit shows that with increasing complexity and a fixed mutation rate, selection often becomes unable to pull an adapting population to those local optima to which connected adaptive walks via fitter variants exist. These beginning steps in theory development are applied to maturation of the immune response, and to the problem of radiation and stasis. Despite the limitations of the adaptive landscape metaphor, we believe that further development along the lines begun here will prove useful.