caa a22 4500 445804858 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00453-010-9387-z doi (NATIONALLICENCE)springer-10.1007/s00453-010-9387-z Simplified Drift Analysis for Proving Lower Bounds inEvolutionary Computation [Elektronische Daten] [Pietro Oliveto, Carsten Witt] 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 the optimization time of EAs. However, this drift theorem is tedious to 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. In some cases even improved results may be achieved. Therefore, the simplified theorem is also a didactical contribution to the runtime analysis of EAs. Springer Science+Business Media, LLC, 2010 Randomized search heuristics nationallicence Evolutionary algorithms nationallicence Computational complexity nationallicence Runtime analysis nationallicence Drift analysis nationallicence Oliveto Pietro Centre of Excellence for Research in Computational Intelligence and Applications (CERCIA), School of Computer Science, University of Birmingham, Birmingham, UK aut Witt Carsten DTU Informatics, Technical University of Denmark, Kgs. Lyngby, Denmark aut Algorithmica Springer-Verlag 59/3(2011-03-01), 369-386 0178-4617 59:3<369 2011 59 453 https://doi.org/10.1007/s00453-010-9387-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9387-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Oliveto Pietro Centre of Excellence for Research in Computational Intelligence and Applications (CERCIA), School of Computer Science, University of Birmingham, Birmingham, UK aut NATIONALLICENCE 700 1- Witt Carsten DTU Informatics, Technical University of Denmark, Kgs. Lyngby, Denmark aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/3(2011-03-01), 369-386 0178-4617 59:3<369 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer