On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

Multi-party multi-objective optimization problems (MPMOPs) require consensus among autonomous decision makers and therefore differ from flattened many-objective formulations. Existing runtime theory for multi-objective evolutionary algorithms is largely tailored to single-party Pareto-front approximation and does not directly explain common-solution search in MPMOPs. We investigate cross-party recombination in two representative settings. On MP-JCG, a pseudo-Boolean benchmark with an explicit gap region, we prove that a payoff-guided mutation baseline faces a gap-crossing bottleneck requiring $Θ(n^2)$ expected fitness evaluations. In contrast, an analytical CPR-NSGA-II variant discovers both common Pareto-optimal solutions in $O(n\log n)$ expected evaluations by directly assembling complementary prefix and suffix templates distributed across party populations. Comparing this with the flattened four-objective formulation F-JCG, our full-front coverage analysis illustrates the additional coverage burden introduced by flattening. For BPBOMST, the bi-party, two-objective-per-party specialization of the multi-party multi-objective minimum spanning tree problem, we develop a layered support-cover analysis. For each common Pareto objective vector, the symmetric average projection induces an auxiliary bi-objective MST instance, and suitable support representatives yield a $2λ$-common approximation cover with $λ\in[1,2]$. We further derive an instance-parameterized expected runtime bound for a representative-pool CPR-NSGA-II variant using edge-union recombination and uniform repair. This bound separates the effects of local auxiliary-front filling, cross-party recombination shortcuts, and edge-union repair ambiguity.

Many-objective optimization has been a field of interest over the past two decades and several evolutionary optimization algorithms have been introduced to tackle these problems; yet two fundamental questions remain underexplored: (i) What happens when the number of objectives grows beyond the typical many-objective regime of about fifteen and becomes massive? (ii) How do problem characteristics, such as the nature of interactions between objectives, influence algorithmic performance? To answer these questions we employ a diagnostic benchmark suite that allows control over problem characteristics and can be scaled to extremely high objective counts. Using this framework we evaluate several state-of-the-art evolutionary algorithms including NSGA-II, NSGA-III, MOEA/D and lexicase selection across a range of dimensionalities and diagnostic problem landscapes. Our experiments reveal that problem characteristics significantly affect algorithm performance. In particular, the nature of interactions between objectives appears important. These results highlight the importance of understanding these properties before selecting an algorithm for a specific problem. We also show that lexicase selection, an algorithm originally designed for genetic programming, compares favorably with state-of-the-art many-objective optimization algorithms while avoiding the dependence on predefined reference directions.

This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class CLIMB and analyze the runtime of GSEMO and the widely used NSGA-II on this problem. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a speedup of order $Ω(\sqrt{n}/\log n)$. In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes we propose in this paper, can find the Pareto front of CLIMB in expected $O(n \log n)$ fitness evaluations, whereas NSGA-II with a fixed population size requires $Ω(n^{1.5})$ fitness evaluations in expectation. To the best of our knowledge, this is the first rigorous runtime analysis in multi-objective optimization demonstrating a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, like the evolution of population diversity over time, and employs the well-known family-three method to prove the lower bound.