Theory of Estimation-of-Distribution Algorithms

Estimation-of-distribution algorithms (EDAs) are general metaheuristics used in optimization that represent a more recent alternative to classical approaches such as evolutionary algorithms. In a nutshell, EDAs typically do not directly evolve populations of search points but build probabilistic models of promising solutions by repeatedly sampling and selecting points from the underlying search space. Recently, significant progress has been made in the theoretical understanding of EDAs. This chapter provides an up-to-date overview of the most commonly analyzed EDAs and the most recent theoretical results in this area. In particular, emphasis is put on the runtime analysis of simple univariate EDAs, including a description of typical benchmark functions and tools for the analysis. Along the way, open problems and directions for future research are described.

Authors and Affiliations

1. Hasso Plattner Institute, University of Potsdam, Potsdam, Germany

   Martin S. Krejca

2. DTU Compute, Technical University of Denmark, Kgs. Lyngby, Denmark

   Carsten Witt

Corresponding author

Correspondence to Martin S. Krejca .

Editors and Affiliations

1. Laboratoire d'Informatique (LIX) - UMR 7161, École Polytechnique, Palaiseau, France

   Benjamin Doerr

2. School of Computer Science, The University of Adelaide, Adelaide, SA, Australia

   Frank Neumann

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics