Evolutionary algorithms are widely used for multi-objective optimization, with NSGA-III being particularly effective for problems with more than three objectives, unlike NSGA-II. Despite its empirical success, its theoretical understanding remains limited, especially regarding runtime analysis. A central open problem concerns its population dynamics, which involve controlling the maximum number of individuals sharing the same fitness value during the exploration process. In this paper, we make a significant step towards such an understanding by proving tight runtime bounds for NSGA-III on the bi-objective OneMinMax (2-OMM) problem. We show that, for population sizes n+1 ≤ µ = O(log(n)^c (n+1)) where c

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.

This paper addresses theory in evolutionary multiobjective optimisation (EMO) and focuses on the role of crossover operators in many-objective optimisation. The advantages of using crossover are hardly understood and rigorous runtime analyses with crossover are lagging far behind its use in practice, specifically in the case of more than two objectives. We present a many-objective problem class together with a theoretical runtime analysis of the widely used NSGA-III to demonstrate that crossover can yield an exponential speedup on the runtime. In particular, this algorithm can find the Pareto set in expected polynomial time when using crossover while without crossover it requires exponential time to even find a single Pareto-optimal point. To our knowledge, this is the first rigorous runtime analysis in many-objective optimisation demonstrating an exponential performance gap when using crossover for more than two objectives.

This paper presents a first mathematical runtime analysis of PAES-25, an enhanced version of the original Pareto Archived Evolution Strategy (PAES) coming from the study of telecommunication problems over two decades ago to understand the dynamics of local search of MOEAs on many-objective fitness landscapes. We derive tight expected runtime bounds of PAES-25 with one-bit mutation on m-LeadingOnesTrailingZeroes until the entire Pareto front is found: Θ(n3) iterations if m = 2, Θ(n3 log2(n)) iterations if m = 4 and Θ(n · (2n/m)m/2 log(n/m)) iterations if m > 4 where n is the problem size and m the number of objectives. To the best of our knowledge, these are the first known tight runtime bounds for an MOEA outperforming the best known upper bound of O(nm+1) for (G)SEMO on m-LOTZ when m ≥ 4. We also show that archivers, such as the Adaptive Grid Archiver (AGA), Hypervolume Archiver (HVA) or Multi-Level Grid Archiver (MGA), help to distribute the set of solutions across the Pareto front of m-LOTZ efficiently. We also show that PAES-25 with standard bit mutation optimizes the bi-objective LeadingOnesTrailingZeroes benchmark in expected O(n4) iterations, and we discuss its limitations on other benchmarks such as OneMinMax or CountingOnesCountingZeros.

Permutation spaces represent a wide range of important problems in domains such as scheduling, routing, sequencing, and assignment. Despite the frequent application of evolutionary algorithms to permutation-based problems, the theory of evolutionary computing in permutation spaces is in its infancy. Many fundamental questions remain open, particularly regarding the effectiveness of various mutation and crossover operators designed for permutation spaces. While there is a substantial body of runtime analyses demonstrating the benefits of crossover in pseudo-Boolean optimisation, there is no such work for permutation spaces.

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.

The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order Ω(n² log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n²), improving over the previous estimate of O(n² log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(n^(k+1)) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2,3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.

The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III of when and why it performs well are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(n^(k+d/2)+ N n ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size N is in 2^(O(n)) and at least (2n/d+1)^(d/2). Notably, NSGA-III is faster than NSGA-II by a factor of N/n^(d/2) for N=omega(n^(d/2)) . We also show that a stochastic population update provably guarantees a speedup of order (k/b)^(k-1) in the runtime where b>0 is a constant. Besides a paper of Wietheger and Doerr (PPSN 2024), this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved.

Abstract The $$\textsc {Jump} _k$$ benchmark was the first problem for which crossover was proven to give a speed-up over mutation-only evolutionary algorithms. Jansen and Wegener (Algorithmica 2002) proved an upper bound of $$O(\textrm{poly}(n) + 4^k/p_c)$$ for the ( $$\mu $$ +1) Genetic Algorithm (( $$\mu $$ +1) GA), but only for unrealistically small crossover probabilities $$p_c$$ . To this date, it remains an open problem to prove similar upper bounds for realistic $$p_c$$ ; the best known runtime bound, in terms of function evaluations, for $$p_c = \Omega (1)$$ is $$O((n/\chi )^{k-1})$$ , $$\chi $$ a positive constant. We provide a novel approach and analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the ( $$\mu $$ +1) GA on $$\textsc {Jump} _k$$ . The ( $$\mu $$ +1)- $${\lambda _c}$$ -GA creates one offspring in each generation either by applying mutation to one parent or by applying crossover $${\lambda _c}$$ times to the same two parents (followed by mutation), to amplify the probability of creating an accepted offspring in generations with crossover. We show that population diversity in the ( $$\mu $$ +1)- $${\lambda _c}$$ -GA converges to an equilibrium of near-perfect diversity. This yields an improved time bound of $$O(\mu n \log (\mu ) + 4^k)$$ function evaluations for a range of k under the mild assumptions $$p_c = O(1/k)$$ and $$\mu \in \Omega (kn)$$ . For all constant k , the restriction is satisfied for some $$p_c = \Omega (1)$$ and it implies that the expected runtime for all constant k and an appropriate $$\mu = \Theta (kn)$$ is bounded by $$O(n^2 \log n)$$ , irrespective of k . For larger k , the expected time of the ( $$\mu $$ +1)- $${\lambda _c}$$ -GA is $$\Theta (4^k)$$ , which is tight for a large class of unbiased black-box algorithms and faster than the original ( $$\mu $$ +1) GA by a factor of $$\Omega (1/p_c)$$ . We also show that our analysis can be extended to other unitation functions such as $$\textsc {Jump} _{k, \delta }$$ and H urdle .

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.

The Jumpk benchmark was the first problem for which crossover was proven to give a speedup over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of O(poly(n) + 4k/pc) for the (μ+1) Genetic Algorithm ((μ+1) GA), but only for unrealistically small crossover probabilities pc. To this date, it remains an open problem to prove similar upper bounds for realistic pc; the best known runtime bound for pc = Ω(1) is O((n/x)k-1), χ a positive constant.

Quality Diversity (QD) aims to evolve a population of solutions that are both diverse and of high quality. The Map-Elites QD approach partitions the search space according to a feature space and stores the best solution for each feature. Bossek & Sudholt (GECCO 2023) showed that a simple QD algorithm on the feature space defined by the number of selected elements efficiently computes (1 - 1/e)-approximations for maximising monotone submodular functions.

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.

Abstract Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time. We study how the population diversity of $$(\mu +1)$$ ( μ + 1 ) algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment. We give an exact formula for the drift of population diversity and show that it is driven towards an equilibrium state. Moreover, we bound the expected time for getting close to the equilibrium state. We find that these dynamics, including the location of the equilibrium, are unaffected by surprisingly many algorithmic choices. All unbiased mutation operators with the same expected number of bit flips have the same effect on the expected diversity. Many crossover operators have no effect at all, including all binary unbiased, respectful operators. We review crossover operators from the literature and identify crossovers that are neutral towards the evolution of diversity and crossovers that are not.

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.

Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time.