Algorithmic Perspectives on Evolution
Dr. Per Kristian Lehre, University of Birmingham, UK

To the main page

Evolution, repeated selection, and variation of the genetic material in a population has fascinated computer scientists for decades. Evolutionary algorithms are used to find practical solutions to hard combinatorial optimisation problems. However, there is also an increasing interest in understanding the fundamental algorithmic properties of evolution. When can we say that an evolutionary process is an efficient algorithm, i.e., discovers a solution with prescribed quality in expected polynomial time?

This talk starts by contrasting classical theoretical models of evolution from population genetics, with algorithmic models of evolution arising from theoretical computer science. We will describe analytical techniques which provide estimates on the time-complexity of evolutionary algorithms, i.e., the "speed" of evolution. These results show how the optimisation time depends both on evolutionary model parameters (such as population size, mutation rates, and selective pressure), and characteristics of the optimisation problem (e.g., noise and deceptiveness).