AI Glossary / AI and machine learning / Advanced
Estimation of distribution algorithm
Definition
An estimation of distribution algorithm, or EDA, is an optimization method that learns a probability model of promising candidate solutions and samples that model to generate new candidates. It repeatedly evaluates, selects, models and samples as the search proceeds.
What it means
Many optimization problems involve combinations: which settings to choose, which features to include or how to arrange a schedule. Searching every combination may be impractical.
An EDA starts with a collection of candidates and uses the better-performing ones to learn patterns about promising choices. It then generates new candidates using a probability distribution informed by those patterns.
This differs from a basic genetic-algorithm description in which selected candidates are recombined and mutated directly. In an EDA, an explicit probabilistic model plays the central role in creating new search points.
The distribution is a search aid, not a guarantee that sampled candidates are good. It reflects what the algorithm has observed so far, and early sampling can miss important parts of the solution space.
How it works
The designer defines a candidate representation, an objective and any constraints. The algorithm samples or constructs an initial population and evaluates each candidate.
A selection rule identifies promising candidates. The algorithm fits a probability model to them, ranging from simple independent probabilities for each variable to models that capture dependencies between choices.
New candidates are sampled from that model, checked for feasibility and evaluated. The process repeats until a budget, convergence rule or other stopping condition is reached.
Maintaining exploration matters. If probabilities become concentrated too early, the algorithm may repeatedly sample variations of a merely adequate solution. Population size, model complexity and update rules influence that trade-off.
Three practical examples
- Feature selection: search combinations of input features while evaluating predictive performance and the cost of collecting them.
- Scheduling experiments: generate candidate assignments and score them against timing, resource and feasibility requirements.
- Engineering design: explore combinations of design variables when a simulation or calculation can score each candidate.
Think of it this way
Think of a chef studying several successful recipes, learning which ingredients tend to work together, then creating new recipes from that pattern. The next generation is guided by a learned distribution of choices.
The analogy has a limit. Good ingredients can fail in a bad combination. A model that treats choices independently may miss essential relationships, and every new candidate still needs evaluation.
Worked example
Learning a simple distribution over choices
Suppose a fictional design problem has three on-off settings. After evaluating an initial population, the algorithm selects ten promising designs. Setting A is on in eight, B in six and C in two.
A simple independent model could use probabilities 0.8, 0.6 and 0.2 for switching those settings on when sampling the next population. This makes some combinations more likely without declaring any one combination optimal.
In a separate version of the problem, suppose A and B work well only when exactly one is on. Five selected designs use A alone and five use B alone. Independent probabilities of 0.5 for each setting would still generate both-on and both-off combinations, each with probability 0.25. A more suitable model or representation may be needed to preserve the useful relationship.
The counts are invented. They illustrate why learning a probability for each setting is different from learning how settings interact, and why candidate evaluation remains essential.
Illustrative case study
A fictional analytics team uses an EDA to select features for a prediction model. It repeatedly scores candidate subsets on the same validation sample and obtains an impressive final result.
A later evaluation reveals that extensive search has overfit that sample. The team separates search feedback from final assessment and includes the cost of collecting selected features in the objective.
The invented lesson is that optimization can exploit weaknesses in an evaluation setup. A more effective search does not make an unreliable score more trustworthy; it may make the exploitation more thorough.
Common misconceptions and mistakes
- The learned distribution describes how the real world generates data. It may instead describe promising solutions within an optimization search.
- Sampling guarantees a globally optimal answer. Finite searches can miss better solutions or concentrate prematurely.
- Independent variable probabilities always suffice. Important interactions may require a richer model, with additional data and computational cost.
Business use
EDAs are specialist tools for difficult search and optimization problems. They are most useful when candidate solutions can be represented, scored and checked against constraints in a repeatable way.
Ask how many evaluations are affordable, how feasibility is enforced and how the result compares with simpler search methods. If scoring a candidate is expensive, the evaluation budget can matter more than the elegance of the sampling model.
People also ask
Is an EDA a generative AI chatbot?
No. It generates candidate solutions from a search distribution, not necessarily language or media.
Can it handle continuous variables?
Yes. The candidate representation and probability model can be designed for discrete, continuous or mixed variables.
Does it always replace every genetic operator?
The basic idea emphasizes model learning and sampling, but hybrid methods can combine mechanisms.
Check your understanding
Why can probabilities for individual settings fail when two settings only work well in a particular combination?
Answer: Separate probabilities do not represent their dependency. Sampling independently can create combinations that were not responsible for the good observed results.
Related terms
Learn next
Read optimization and Feature Selection. Define the candidate, scoring rule, constraints and untouched final evaluation before comparing search algorithms.
More in AI and machine learning
- Epistemic modal logic - Epistemic modal logic is a formal system for reasoning about knowledge, including what one agent knows about the world and about other agents' knowledge.
- Epoch - An epoch is one complete pass through the entire training dataset during a model's training; training usually runs for many epochs.
- Error-driven learning - Error-driven learning adjusts a model using a discrepancy between its output and a desired or observed outcome.
- Evaluation of binary classifiers - Evaluation of binary classifiers measures how well a system distinguishes between two outcome classes.
- Evolutionary acquisition of neural topologies - Evolutionary acquisition of neural topologies, usually shortened to EANT, is a neuroevolution method that searches for both a neural network's structure and...
- Evolutionary developmental robotics - Evolutionary developmental robotics studies robot design and behavior by combining evolutionary search across generations with development within a robot's...
Sources
Larrañaga and Lozano, Estimation of Distribution Algorithms: https://link.springer.com/book/10.1007/978-1-4615-1539-5. Krejca and Witt, Theory of Estimation-of-Distribution Algorithms: https://arxiv.org/abs/1806.05392. Summaries consulted 12 October 2026. Editorial review on 14 October 2026 additionally consulted sections 2 and 2.2 of Krejca and Witt for model-based sampling and the distinction between independent and dependency-aware models. Examples are original illustrations.
Previous: Estimation error Next: Eta squared ( h 2 )