Authors: Wegener, Ingo
Title: On the Expected Runtime and the Success Probability of Evolutionary Algorithms
Language (ISO): en
Abstract: Evolutionary algorithms are randomized search heuristics whose general variants have been successfully applied in black box optimization. In this scenario the function f to be optimized is not known in advance and knowledge on f can be obtained only by sampling search points a revealing the value of f a . In order to analyze the behavior of different variants of evolutionary algorithms on certain functions f, the expected runtime until some optimal search point is sampled and the success probability i.e., the probability that an optimal search point is among the first sampled points , are of particular interest. Here a simple method for the analysis is discussed and applied to several functions. For specific situations more involved techniques are necessary. Two such results are presented. First, it is shown that the most simple evolutionary algorithm optimizeseach pseudo-boolean linear function in an expected time of O n log n . Second, an example is shown where crossover decreases the expected runtime from superpolynomial to polynomial.
URI: http://hdl.handle.net/2003/5401
http://dx.doi.org/10.17877/DE290R-5639
Issue Date: 2001-10-17
Publisher: Unversität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
ci98.pdfDNB130.62 kBAdobe PDFView/Open
ci98.ps293.46 kBPostscriptView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.