---
_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: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:10.1145/3449639.3459363'
apa: Bossek, J., & Neumann, F. (2021). Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem. Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. https://doi.org/10.1145/3449639.3459363
bibtex: '@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO
’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem}, DOI={10.1145/3449639.3459363},
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 Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. GECCO ’21. New York, NY, USA: Association
for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459363.'
ieee: 'J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum
Spanning Tree Problem,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2021, pp. 198–206, doi: 10.1145/3449639.3459363.'
mla: Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 198–206,
doi:10.1145/3449639.3459363.
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'
...
---
_id: '48895'
abstract:
- lang: eng
text: Evolutionary algorithms (EAs) are general-purpose problem solvers that usually
perform an unbiased search. This is reasonable and desirable in a black-box scenario.
For combinatorial optimization problems, often more knowledge about the structure
of optimal solutions is given, which can be leveraged by means of biased search
operators. We consider the Minimum Spanning Tree (MST) problem in a single- and
multi-objective version, and introduce a biased mutation, which puts more emphasis
on the selection of edges of low rank in terms of low domination number. We present
example graphs where the biased mutation can significantly speed up the expected
runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate
that bias can lead to exponential runtime if "heavy" edges are necessarily part
of an optimal solution. However, on general graphs in the single-objective setting,
we show that a combined mutation operator which decides for unbiased or biased
edge selection in each step with equal probability exhibits a polynomial upper
bound - as unbiased mutation - in the worst case and benefits from bias if the
circumstances are favorable.
author:
- first_name: Vahid
full_name: Roostapour, Vahid
last_name: Roostapour
- 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: 'Roostapour V, Bossek J, Neumann F. Runtime Analysis of Evolutionary Algorithms
with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. In:
Proceedings of the 2020 Genetic and Evolutionary Computation Conference.
{GECCO} ’20. Association for Computing Machinery; 2020:551–559. doi:10.1145/3377930.3390168'
apa: Roostapour, V., Bossek, J., & Neumann, F. (2020). Runtime Analysis of Evolutionary
Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree
Problem. Proceedings of the 2020 Genetic and Evolutionary Computation Conference,
551–559. https://doi.org/10.1145/3377930.3390168
bibtex: '@inproceedings{Roostapour_Bossek_Neumann_2020, place={New York, NY, USA},
series={{GECCO} ’20}, title={Runtime Analysis of Evolutionary Algorithms with
Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem}, DOI={10.1145/3377930.3390168}, booktitle={Proceedings
of the 2020 Genetic and Evolutionary Computation Conference}, publisher={Association
for Computing Machinery}, author={Roostapour, Vahid and Bossek, Jakob and Neumann,
Frank}, year={2020}, pages={551–559}, collection={{GECCO} ’20} }'
chicago: 'Roostapour, Vahid, Jakob Bossek, and Frank Neumann. “Runtime Analysis
of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum
Spanning Tree Problem.” In Proceedings of the 2020 Genetic and Evolutionary
Computation Conference, 551–559. {GECCO} ’20. New York, NY, USA: Association
for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390168.'
ieee: 'V. Roostapour, J. Bossek, and F. Neumann, “Runtime Analysis of Evolutionary
Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree
Problem,” in Proceedings of the 2020 Genetic and Evolutionary Computation Conference,
2020, pp. 551–559, doi: 10.1145/3377930.3390168.'
mla: Roostapour, Vahid, et al. “Runtime Analysis of Evolutionary Algorithms with
Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” Proceedings
of the 2020 Genetic and Evolutionary Computation Conference, Association for
Computing Machinery, 2020, pp. 551–559, doi:10.1145/3377930.3390168.
short: 'V. Roostapour, J. Bossek, F. Neumann, in: Proceedings of the 2020 Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2020, pp. 551–559.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:38Z
department:
- _id: '819'
doi: 10.1145/3377930.3390168
extern: '1'
keyword:
- biased mutation
- evolutionary algorithms
- minimum spanning tree problem
- runtime analysis
language:
- iso: eng
page: 551–559
place: New York, NY, USA
publication: Proceedings of the 2020 Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-7128-5
publisher: Association for Computing Machinery
series_title: '{GECCO} ’20'
status: public
title: Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective
Minimum Spanning Tree Problem
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48840'
abstract:
- lang: eng
text: Research has shown that for many single-objective graph problems where optimum
solutions are composed of low weight sub-graphs, such as the minimum spanning
tree problem (MST), mutation operators favoring low weight edges show superior
performance. Intuitively, similar observations should hold for multi-criteria
variants of such problems. In this work, we focus on the multi-criteria MST problem.
A thorough experimental study is conducted where we estimate the probability of
edges being part of non-dominated spanning trees as a function of the edges’ non-domination
level or domination count, respectively. Building on gained insights, we propose
several biased one-edge-exchange mutation operators that differ in the used edge-selection
probability distribution (biased towards edges of low rank). Our empirical analysis
shows that among different graph types (dense and sparse) and edge weight types
(both uniformly random and combinations of Euclidean and uniformly random) biased
edge-selection strategies perform superior in contrast to the baseline uniform
edge-selection. Our findings are in particular strong for dense graphs.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Christian
full_name: Grimme, Christian
last_name: Grimme
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Grimme C, Neumann F. On the Benefits of Biased Edge-Exchange Mutation
for the Multi-Criteria Spanning Tree Problem. In: Proceedings of the Genetic
and Evolutionary Computation Conference. GECCO ’19. Association for Computing
Machinery; 2019:516–523. doi:10.1145/3321707.3321818'
apa: Bossek, J., Grimme, C., & Neumann, F. (2019). On the Benefits of Biased
Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem. Proceedings
of the Genetic and Evolutionary Computation Conference, 516–523. https://doi.org/10.1145/3321707.3321818
bibtex: '@inproceedings{Bossek_Grimme_Neumann_2019, place={New York, NY, USA}, series={GECCO
’19}, title={On the Benefits of Biased Edge-Exchange Mutation for the Multi-Criteria
Spanning Tree Problem}, DOI={10.1145/3321707.3321818},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Grimme,
Christian and Neumann, Frank}, year={2019}, pages={516–523}, collection={GECCO
’19} }'
chicago: 'Bossek, Jakob, Christian Grimme, and Frank Neumann. “On the Benefits of
Biased Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem.” In
Proceedings of the Genetic and Evolutionary Computation Conference, 516–523.
GECCO ’19. New York, NY, USA: Association for Computing Machinery, 2019. https://doi.org/10.1145/3321707.3321818.'
ieee: 'J. Bossek, C. Grimme, and F. Neumann, “On the Benefits of Biased Edge-Exchange
Mutation for the Multi-Criteria Spanning Tree Problem,” in Proceedings of the
Genetic and Evolutionary Computation Conference, 2019, pp. 516–523, doi: 10.1145/3321707.3321818.'
mla: Bossek, Jakob, et al. “On the Benefits of Biased Edge-Exchange Mutation for
the Multi-Criteria Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2019, pp. 516–523,
doi:10.1145/3321707.3321818.
short: 'J. Bossek, C. Grimme, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2019, pp. 516–523.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:42:24Z
department:
- _id: '819'
doi: 10.1145/3321707.3321818
extern: '1'
keyword:
- biased mutation
- combinatorial optimization
- minimum spanning tree
- multi-objective optimization
language:
- iso: eng
page: 516–523
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-6111-8
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’19
status: public
title: On the Benefits of Biased Edge-Exchange Mutation for the Multi-Criteria Spanning
Tree Problem
type: conference
user_id: '102979'
year: '2019'
...