Simplified drift analysis for proving lower bounds in evolutionary computation

Oliveto, Pietro S.; Witt, Carsten

Simplified drift analysis for proving lower bounds in evolutionary computation

dc.contributor.author	Oliveto, Pietro S.	de
dc.contributor.author	Witt, Carsten	de
dc.date.accessioned	2009-05-12T16:01:59Z
dc.date.available	2009-05-12T16:01:59Z
dc.date.issued	2008-04	de
dc.description.abstract	Drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (EAs). Various previous works apply a drift theorem going back to Hajek in order to show exponential lower bounds on read and to apply since it requires two bounds on the moment-generating (exponential) function of the drift. A recent work identifies a specialization of this drift theorem that is much easier to apply. Nevertheless, it is not as simple and not as general as possible. The present paper picks up Hajek s line of thought to prove a drift theorem that is very easy to use in evolutionary computation. Only two conditions have to be verified, one of which holds for virtually all EAs with standard mutation. The other condition is a bound on what is really relevant, the drift. Applications show how previous analyses involving the complicated theorem can be redone in a much simpler and clearer way. Therefore, the simplified theorem is also a didactical contribution to the runtime analysis of EAs.	en
dc.identifier.uri	http://hdl.handle.net/2003/26154
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9032
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 247-08	de
dc.subject.ddc	004	de
dc.title	Simplified drift analysis for proving lower bounds in evolutionary computation	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Original bundle

Now showing 1 - 1 of 1

Name:: 24708.pdf
Size:: 212.71 KB
Format:: Adobe Portable Document Format
Description:: DNB

Download

Collections

Sonderforschungsbereich (SFB) 531