Proven advantage of multiobjective evolutionary algorithms for problems with different degrees of conflict

The field of multiobjective evolutionary algorithms (MOEAs) often emphasizes its popularity for optimization problems with conflicting objectives. However, it is still theoretically unknown how MOEAs perform compared with typical approaches outside this field. This paper conducts such a systematic theoretical comparison on problem classes with different degrees of conflict. With ONEMAXMIN_k depicting k ∈ [0..n] degrees of conflict, we show the difficulties of two typical non-MOEA approaches, the scalarization (weighted-sum) and the ε-constraint approach. We prove that for any set of weights, the set of optima formed by the scalarization approach cannot cover its full Pareto front for k > 2. Although constrained problems constructed from ε-constraint approach ensure the full coverage, general ways (via exterior or nonparameter penalty functions) to solve these constrained problems encounter difficulties. The nonparameter penalty function way cannot guarantee the full coverage, and the exterior way covers the Pareto front with expected O(max {k, 1}nln n) number of function evaluations, but only with careful settings of ε and r (r>1/(ε+1−⌈ε⌉)). In contrast, MOEAs efficiently solve ONEMAXMIN_k without careful designs. We prove the same expected runtime of O(max {k, 1}nln n) for the (G)SEMO, MOEA/D, NSGA-II, and SMS-EMOA. Our brief discussions on a bi-objective LEADINGONES variant with different degrees of conflict show similar findings.