Runtime analysis of evolutionary diversity maximization for OneMinMax

Abstract

Diversity mechanisms are key to the working behaviour of evolutionary multi-objective algorithms. With this paper, we contribute to the theoretical understanding of such mechanisms by means of rigorous runtime analysis. We consider the OneMinMax problem for which it has been shown in [11] that a standard benchmark algorithm called (mu+1)-SIBEA is not able to obtain a population with optimal hypervolume distribution in expected polynomial time if the population size is relatively small. We investigate the same setting as in [11] and show that (mu + 1)-SIBEA is able to achieve a good approximation of the optimal hypervolume distribution very efficiently. Furthermore, we study OneMinMax in the context of search-based diversity optimization and examine the time until (mu+1)-SIBEA with a search-based diversity mechanism has obtained a population of maximal diversity covering the whole Pareto front.