@inproceedings{48860,
  abstract     = {{In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of {$\mu$} = 2 fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple ({$\mu$} + 1)-EA can effectively compute a diversified population of spanning trees of high quality.}},
  author       = {{Bossek, Jakob and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-8350-9}},
  keywords     = {{evolutionary algorithms, evolutionary diversity optimization, minimum spanning tree, runtime analysis}},
  pages        = {{198–206}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem}}},
  doi          = {{10.1145/3449639.3459363}},
  year         = {{2021}},
}

@inproceedings{48895,
  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.}},
  author       = {{Roostapour, Vahid and Bossek, Jakob and Neumann, Frank}},
  booktitle    = {{Proceedings of the 2020 Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-7128-5}},
  keywords     = {{biased mutation, evolutionary algorithms, minimum spanning tree problem, runtime analysis}},
  pages        = {{551–559}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem}}},
  doi          = {{10.1145/3377930.3390168}},
  year         = {{2020}},
}

@inproceedings{48840,
  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.}},
  author       = {{Bossek, Jakob and Grimme, Christian and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-6111-8}},
  keywords     = {{biased mutation, combinatorial optimization, minimum spanning tree, multi-objective optimization}},
  pages        = {{516–523}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{On the Benefits of Biased Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem}}},
  doi          = {{10.1145/3321707.3321818}},
  year         = {{2019}},
}