Estimation of distribution algorithms
Algorithms AIMech:EstimationOfDistributionAlgorithms DRAFT
A family of population-based optimization algorithms whose central offspring-generation mechanism estimates a search distribution from selected evaluated candidates and samples new candidates from that distribution. The family leaves the distribution model, estimation rule and selection policy to concrete algorithms; it is not one fully specified optimizer.
Identity Notes & Concept Scope
Fresh identity inventory and ignored/hidden-inclusive searches at merged base 50d9a115a61f9a8d40db79fef421ce23c3409bd9 covered 739 maintained and 442 pinned AIO records. There was no normalized identity collision for the candidate probes. All ten distinct hit contents were read and identify prior leads or existing continuous-SMOTE context, not a canonical record for this identity. The scoped no-match rationale and thirteen exact AIO target assessments remain those established from the pinned source and primary method evidence. This record denotes the named family of optimization procedures that estimate a search distribution from selected candidates and resample. It is broader than original binary UMDA and distinct from a requirement to use natural-gradient NES/IGO, a particular incremental PBIL update, or any standalone probabilistic model. Specific overlapping choices in CEM or PBIL do not identify every whole algorithm with this family definition. The schema algorithm type is used with explicit family-level definition; no acronym alias is asserted.
Claims & Grounded Evidence
6 Claims
Mechanism
#selected-population-distribution-sampling
The defining variation step estimates a probability law from selected evaluated candidates and generates new candidates by sampling it. In the inspected binary procedures, evaluation and selection supply the data used by the next distribution estimate. This replaces pairwise chromosome recombination as the central offspring-generation mechanism. It does not make every method that samples candidates an estimation of distribution algorithm, or prohibit additional operators in later hybrid methods.
Mechanism
#model-structure-is-an-algorithm-choice
The distribution model determines which dependencies the fitted search law can represent. The original UMDA uses a product of univariate binary marginals, whereas the later chapter describes factorized models with conditional distributions for interacting variables. Model structure can be supplied or estimated in particular procedures. A Bayesian network, learned graph or independent-coordinate model is therefore not mandatory for the entire family.
Mechanism
#selection-and-estimation-are-distinct-choices
A selection policy determines which evaluated candidates, or their weighted population law, contribute to distribution estimation. The inspected chapter distinguishes fitness-proportionate selection from truncation and tournament selection, and separately studies Boltzmann selection. Changing that policy changes the distribution being estimated. The family does not require one universal elite fraction, fitness weighting, objective direction or treatment of ties.
Scope
#refitting-and-incremental-memory-are-distinct
Replacing binary marginals by the selected empirical frequencies and blending those frequencies with the preceding parameter vector are different update choices. Original UMDA uses the replacement rule. The 1996 paper separately describes SUMDA with p_new=p+lambda*(r-p); the later chapter discusses that blend as a PBIL update and identifies lambda=1 with the unsmoothed rule. This formula-level boundary does not identify every full PBIL implementation, with its selection and optional mutation rules, as UMDA.
Limitation
#population-theory-does-not-remove-sampling-error
An exact search-distribution recurrence and a finite run that estimates the distribution from sampled candidates are different objects. The chapter explicitly conditions its UMDA proportionate-selection equations on infinite populations and separately discusses finite-population fixation. Consequently the family abstraction supplies no universal finite population size, convergence rate or guarantee that useful values and dependencies remain represented after sampling and selection.
Scope
#family-and-concrete-optimizer-boundary
The family name denotes a construction pattern, while a runnable member must specify its candidate domain, selection rule, model and estimation rule, sampling procedure, initialization and stopping policy. The inspected sources instantiate this pattern with binary marginal procedures and discuss richer conditional models. These examples support the family identity without asserting that all members share UMDA equations, graphical-model structure, numerical behavior or optimization guarantees.
⚠️ Curated Limitations & Negative Results
- This is a named algorithm family, not one executable procedure or a claim that every stochastic optimizer is a member. The inspected method evidence is concentrated on binary search. It does not establish a universal continuous, constrained, noisy or mixed-variable implementation.
- Concrete methods can overlap under matched model, selection and update choices without being exact identities. In particular, a matching unsmoothed product-Bernoulli cross-entropy update can coincide with UMDA, while incremental PBIL with additional mutation has a different full procedure. Distribution fitting alone does not equate this family with natural evolution strategies or information-geometric optimization.
- The 1996 article expressly does not fully describe its conditional distribution algorithm. Its statement that full conditional laws determine a unique joint law requires support qualifications: laws supported only on 00 and 11 can share deterministic full conditionals while assigning different masses to the two points. This is a bounded mathematical caveat, not an independent audit or erratum of the cited Besag work.
- The later author chapter prints FDA Step 5 as a return to Step 2, bypassing the separately listed selection step. It maximizes the displayed BIC score in Section 9 but describes minimization in its conclusion. Neither a repaired FDA/LFDA implementation nor general score superiority is asserted by this family record.
- Infinite-population equations, selected finite-population examples and empirical sample-size discussions do not establish global optimization, universal preservation of dependencies, an optimal population size or superiority over other optimizers. No optimizer, author implementation or benchmark was executed for this assessment.
- The 1996 source is a ten-page author-hosted proceedings copy; its PDF build date is not its 1996 publication date. The later source is an author PostScript manuscript indexed as 2000 for a chapter published in 2001. Its 39-page reading PDF was derived after removing only a trailing MIME delimiter after the unique document EOF; the original PostScript and conversion failures remain separately retained. Publisher-byte equivalence is not established. The author webpage supports the family name, not a historical priority claim.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: The selected AIO targets describe learning tasks, particular models or mathematical components rather than this optimization family. Optional applications, graphical representations or scalar formulas do not justify a forced mapping. This no-match applies only to the inspected snapshot and targets.
Search Scope: On 2026-10-15, the fresh merged-base inventory covered all 739 maintained and 442 pinned AIO identities, with IDs, names, aliases and scoped synonyms; the 31 exact/related probes had no normalized identity collision. Four full-checkout fixed-string word searches included ignored and hidden files and produced 280, 283, 787 and 829 occurrences, representing ten distinct matching contents. Root read all ten complete content strings, the collection and selected owner context; exact reconstruction accounts for all 2179 occurrences, without claiming individual manual reading of every duplicate line. Hits are existing candidate leads and the continuous-SMOTE record or its derived historical representations, not existing records for these three identities. The earlier research separately inspected 159 selected semantic definitions and four full optimizer neighbors, and thirteen exact AIO CLASS nodes with all 47 incident edges; root additionally read selected identity, definition, claim and limitation fields of PBIL, cross-entropy optimization, NES, IGO and continuous SMOTE. This is bounded snapshot and neighborhood evidence, not exhaustive equivalence testing across all possible methods or ontologies.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:EvolutionaryLLM
|
The exact class is an evolutionary large language model; its related evolutionary-algorithms synonym is not an exact/broad identity for general distribution-based optimization. |
AIO:TrainingStrategy
|
General objective search need not preprocess or train a machine-learning model. |
AIO:MachineLearningTask
|
Fitting search distributions is an internal optimization operation; the general optimizer is not identified with the pinned task of building methods that learn from data. |
AIO:MetaLearning
|
Neither family nor UMDA inherently learns from metadata about machine-learning experiments. |
AIO:ActiveLearning
|
Evaluating black-box objective values is not necessarily querying labels for data points. |
AIO:ReinforcementLearning
|
A policy/environment learning problem is not required; an application to it would not identify the general optimizer. |
AIO:RandomForest
|
Regression trees are mentioned only in the incompletely specified CDA extension; no predictive tree ensemble is required by the family or UMDA. |
AIO:ContinualLearning
|
The target is a deep network learning sequential tasks without forgetting, not updating a search distribution. |
AIO:MarkovChain
|
An optional stochastic-state representation does not ground the optimization identity in the target network/model or make it a target-invariant Monte Carlo sampler. |
AIO:MathematicalFunction
|
The concepts are iterative selection/model-estimation/sampling procedures, not a stand-alone mathematical function or covariance/acquisition component; the generic availability of a formula is insufficient. |
AIO:BayesianNetwork
|
FDA/LFDA use graphical representations, and a product law may be represented by an edgeless network, but this does not make the general optimization family or whole UMDA algorithm a Bayesian network. |
AIO:ProbabilisticGraphicalModel
|
The pinned graph-expressed conditional-dependence task is optional model structure, not the whole optimizer; an explicit graph is not a mandatory mechanism of UMDA. |
AIO:ExponentialFunction
|
Boltzmann selection is one studied policy; exponential weighting or scalar exponential adaptation is not mandatory for the family or UMDA. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
muhlenbein1996
|
Heinz Mühlenbein, Gerhard Paaß
|
primary paper
full_text
|
ID: https://doi.org/10.1007/3-540-61723-X_982
sha256:4834a0d8e4de…
|
muhlenbein-mahnig-chapter
|
Heinz Mühlenbein, Thilo Mahnig
|
author technical report
full_text
|
ID: https://doi.org/10.1007/978-3-662-04448-3_7
sha256:078e7787fb89…
|
muhlenbein-author-index
|
Heinz Mühlenbein
|
official documentation
documentation
|
sha256:11749b4ab415…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-15T07:33:19Z
Updated: 2026-10-15T07:33:19Z
Source File:
data/curated/EstimationOfDistributionAlgorithms.yaml