期刊
EVOLUTIONARY COMPUTATION
卷 13, 期 1, 页码 125-143出版社
MIT PRESS
DOI: 10.1162/1063656053583423
关键词
estimation of distribution algorithms; space complexity; additive fitness functions; graphical models and bayesian networks; treewidth
In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据