Evolutionary Algorithms and the Boltzmann Distribution.
Heinz Mühlenbein, Thilo Mahnig · 2002
We perform a stochastic analysis of evolutionary algorithms. The analysis centers on the question how to efficiently compute probabilities of promising alleles derived from evolving populations under selection and how to use these probabilities to generate new points. We shortly discuss the Univariate Marginal Distribution Algorithm (UMDA). It uses univariate marginals to generate new search points. We extend UMDA to the Factorized Distribution Algorithm (FDA) which uses a factorization of the Boltzmann distribution. We describe a well known algorithm to compute a factorization based on junction trees. We explain the sampling method of FDA and discuss the difference to Simulated Annealing. We introduce mutation into the algorithm with the help of a Bayesian hyper parameter. We show that FDA using Boltzmann selection fulfills an equation which Holland claimed to be necessary for an almost "optimal" algorithm. We formulate FDA as a population dynamics algorithm. We conclude with a short discussion about the interdisciplinary research to approximate distributions, especially the Boltzmann distribution.