Abstract: |
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. |
