Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/134974
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem |
Author: | Bossek, J. Neumann, F. |
Citation: | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2021), 2021, vol.abs/2010.10913, pp.198-206 |
Publisher: | Association for Computing Machinery |
Publisher Place: | New York, United States |
Issue Date: | 2021 |
ISBN: | 9781450383509 |
Conference Name: | Genetic and Evolutionary Computation Conference (GECCO) (10 Jul 2021 - 14 Jul 2021 : Lille, France) |
Statement of Responsibility: | Jakob Bossek, Frank Neumann |
Abstract: | In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of µ = 2 fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple (µ + 1)-EA can effectively compute a diversified population of spanning trees of high quality. |
Keywords: | Evolutionary algorithms; evolutionary diversity optimization; runtime analysis; minimum spanning tree |
Rights: | © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. |
DOI: | 10.1145/3449639.3459363 |
Grant ID: | http://purl.org/au-research/grants/arc/DP190103894 |
Published version: | http://dx.doi.org/10.1145/3449639.3459363 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.