Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem

Simple item page
dc.contributor.authorHarder, J.G.
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.conferenceInternational Conference on Parallel Problem Solving from Nature (PPSN) (14 Sep 2024 - 18 Sep 2024 : Hagenberg, Austria)
dc.contributor.editorAffenzeller, M.
dc.contributor.editorWinkler, S.M.
dc.contributor.editorKononova, A.V.
dc.contributor.editorTrautmann, H.
dc.contributor.editorTusar, T.
dc.contributor.editorMachado, P.
dc.contributor.editorBack, T.
dc.date.issued2024
dc.description.abstractThis paper delves into the enhancement of solution diversity in evolutionary algorithms (EAs) for the maximum matching problem, with a particular focus on complete bipartite graphs and paths. We utilize binary string encoding for matchings and employ Hamming distance as the metric for measuring diversity, aiming to maximize it. Central to our research is the (μ + 1)-EAD and 2P-EAD, applied for diversity optimization, which we rigorously analyze both theoretically and empirically. For complete bipartite graphs, our runtime analysis demonstrates that, for reasonably small μ, the (μ + 1)-EAD achieves maximal diversity with an expected runtime of O(μ2m4 log(m)) for the big gap case (where the population size μ is less than the difference in the sizes of the bipartite partitions) and O(μ2m2 log(m)) otherwise. For paths we give an upper bound of O(μ3m3). Additionally, for the 2P-EAD we give stronger performance bounds of O(μ2m2 log(m)) for the big gap case, O(μ2n2 log(n)) otherwise, and O(μ3m2) for paths. Here n is the total number of vertices and m the number of edges. Our empirical studies, examining the scaling behavior with respect to m and μ, complement these theoretical insights and suggest potential for further refinement of the runtime bounds.
dc.description.statementofresponsibilityJonathan Gadea Harder, Aneta Neumann, and Frank Neumann
dc.identifier.citationLecture Notes in Artificial Intelligence, 2024 / Affenzeller, M., Winkler, S.M., Kononova, A.V., Trautmann, H., Tusar, T., Machado, P., Back, T. (ed./s), vol.15150, pp.149-165
dc.identifier.doi10.1007/978-3-031-70071-2_10
dc.identifier.isbn978-3-031-70071-2
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttps://hdl.handle.net/2440/144265
dc.language.isoen
dc.publisherSpringer Nature
dc.publisher.placeCham, Switzerland
dc.relation.granthttp://purl.org/au-research/grants/arc/DP190103894
dc.relation.ispartofseriesLecture Notes in Computer Science; 15150
dc.rights© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024
dc.source.urihttps://link.springer.com/book/10.1007/978-3-031-70071-2
dc.titleAnalysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Research Outputs