Proven Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict
For researchers in multiobjective optimization, this provides the first theoretical evidence that MOEAs have a provable advantage over classical methods for problems with different degrees of conflict.
This paper theoretically compares multiobjective evolutionary algorithms (MOEAs) with scalarization and ε-constraint approaches on problems with varying degrees of conflict. It proves that MOEAs achieve the same expected runtime of O(max{k,1}n ln n) without careful parameter tuning, while scalarization fails to cover the full Pareto front for k>2 and ε-constraint requires careful settings.
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\in[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\}n\ln n)$ number of function evaluations, but only with careful settings of $ε$ and $r$ ($r>1/(ε+1-\lceil ε\rceil)$). In contrast, MOEAs efficiently solve OneMaxMin$_k$ without careful designs. We prove the same expected runtime of $O(\max\{k,1\}n\ln 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.