Approximate factorizations of distributions and the minimum relative entropy principle

Estimation of Distribution Algorithms (EDA) have been proposed as an extension of genetic algorithms. In this paper the major design issues of EDA's are discussed within a general interdisciplinary framework, the maximum entropy approximation. Our EDA algorithm FDA assumes that the function to be optimized is additively decomposed (ADF). The interaction graph G ADF is used to create exact or approximate factorizations of the Boltzmann distribution. The relation between FDA factorizations and the MaxEnt solution is shown. We introduce a second algorithm, derived from the Bethe-Kikuchi approach developed in statistical physics. It tries to minimize the Kullback-Leibler divergence KLD(q\pβ) to the Boltzmann distribution pβ by solving a difficult constrained optimization problem. We present in detail the concave-convex minimization algorithm CCCP to solve the optimization problem. The two algorithms are compared using popular benchmark problems (2-d grid problems, 2-d Ising spin glasses, Kaufman's n — k function.) We use instances up to 900 variables.