Current studentsExisting staffContact us
 

Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax

Simple item page
dc.contributor.authorAntipov, D.
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.conference17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA) (30 Aug 2023 - 1 Sep 2023 : Potsdam, Germany)
dc.date.issued2023
dc.description.abstractThe 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.
dc.description.statementofresponsibilityDenis Antipov, Aneta Neumann, Frank Neumann
dc.identifier.citationProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2023), 2023, pp.3-14
dc.identifier.doi10.1145/3594805.3607135
dc.identifier.isbn9798400702020
dc.identifier.orcidAntipov, D. [0000-0001-7906-096X]
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttps://hdl.handle.net/2440/148458
dc.language.isoen
dc.publisherAssociation for Computing Machinery (ACM)
dc.relation.granthttp://purl.org/au-research/grants/arc/DP190103894
dc.relation.granthttp://purl.org/au-research/grants/arc/FT200100536
dc.rights© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
dc.source.urihttps://dl.acm.org/doi/proceedings/10.1145/3594805
dc.subjectDiversity optimization; multi-objective optimization; theory; runtime analysis
dc.titleRigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Research Outputs