Initializing Multi-Objective Evolutionary Algorithms with the Optima of Each Objective

Multi-objective evolutionary algorithms (MOEAs) are among the most popular approaches to solve multi-objective optimization problems. In this work, we revisit a classic idea in multi-objective optimization, which is surprisingly little used in MOEAs, namely to start the optimization from the optima of the different objectives. The little theoretical previous work studying this idea in MOEAs has shown significant speed-ups for the theory-based GSEMO algorithm, but only together with a strong and non-standard diversity mechanism. In this work, we show that the GSEMO also profits from the initialization with the single-objective optima without additional non-standard mechanisms. We prove that this algorithm optimizes the OneMinMax and COCZ benchmarks in $O(n^{4/3}{\log }^{4/3}n)$ function evaluations, considerably faster than the classic $O(n^2\log n)$ runtime known from previous works. We extend this result to the NSGA-II, the most prominent MOEA in practice. Here this speed-up is obtained as soon as each single-objective optimum is contained once in the typically large initial population. These results constitute the first proof that initializing standard multi-objective evolutionary algorithms with the optima of the objectives can significantly improve their performance.