Authors: Wegener, Ingo
Witt, Carsten
Title: On the Behavior of the (1+1) Evolutionary Algorithm on Quadratic Pseudo-Boolean Functions
Language (ISO): en
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.
Subject Headings: boolean functions
complexity analysis
evolutionary algorithms
evolution strategies
quadratic functions
Issue Date: 2001-10-17
Publisher: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
ci97.pdfDNB245.54 kBAdobe PDFView/Open
ci97.ps508.3 kBPostscriptView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.