Runtime Analysis of the SMS-EMOA for Many-Objective Optimization

The widely used multiobjective optimizer NSGA-II was recently proven to have considerable difficulties in many-objective optimization. In contrast, experimental results in the literature show a good performance of the SMS-EMOA, which can be seen as a steady-state NSGA-II that uses the hypervolume contribution instead of the crowding distance as the second selection criterion. This paper conducts the first rigorous runtime analysis of the SMS-EMOA for many-objective optimization. To this aim, we first propose a many-objective counterpart, the mobjective mOJZJ problem, of the bi-objective OJZJ benchmark, which is the first many-objective multimodal benchmark used in a mathematical runtime analysis. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of O(M²n^k) iterations, where n denotes the problem size (length of the bit-string representation), k the gap size (a difficulty parameter of the problem), and M = (2n/m − 2k + 3)^m/2 the size of the Pareto front. This result together with the existing negative result on the original NSGA-II shows that in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies. We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective OJZJ benchmark, the stochastic population update often does not help for mOJZJ. It results in a 1/Θ(min{Mk¹/²/2^k/2, 1}) speedup, which is Θ(1) for large m such as m > k. On the positive side, we prove that heavy-tailed mutation still results in a speed-up of order k^0.5+k−β. Finally, we conduct the first runtime analyses of the SMS-EMOA on the bi-objective ONEMINMAX and LOTZ benchmarks and show that it has a performance comparable to the GSEMO and the NSGA-II.