Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing.

Parameter control and dynamic algorithm configuration study how to dynamically choose suitable configurations of a parametrized algorithm during the optimization process. Despite being an intensively researched topic in evolutionary computation, optimal control policies are known only for very few cases, limiting the development of automated approaches to achieve them.

Randomized search heuristics (RSHs) are known to have a certain robustness to noise. Mathematical analyses trying to quantify rigorously how robust RSHs are to a noisy access to the objective function typically assume that each solution is re-evaluated whenever it is compared to others. This aims at preventing that a single noisy evaluation has a lasting negative effect, but is computationally expensive and requires the user to foresee that noise is present (as in a noise-free setting, one would never re-evaluate solutions). In this work, we conduct the first mathematical runtime analysis of an evolutionary algorithm solving a single-objective noisy problem without re-evaluations. We prove that the (1+1) evolutionary algorithm without re-evaluations can optimize the classic LeadingOnes benchmark with up to constant noise rates, in sharp contrast to the version with re-evaluations, where only noise with rates O(n⁻²log n) can be tolerated. This result suggests that re-evaluations are much less needed than what was previously thought, and that they actually can be highly detrimental. The insights from our mathematical proofs indicate that this similar results are plausible for other classic benchmarks.

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 an 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+(\lambda,\lambda))\) genetic algorithms on the OneMax benchmark. We are optimistic that the question of how to profit from good initial solutions is interesting beyond these first examples.

Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the (1 + λ) and (1, λ) evolutionary algorithms in the presence of prior bit-wise noise, we show that both algorithms can tolerate constant noise probabilities without increasing the asymptotic runtime on the OneMax benchmark. For this, a population size λ suffices that is at least logarithmic in the problem size n. The only previous result in this direction regarded the less realistic one-bit noise model, required a population size super-linear in the problem size, and proved a runtime guarantee roughly cubic in the noiseless runtime for the OneMax benchmark. Our significantly stronger results are based on the novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring. We are optimistic that the technical lemmas resulting from this insight will find applications also in future mathematical runtime analyses of evolutionary algorithms.

Real-world optimization problems often require finding not only one good solution, but a diverse set of good solutions. Evolutionary algorithms (EAs) have been shown to suit well for such a task. However our theoretical understanding of their behavior remains unsatisfying, especially in the multi-objective domain.

Optimizing real-world problems often involves decision-making under uncertainty due to the presence of unknown or uncontrollable variables. Chance-constraints allow to model the optimization problem with stochastic components by ensuring the probabilistic constraint is satisfied with high probability. Multi-objective evolutionary algorithms (MOEAs) are successfully applied to chance constrained optimization problems to achieve high-quality results. Most of these algorithms are based on Pareto dominance for measuring the quality of solutions during their search. A very few algorithms are based on the decomposition approach which tries to optimize the aggregations of the objectives. Among them, multi-objective evolutionary algorithm based on decomposition (MOEA/D) is one of the efficient MOEAs which decomposes the multi-objective optimization problems (MOPs) into a number of scalar optimization problems and then optimizes these sub-problems simultaneously. In this paper, we investigate the effectiveness of the MOEA/D algorithm when solving 2- and 3-objective formulations of the chance constrained knapsack problem, where the weights of each item are stochastic. We compare its performance with global simple evolutionary multi-objective optimizer (GSEMO) across various benchmark scenarios. Overall, we demonstrate that the MOEA/D achieved high-quality solutions with lower computational complexity.

Real-world optimization problems often involve stochastic and dynamic components. Evolutionary algorithms are particularly effective in these scenarios, as they can easily adapt to uncertain and changing environments but often uncertainty and dynamic changes are studied in isolation. In this paper, we explore the use of 3-objective evolutionary algorithms for the chance constrained knapsack problem with dynamic constraints. In our setting, the weights of the items are stochastic and the knapsack's capacity changes over time. We introduce a 3-objective formulation that is able to deal with the stochastic and dynamic components at the same time and is independent of the confidence level required for the constraint. This new approach is then compared to the 2-objective formulation which is limited to a single confidence level. We evaluate the approach using two different multi-objective evolutionary algorithms (MOEAs), namely the global simple evolutionary multi-objective optimizer (GSEMO) and the multi-objective evolutionary algorithm based on decomposition (MOEA/D), across various benchmark scenarios. Our analysis highlights the advantages of the 3-objective formulation over the 2-objective formulation in addressing the dynamic chance constrained knapsack problem.

Abstract 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+(\lambda ,\lambda ))$$ ( 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)$$ ( 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.

The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time O(n2), when the problem size n is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.

Evolutionary algorithms are known to be robust to noise in the evaluation of the fitness. In particular, larger offspring population sizes often lead to strong robustness. We analyze to what extent the (1 + (Λ, Λ)) genetic algorithm is robust to noise. This algorithm also works with larger offspring population sizes, but an intermediate selection step and a non-standard use of crossover as repair mechanism could render this algorithm less robust than, e.g., the simple (1 + Λ) evolutionary algorithm. Our experimental analysis on several classic benchmark problems shows that this difficulty does not arise. Surprisingly, in many situations this algorithm is even more robust to noise than the (1 + Λ) EA.

Computing diverse sets of high quality solutions for a given optimization problem has become an important topic in recent years. In this paper, we introduce a coevolutionary Pareto Diversity Optimization approach which builds on the success of reformulating a constrained single-objective optimization problem as a bi-objective problem by turning the constraint into an additional objective. Our new Pareto Diversity optimization approach uses this bi-objective formulation to optimize the problem while also maintaining an additional population of high quality solutions for which diversity is optimized with respect to a given diversity measure. We show that our standard co-evolutionary Pareto Diversity Optimization approach outperforms the recently introduced DIVEA algorithm which obtains its initial population by generalized diversifying greedy sampling and improving the diversity of the set of solutions afterwards. Furthermore, we study possible improvements of the Pareto Diversity Optimization approach. In particular, we show that the use of inter-population crossover further improves the diversity of the set of solutions.

Theory of evolutionary computation has brought plenty of useful recommendations to the practitioners on how to deal with local optima. Many of these results were obtained through the runtime analysis of evolutionary algorithms (EAs for brevity) on Jump benchmark function, which has a local optimum which is very hard to leave for most EAs. The performed analyses resulted into multiple new algorithms which showed a good performance on Jump function, including the (1 + (λ, λ)) GA (with dynamic parameters choices or with non-standard static parameters), the (μ + 1) GA with various diversity mechanisms, and the hybrid GA.

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 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 is necessary.

To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the n -dimensional Plateau k function as natural benchmark and analyze how different variants of the (1 + 1) EA optimize it. The Plateau k function has a plateau of second-best fitness in a ball of radius k around the optimum. As evolutionary algorithm, we regard the (1 + 1) EA using an arbitrary unbiased mutation operator. Denoting by α the random number of bits flipped in an application of this operator and assuming that Pr [α = 1] has at least some small sub-constant value, we show the surprising result that for all constant k ≥ 2, the runtime T follows a distribution close to the geometric one with success probability equal to the probability to flip between 1 and k bits divided by the size of the plateau. Consequently, the expected runtime is the inverse of this number, and thus only depends on the probability to flip between 1 and k bits, but not on other characteristics of the mutation operator. Our result also implies that the optimal mutation rate for standard bit mutation here is approximately k/(en) . Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was successfully used only in purely 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.

For the (1 + (λ, λ)) genetic algorithm rigorous runtime analyses on unimodal fitness functions have shown that it can be faster than classical evolutionary algorithms, though on these simple problems the gains are only moderate.

We conduct a rigorous runtime analysis of the (1 + (λ, λ)) evolutionary algorithm with standard parameter settings, that is, a mutation rate of p = λ/n and a crossover bias of c = 1/λ when optimizing the classic LeadingOnes benchmark function. We show that, for all λ ∈ [1..n/2], the runtime is Θ(n2/λ) iterations and Θ(n2) fitness evaluations. This is, asymptotically, the same number of iterations as for the (1 + λ) EA and the same number of fitness evaluations as for the (1 + λ) EA for any value of λ = O(n). We also extend our results to parameter control techniques and prove that for any dynamic choice of λ the bound of Θ(n2) fitness evaluations still holds.

Understanding when evolutionary algorithms are efficient or not, and how they efficiently solve problems, is one of the central research tasks in evolutionary computation. In this work, we make progress in understanding the interplay between parent and offspring population size of the (µ, λ) EA. Previous works, roughly speaking, indicate that for λ ≥ (1 + ε)eµ, this EA easily optimizes the OneMax function, whereas an offspring population size λ ≤ (1 - ε)eµ leads to an exponential runtime.

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of true population-based evolutionary algorithms remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the (μ + λ) evolutionary algorithm on the simple OneMax benchmark function, only the special cases μ = 1 and λ = 1 have been solved.

In certain optimization problems, aside from the target objective, auxiliary objectives can be used. These auxiliary objectives may be either helpful or not. Often we can not determine whether an auxiliary objective is helpful. In this work we consider the EA+RL method that dynamically chooses auxiliary objectives in random local search using reinforcement learning. This method's runtime has already been theoretically analysed on different monotonic functions, and it was shown that EA+RL can exclude harmful auxiliary objectives from consideration. EA+RL has also shown good results on different real-world problems. However, it has not been theoretically analysed whether this method can efficiently optimize non-monotonic functions using simple evolutionary algorithms and reinforcement learning agents. In this paper we consider optimization of the non-monotonic JUMP function with the EA+RL method. We use two auxiliary objectives. One of them is helpful during the first phase of optimization and another one is helpful during the last phase. On other stages they are constant, so they neither help nor slow optimization down. We show that EA+RL has at least Ω(ℓ/n) probability of solving this problem in polynomial time using random local search, which is impossible for the conventional random local search without learning. We also propose a modification of EA+RL that is guaranteed to find the optimum.