Gao Yong, Culberson Joseph
Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8.
Evol Comput. 2005 Spring;13(1):125-43. doi: 10.1162/1063656053583423.
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.
在本文中，我们研究分布估计算法（EDAs）的空间复杂度，它是遗传算法的一类基于采样的变体。通过分析EDAs的本质，我们确定了表征EDAs两种典型实现方案（因式分解分布算法和基于贝叶斯网络的算法）空间复杂度的标准。以随机加性函数作为原型，我们证明即使优化问题具有非常稀疏的交互结构，因式分解分布算法和基于贝叶斯网络的算法的空间复杂度在问题规模上也是指数级的。
