Maxim Buzdalov

Deyao Chen, Maxim Buzdalov, Carola Doerr et al.

Dynamic Algorithm Configuration (DAC) tackles the question of how to automatically learn policies to control parameters of algorithms in a data-driven fashion. This question has received considerable attention from the evolutionary community in recent years. Having a good benchmark collection to gain structural understanding on the effectiveness and limitations of different solution methods for DAC is therefore strongly desirable. Following recent work on proposing DAC benchmarks with well-understood theoretical properties and ground truth information, in this work, we suggest as a new DAC benchmark the controlling of the key parameter $λ$ in the $(1+(λ,λ))$~Genetic Algorithm for solving OneMax problems. We conduct a study on how to solve the DAC problem via the use of (static) automated algorithm configuration on the benchmark, and propose techniques to significantly improve the performance of the approach. Our approach is able to consistently outperform the default parameter control policy of the benchmark derived from previous theoretical work on sufficiently large problem sizes. We also present new findings on the landscape of the parameter-control search policies and propose methods to compute stronger baselines for the benchmark via numerical approximations of the true optimal policies.

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem (parameter tuning) is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice (parameter control) is necessary. In this work, we propose a lazy but effective solution, namely choosing all parameter values (where this makes sense) in each iteration randomly from a suitably scaled power-law distribution. To demonstrate the effectiveness of this approach, we perform runtime analyses of the $(1+(λ,λ))$ genetic algorithm with all three parameters chosen in this manner. We show that this algorithm on the one hand can imitate simple hill-climbers like the $(1+1)$ EA, giving the same asymptotic runtime on problems like OneMax, LeadingOnes, or Minimum Spanning Tree. On the other hand, this algorithm is also very efficient on jump functions, where the best static parameters are very different from those necessary to optimize simple problems. We prove a performance guarantee that is comparable to the best performance known for static parameters. For the most interesting case that the jump size $k$ is constant, we prove that our performance is asymptotically better than what can be obtained with any static parameter choice. We complement our theoretical results with a rigorous empirical study confirming what the asymptotic runtime results suggest.

Kirill Antonov, Maxim Buzdalov, Arina Buzdalova et al.

With the goal to provide absolute lower bounds for the best possible running times that can be achieved by $(1+λ)$-type search heuristics on common benchmark problems, we recently suggested a dynamic programming approach that computes optimal expected running times and the regret values inferred when deviating from the optimal parameter choice. Our previous work is restricted to problems for which transition probabilities between different states can be expressed by relatively simple mathematical expressions. With the goal to cover broader sets of problems, we suggest in this work an extension of the dynamic programming approach to settings in which the transition probabilities cannot necessarily be computed exactly, but in which they can be approximated numerically, up to arbitrary precision, by Monte Carlo sampling. We apply our hybrid Monte Carlo dynamic programming approach to a concatenated jump function and demonstrate how the obtained bounds can be used to gain a deeper understanding into parameter control schemes.

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of the algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the $(1+1)$ evolutionary algorithm and the static, self-adjusting, and heavy-tailed $(1 + (λ,λ))$ GA on the OneMax benchmark. We are optimistic that the question how to profit from good initial solutions is interesting beyond these first examples.

Maxim Buzdalov, Carola Doerr

The OneMax problem, alternatively known as the Hamming distance problem, is often referred to as the "drosophila of evolutionary computation (EC)", because of its high relevance in theoretical and empirical analyses of EC approaches. It is therefore surprising that even for the simplest of all mutation-based algorithms, Randomized Local Search and the (1+1) EA, the optimal mutation rates were determined only very recently, in a GECCO 2019 poster. In this work, we extend the analysis of optimal mutation rates to two variants of the $(1+λ)$ EA and to the $(1+λ)$ RLS. To do this, we use dynamic programming and, for the $(1+λ)$ EA, numeric optimization, both requiring $Θ(n^3)$ time for problem dimension $n$. With this in hand, we compute for all population sizes $λ\in \{2^i \mid 0 \le i \le 18\}$ and for problem dimension $n \in \{1000, 2000, 5000\}$ which mutation rates minimize the expected running time and which ones maximize the expected progress. Our results do not only provide a lower bound against which we can measure common evolutionary approaches, but we also obtain insight into the structure of these optimal parameter choices. For example, we show that, for large population sizes, the best number of bits to flip is not monotone in the distance to the optimum. We also observe that the expected remaining running time are not necessarily unimodal for the $(1+λ)$ EA$_{0 \rightarrow 1}$ with shifted mutation.

Maxim Buzdalov, Benjamin Doerr, Carola Doerr et al.

Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

The heavy-tailed mutation operator proposed in Doerr, Le, Makhmara, and Nguyen (GECCO 2017), called \emph{fast mutation} to agree with the previously used language, so far was proven to be advantageous only in mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives. In this first runtime analysis of a crossover-based algorithm using a heavy-tailed choice of the mutation rate, we show an even stronger impact. For the $(1+(λ,λ))$ genetic algorithm optimizing the OneMax benchmark function, we show that with a heavy-tailed mutation rate a linear runtime can be achieved. This is asymptotically faster than what can be obtained with any static mutation rate, and is asymptotically equivalent to the runtime of the self-adjusting version of the parameters choice of the $(1+(λ,λ))$ genetic algorithm. This result is complemented by an empirical study which shows the effectiveness of the fast mutation also on random satisfiable Max-3SAT instances.

Anton Bassin, Maxim Buzdalov

Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the $(1+(λ,λ))$ genetic algorithm, where the adaptation of the population size helps to achieve the linear runtime on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to performance degradation compared to static parameter choices. In particular, the one fifth rule, which guides the adaptation in the example above, is able to raise the population size too fast on problems which are too far away from the perfect fitness-distance correlation. We propose a modification of the one fifth rule in order to have less negative impact on the performance in scenarios when the original rule reduces the performance. Our modification, while still having a good performance on OneMax, both theoretically and in practice, also shows better results on linear functions with random weights and on random satisfiable MAX-SAT instances.

Nina Bulanova, Maxim Buzdalov

In their GECCO'12 paper, Doerr and Doerr proved that the $k$-ary unbiased black-box complexity of OneMax on $n$ bits is $O(n/k)$ for $2\le k\le O(\log n)$. We propose an alternative strategy for achieving this unbiased black-box complexity when $3\le k\le\log_2 n$. While it is based on the same idea of block-wise optimization, it uses $k$-ary unbiased operators in a different way. For each block of size $2^{k-1}-1$ we set up, in $O(k)$ queries, a virtual coordinate system, which enables us to use an arbitrary unrestricted algorithm to optimize this block. This is possible because this coordinate system introduces a bijection between unrestricted queries and a subset of $k$-ary unbiased operators. We note that this technique does not depend on OneMax being solved and can be used in more general contexts. This together constitutes an algorithm which is conceptually simpler than the one by Doerr and Doerr, and at the same time achieves better constant factors in the asymptotic notation. Our algorithm works in $(2+o(1))\cdot n/(k-1)$, where $o(1)$ relates to $k$. Our experimental evaluation of this algorithm shows its efficiency already for $3\le k\le6$.

Maxim Buzdalov, Benjamin Doerr

The $(1+(λ,λ))$ genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on so me optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect fitness-distance correlation. In this work, we conduct a rigorous runtime analysis of this GA on random 3-SAT instances in the planted solution model having at least logarithmic average degree, which are known to have a weaker fitness distance correlation. We prove that this GA with fixed not too large population size again obtains runtimes better than $Θ(n \log n)$, which is a lower bound for most evolutionary algorithms on pseudo-Boolean problems with unique optimum. However, the self-adjusting version of the GA risks reaching population sizes at which the intermediate selection of the GA, due to the weaker fitness-distance correlation, is not able to distinguish a profitable offspring from others. We show that this problem can be overcome by equipping the self-adjusting GA with an upper limit for the population size. Apart from sparse instances, this limit can be chosen in a way that the asymptotic performance does not worsen compared to the idealistic OneMax case. Overall, this work shows that the $(1+(λ,λ))$ GA can provably have a good performance on combinatorial search and optimization problems also in the presence of a weaker fitness-distance correlation.

Viktor Arkhipov, Maxim Buzdalov, Anatoly Shalyto

We present our asynchronous implementation of the LM-CMA-ES algorithm, which is a modern evolution strategy for solving complex large-scale continuous optimization problems. Our implementation brings the best results when the number of cores is relatively high and the computational complexity of the fitness function is also high. The experiments with benchmark functions show that it is able to overcome its origin on the Sphere function, reaches certain thresholds faster on the Rosenbrock and Ellipsoid function, and surprisingly performs much better than the original version on the Rastrigin function.