Journal
EVOLUTIONARY COMPUTATION
Volume 13, Issue 1, Pages 125-143Publisher
MIT PRESS
DOI: 10.1162/1063656053583423
Keywords
estimation of distribution algorithms; space complexity; additive fitness functions; graphical models and bayesian networks; treewidth
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available