Estimation of Distribution Algorithms with Kikuchi Approximations
- 1 March 2005
- journal article
- Published by MIT Press in Evolutionary Computation
- Vol. 13 (1), 67-97
- https://doi.org/10.1162/1063656053583496
Abstract
The question of finding feasible ways for estimating probability distributions is one of the main challenges for Estimation of Distribution Algorithms (EDAs). To estimate the distribution of the selected solutions, EDAs use factorizations constructed according to graphical models. The class of factorizations that can be obtained from these probability models is highly constrained. Expanding the class of factorizations that could be employed for probability approximation is a necessary step for the conception of more robust EDAs. In this paper we introduce a method for learning a more general class of probability factorizations. The method combines a reformulation of a probability approximation procedure known in statistical physics as the Kikuchi approximation of energy, with a novel approach for finding graph decompositions. We present the Markov Network Estimation of Distribution Algorithm (MN-EDA), an EDA that uses Kikuchi approximations to estimate the distribution, and Gibbs Sampling (GS) to generate new points. A systematic empirical evaluation of MN-EDA is done in comparison with different Bayesian network based EDAs. From our experiments we conclude that the algorithm can outperform other EDAs that use traditional methods of probability approximation in the optimization of functions with strong interactions among their variables.Keywords
This publication has 7 references indexed in Scilit:
- 10.1162/153244301753344614Applied Physics Letters, 2000
- Schemata, Distributions and Graphical Models in Evolutionary OptimizationJournal of Heuristics, 1999
- The Equation for Response to Selection and Its Use for PredictionEvolutionary Computation, 1997
- Formal Structure of the Cluster Variation MethodProgress of Theoretical Physics Supplement, 1994
- Optimization by Simulated AnnealingScience, 1983
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973
- A Theory of Cooperative PhenomenaPhysical Review B, 1951