A rigorous complexity analysis of the (1 + 1)- evolution strategy for separable functions with boolean inputs

dc.contributor.authorDroste, Stefande
dc.contributor.authorJansen, Thomasde
dc.contributor.authorWegener, Ingode
dc.date.accessioned2004-12-07T08:19:14Z
dc.date.available2004-12-07T08:19:14Z
dc.date.issued1998-11-08de
dc.description.abstractEvolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In order to improve our abilities in applying these algorithms three approaches should be followed in parallel. First, experiments for benchmark and practical problems have to be performed. Second, explanations about the behavior of EAs can be obtained by an analysis based on reasonable assumptions. Third, also a rigorous analysis without any unproven assumptions is necessary to establish in future a theory of EAs. Here, for the first time, a rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs is given. Different mutation rates are compared and the use of the crossover operator is investigated. The main contribution is not the result that the expected run time of the (1 + 1) evolutionary algorithm is O( n ln n ) for separable functions with n variables but the presentation of the methods how this result can be proven rigorously.en
dc.format.extent169759 bytes
dc.format.extent437713 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/2003/5322
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-15291
dc.language.isoende
dc.publisherUniversität Dortmundde
dc.relation.ispartofseriesReihe Computational Intelligence ; 6de
dc.subject.ddc004de
dc.titleA rigorous complexity analysis of the (1 + 1)- evolution strategy for separable functions with boolean inputsen
dc.typeTextde
dc.type.publicationtypereport
dcterms.accessRightsopen access

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CI0697doc.ps
Size:
427.45 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
ci0697doc.pdf
Size:
165.78 KB
Format:
Adobe Portable Document Format
Description:
DNB