The goal of this project is to investigate connections between algorithms from evolutionary computation and models of adaptation in population genetics. Evolutionary algorithms are computer programs inspired by biological evolution that can be used for optimizing functions. These techniques rely on selection and varation operators to search a large space of potential solutions to complicated optimization problems.
In the last decades, many tools have been developed for analyzing these kinds of algorithms from both an empirical and theoretical perspective. Recently, a surprising connection was made between the field of population genetics, which studies models of evolving populations, and simple evolutionary algorithms. This connection is a promising avenue for studying adaptation from a computational perspective. In the Fisherian view of adaptation, most of the process can be described as a simple climb toward an optimum, and there always exists some beneficial variation in which to select. From an optimization standpoint, this corresponds to an easy unimodal function. A competing view is that a crucial part of adaptation is to overcome deleterious combinations of genes (called fitness valleys), and adaptation is a more complicated process in which the forces of mutation, selection, drift and migration allow adaptation to explore peaks separated by fitness valleys. These two competing views are 90 years old, but have still not been completely reconciled or refined. The shifting-balance process consists of a set of evolving sub-populations (demes), and is divided into three phases. In the first phase, genetic drift drives sub-populations towards fitness valleys. In the second phase, selection pushes populations up toward potentially different fitness peaks. Finally, the third phase consists of migration driving the fittest populations to colonize demes of lower fitness. In this scenario, the sets of sub-populations take on different cooperative roles for navigating rugged fitness landscapes. This project will study the shifting-balance process (and eventually other models) from an algorithmic perspective. Adaptation in a rugged fitness landscape is similar to a stochastic optimization process, and these researchers are interested in learning how results from evolutionary computation might translate to a better understanding of adaptation. The main part of this work is theoretical, but the group is designing simulations to run on MSI's machines to study particular parameters of the model, and to determine interesting rugged fitness landscapes to investigate.