Authors: | Jägersküpper, Jens |
Title: | Probabilistic analysis of evolution strategies using isotropic mutations |
Language (ISO): | en |
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. |
Subject Headings: | heuristic optimization algorithms theory probabilistic analysis evolutionary algorithms |
URI: | http://hdl.handle.net/2003/23261 http://dx.doi.org/10.17877/DE290R-14189 |
Issue Date: | 2007-02-07T10:49:26Z |
Appears in Collections: | LS 02 Komplexitätstheorie und Effiziente Algorithmen |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dissertation-Jaegerskuepper.pdf | DNB | 1.09 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is protected by original copyright
rightsstatements.org