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 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 …