Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings

Apr 13, 2015

Benjamin Doerr, Carola Doerr

Apr 13, 2015

Benjamin Doerr, Carola Doerr

* This is the full version of a paper that is to appear at GECCO 2015

**Click to Read Paper and Get Code**

A Tight Runtime Analysis of the $(1+(λ, λ))$ Genetic Algorithm on OneMax

Jun 19, 2015

Benjamin Doerr, Carola Doerr

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably is useful, the $(1+(\lambda, \lambda))$ Genetic Algorithm (GA) was proposed recently in [Doerr, Doerr, Ebel: TCS 2015]. Using the fitness level method, the expected optimization time on general OneMax functions was analyzed and a $O(\max\{n\log(n)/\lambda, \lambda n\})$ bound was proven for any offspring population size $\lambda \in [1..n]$. We improve this work in several ways, leading to sharper bounds and a better understanding of how the use of crossover speeds up the runtime in this algorithm. We first improve the upper bound on the runtime to $O(\max\{n\log(n)/\lambda, n\lambda \log\log(\lambda)/\log(\lambda)\})$. This improvement is made possible from observing that in the parallel generation of $\lambda$ offspring via crossover (but not mutation), the best of these often is better than the expected value, and hence several fitness levels can be gained in one iteration. We then present the first lower bound for this problem. It matches our upper bound for all values of $\lambda$. This allows to determine the asymptotically optimal value for the population size. It is $\lambda = \Theta(\sqrt{\log(n)\log\log(n)/\log\log\log(n)})$, which gives an optimization time of $\Theta(n \sqrt{\log(n)\log\log\log(n)/\log\log(n)})$. Hence the improved runtime analysis gives a better runtime guarantee along with a better suggestion for the parameter $\lambda$. We finally give a tail bound for the upper tail of the runtime distribution, which shows that the actual runtime exceeds our runtime guarantee by a factor of $(1+\delta)$ with probability $O((n/\lambda^2)^{-\delta})$ only.
Jun 19, 2015

Benjamin Doerr, Carola Doerr

* This is a preliminary version of a paper that is to appear at Genetic and Evolutionary Computation Conference (GECCO 2015)

**Click to Read Paper and Get Code**

* This survey article is to appear (in a slightly modified form) in the book "Theory of Randomized Search Heuristics in Discrete Search Spaces", which will be published by Springer in 2018. The book is edited by Benjamin Doerr and Frank Neumann. Missing numbers of pointers to other chapters of this book will be added as soon as possible

**Click to Read Paper and Get Code**

**Click to Read Paper and Get Code**

We show that for all $1<k \leq \log n$ the $k$-ary unbiased black-box complexity of the $n$-dimensional $\onemax$ function class is $O(n/k)$. This indicates that the power of higher arity operators is much stronger than what the previous $O(n/\log k)$ bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163--172, ACM, 2011) suggests. The key to this result is an encoding strategy, which might be of independent interest. We show that, using $k$-ary unbiased variation operators only, we may simulate an unrestricted memory of size $O(2^k)$ bits.

* An extended abstract of this paper has been accepted for inclusion in the proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012)

* An extended abstract of this paper has been accepted for inclusion in the proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012)

**Click to Read Paper and Get Code**
Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices

Jun 11, 2018

Benjamin Doerr, Carola Doerr

Jun 11, 2018

Benjamin Doerr, Carola Doerr

* This book chapter is to appear in the book "Theory of Randomized Search Heuristics in Discrete Search Spaces", which is edited by Benjamin Doerr and Frank Neumann and is scheduled to be published by Springer in 2018

**Click to Read Paper and Get Code**

Motivated by a problem in the theory of randomized search heuristics, we give a very precise analysis for the coupon collector problem where the collector starts with a random set of coupons (chosen uniformly from all sets). We show that the expected number of rounds until we have a coupon of each type is $nH_{n/2} - 1/2 \pm o(1)$, where $H_{n/2}$ denotes the $(n/2)$th harmonic number when $n$ is even, and $H_{n/2}:= (1/2) H_{\lfloor n/2 \rfloor} + (1/2) H_{\lceil n/2 \rceil}$ when $n$ is odd. Consequently, the coupon collector with random initial stake is by half a round faster than the one starting with exactly $n/2$ coupons (apart from additive $o(1)$ terms). This result implies that classic simple heuristic called \emph{randomized local search} needs an expected number of $nH_{n/2} - 1/2 \pm o(1)$ iterations to find the optimum of any monotonic function defined on bit-strings of length $n$.

* Algorithmica 75 (2016), 529-553

* Algorithmica 75 (2016), 529-553

**Click to Read Paper and Get Code*** To appear at ACM Genetic and Evolutionary Computation Conference (GECCO'19). This version has some additional plots and data

**Click to Read Paper and Get Code**

On the Effectiveness of Simple Success-Based Parameter Selection Mechanisms for Two Classical Discrete Black-Box Optimization Benchmark Problems

Mar 04, 2018

Carola Doerr, Markus Wagner

Mar 04, 2018

Carola Doerr, Markus Wagner

**Click to Read Paper and Get Code**

* An extended abstract of this paper will appear at GECCO 2016

**Click to Read Paper and Get Code**

* This is the full version of a paper accepted to GECCO 2015

**Click to Read Paper and Get Code**

Introducing Elitist Black-Box Models: When Does Elitist Selection Weaken the Performance of Evolutionary Algorithms?

Aug 27, 2015

Carola Doerr, Johannes Lengler

Black-box complexity theory provides lower bounds for the runtime of black-box optimizers like evolutionary algorithms and serves as an inspiration for the design of new genetic algorithms. Several black-box models covering different classes of algorithms exist, each highlighting a different aspect of the algorithms under considerations. In this work we add to the existing black-box notions a new \emph{elitist black-box model}, in which algorithms are required to base all decisions solely on (a fixed number of) the best search points sampled so far. Our model combines features of the ranking-based and the memory-restricted black-box models with elitist selection. We provide several examples for which the elitist black-box complexity is exponentially larger than that the respective complexities in all previous black-box models, thus showing that the elitist black-box complexity can be much closer to the runtime of typical evolutionary algorithms. We also introduce the concept of $p$-Monte Carlo black-box complexity, which measures the time it takes to optimize a problem with failure probability at most $p$. Even for small~$p$, the $p$-Monte Carlo black-box complexity of a function class $\mathcal F$ can be smaller by an exponential factor than its typically regarded Las Vegas complexity (which measures the \emph{expected} time it takes to optimize $\mathcal F$).
Aug 27, 2015

Carola Doerr, Johannes Lengler

* A short version of this work has been presented at the GECCO conference 2015 in Madrid, Spain. Available at http://dl.acm.org/citation.cfm?doid=2739480.2754654

**Click to Read Paper and Get Code**

Black-Box Complexity: Breaking the $O(n \log n)$ Barrier of LeadingOnes

Oct 24, 2012

Benjamin Doerr, Carola Winzen

We show that the unrestricted black-box complexity of the $n$-dimensional XOR- and permutation-invariant LeadingOnes function class is $O(n \log (n) / \log \log n)$. This shows that the recent natural looking $O(n\log n)$ bound is not tight. The black-box optimization algorithm leading to this bound can be implemented in a way that only 3-ary unbiased variation operators are used. Hence our bound is also valid for the unbiased black-box complexity recently introduced by Lehre and Witt (GECCO 2010). The bound also remains valid if we impose the additional restriction that the black-box algorithm does not have access to the objective values but only to their relative order (ranking-based black-box complexity).
Oct 24, 2012

Benjamin Doerr, Carola Winzen

* 12 pages, to appear in the Proc. of Artificial Evolution 2011, LNCS 7401, Springer, 2012. For the unrestricted black-box complexity of LeadingOnes there is now a tight $\Theta(n \log\log n)$ bound, cf. http://eccc.hpi-web.de/report/2012/087/

**Click to Read Paper and Get Code**

Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed. We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems. For example, the class of all binary-value functions has a black-box complexity of $O(\log n)$ in the previous black-box models, but has a ranking-based complexity of $\Theta(n)$. For the class of all OneMax functions, we present a ranking-based black-box algorithm that has a runtime of $\Theta(n / \log n)$, which shows that the OneMax problem does not become harder with the additional ranking-basedness restriction.

* This is an extended version of our CSR 2011 paper. 31 pages. The journal version is to appear in Algorithmica, DOI: 10.1007/s00453-012-9684-9

* This is an extended version of our CSR 2011 paper. 31 pages. The journal version is to appear in Algorithmica, DOI: 10.1007/s00453-012-9684-9

**Click to Read Paper and Get Code**
We analyze the classic board game of Mastermind with $n$ holes and a constant number of colors. A result of Chv\'atal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with $\Theta(n / \log n)$ questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006), 525-544) on the memory-restricted black-box complexity of the OneMax function class.

* 23 pages

* 23 pages

**Click to Read Paper and Get Code**
Fast Re-Optimization via Structural Diversity

Apr 16, 2019

Benjamin Doerr, Carola Doerr, Frank Neumann

When a problem instance is perturbed by a small modification, one would hope to find a good solution for the new instance by building on a known good solution for the previous one. Via a rigorous mathematical analysis, we show that evolutionary algorithms, despite usually being robust problem solvers, can have unexpected difficulties to solve such re-optimization problems. When started with a random Hamming neighbor of the optimum, the (1+1) evolutionary algorithm takes $\Omega(n^2)$ time to optimize the LeadingOnes benchmark function, which is the same asymptotic optimization time when started in a randomly chosen solution. There is hence no significant advantage from re-optimizing a structurally good solution. We then propose a way to overcome such difficulties. As our mathematical analysis reveals, the reason for this undesired behavior is that during the optimization structurally good solutions can easily be replaced by structurally worse solutions of equal or better fitness. We propose a simple diversity mechanism that prevents this behavior, thereby reducing the re-optimization time for LeadingOnes to $O(\gamma\delta n)$, where $\gamma$ is the population size used by the diversity mechanism and $\delta \le \gamma$ the Hamming distance of the new optimum from the previous solution. We show similarly fast re-optimization times for the optimization of linear functions with changing constraints and for the minimum spanning tree problem.
Apr 16, 2019

Benjamin Doerr, Carola Doerr, Frank Neumann

* To appear at Genetic and Evolutionary Computation Conference (GECCO '19)

**Click to Read Paper and Get Code**

Self-Adjusting Mutation Rates with Provably Optimal Success Rules

Feb 07, 2019

Benjamin Doerr, Carola Doerr, Johannes Lengler

Feb 07, 2019

Benjamin Doerr, Carola Doerr, Johannes Lengler

**Click to Read Paper and Get Code**

Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms

Dec 03, 2018

Eduardo Carvalho Pinto, Carola Doerr

Dec 03, 2018

Eduardo Carvalho Pinto, Carola Doerr

* Internship report as of July 2017. Some references are outdated. Please get in touch if you are interested in a specific result and we will be happy to discuss the latest version

**Click to Read Paper and Get Code**

Optimal Parameter Choices via Precise Black-Box Analysis

Oct 17, 2018

Benjamin Doerr, Carola Doerr, Jing Yang

Oct 17, 2018

Benjamin Doerr, Carola Doerr, Jing Yang

* Thoroughly revised version

**Click to Read Paper and Get Code**