Autor(en): Jägersküpper, Jens
Titel: Probabilistic analysis of evolution strategies using isotropic mutations
Sprache (ISO): en
Zusammenfassung: 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.
Schlagwörter: heuristic optimization
algorithms
theory
probabilistic analysis
evolutionary algorithms
URI: http://hdl.handle.net/2003/23261
http://dx.doi.org/10.17877/DE290R-14189
Erscheinungsdatum: 2007-02-07T10:49:26Z
Enthalten in den Sammlungen:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation-Jaegerskuepper.pdfDNB1.09 MBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org