Evolutionary Optimization and the Estimation of Search Distributions with Applications to Graph Bipartitioning

We present a theory of population based optimization methods using approximations of search distributions. We prove convergence of the search distribution to the global optima for the Factorized Distribution Algorithm FDA if the search distribution is a Boltzmann distribution and the size of the population is large enough. Convergence is defined in a strong sense -- the global optima are attractors of a dynamical system describing mathematically the algorithm. We investigate an adaptive annealing schedule and show its similarity to truncation selection. The inverse temperature beta is changed inversely proportionally to the standard deviation of the population. We extend FDA by using a Bayesian hyper parameter. The hyper parameter is related to mutation in evolutionary algorithms. We derive an upper bound on the hyper parameter to ensure that FDA still generates the optima with high probability. We discuss the relation of the FDA approach to methods used in statistical physics to approximate a Boltzmann distribution and to belief propagation in probabilistic reasoning. In the last part, we apply the algorithm to an important practical problem, the bipartioning of large graphs. We assume that the graphs are sparsely connected. Our empirical results are as good or even better than any other method used for this problem