The factorized distribution algorithm 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 using an interdisciplinary framework, the minimum relative entropy (MinRel) approximation. We assume that the function to be optimized is additively decomposed (ADF). The interaction graph GADF of the ADF is used to create exact or approximate factorizations of the Boltzmann distribution. The relation between the Factorized distribution algorithm (FDA) and the MinRel approximation is shown. We present a new algorithm, derived from the Bethe-Kikuchi approach developed in statistical physics. It minimizes the relative entropy 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.