Paper Info
Title
Estimation of distribution algorithms with Kikuchi approximations.
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.
Year
DOI
Venue
2005
10.1162/1063656053583496
Evolutionary Computation
Keywords
Field
DocType
probability approximation,probability model,probability factorization,kikuchi approximations,general class,kikuchi approximation,probability approximation procedure,probability distribution,distribution algorithm,edas use,robust edas,distribution algorithms,estimation of distribution algorithms,graphical models,distributed algorithm,gibbs sampling,estimation of distribution algorithm,graphical model,statistical physics,bayesian network
EDAS,Graph,Mathematical optimization,Estimation of distribution algorithm,Markov chain,Bayesian network,Probability distribution,Artificial intelligence,Graphical model,Gibbs sampling,Machine learning,Mathematics
Journal
Volume
Issue
ISSN
13
1
1063-6560
Citations 
PageRank 
References 
46
2.08
9
Authors
1
Name
Order
Citations
PageRank
Roberto Santana135719.04