An exact MCMC model of evolutionary computation:
sex as Gibbs sampling
April 22 2013, 4:30 PM
Evolution is a powerful learning algorithm, and it is an important scientific problem to find an explanation of how evolution is so effective. This talk will consider from first principles how to model evolution as sampling from an explicitly probability distribution, rather than as a randomised algorithm. An old approach from population genetics -- the Moran model -- is adapted to model a population as a Markov random field, so that the stationary distribution of the population can be expressed in closed form, for any fitness function. Breeding is modelled as blocked Gibbs sampling, and the sequence of populations is a reversible Markov chain that satisfies the detailed balance condition. An advantage of this approach is that the stationary distribution of the population -- or in genetic terms, the mutation-selection equilibrium -- is explicitly given, and the problem becomes to find a suitable MCMC method to sample from this distribution. Conventional genetic breeding is one possible algorithm -- but many other MCMC methods could also be used, and these also provably converge to the same stationary distribution. Some preliminary experimental results from work in progress will be presented.