Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T19:38:16.197Z Has data issue: false hasContentIssue false
  • English
  • Français

Drift Analysis and Evolutionary Algorithms Revisited

Published online by Cambridge University Press:  20 June 2018

J. LENGLER  and
A. STEGER
J. LENGLER
Affiliation:
Department of Computer Science, ETH Zürich, Zürich, Switzerland (e-mail: johannes.lengler@inf.ethz.ch, steger@inf.ethz.ch)
A. STEGER
Affiliation:
Department of Computer Science, ETH Zürich, Zürich, Switzerland (e-mail: johannes.lengler@inf.ethz.ch, steger@inf.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a function f: {0,1}n → ℝ. The algorithm starts with a random search point ξ ∈ {0,1}n, and in each round it flips each bit of ξ with probability c/n independently at random, where c > 0 is a fixed constant. The thus created offspring ξ' replaces ξ if and only if f(ξ') ≥ f(ξ). The analysis of the runtime of this simple algorithm for monotone and for linear functions turned out to be highly non-trivial. In this paper we review known results and provide new and self-contained proofs of partly stronger results.

Keywords

Primary 68W2068W40Secondary 60G40

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 643 - 666
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Bäck, T. (1996) Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press.CrossRefGoogle Scholar
[2] Doerr, B. and Goldberg, L. A. (2013) Adaptive drift analysis. Algorithmica 65 224–250.Google Scholar
[3] Doerr, B., Jansen, T., Sudholt, D., Winzen, C. and Zarges, C. (2013) Mutation rate matters even when optimizing monotonic functions. Evolutionary Comput. 21 1–27.Google Scholar
[4] Doerr, B., Johannsen, D. and Winzen, C. (2012) Multiplicative drift analysis. Algorithmica 64 673–697.Google Scholar
[5] Doerr, B., Johannsen, D. and Winzen, C. (2012) Non-existence of linear universal drift functions. Theoret. Comput. Sci. 436 71–86.Google Scholar
[6] Droste, S., Jansen, T. and Wegener, I. (2002) On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 287 131–144.Google Scholar
[7] Hajek, B. (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 13 502–525.Google Scholar
[8] He, J. and Yao, X. (2001) Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127 57–85.Google Scholar
[9] He, J. and Yao, X. (2004) A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Comput. 3 21–35.Google Scholar
[10] Jägersküpper, J. (2011) Combining Markov-chain analysis and drift analysis. Algorithmica 59 409–424.CrossRefGoogle Scholar
[11] Jansen, T. (2007) On the brittleness of evolutionary algorithms. In FOGA 2007: 9th International Workshop on Foundations of Genetic Algorithms, Springer, pp. 54–69.Google Scholar
[12] Johannsen, D. (2010) Random combinatorial structures and randomized search heuristics. PhD thesis, Universität des Saarlandes.Google Scholar
[13] Kötzing, T. (2016) Concentration of first hitting times under additive drift. Algorithmica 75 490–506.Google Scholar
[14] Mitavskiy, B., Rowe, J. and Cannings, C. (2009) Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Internat. J. Intelligent Comput. Cybernet. 2 243–284.Google Scholar
[15] Mühlenbein, H. (1992) How genetic algorithms really work: Mutation and hillclimbing. In PPSN 1992: 2nd International Conference on Parallel Problem Solving from Nature, Elsevier, pp. 15–26.Google Scholar
[16] Oliveto, P. S. and Witt, C. (2011) Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59 369–386.Google Scholar
[17] Oliveto, P. S. and Witt, C. (2012) Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation. arXiv:1211.7184Google Scholar
[18] Witt, C. (2013) Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combin. Probab. Comput. 22 294–318.Google Scholar