Speaker
Prof.
Chris Watkins
(Royal Holloway)
Description
Evolution by natural selection is a learning algorithm of
remarkable power. We propose a simple, general abstract
model of evolution for which the mutation-selection
equilibrium can be given in closed form for arbitrary
fitness functions. The model is a modification of the Moran
process for evolution with overlapping generations.
Computational models of evolution -- such as genetic algorithms -- are usually specified as processes, in which breeding with recombination, mutation, and selection is repeatedly applied to produce a sequence of populations: this sequence of populations is a Markov chain, and the stationary distribution of this Markov chain is the mutation-selection equilibrium distribution over populations. Unfortunately, these Markov chains are typically not easy to analyse because they do not satisfy the detailed balance condition and their stationary distributions do not in general have a simple closed form.
In contrast, we specify a probability model explicitly by considering the population of genomes as a Markov random field. We then observe that a standard Markov chain Monte Carlo (MCMC) sampling method -- blocked Gibbs sampling within Metropolis Hastings -- can naturally be regarded as a genetic algorithm. The Markov chain of populations satisfies detailed balance. Although this result is rather simple, we have so far been unable to find it in the literature.
The implications seem quite deep. The stationary distribution factorises as the product of two terms: the first term is the probability of generating the population by pure genetic drift with no selection; the second term is the product of the fitnesses of the genomes. This expression is analogous to that for a Bayesian posterior distribution, and a population in equilibrium is analogous to a sample from a Bayes posterior distribution.
A practical computational consequence is that for evolutionary simulations, it is possible to apply alternative MCMC sampling methods to achieve faster convergence to the same stationary distribution. In other words, one can do 'evolution' with non-biological sampling methods that may be much faster for some interesting cases.
Computational models of evolution -- such as genetic algorithms -- are usually specified as processes, in which breeding with recombination, mutation, and selection is repeatedly applied to produce a sequence of populations: this sequence of populations is a Markov chain, and the stationary distribution of this Markov chain is the mutation-selection equilibrium distribution over populations. Unfortunately, these Markov chains are typically not easy to analyse because they do not satisfy the detailed balance condition and their stationary distributions do not in general have a simple closed form.
In contrast, we specify a probability model explicitly by considering the population of genomes as a Markov random field. We then observe that a standard Markov chain Monte Carlo (MCMC) sampling method -- blocked Gibbs sampling within Metropolis Hastings -- can naturally be regarded as a genetic algorithm. The Markov chain of populations satisfies detailed balance. Although this result is rather simple, we have so far been unable to find it in the literature.
The implications seem quite deep. The stationary distribution factorises as the product of two terms: the first term is the probability of generating the population by pure genetic drift with no selection; the second term is the product of the fitnesses of the genomes. This expression is analogous to that for a Bayesian posterior distribution, and a population in equilibrium is analogous to a sample from a Bayes posterior distribution.
A practical computational consequence is that for evolutionary simulations, it is possible to apply alternative MCMC sampling methods to achieve faster convergence to the same stationary distribution. In other words, one can do 'evolution' with non-biological sampling methods that may be much faster for some interesting cases.
Primary author
Prof.
Chris Watkins
(Royal Holloway)
