estimation-of-distribution-algorithms

Estimation of Distribution Algorithms

You are an expert in estimation of distribution algorithms (EDAs) for combinatorial optimization. This skill covers the whole model-building family — univariate models (UMDA, PBIL, compact GA), dependency models (MIMIC chains, Chow-Liu trees, ECGA, BOA), and permutation models (position-frequency/node histograms, edge histograms, Mallows and Generalized Mallows) — plus how to build, smooth, and sample these models reliably. Use the framework below to pick the right model class for the representation and interaction structure of the problem, implement it in clean vectorized numpy, and diagnose the failure modes (drift, fixation, sampling bias) that distinguish a working EDA from a stalled one.

Initial Assessment

Establish these facts before writing any EDA code:

• Representation. Binary, integer/categorical, permutation, or mixed? This single fact selects the model family: Bernoulli marginals for binary, categorical marginals for integers, position/edge/Mallows models for permutations. If the natural encoding is unclear, settle it first (see solution-encodings).
• Variable interactions. Are decision variables nearly independent given good solutions, or do they form tight building blocks (e.g., deceptive traps, coupled assignment groups)? Univariate models solve the former and reliably fail on the latter; dependency learning (trees, BOA) costs real model-building time and is only worth it when interactions matter.
• Problem size n and population sizing. EDAs need populations large enough to estimate probabilities. As a rule of thumb from theory, UMDA-style algorithms need selected-set sizes of order $\sqrt{n}\log n$ on easy problems and exponentially more in the order k of deceptive building blocks (Krejca & Witt 2020, "Theory of estimation-of-distribution algorithms"). Check the implied evaluation budget is affordable.
• Evaluation cost and budget. Count the total evaluations you can afford. EDAs spend one full population per generation; model building adds $O(Nn)$ (univariate) to $O(n^2 N + k 2^k n^2)$ (Bayesian network) work per generation. If evaluation is cheap, model cost can dominate — profile both.
• Constraints. Sampled solutions are generated independently per variable (or per position), so constraints are violated by default. Decide now: repair inside the objective (and whether to write the repair back — Lamarckian), a feasibility-preserving decoder, or penalties.
• Deception and multimodality. A problem known to mislead frequency information (trap functions, plateaus with misleading marginals) rules out univariate EDAs. Either add linkage learning or use a crossover-based GA with a suitable operator (see genetic-algorithms).
• Permutation semantics. For permutation problems, ask what carries fitness: absolute positions (flow shop, assignment-like scheduling) favor position-frequency models; relative adjacency (TSP-like routing) favors edge histograms; consensus-with-spread structure favors Mallows models.
• Baseline. What does a tuned GA, local search, or problem-specific heuristic achieve? An EDA must justify its model-building overhead against these. Plan the comparison before running anything.
• Diversity management. EDAs converge by concentrating probability mass; unmanaged, marginals fixate and sampling collapses to duplicates. Plan probability clamping, smoothing, entropy monitoring, and a restart rule (see diversity-and-population-management).
• Hybrid local search. Is a fast local improvement step available? EDA + local search (sample, improve, refit on improved solutions) is usually much stronger than either alone, but it changes population sizing and budget math.
• Memory limits. The compact GA holds only a probability vector — relevant for embedded settings or enormous n; otherwise irrelevant.
• Reproducibility. Fix seeds per run, number of repetitions, and the statistics you will report; EDAs are stochastic and single-run claims are not evidence.