Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives

Previous theory work on multi-objective evolutionary algorithms considers mostly easy problems that are composed of unimodal objectives. This paper takes a first step towards a deeper understanding of how evolutionary algorithms solve multi-modal multi-objective problems. We propose the ONEJumEZERoJumE problem, a bi-objective problem whose single objectives are isomorphic to the classic jump functions benchmark. We prove that the simple evolutionary multi-objective optimizer (SEMO) cannot compute the full Pareto front. In contrast, for all problem sizes n and all jump sizes k is an element of [4.. n/2- 1], the global SEMO (GSEMO) covers the Pareto front in circle minus((n - 2k)n(k)) iterations in expectation. To improve the performance, we combine the GSEMO with two approaches, a heavy-tailed mutation operator and a stagnation detection strategy, that showed advantages in single-objective multi-modal problems. Run-time improvements of asymptotic order at least k(Omega(k)) are shown for both strategies. Our experiments verify the substantial run-time gains already for moderate problem sizes. Overall, these results show that the ideas recently developed for single-objective evolutionary algorithms can be effectively employed also in multi-objective optimization.