While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang, Eremeev, and Lehre introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs Dang et al. (in Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery, New York, NY, USA, GECCO'21, pp 1133-1141, 10.1145/3449639.3459398, 2021c). However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy. We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions, denoted Slo[Formula: see text]. The hierarchy is consistent with existing results for the runtime of EAs. The easiest problems are in Slo[Formula: see text] for [Formula: see text] and [Formula: see text]. As we increase [Formula: see text] and decrease [Formula: see text], the function class contains more interesting functions, including instances of hard combinatorial optimisation problems and problems perturbed by static noise. For [Formula: see text] and [Formula: see text] the problem class contains every problem, including problems closed under permutation (No Free Lunch). Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We also study how random perturbations of a function can change its classification. E.g., randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.

Abstract Practical evolutionary multi-objective (EMO) algorithms like NSGA-II, NSGA-III, and SMS-EMOA combine the dominance relation with diversity criteria to identify promising solutions. Despite many success stories, their theoretical foundation remains underdeveloped, with key questions still unanswered–such as which information obtained during evolution is critical for their success. In this work, we explore the limitations of the information provided by the dominance relation between search points encountered so far. We present a large class of bi-objective problems whose Pareto-optimal set is small, while almost all pairs of search points are incomparable. On such problems, we prove that any black-box EMO algorithm that only relies on the dominance relation for making decisions fails spectacularly, requiring exponential time with high probability. In stark contrast, NSGA-II, NSGA-III, and SMS-EMOA efficiently cover the Pareto front in at most expected quadratic time by incorporating additional information from the objective values, such as crowding distances or hypervolume contributions of search points. Experiments conducted on randomly generated problems complement our theoretical findings. Our results highlight the superiority of practical EMO algorithms and the necessity of using information beyond dominance for effective multi-objective optimisation.

In evolutionary multi-objective optimisation, runtime analysis examines the (expected) time for Evolutionary Multi-Objective Algorithms (EMOAs) to cover the Pareto front. It has recently been applied to NSGA-II, NSGA-III and SMS-EMOA. However, most analyses showed that these widely used algorithms have the same runtime guarantee as the simplest EMOA, (G)SEMO. To our knowledge, no runtime analyses demonstrate an advantage of a popular EMOA over (G)SEMO for deterministic problems. We propose such problems to illustrate the superiority of popular EMOAs over (G)SEMO. We introduce a classification of multi-objective problems and identify the so-called ( \( a \) , \( b \) )-Pareto-sparse problems that are difficult for (G)SEMO as Pareto-optimal points are separated by large genotypic distances. A general lower bound on the expected number of fitness evaluations for (G)SEMO to solve any ( \( a \) , \( b \) )-Pareto-sparse problem is proven. On many example problems, this bound is \(n^{\Omega(n)}\) : OneTrapZeroTrap , a generalisation of Trap function to two objectives, the OneJumpZeroJump class with a large gap parameter and a class of bi-objective MaxSat instances called OneZeroCountSat . Therefore, (G)SEMO performs poorly on all these problems. Conversely, we prove that the three popular EMO algorithms—NSGA-II, NSGA-III and SMS-EMOA—enhanced with a mild diversity mechanism of avoiding genotype duplication, are highly efficient as they optimise OneTrapZeroTrap in only \(O(n\log{n})\) fitness evaluations in expectation. Experimental results on OneTrapZeroTrap and OneZeroCountSat match our theoretical prediction that (G)SEMO always fails, while the other algorithms always succeed. Our analysis reveals the importance of the key components in these sophisticated algorithms and contributes to a better understanding of their capabilities.

Quality diversity (QD) algorithms, an extension of evolutionary algorithms, excel at generating diverse sets of high-quality solutions for complex problems in robotics, games, and combinatorial optimisation. Despite their success, the underlying mechanisms remain poorly understood due to a lack of a theoretical foundation. We address this gap by analysing QD algorithms on the all-pairs-shortest-paths (APSP) problem, a classical planning task that naturally seeks multiple solutions. Using Map-Elites, a prominent QD approach, we leverage its ability to evolve solutions across distinct regions of a behavioural space, which for APSP corresponds to all pairs of nodes in the graph. Our analysis rigorously demonstrates that evolutionary algorithms using Map-Elites efficiently compute shortest paths for all node pairs in parallel by exploiting synergies in the behavioural space. By appending edges to an existing shortest path, mutation can create optimal solutions in other regions of the behavioural space. Crossover is particularly effective, as it can combine optimal paths from two regions to produce an optimal path for a third region simply by concatenating two shortest paths. Finally, refining the parent selection to facilitate successful crossovers exhibits significant speed-ups compared to standard QD approaches.

While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy.

Runtime analysis has recently been applied to popular evolutionary multi-objective (EMO) algorithms like NSGA-II in order to establish a rigorous theoretical foundation. However, most analyses showed that these algorithms have the same performance guarantee as the simple (G)SEMO algorithm. To our knowledge, there are no runtime analyses showing an advantage of a popular EMO algorithm over the simple algorithm for deterministic problems.

NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this state-of-the-art algorithm can be analyzed rigorously.

Evolutionary algorithms are popular algorithms for multi-objective optimisation (also called Pareto optimisation) as they use a population to store trade-offs between different objectives. Despite their popularity, the theoretical foundation of multi-objective evolutionary optimisation (EMO) is still in its early development. Fundamental questions such as the benefits of the crossover operator are still not fully understood. We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover: we propose classes of “royal road” functions on which these algorithms cover the whole Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time in expectation to cover the Pareto front. The latter even holds for a large class of black-box algorithms using any elitist selection and any unbiased mutation operator. Moreover, even the expected time to create a single Pareto-optimal search point is exponential. We provide two different function classes, one tailored for one-point crossover and another one tailored for uniform crossover, and we show that some immune-inspired hypermutations cannot avoid exponential optimisation times. Our work shows the first example of an exponential performance gap through the use of crossover for the widely used NSGA-II algorithm and contributes to a deeper understanding of its limitations and capabilities.

Evolutionary algorithms are popular algorithms for multiobjective optimisation (also called Pareto optimisation) as they use a population to store trade-offs between different objectives. Despite their popularity, the theoretical foundation of multiobjective evolutionary optimisation (EMO) is still in its early development. Fundamental questions such as the benefits of the crossover operator are still not fully understood. We provide a theoretical analysis of well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover. We propose a class of problems on which these EMO algorithms using crossover find the Pareto set in expected polynomial time. In sharp contrast, they and many other EMO algorithms without crossover require exponential time to even find a single Pareto-optimal point. This is the first example of an exponential performance gap through the use of crossover for the widely used NSGA-II algorithm.

Runtime analysis has produced many results on the efficiency of simple evolutionary algorithms like the (1+1) EA, and its analogue called GSEMO in evolutionary multiobjective optimisation (EMO). Recently, the first runtime analyses of the famous and highly cited EMO algorithm NSGA-II have emerged, demonstrating that practical algorithms with thousands of applications can be rigorously analysed. However, these results only show that NSGA-II has the same performance guarantees as GSEMO and it is unclear how and when NSGA-II can outperform GSEMO.

Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and mutation rates carefully chosen close to the "error threshold", above which they cease to be efficient. On problems easier for hill-climbing, the populations may slow down these algorithms, leading to worse runtime compared with variants of the elitist (1+1) EA.

Most discrete evolutionary algorithms (EAs) implement elitism, meaning that they make the biologically implausible assumption that the fittest individuals never die. While elitism favours exploitation and ensures that the best seen solutions are not lost, it has been widely conjectured that non-elitism is necessary to explore promising fitness valleys without getting stuck in local optima. Determining when non-elitist EAs outperform elitist EAs has been one of the most fundamental open problems in evolutionary computation. A recent analysis of a non-elitist EA shows that this algorithm does not outperform its elitist counterparts on the benchmark problem JUMP. We solve this open problem through rigorous runtime analysis of elitist and non-elitist population-based EAs on a class of multi-modal problems. We show that with 3-tournament selection and appropriate mutation rates, the non-elitist EA optimises the multi-modal problem in expected polynomial time, while an elitist EA requires exponential time with overwhelmingly high probability. A key insight in our analysis is the non-linear selection profile of the tournament selection mechanism which, with appropriate mutation rates, allows a small sub-population to reside on the local optimum while the rest of the population explores the fitness valley. In contrast, we show that the comma-selection mechanism which does not have this non-linear profile, fails to optimise this problem in polynomial time. The theoretical analysis is complemented with an empirical investigation on instances of the set cover problem, showing that non-elitist EAs can perform better than the elitist ones. We also provide examples where usage of mutation rates close to the error thresholds is beneficial when employing non-elitist population-based EAs.

It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.

Estimation of Distribution Algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal Distribution Algorithm (UMDA)—a simple population-based EDA assuming independence between decision variables—the optimisation time on the linear problem OneMax was until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound $$\mathcal {O}\left( n\lambda \log \lambda +n^2\right) $$ on the LeadingOnes and BinVal problems for population sizes $$\lambda >\mu =\varOmega (\log n)$$ , where $$\mu $$ and $$\lambda $$ are parameters of the algorithm. We also prove that the UMDA with population sizes $$\mu \in \mathcal {O}\left( \sqrt{n}\right) \cap \varOmega (\log n)$$ optimises OneMax in expected time $$\mathcal {O}\left( \lambda n\right) $$ , and for larger population sizes $$\mu =\varOmega (\sqrt{n}\log n)$$ , in expected time $$\mathcal {O}\left( \lambda \sqrt{n}\right) $$ . The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.

Understanding how the time complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time complexity results concern simple EAs, such as the (1+1) EA. We present the level-based theorem, a new technique tailored to population-based processes. It applies to any nonelitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimization. The conditions of the theorem are often straightforward to verify, even for genetic algorithms and estimation of distribution algorithms which were considered highly nontrivial to analyze. The proofs for the example applications are available in the supplementary materials. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.

Population diversity is essential for avoiding premature convergence in genetic algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the (μ + 1) GA and the Jump test function. We show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to significant improvements of the expected optimization time compared to mutation-only algorithms like the (1 + 1) evolutionary algorithm. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to even larger speedups. Experiments were conducted to complement our theoretical findings and further highlight the benefits of crossover on the function class.

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases. This paper provides theoretical explanations of how populations can be essential in evolutionary dynamic optimisation in a general and natural setting. We describe a natural class of dynamic optimisation problems where a sufficiently large population is necessary to keep track of moving optima reliably. We establish a relationship between the population-size and the probability that the algorithm loses track of the optimum.

Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jumpk. All previous results in this context only hold for unrealistically low crossover probability pc=O(k/n), while we give analyses for the setting of constant pc < 1 in all but one case. Our bounds show a dependence on the problem size~$n$, the jump length k, the population size μ, and the crossover probability pc. For the typical case of constant k > 2 and constant pc, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ:

Population-based EAs can optimise pseudo-Boolean functions in expected polynomial time, even when only partial information about the problem is available [7]. In this paper, we show that the approach used to analyse optimisation with partial information extends naturally to optimisation under noise. We consider pseudo-Boolean problems with an additive noise term. Very general conditions on the noise term is derived, under which the EA optimises the noisy function in expected polynomial time. In the case of the Onemax and Leadingones problems, efficient optimisation is even possible when the variance of the noise distribution grows quickly with the problem size.

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous, theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases.

Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as Onemax are still missing.

Complete and accurate information about the quality of candidate solutions is not always available in real-world optimisation. It is often prohibitively expensive to evaluate candidate solution on more than a few test cases, or the evaluation mechanism itself is unreliable. While evolutionary algorithms are popular methods in optimisation, the theoretical understanding is lacking for the case of partial information. This paper initiates runtime analysis of evolutionary algorithms where only partial information about fitness is available. Two scenarios are investigated. In partial evaluation of solutions, only a small amount of information about the problem is revealed in each fitness evaluation. We formulate a model that makes this scenario concrete for pseudo-Boolean optimisation. In partial evaluation of populations, only a few individuals in the population are evaluated, and the fitness values of the other individuals are missing or incorrect.

Recently, an easy-to-use fitness-level technique was introduced to prove upper bounds on the expected runtime of randomised search heuristics with non-elitist populations and unary variation operators. Following this work, we present a new and much more detailed analysis of the population dynamics, leading to a significantly improved fitness-level technique. In addition to improving the technique, the proof has been simplified.