On the Behavior of the (1+1) Evolutionary Algorithm on Quadratic Pseudo-Boolean Functions
Loading...
Date
2001-10-17
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universität Dortmund
Abstract
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.
Description
Table of contents
Keywords
boolean functions, complexity analysis, evolutionary algorithms, evolution strategies, quadratic functions