Population size matters: Rigorous runtime results for maximizing the hypervolume indicator

Evolutionary multi-objective optimization is one of the most successful areas in the field of evolutionary computation. Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multi-objective variants of the problems OneMax and LeadingOnes called OneMinMax and LOTZ, respectively, and investigate hypervolume-based algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OneMinMax for hypervolume-based evolutionary multi-objective algorithms, which is contrary to the results on their single-objective variants and the well-studied (1+1)(1+1) EA. Furthermore, we study multi-objective genetic programming using the hypervolume indicator. We show that the classical ORDER problem is easy to optimize if the population size is large enough to cover the whole Pareto front and point out situations where a small population size leads to an exponential optimization time.