. Pr,

, Static (1,?) EA using p = 1/n (1,?) EA using p = max{1/n, ln(?)/(ln(en/d(x)))/n} Self-adaptive (1,?) EA using F = 32

, Self-adaptive (1,?) EA using F = 2

, Self-adaptive (1,?) EA using F =, vol.1

, Average runtime over 100 runs of five variants of the (1,?) EA on OneMax for n, vol.10

, Static (1,?) EA using p = 1/n (1,?) EA using p = max{1/n, ln(?)/(ln(en/d(x)))/n} Self-adaptive (1,?) EA using F = 2

, Self-adaptive (1,?) EA using F =, vol.1

, Self-adp (1,?) EA using F = 32

, Self-adp (1,?) EA using F = 32 (breaking ties randomly) Self-adp (1,?) EA using F = 2

, Self-adp (1,?) EA using F = 2 (breaking ties randomly) Self-adp (1,?) EA using F =, vol.1

, EA using F = 1.2 (breaking ties randomly) Chapter 6. Conclusions we are optimistic that our research helps pave the ground for further analyses of self-adaptive EAs, Self-adp (1,?)

K. Azuma, Weighted sums of certain dependent variables, Tohoku Mathematical Journal, vol.19, pp.357-367, 1967.

T. Bäck, Self-adaptation in genetic algorithms, Proc. of ECAL '92, pp.263-271, 1992.

G. Badkobeh, D. Per-kristian-lehre, and . Sudholt, Unbiased black-box complexity of parallel search, Proc. of PPSN '14, pp.892-901, 2014.

S. Böttcher, B. Doerr, and F. Neumann, Optimal fixed and adaptive mutation rates for the LeadingOnes problem, Proc. of PPSN '10, pp.1-10, 2010.

N. Buskulic and C. Doerr, , 2018.

M. Buzdalov and B. Doerr, Runtime Analysis of the (1 + (?, ?)) Genetic Algorithm on Random Satisfiable 3-CNF Formulas, Proc. of GECCO '17, pp.1343-1350, 2017.

C. Duc, . Dang, and . Per-kristian-lehre, Self-adaptation of mutation rates in non-elitist populations, Proc. of PPSN '16, pp.803-813, 2016.

L. Devroye, The compound random search, 1972.

B. Doerr, Analyzing randomized search heuristics: tools from probability theory, Theory of Randomized Search Heuristics, pp.1-20, 2011.

B. Doerr, Better Runtime Guarantees via Stochastic Domination, Proc. of EvoCOP '18, pp.1-17, 2018.

B. Doerr, Probabilistic Tools for the Analysis of Randomized Optimization Heuristics, 2018.

B. Doerr and C. Doerr, Optimal parameter choices through self-adjustment: applying the 1/5-th rule in discrete settings, Proc. of GECCO '15, pp.1335-1342, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01272868

B. Doerr and C. Doerr, The Impact of Random Initialization on the Runtime of Randomized Search Heuristics, Algorithmica 75, vol.3, pp.529-553, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01363851

B. Doerr and C. Doerr, Optimal Static and Self-Adjusting Parameter Choices for the (1 + (?, ?)) Genetic Algorithm, Algorithmica, vol.80, pp.1658-1709, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01668262

B. Doerr and C. Doerr, Theory of Parameter Control Mechanisms for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices, Theory of Randomized Search Heuristics in Discrete Search Spaces, 2018.

B. Doerr, C. Doerr, and F. Ebel, From black-box complexity to designing new genetic algorithms, In: Theoretical Computer Science, vol.567, pp.87-104, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01272858

B. Doerr, C. Doerr, and F. Ebel, From black-box complexity to designing new genetic algorithms, In: Theoretical Computer Science, vol.567, pp.87-104, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01272858

B. Doerr, C. Doerr, and T. Kötzing, Provably optimal self-adjusting step sizes for multi-valued decision variables, Proc. of PPSN '16, pp.782-791, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01363911

B. Doerr, C. Doerr, and J. Yang, k-Bit mutation with selfadjusting k outperforms standard bit mutation, Proc. of PPSN '16, pp.824-834, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01363906

B. Doerr, C. Doerr, and J. Yang, Optimal parameter choices via precise black-box analysis, Proc. of GECCO '16, pp.1123-1130, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01363930

B. Doerr, M. Fouz, and C. Witt, Quasirandom evolutionary algorithms, Proc. of GECCO '10, pp.1457-1464, 2010.

B. Doerr, M. Fouz, and C. Witt, Sharp bounds by probability-generating functions and variable drift, Proc. of GECCO '11, pp.2083-2090, 2011.

B. Doerr, D. Johannsen, and C. Winzen, Multiplicative Drift Analysis, Algorithmica 64, pp.673-697, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01797908

B. Doerr and M. Künnemann, Optimizing linear functions with the (1+?) evolutionary algorithm-different asymptotic runtimes for different instances, Theoretical Computer Science, vol.561, pp.3-23, 2015.

B. Doerr, C. Witt, and J. Yang, Runtime Analysis for Self-adaptive Mutation Rates, Proc. of GECCO '18, 2018.

B. Doerr, T. Jansen, C. Witt, and C. Zarges, A method to derive fixed budget results from expected optimisation times, Proc. of GECCO '13, pp.1581-1588, 2013.

B. Doerr, T. Kötzing, J. Lengler, and C. Winzen, Black-Box Complexities of Combinatorial Problems, Theoretical Computer Science, vol.471, pp.84-106, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01086551

B. Doerr, T. Jansen, D. Sudholt, C. Winzen, and C. Zarges, Mutation rate matters even when optimizing monotone functions, Evolutionary Computation, vol.21, pp.1-21, 2013.

B. Doerr, C. Gießen, C. Witt, and J. Yang, The (1+?) Evolutionary Algorithm with Self-Adjusting Mutation Rate, Proc. of PPSN '17, pp.1351-1358, 2017.

C. Doerr and M. Wagner, On the Effectiveness of Simple Success-Based Parameter Selection Mechanisms for Two Classical Discrete Black-Box Optimization Benchmark Problems, Proc. of GECCO '18, 2018.

S. Droste, T. Jansen, and I. Wegener, On the analysis of the (1+1) Evolutionary Algorithm, Theoretical Computer Science, vol.276, pp.51-81, 2002.

S. Droste, T. Jansen, and I. Wegener, Upper and Lower Bounds for Randomized Search Heuristics in Black-box Optimization, Theory of Computing Systems, vol.39, pp.525-544, 2006.

R. Agoston-endre-eiben, Z. Hinterding, and . Michalewicz, Parameter control in evolutionary algorithms, IEEE Transactions on Evolutionary Computation, vol.3, pp.124-141, 1999.

Á. Fialho, L. Costa, M. Schoenauer, and M. Sebag, Extreme Value Based Adaptive Operator Selection, Proc. PPSN '08, vol.5199, pp.175-184, 2008.
URL : https://hal.archives-ouvertes.fr/inria-00287355

Á. Fialho, L. Costa, M. Schoenauer, and M. Sebag, Dynamic Multi-Armed Bandits and Extreme Value-Based Rewards for Adaptive Operator Selection in Evolutionary Algorithms, Proc
URL : https://hal.archives-ouvertes.fr/inria-00377401

, Lecture Notes in Computer Science, vol.5851, pp.176-190, 2009.

J. Garnier, L. Kallel, and M. Schoenauer, Rigorous Hitting Times for Binary Mutations, Evolutionary Computation, vol.7, pp.173-203, 1999.
URL : https://hal.archives-ouvertes.fr/inria-00001277

C. Gießen and C. Witt, The interplay of population size and mutation probability in the (1+?) EA on OneMax, Algorithmica 78, pp.587-609, 2017.

C. Gießen and C. Witt, Population Size vs. Mutation Strength for the (1+?) EA on OneMax, Proc. GECCO '15, pp.1439-1446, 2015.

C. Gießen and C. Witt, Optimal Mutation Rates for the (1+?) EA on OneMax, Proc. of GECCO '16, pp.1147-1154, 2016.

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

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

H. Hwang, A. Panholzer, N. Rolin, T. Tsai, and W. Chen, Probabilistic analysis of the (1+1)-evolutionary algorithm, Evolutionary Computation, vol.26, pp.299-345, 2018.

J. Jägersküpper, Combining Markov-chain analysis and drift analysis-the (1+1) evolutionary algorithm on linear functions reloaded, Algorithmica, vol.59, pp.409-424, 2011.

T. Jansen, Analyzing Evolutionary Algorithms-The Computer Science Perspective, Natural Computing Series, pp.978-981, 2013.

T. Jansen and I. Wegener, On the analysis of a dynamic evolutionary algorithm, Journal of Discrete Algorithms, vol.4, pp.181-199, 2006.

T. Jansen and C. Zarges, Performance analysis of randomised search heuristics operating with a fixed budget, Theoretical Computer Science, vol.545, pp.39-58, 2014.

D. Johannsen, Random combinatorial structures and randomized search heuristics, 2010.

R. Kaas and J. M. Buhrman, Mean, Median and Mode in Binomial Distributions, Statistica Neerlandica, vol.34, pp.13-18, 1980.

T. Kötzing, A. Lissovoi, and C. Witt, (1+1) EA on generalized dynamic OneMax, Proc. of FOGA '15, pp.40-51, 2015.

A. De-perthuis-de-laillevault, B. Doerr, and C. Doerr, Money for Nothing: Speeding Up Evolutionary Algorithms Through Better Initialization, Proc. of the GECCO '15, pp.815-822, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01272863

J. Lässig and D. Sudholt, Adaptive population models for offspring populations and parallel evolutionary algorithms, Proc. of FOGA '11, pp.181-192, 2011.

K. Per, C. Lehre, and . Witt, Black-Box Search by Unbiased Variation, Algorithmica 64, pp.623-642, 2012.

J. Lengler, A General Dichotomy of Evolutionary Algorithms on Monotone Functions, 2018.

B. Mitavskiy, J. E. Rowe, and C. Cannings, Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links, Journal of Intelligent Computing and Cybernetics, vol.2, pp.243-284, 2009.

F. Neumann and I. Wegener, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theoretical Computer Science, vol.378, pp.32-40, 2007.

P. Cesa-bianchi, Finite-time analysis of the multiarmed bandit problem, Machine Learning, vol.47, pp.235-256, 2002.

I. Rechenberg, , p.Evolutionsstrategie, 1973.

H. Robbins, A Remark on Stirling's Formula, The American Mathematical Monthly, vol.62, pp.26-29, 1955.

J. E. Rowe and D. Sudholt, The choice of the offspring population size in the (1, ?) evolutionary algorithm, Theoretical Computer Science, vol.545, pp.20-38, 2014.

A. Michael, K. Schumer, and . Steiglitz, Adaptive step size random search, IEEE Transactions on Automatic Control, vol.13, pp.270-276, 1968.

D. Sudholt, A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, vol.17, pp.418-435, 2013.

C. Witt, Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions, Combinatorics, Probability & Computing, vol.22, pp.294-318, 2013.