@inproceedings{e32503f1f192446cb3a859da02d200b1,
title = "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 (μ+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 (μ + 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 (μ+1)-SIBEA with a search-based diversity mechanism has obtained a population of maximal diversity covering the whole Pareto front.",
keywords = "Diversity, Evolutionary multi-objective optimization, Runtime analysis, Theory",
author = "Benjamin Doerr and Wanru Gao and Frank Neumann",
year = "2016",
month = jul,
day = "20",
doi = "10.1145/2908812.2908827",
language = "English",
series = "GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery, Inc",
pages = "557--564",
editor = "Tobias Friedrich",
booktitle = "GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference",
note = "2016 Genetic and Evolutionary Computation Conference, GECCO 2016 ; Conference date: 20-07-2016 Through 24-07-2016",
}