Santana Roberto
Institute of Cybernetics, Mathematics, and Physics, Calle 15, e/ C y D, Vedado, Cp-10400 Havana, Cuba.
Evol Comput. 2005 Spring;13(1):67-97. doi: 10.1162/1063656053583496.
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.
寻找估计概率分布的可行方法这一问题是分布估计算法（EDA）面临的主要挑战之一。为了估计所选解的分布，EDA 使用根据图形模型构建的因式分解。从这些概率模型中可获得的因式分解类别受到高度限制。扩展可用于概率近似的因式分解类别是构思更强大的 EDA 的必要步骤。在本文中，我们介绍一种学习更一般概率因式分解类别的方法。该方法将统计物理学中已知的作为能量的菊池近似的概率近似过程的重新表述，与一种寻找图分解的新方法相结合。我们提出了马尔可夫网络分布估计算法（MN - EDA），这是一种使用菊池近似来估计分布，并使用吉布斯采样（GS）生成新点的 EDA。与不同的基于贝叶斯网络的 EDA 相比，对 MN - EDA 进行了系统的实证评估。从我们的实验中我们得出结论，在优化变量之间具有强相互作用的函数时，该算法可以优于其他使用传统概率近似方法的 EDA。
