Autor(en): | Wegener, Ingo Witt, Carsten |
Titel: | On the Behavior of the (1+1) Evolutionary Algorithm on Quadratic Pseudo-Boolean Functions |
Sprache (ISO): | en |
Zusammenfassung: | Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1)Evolutionary Algorithm ((1+1)EA)and its multistart variants are studied. Several results on the expected runtime of the (1+1)EA on linear or unimodal functions have already been presented by other authors. This paper is focused on quadratic pseudo-boolean functions, i.e., functions of degree 2. Whereas quadratic pseudoboolean functions without negative coefficients can be optimized efficiently by the (1+1)EA, there are quadratic functions for which the expected runtime is exponential. However, multistart variants of the (1+1)EA are very efficient for many of these functions. This is not the case with a special quadratic function for which the (1+1)EA requires exponential time with a probability exponentially close to 1. At last, some necessary conditions for exponential runtimes are examined, and an 'easy' subclass within the class of quadratic functions is presented. |
Schlagwörter: | boolean functions complexity analysis evolutionary algorithms evolution strategies quadratic functions |
URI: | http://hdl.handle.net/2003/5400 http://dx.doi.org/10.17877/DE290R-15410 |
Erscheinungsdatum: | 2001-10-17 |
Provinienz: | Universität Dortmund |
Enthalten in den Sammlungen: | Sonderforschungsbereich (SFB) 531 |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
ci97.pdf | DNB | 245.54 kB | Adobe PDF | Öffnen/Anzeigen |
ci97.ps | 508.3 kB | Postscript | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org