---
_id: '48860'
abstract:
- lang: eng
  text: 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 {$\mu$} = 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 ({$\mu$} + 1)-EA can effectively
    compute a diversified population of spanning trees of high quality.
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
citation:
  ama: 'Bossek J, Neumann F. Evolutionary Diversity Optimization and the Minimum Spanning
    Tree Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>.
    GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:<a href="https://doi.org/10.1145/3449639.3459363">10.1145/3449639.3459363</a>'
  apa: Bossek, J., &#38; Neumann, F. (2021). Evolutionary Diversity Optimization and
    the Minimum Spanning Tree Problem. <i>Proceedings of the Genetic and Evolutionary
    Computation Conference</i>, 198–206. <a href="https://doi.org/10.1145/3449639.3459363">https://doi.org/10.1145/3449639.3459363</a>
  bibtex: '@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO
    ’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree
    Problem}, DOI={<a href="https://doi.org/10.1145/3449639.3459363">10.1145/3449639.3459363</a>},
    booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
    publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
    Frank}, year={2021}, pages={198–206}, collection={GECCO ’21} }'
  chicago: 'Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization
    and the Minimum Spanning Tree Problem.” In <i>Proceedings of the Genetic and Evolutionary
    Computation Conference</i>, 198–206. GECCO ’21. New York, NY, USA: Association
    for Computing Machinery, 2021. <a href="https://doi.org/10.1145/3449639.3459363">https://doi.org/10.1145/3449639.3459363</a>.'
  ieee: 'J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum
    Spanning Tree Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation
    Conference</i>, 2021, pp. 198–206, doi: <a href="https://doi.org/10.1145/3449639.3459363">10.1145/3449639.3459363</a>.'
  mla: Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and
    the Minimum Spanning Tree Problem.” <i>Proceedings of the Genetic and Evolutionary
    Computation Conference</i>, Association for Computing Machinery, 2021, pp. 198–206,
    doi:<a href="https://doi.org/10.1145/3449639.3459363">10.1145/3449639.3459363</a>.
  short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
    Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp.
    198–206.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:37Z
department:
- _id: '819'
doi: 10.1145/3449639.3459363
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- minimum spanning tree
- runtime analysis
language:
- iso: eng
page: 198–206
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
  isbn:
  - 978-1-4503-8350-9
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’21
status: public
title: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
type: conference
user_id: '102979'
year: '2021'
...