Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Runtime analysis of evolutionary diversity maximization for OneMinMax
Author: Doerr, B.
Gao, W.
Neumann, F.
Citation: Proceedings of the 2016 Genetic and Evolutionary Computation Conference, 2016 / pp.557-564
Publisher: Association for Computing Machinery
Issue Date: 2016
ISBN: 9781450342063
Conference Name: 2016 Genetic and Evolutionary Computation Conference (GECCO 2016) (20 Jul 2016 - 24 Jul 2016 : Denver, Colorado, USA)
Statement of
Benjamin Doerr, Wanru Gao, Frank Neumann
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.
Keywords: Evolutionary multi-objective optimization, diversity, runtime analysis, theory
Rights: © 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.
RMID: 0030055436
DOI: 10.1145/2908812.2908827
Grant ID:
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_109193.pdfRestricted Access951.8 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.