---
_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'
...