Proven Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict

Weijie Zheng's paper provides the first systematic theoretical comparison of multiobjective evolutionary algorithms (MOEAs) against traditional approaches like scalarization and ε-constraint on problems with varying conflict levels. Using the OneMaxMinₖ benchmark (with k ∈ [0..n] degrees of conflict), Zheng proves that scalarization (weighted-sum) cannot cover the full Pareto front for k>2, regardless of weight selection. The ε-constraint method can achieve full coverage but only with careful settings of ε and penalty parameters (r > 1/(ε+1−⌈ε⌉)).

In contrast, MOEAs like (G)SEMO, MOEA/D, NSGA-II, and SMS-EMOA all achieve the same expected runtime of O(max{k,1}n ln n) to cover the full Pareto front without any parameter tuning. This holds for both the OneMaxMinₖ and a bi-objective LeadingOnes variant. The work provides a rigorous theoretical foundation for why MOEAs are preferred in practice, especially for real-world problems where conflict degrees are unknown.