Impacts of Single-objective Landscapes on Multi-objective Optimization

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.

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.

Scalar objective functions are required when a multi-criteria optimization problem must yield a single preferred design rather than only a Pareto set. The choice of scalarization influences which compromise is selected, how preference parameters are interpreted, and whether non-supported Pareto regions can be reached. This paper compares four formulations for normalized bi-criteria minimization: weighted sums, achievement scalarizing functions, desirability functions, and a fuzzy-logic-based formulation. Two analytically defined Pareto fronts, one convex and one concave, isolate the effect of the objective formulation from numerical optimizer behavior. The comparison focuses on reachable Pareto regions, parameter-induced selection density, compensation between criteria, sensitivity, and interpretability. Results show that weighted sums are simple but structurally limited on concave fronts, while achievement, desirability, and fuzzy formulations reach interior non-supported regions through different mechanisms. Desirability functions introduce nonlinear single-criterion preference mappings, whereas fuzzy rules express nonseparable and reference-dependent engineering preferences.