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

The widely used multi-objective 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 of the bi-objective OJZJ benchmark. 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), M = (2n/m -2k + 3) m/2 the size of the Pareto front, and µ the population size (at least the same size as the largest incomparable set). This result together with the existing negative result for the original NSGA-II shows that, in principle, the general approach of the * Corresponding author. 1 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, a recently proposed stochastic population update often does not help for its many-objective counterpart. It at most results in a speed-up by a factor of order 2 k /µ, which is Θ(1) for large m, such as m > k. On the positive side, we prove that heavy-tailed mutation irrespective of the number m of objectives results in a speed-up of order k 0.5+k-β /e k . Finally, we conduct the first runtime analyses of the SMS-EMOA on the classic bi-objective OneMinMax and LOTZ benchmarks and show that the SMS-EMOA has a performance comparable to the GSEMO and the NSGA-II. Our main technical insight, a general condition ensuring that the SMS-EMOA does not lose Pareto-optimal objective values, promises to be useful also in other runtime analyses of this algorithm.