Estimation of Distribution Algorithm

Some problems cannot simply be computed through — there are too many possible solutions. In such cases, one is not looking for the one correct answer, but for the best one out of a vast set. An Estimation of Distribution Algorithm, or EDA for short, is a method that does exactly that. It generates many candidate solutions, selects the best ones among them, and learns from them what a good solution looks like. It expresses this knowledge as a probability distribution — a description of which features frequently occur in good solutions. It then draws new candidates from this distribution that are, on average, even better.

EDAs as an answer to the limits of classical search algorithms

Many classical optimization methods, such as genetic algorithms, improve solutions through small random changes — similar to biological mutations. This works well when the individual parts of a solution are independent of one another. But as soon as dependencies exist, this approach often fails. If, for example, two features are only good in combination but useless on their own, a random mutation can easily destroy exactly the combination that would have been valuable.

EDAs sidestep this problem. Instead of mutating blindly, they learn the structure of the problem. The probability model captures which features belong together — and generates new solutions that respect these dependencies from the outset. This makes EDAs particularly powerful for problems in which many variables are interlinked.

From the first candidates to a learned distribution

An EDA operates in a loop. In the first step, it generates a starting set of random solutions. Then it evaluates each one: how good is it? Next, it keeps only the best ones — say, the top quarter. From these survivors, it estimates a statistical model: which features do the good solutions have in common, which ones tend to occur together? This model is not a fixed formula, but a learnable probability distribution.

In the next step, the algorithm draws a new generation of candidates from this distribution. Features that were common among the good solutions are passed on with a higher probability. The loop then starts over: evaluate, select, update the model, draw new candidates. After many rounds, the model converges toward a distribution from which almost only very good solutions originate.

Exactly how the model captures the dependencies depends on the chosen type of EDA. Simple variants assume that all features are independent — this saves computation time but is imprecise. More advanced variants, such as the Bayesian Optimization Algorithm (BOA), explicitly learn which features are related to one another and build a network of conditional probabilities for this purpose.

EDAs in practice, research, and related fields

EDAs turn up wherever optimization problems with many interlinked variables need to be solved. In logistics, they help plan routes or production processes. In bioinformatics, they search for optimal gene combinations. In engineering, they support the design of components in which many parameters must be coordinated with one another simultaneously.

In the field of machine learning, EDAs are closely related to the area of hyperparameter optimization — that is, the search for the best settings for an AI model. Well-known libraries such as Google's Vizier or the open-source tool Optuna employ related ideas: based on past trials, they estimate where worthwhile settings are likely to be found and derive new trials from that.

A common misconception is confusing EDAs with pure genetic algorithms. Both work with populations of solutions and select the best ones. But while genetic algorithms directly cross and mutate these, EDAs discard the solutions themselves and retain only the learned model. The difference is fundamental: it is not the solutions that get passed on, but the knowledge about their structure.