Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: On the benefits of biased edge-exchange mutation for the multi-criteria spanning tree problem
Author: Bossek, J.
Grimme, C.
Neumann, F.
Citation: GECCO '19: Proceedings of the 2019 Genetic and Evolutionary Computation Conference, 2019 / LopezIbanez, M. (ed./s), pp.516-523
Publisher: ACM
Publisher Place: New York
Issue Date: 2019
ISBN: 9781450361118
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (13 Jul 2019 - 17 Oct 2019 : Prague, Czech Republic)
Editor: LopezIbanez, M.
Abstract: 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.
Keywords: Multi-objective optimization, Combinatorial optimization, Minimum spanning tree, Biased mutation
Rights: © 2019 Copyright held by the owner/author(s). Publication rights licensed to Association for Computing Machinery.
DOI: 10.1145/3321707.3321818
Grant ID:
Appears in Collections:Aurora harvest 4
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.