Authors: Witt, Carsten
Title: Population Size vs. Runtime of a Simple Evolutionary Algorithm
Language (ISO): en
Abstract: Evolutionary algorithms (EAs) find numerous applications,and practical knowledge on EAs is immense. In practice,sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often concentrates on very simple algorithms like the (1+1)EA, where the population size equals 1.In this paper, the question is addressed whether the use of a population by itself can be advantageous.A population-based EA that does neither make use of crossover nor any diversity-maintaining operator is investigated on an example function.It is shown that an increase of the population size by a constant factor decreases the expected runtime from exponential to polynomial.Thereby, the so far best known gap is improved from superpolynomial vs.polynomial to exponential vs.polynomial. Moreover, it is proved that the exponential and polynomial runtime bounds occur with a probability exponentially close to one if the population size is a constant resp.a small polynomial.Finally,a second example function,where only a small population leads to a polynomial runtime,and a hierarchy result on the appropriate population size are presented.
URI: http://hdl.handle.net/2003/5446
http://dx.doi.org/10.17877/DE290R-15673
Issue Date: 2003-12-23
Publisher: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
156.pdfDNB284 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.