Convergence theorems of estimation of distribution algorithms

Estimation of Distribution Algorithms (EDAs) have been proposed as an extension of genetic algorithms.We assume that the function to be optimized is additively decomposed (ADF). The interaction graph of the ADF function is used to create exact or approximate factorizations of the Boltzmann distribution. Convergence of the algorithmMN-GIBBS is proven.MN-GIBBS uses a Markov network easily derived from the ADF and Gibbs sampling. We discuss different variants of Gibbs sampling. We show that a good approximation of the true distribution is not necessary, it suffices to use a factorization where the global optima have a large enough probability. This explains the success of EDAs in practical applications using Bayesian networks.