---
_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:
    <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>.
    {GECCO} ’20. Association for Computing Machinery; 2020:551–559. doi:<a href="https://doi.org/10.1145/3377930.3390168">10.1145/3377930.3390168</a>'
  apa: Roostapour, V., Bossek, J., &#38; Neumann, F. (2020). Runtime Analysis of Evolutionary
    Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree
    Problem. <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>,
    551–559. <a href="https://doi.org/10.1145/3377930.3390168">https://doi.org/10.1145/3377930.3390168</a>
  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={<a
    href="https://doi.org/10.1145/3377930.3390168">10.1145/3377930.3390168</a>}, 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 <i>Proceedings of the 2020 Genetic and Evolutionary
    Computation Conference</i>, 551–559. {GECCO} ’20. New York, NY, USA: Association
    for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3377930.3390168">https://doi.org/10.1145/3377930.3390168</a>.'
  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 <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>,
    2020, pp. 551–559, doi: <a href="https://doi.org/10.1145/3377930.3390168">10.1145/3377930.3390168</a>.'
  mla: Roostapour, Vahid, et al. “Runtime Analysis of Evolutionary Algorithms with
    Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” <i>Proceedings
    of the 2020 Genetic and Evolutionary Computation Conference</i>, Association for
    Computing Machinery, 2020, pp. 551–559, doi:<a href="https://doi.org/10.1145/3377930.3390168">10.1145/3377930.3390168</a>.
  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: <i>Proceedings of the Genetic
    and Evolutionary Computation Conference</i>. GECCO ’19. Association for Computing
    Machinery; 2019:516–523. doi:<a href="https://doi.org/10.1145/3321707.3321818">10.1145/3321707.3321818</a>'
  apa: Bossek, J., Grimme, C., &#38; Neumann, F. (2019). On the Benefits of Biased
    Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem. <i>Proceedings
    of the Genetic and Evolutionary Computation Conference</i>, 516–523. <a href="https://doi.org/10.1145/3321707.3321818">https://doi.org/10.1145/3321707.3321818</a>
  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={<a href="https://doi.org/10.1145/3321707.3321818">10.1145/3321707.3321818</a>},
    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
    <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 516–523.
    GECCO ’19. New York, NY, USA: Association for Computing Machinery, 2019. <a href="https://doi.org/10.1145/3321707.3321818">https://doi.org/10.1145/3321707.3321818</a>.'
  ieee: 'J. Bossek, C. Grimme, and F. Neumann, “On the Benefits of Biased Edge-Exchange
    Mutation for the Multi-Criteria Spanning Tree Problem,” in <i>Proceedings of the
    Genetic and Evolutionary Computation Conference</i>, 2019, pp. 516–523, doi: <a
    href="https://doi.org/10.1145/3321707.3321818">10.1145/3321707.3321818</a>.'
  mla: Bossek, Jakob, et al. “On the Benefits of Biased Edge-Exchange Mutation for
    the Multi-Criteria Spanning Tree Problem.” <i>Proceedings of the Genetic and Evolutionary
    Computation Conference</i>, Association for Computing Machinery, 2019, pp. 516–523,
    doi:<a href="https://doi.org/10.1145/3321707.3321818">10.1145/3321707.3321818</a>.
  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'
...