Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Runtime analysis of evolutionary algorithms with biased mutation for the multi-objective minimum spanning tree problem
Author: Roostapour, V.
Bossek, J.
Neumann, F.
Citation: Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO'20), 2020, vol.abs/2004.10424, pp.551-559
Publisher: Association for Computing Machinery
Publisher Place: New York
Issue Date: 2020
ISBN: 9781450371285
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (8 Jul 2020 - 18 Jul 2020 : Cancun, Mexico)
Statement of
Vahid Roostapour, Jakob Bossek, Frank Neumann
Abstract: 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.
Keywords: Evolutionary algorithms; Minimum spanning tree problem; Runtime analysis; Biased mutation
Rights: © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM.
DOI: 10.1145/3377930.3390168
Grant ID:
Published version:
Appears in Collections:Aurora harvest 8
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.