Fetching the paper…
Reading the bibliography…
This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics.
On a modification of Chebyshev’s inequality and of the error formula of Laplace
Sergey N. Bernstein · 1924
Earlier work this paper cites.
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
Herman Chernoff · 1952
Earlier work this paper cites.
A remark on Stirling’s formula
Herbert Robbins · 1955
Earlier work this paper cites.
Convergence of random processes and limit theorems in probability theory
Yuri Prokhorov · 1956
Earlier work this paper cites.
Probability inequalities for the sum of independent random variables
George Bennett · 1962
Earlier work this paper cites.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
Weighted sums of certain dependent variables
Kazuoki Azuma · 1967
Earlier work this paper cites.
An Introduction to Probability Theory and Its Applications
William Feller · 1968
Earlier work this paper cites.
Distribution inequalities for the binomial law
Eric V. Slud · 1977
Earlier work this paper cites.
The tail of the hypergeometric distribution
Vasek Chvátal · 1979
Earlier work this paper cites.
Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds
Alessandro Panconesi and Aravind Srinivasan · 1997
Earlier work this paper cites.
Concentration
Colin McDiarmid · 1998
Earlier work this paper cites.
Rigorous hitting times for binary mutations
Josselin Garnier, Leila Kallel, and Marc Schoenauer · 1999
Earlier work this paper cites.
Bounds on tail probabilities of discrete distributions
Bernhard Klar · 2000
Earlier work this paper cites.
Probabilistic Methods for Coordination Problems
Christian Scheideler · 2000
Earlier work this paper cites.
Random Graphs
Béla Bollobás · 2001
Earlier work this paper cites.
Drift analysis and average time complexity of evolutionary algorithms
Jun He and Xin Yao · 2001
Earlier work this paper cites.
Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness
Thomas Jansen and Ingo Wegener · 2001
Earlier work this paper cites.
Lower bounds on large deviation probabilities for sums of independent random variables
S. V. Nagaev · 2001
Earlier work this paper cites.
Theoretical aspects of evolutionary algorithms
Ingo Wegener · 2001
Earlier work this paper cites.
On the analysis of the (1+1) evolutionary algorithm
Stefan Droste, Thomas Jansen, and Ingo Wegener · 2002
Earlier work this paper cites.
Comparison Methods for Stochastic Models and Risks
Alfred Müller and Dietrich Stoyan · 2002
Earlier work this paper cites.
Analysis of the (1+1) EA for a dynamically bitwise changing OneMax
Stefan Droste · 2003
Earlier work this paper cites.
Analysis of the (1+1) EA for a noisy OneMax
Stefan Droste · 2004
Earlier work this paper cites.
The analysis of evolutionary algorithms on sorting and shortest paths problems
Jens Scharnow, Karsten Tinnefeld, and Ingo Wegener · 2004
Earlier work this paper cites.
On the choice of the offspring population size in evolutionary algorithms
Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener · 2005
Earlier work this paper cites.
Probability and Computing—Randomized Algorithms and Probabilistic Analysis
Michael Mitzenmacher and Eli Upfal · 2005
Earlier work this paper cites.
On the optimization of monotone polynomials by simple randomized search heuristics
Ingo Wegener and Carsten Witt · 2005
Earlier work this paper cites.
On sums of independent random variables with unbounded variance and estimating the average degree in a graph
Uriel Feige · 2006
Earlier work this paper cites.
On the analysis of a dynamic evolutionary algorithm
Thomas Jansen and Ingo Wegener · 2006
Earlier work this paper cites.
Runtime analysis of the ( μ \mu + 1) EA on simple pseudo-Boolean functions
Carsten Witt · 2006
Earlier work this paper cites.
A tight bound for the (1 + 1)-EA for the single source shortest path problem
Benjamin Doerr, Edda Happ, and Christian Klein · 2007
Earlier work this paper cites.
Adjacency list matchings: an ideal genotype for cycle covers
Benjamin Doerr and Daniel Johannsen · 2007
Earlier work this paper cites.
Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
Frank Neumann and Ingo Wegener · 2007
Earlier work this paper cites.
Comparing evolutionary algorithms to the (1+1)-EA
Pavel A. Borisovsky and Anton V. Eremeev · 2008
Cited alongside, same era.
Directed trees: A powerful representation for sorting and ordering problems
Benjamin Doerr and Edda Happ · 2008
Cited alongside, same era.
Population size versus runtime of a simple evolutionary algorithm
Carsten Witt · 2008
Cited alongside, same era.
Computing single source shortest paths using single-objective fitness
Surender Baswana, Somenath Biswas, Benjamin Doerr, Tobias Friedrich, Piyush P. Kurur, and Frank Neumann · 2009
Cited alongside, same era.
Runtime analysis of a simple ant colony optimization algorithm
Frank Neumann and Carsten Witt · 2009
Cited alongside, same era.
Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems
Pietro Simone Oliveto, Jun He, and Xin Yao · 2009
Ranking-based black-box complexity
Benjamin Doerr and Carola Winzen · 2014
Later among the works it cites.
Tight lower bound on the probability of a binomial exceeding its expectation
Spencer Greenberg and Mehryar Mohri · 2014
Later among the works it cites.
Concentrated hitting times of randomized search heuristics with variable drift
Per Kristian Lehre and Carsten Witt · 2014
Later among the works it cites.
The choice of the offspring population size in the (1, λ \lambda ) evolutionary algorithm
Jonathan E. Rowe and Dirk Sudholt · 2014
Later among the works it cites.
Fitness levels with tail bounds for the analysis of randomized search heuristics
Carsten Witt · 2014
Later among the works it cites.
Optimizing linear functions with the ( 1 + λ ) (1+\lambda) evolutionary algorithm—different asymptotic runtimes for different instances
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Theoretical analysis of rank-based mutation - combining exploration and exploitation
Pietro Simone Oliveto, Per Kristian Lehre, and Frank Neumann · 2009
Cited alongside, same era.
The impact of parametrization in memetic evolutionary algorithms
Dirk Sudholt · 2009
Cited alongside, same era.
Optimal fixed and adaptive mutation rates for the LeadingOnes problem
Süntje Böttcher, Benjamin Doerr, and Frank Neumann · 2010
Cited alongside, same era.
Quasirandom evolutionary algorithms
Benjamin Doerr, Mahmoud Fouz, and Carsten Witt · 2010
Cited alongside, same era.
Edge-based representation beats vertex-based representation in shortest path problems
Benjamin Doerr and Daniel Johannsen · 2010
Cited alongside, same era.
A few ants are enough: ACO with iteration-best update
Frank Neumann, Dirk Sudholt, and Carsten Witt · 2010
Cited alongside, same era.
Benjamin Doerr and Marvin Künnemann · 2015
Later among the works it cites.
Simplified runtime analysis of estimation of distribution algorithms
Duc-Cuong Dang and Per Kristian Lehre · 2015
Later among the works it cites.
Money for nothing: Speeding up evolutionary algorithms through better initialization
Axel de Perthuis de Laillevault, Benjamin Doerr, and Carola Doerr · 2015
Later among the works it cites.
Improved time complexity analysis of the simple genetic algorithm
Pietro Simone Oliveto and Carsten Witt · 2015
Later among the works it cites.
The unrestricted black-box complexity of jump functions
Maxim Buzdalov, Benjamin Doerr, and Mikhail Kever · 2016
Later among the works it cites.
The impact of random initialization on the runtime of randomized search heuristics
Benjamin Doerr and Carola Doerr · 2016
Later among the works it cites.
k k -bit mutation with self-adjusting k k outperforms standard bit mutation
Benjamin Doerr, Carola Doerr, and Jing Yang · 2016
Later among the works it cites.
Optimal parameter choices via precise black-box analysis
Benjamin Doerr, Carola Doerr, and Jing Yang · 2016
Later among the works it cites.
Self-adaptation of mutation rates in non-elitist populations
Duc-Cuong Dang and Per Kristian Lehre · 2016
Later among the works it cites.
Concentration of first hitting times under additive drift
Timo Kötzing · 2016
Later among the works it cites.
A lower bound on the probability that a binomial random variable is exceeding its mean
Christos Pelekis and Jan Ramon · 2016
Later among the works it cites.
Update strength in EDAs and ACO: How to avoid genetic drift
Dirk Sudholt and Carsten Witt · 2016
Later among the works it cites.
Maxim Buzdalov and Benjamin Doerr · 2017
Later among the works it cites.
The (1+ λ \lambda ) evolutionary algorithm with self-adjusting mutation rate
Benjamin Doerr, Christian Gießen, Carsten Witt, and Jing Yang · 2017
Later among the works it cites.
Fast genetic algorithms
Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen · 2017
Later among the works it cites.
The interplay of population size and mutation probability in the (1 + λ \lambda ) EA on OneMax
Christian Gießen and Carsten Witt · 2017
Later among the works it cites.
Tail bounds for sums of geometric and exponential variables
Swante Janson · 2017
Later among the works it cites.
Lower bounds on the run time of the univariate marginal distribution algorithm on onemax
Martin S. Krejca and Carsten Witt · 2017
Later among the works it cites.
Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration
Per Kristian Lehre and Phan Trung Hai Nguyen · 2017
Later among the works it cites.
On the runtime analysis of generalised selection hyper-heuristics for pseudo-Boolean optimisation
Andrei Lissovoi, Pietro Simone Oliveto, and John Alasdair Warwicker · 2017
Later among the works it cites.
Upper bounds on the runtime of the univariate marginal distribution algorithm on OneMax
Carsten Witt · 2017
Later among the works it cites.
Runtime analysis for the ( μ + λ ) {(\mu+\lambda)} EA optimizing OneMax
Denis Antipov, Benjamin Doerr, Jiefeng Fang, and Tangi Hetet · 2018
Closest in time.
Level-based analysis of genetic algorithms and other search processes
Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre · 2018
Closest in time.
Optimal static and self-adjusting parameter choices for the ( 1 + ( λ , λ ) ) {(1+(\lambda,\lambda))} genetic algorithm
Benjamin Doerr and Carola Doerr · 2018
Closest in time.
Better runtime guarantees via stochastic domination
Benjamin Doerr · 2018
Closest in time.
An elementary analysis of the probability that a binomial random variable exceeds its expectation
Benjamin Doerr · 2018
Closest in time.
Runtime analysis for self-adaptive mutation rates
Benjamin Doerr, Carsten Witt, and Jing Yang · 2018
Closest in time.
Probabilistic analysis of the (1+1)-evolutionary algorithm
Hsien-Kuei Hwang, Alois Panholzer, Nicolas Rolin, Tsung-Hsi Tsai, and Wei-Mei Chen · 2018
Closest in time.
Probabilistic tools for the analysis of randomized optimization heuristics
Benjamin Doerr · 2020
Closest in time.