Andre Opris

Andre Opris

NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is particularly well suited for optimizing problems with more than three objectives, distinguishing it from the classical NSGA-II. However, theoretical understanding of when and why NSGA-III performs well is still at an early stage. In this paper, we contribute to closing this gap by conducting rigorous runtime analyses on the classical many-objective benchmark problems $d$-\textsc{LeadingOnesTrailingZeros} ($d$-LOTZ), $d$-\textsc{CountingOnesCountingZeros} ($d$-COCZ), $d$-\textsc{OneMinMax} ($d$-OMM), and $d$-\textsc{OneJumpZeroJump} ($d$-OJZJ) for arbitrary numbers of objectives $d$. In particular, we improve upon previous results when the population size is asymptotically larger than the size of the Pareto front. Notably, in the bi-objective case, the derived upper runtime bounds are asymptotically tighter than those known for NSGA-II. For the problems $2$-OMM and $2$-OJZJ, NSGA-III even outperforms NSGA-II in terms of expected runtime for suitable population sizes $μ$. Further, we show that a stochastic population update mechanism provably yields an exponential speedup in the expected runtime on many-objective multimodal problems such as $d$-OJZJ, as well as on the function $d$-\textsc{RRMO}, a many-objective variant of the Real-Royal-Road function, for certain parameter regimes. To complement our analysis, we also establish tight runtime bounds for NSGA-III on $2$-\textsc{OJZJ} and $4$-\textsc{OJZJ}. In particular, the result for $4$-OJZJ provides, to the best of our knowledge, the first lower bound for NSGA-III on a classical benchmark problem with more than two objectives. Deriving these bounds requires a substantially deeper analysis of the population dynamics of NSGA-III than has been achieved in previous work.

Andre Opris

In recent years, a theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical $m$-objective $m$-OneJumpZeroJump function ($m$-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes $m$-OJZJ asymptotically faster than NSGA-III without crossover for any number $m$ of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on $4$-OJZJ when crossover is turned off.

Andre Opris, Denis Antipov

Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by incorporating different parent selection strategies into the $(μ+1)$ genetic algorithm (GA). We show that, with an appropriately chosen population size and a parent selection strategy that selects a pair of maximally distant parents with probability $Ω(1)$ for crossover, the resulting algorithm solves the Jump$_k$ problem in $O(k4^kn\log(n))$ expected time. This bound is significantly smaller than the best known bound of $O(nμ\log(μ)+n\log(n)+n^{k-1})$ for any $(μ+1)$~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The crucial point of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals, as it has been done in many previous works. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.

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.

Duc-Cuong Dang, Aneta Neumann, Frank Neumann et al.

Quality diversity (QD) algorithms have shown to provide sets of high quality solutions for challenging problems in robotics, games, and combinatorial optimisation. So far, theoretical foundational explaining their good behaviour in practice lack far behind their practical success. We contribute to the theoretical understanding of these algorithms and study the behaviour of QD algorithms for a classical planning problem seeking several solutions. We study the all-pairs-shortest-paths (APSP) problem which gives a natural formulation of the behavioural space based on all pairs of nodes of the given input graph that can be used by Map-Elites QD algorithms. Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel. Furthermore, we examine parent selection techniques for crossover that exhibit significant speed ups compared to the standard QD approach.