Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
Date
2023
Authors
Antipov, D.
Neumann, A.
Neumann, F.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2023), 2023, pp.3-14
Statement of Responsibility
Denis Antipov, Aneta Neumann, Frank Neumann
Conference Name
17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA) (30 Aug 2023 - 1 Sep 2023 : Potsdam, Germany)
Abstract
The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time O(n2), when the problem size n is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.