Related Experiment Video
Updated: Jul 10, 2026

Quantification of Information Encoded by Gene Expression Levels During Lifespan Modulation Under Broad-range Dietary Restriction in C. elegans
Published on: August 16, 2017
Space complexity of estimation of distribution algorithms
1Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8. ygao@cs.ualberta.ca
Abstract:
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.
Related Concept Videos
Probability Distributions
A discrete probability distribution is a probability distribution of discrete random variables. It can be categorized into binomial probability distribution and Poisson probability...
Sampling Distribution
Distributions to Estimate Population Parameter
Choosing Between z and t Distribution
One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
On...
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...

