Author name cluster

Andre Opris

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

AIJ Journal 2026 Journal Article

Many-objective problems where crossover is provably essential

Andre Opris

This article addresses theory in evolutionary many-objective optimization and focuses on the role of crossover operators. 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 two many-objective problems $RR_{\text{RO}}$ and $uRR_{\text{RO}}$ together with a theoretical runtime analysis of the GSEMO and the widely used NSGA-III algorithm to demonstrate that one point crossover on $RR_{\text{RO}}$, as well as uniform crossover on $uRR_{\text{RO}}$, can yield an exponential speedup in the runtime. In particular, when the number of objectives is constant, this algorithms can find the Pareto set of both problems in expected polynomial time when using crossover while without crossover they require exponential time to even find a single Pareto-optimal point. For both problems, we also demonstrate a significant performance gap in certain superconstant parameter regimes for the number of objectives. To the best of our knowledge, this is one of the first rigorous runtime analysis in many-objective optimization which demonstrates an exponential performance gap when using crossover for more than two objectives. Additionally, it is the first runtime analysis involving crossover in many-objective optimization where the number of objectives is not necessarily constant.

Details DOI

AAAI Conference 2026 Conference Paper

Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds

Andre Opris

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<1 is a constant, NSGA-III requires Ω(n^2 \log n / \mu) generations in expectation for covering the Pareto front, providing one of the first lower bounds for NSGA-III on a classical benchmark. Complementing this, we also improve the best known upper bound for NSGA-III on the m-objective OneMinMax problem (m-OMM) of O(n log(n)) generations by a factor of µ / (2n/m + 1)^(m/2) for constant m and (2n/m + 1)^(m/2) ≤ µ ∈ O((log n)^(1/2) (2n/m + 1)^(m/2)). This yields tight runtime bounds for m=2, and the surprising result that NSGA-III outperforms NSGA-II by a factor of µ/n in the expected runtime.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update

Andre Opris

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.

PDF Details DOI

AAAI Conference 2025 Conference Paper

A Many-Objective Problem Where Crossover Is Provably Indispensable

Andre Opris

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.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem

Duc-Cuong Dang
Aneta Neumann
Frank Neumann
Andre Opris
Dirk Sudholt

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.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm

Benjamin Doerr
Martin S. Krejca
Andre Opris

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.

PDF Details DOI

AIJ Journal 2024 Journal Article

Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation

Duc-Cuong Dang
Andre Opris
Dirk Sudholt

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.

Details DOI

AAAI Conference 2023 Conference Paper

A Proof That Using Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation

Duc-Cuong Dang
Andre Opris
Bahare Salehi
Dirk Sudholt

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.

PDF Details DOI