View article

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 …