Article

Drift analysis with tail bounds

Authors:

Benjamin Doerr,

Leslie Ann GoldbergAuthors Info & Claims

PPSN'10: Proceedings of the 11th international conference on Parallel problem solving from nature: Part I

Pages 174 - 183

Published: 11 September 2010 Publication History

Abstract

We give a simple and short alternative proof of the multiplicative drift theorem published recently (Doerr, Johannsen, Winzen (GECCO 2010)). It completely avoids the use of drift theorems previously used in the theory of evolutionary computation. By this, its proof is fully self-contained.

The new theorem yields exactly the same bounds for expected runtimes as the previous theorem. In addition, it also gives good bounds on the deviations from the mean. This shows, for the first time, that the classical O(n log n) run-time bound for the (1+1) evolutionary algorithm for optimizing linear functions holds with high probability (and not just in expectation). Similar improvements are obtained for other classical problems in the evolutionary algorithms literature, for example computing minimum spanning trees, finding single-source shortest paths, and finding Eulerian cycles.

References

[1]

Baswana, S., Biswas, S., Doerr, B., Friedrich, T., Kurur, P.P., Neumann, F.: Computing single source shortest paths using single-objective fitness. In: Proceedings of FOGA 2009, pp. 59-66. ACM, New York (2009)

Digital Library

[2]

Doerr, B., Hebbinghaus, N., Neumann, F.: Speeding up evolutionary algorithms through restricted mutation operators. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 978-987. Springer, Heidelberg (2006)

Digital Library

[3]

Doerr, B., Goldberg, L.A.: Adaptive drift analysis. In: Proceedings of PPSN XI. Springer, Heidelberg (to appear, 2010)

Digital Library

[4]

Doerr, B., Happ, E., Klein, C.: A tight bound for the (1+1)-EA on the single-source shortest path problem. In: Proceedings of CEC 2007, pp. 1890-1895. IEEE, Los Alamitos (2007)

[5]

Doerr, B., Johannsen, D.: Adjacency list matchings -- an ideal genotype for cycle covers. In: Proceedings of GECCO 2007, pp. 1203-1210. ACM, New York (2007)

Digital Library

[6]

Doerr, B., Johannsen, D.: Edge-based representation beats vertex-based representation in shortest path problems. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)

Digital Library

[7]

Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)

[8]

Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)

Digital Library

[9]

Doerr, B., Klein, C., Storch, T.: Faster evolutionary algorithms by superior graph representation. In: Proceedings of FOCI 2007, pp. 245-250. IEEE, Los Alamitos (2007)

[10]

Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276, 51-81 (2002)

Digital Library

[11]

Dyer, M., Greenhill, C.: Random walks on combinatorial objects. In: Surveys in Combinatorics 1999, pp. 101-136. University Press (1999)

[12]

Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8, 128-140 (1741)

[13]

Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415-426. Springer, Heidelberg (2003)

Digital Library

[14]

Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651-658. ACM, New York (2006)

Digital Library

[15]

Grimmett, G.R., Stirzaker, D.R.: Probability and random processes, 2nd edn. The Clarendon Press Oxford University Press, New York (1992)

[16]

Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability 13, 502-525 (1982)

[17]

Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953-960. ACM, New York (2008)

Digital Library

[18]

He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57-85 (2001)

Digital Library

[19]

He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21-35 (2004)

Digital Library

[20]

Hierholzer, C.: Über die Möglichkeit, einen Linenzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6, 30-32 (1873)

[21]

Neumann, F.: Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. In: Proceedings of CEC 2004, pp. 904-910. IEEE, Los Alamitos (2004)

[22]

Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835-842. ACM, New York (2009)

Digital Library

[23]

Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Compututer Science 378, 32-40 (2007)

Digital Library

[24]

Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82-91. Springer, Heidelberg (2008)

Digital Library

[25]

Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. In: Proceedings of GECCO 2007, pp. 947-954. ACM, New York (2007)

Digital Library

[26]

Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms 4, 349-366 (2004)

Cited By

Lehre POliveto PKrawiec K(2021)Runtime analysis of population-based evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461423(856-880)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461423
Lehrexwid POliveto PCoello Coello C(2020)Runtime analysis of population-based evolutionary algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389890(458-494)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389890
Lehre POliveto PAuger AStützle T(2019)Runtime analysis of evolutionary algorithms: basic introductionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323394(662-693)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323394
Show More Cited By

Drift analysis with tail bounds
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

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, ...
Fitness levels with tail bounds for the analysis of randomized search heuristics

The fitness-level method, also called the method of f-based partitions, is an intuitive and widely used technique for the running time analysis of randomized search heuristics. It was originally defined to prove upper and lower bounds on the expected ...
Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
Special Issue: Theory of Evolutionary Computation

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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PPSN'10: Proceedings of the 11th international conference on Parallel problem solving from nature: Part I

September 2010

741 pages

ISBN:3642158439

Editors:
Robert Schaefer
AGH University of Science and Technology, Faculty of Electrical Engineering, Automatics, Computer Science and Electronics, Department of Computer Science, Kraków, Poland
,
Carlos Cotta
Universidad de Málaga, Departamento Lenguajes y Ciencias de la Computación, ETSI Informática, Málaga, Spain
,
Joanna Kołodziej
University of Bielsko-Biala, Department of Mathematics and Computer Science, Bielsko-Biala, Poland
,
Günter Rudolph
Technische Universität Dortmund, Fakultät für Informatik, Dortmund, Germany

Sponsors

Hewlett-Packard Polska
Microsoft: Microsoft
Intel: Intel

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 September 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lehre POliveto PKrawiec K(2021)Runtime analysis of population-based evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461423(856-880)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461423
Lehrexwid POliveto PCoello Coello C(2020)Runtime analysis of population-based evolutionary algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389890(458-494)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389890
Lehre POliveto PAuger AStützle T(2019)Runtime analysis of evolutionary algorithms: basic introductionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323394(662-693)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323394
Hasenöhrl VSutton ATakadama K(2018)On the runtime dynamics of the compact genetic algorithm on jump functionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205608(967-974)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205608
Osuna ESudholt DTakadama K(2018)Runtime analysis of probabilistic crowding and restricted tournament selection for bimodal optimisationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205591(929-936)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205591
Doerr BDoerr C(2018)Optimal Static and Self-Adjusting Parameter Choices for the $$(1+(\lambda ,\lambda ))$$(1+(ź,ź)) Genetic AlgorithmAlgorithmica10.1007/s00453-017-0354-980:5(1658-1709)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0354-9
Lissovoi ASudholt DWagner MZarges CBosman P(2017)Theoretical results on bet-and-run as an initialisation strategyProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071329(857-864)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071329
(2015)Optimizing linear functions with the ( 1 + λ ) evolutionary algorithm-Different asymptotic runtimes for different instancesTheoretical Computer Science10.1016/j.tcs.2014.03.015561:PA(3-23)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.03.015
Friedrich TKrohmer A(2015)On the Diameter of Hyperbolic Random GraphsProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_49(614-625)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_49
Doerr BKünnemann MAlba E(2013)How the (1+λ) evolutionary algorithm optimizes linear functionsProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463569(1589-1596)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463569
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten