Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Runtime analysis of evolutionary algorithms with biased mutation for the multi-objective minimum spanning tree problem|
|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|
|Conference Name:||Genetic and Evolutionary Computation Conference (GECCO) (08 Jul 2020 - 18 Jul 2020 : Cancun, Mexico)|
|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.|
|Appears in Collections:||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.