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

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 nk) 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 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 2k / μ, which is Theta(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 k0.5+k-β/ek. Finally, we conduct the first runtime analyses of the SMS-EMOA on the classic OMM and LOTZ 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.