Evolution strategies and related estimation of distribution algorithms

ABSTRACT

Evolution Strategies and some continuous domain Estimation of Distribution Algorithms are stochastic optimization procedures based on sampling multivariate Gaussian (normal) distributions. They can be formulated in a common, unified, but still very simple framework. Such a framework is very useful to understand subtle differences of algorithms.

This tutorial focuses on the most important question: how to chose and update the sample distribution parameters. The most common and successful approaches are reviewed. Covered methods include self-adaptation, success rules, path length control, Covariance Matrix Adaptation CMA), and Estimation of Multivariate Normal Algorithm (EMNA).

Methods are motivated with respect to the difficulties one has to face when solving continuous domain non-linear, non-convex optimization problems. Specific problem difficulties will be discussed, for example ill-conditioning and non-separability.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms

Keywords:
adaptation, evolution strategy, tutorial