Probabilistic analysis of evolution strategies using isotropic mutations
Loading...
Date
2007-02-07T10:49:26Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This dissertation deals with optimization in high-dimensional
Euclidean space. Namely, a particular type of direct-search methods
known as Evolution Strategies (ESs) are investigated. Evolution
Strategies mimic natural evolution, in particular mutation, in order
to "evolve" an approximate solution.
As this dissertation focuses on theoretical investigation of ESs in
the way randomized approximation algorithms are analyzed in
theoretical computer science (rather than by means of convergence
theory or dynamical-system theory), very basic and simple ESs are
considered. Namely, the only search operator that is applied are
so-called isotropic mutations. That is, a new candidate solution is
obtained by adding a random vector to the current candidate solution
the distribution of which is spherically symmetric.
General lower bounds on the number of steps/isotropic mutations which
are necessary to reduce the approximation error in the search space
are proved, where the focus is on how the number of optimization steps
depends on (and scales with) the dimensionality of the search
space. These lower bounds hold independently of the function to be
optimized and for large classes of ESs. Moreover, for several
concrete optimization scenarios where certain ESs optimize a unimodal
function, upper bounds on the number of optimization steps are proved.
Description
Table of contents
Keywords
heuristic optimization, algorithms, theory, probabilistic analysis, evolutionary algorithms