Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
This work addresses runtime efficiency for evolutionary algorithms in combinatorial optimization, but it is incremental as it builds on existing methods with specific theoretical analysis.
The paper tackles the problem of optimizing evolutionary algorithms for the Minimum Spanning Tree problem by introducing a biased mutation operator that emphasizes edges with low domination number, showing it can speed up runtime in some cases but cause exponential slowdown in others, and proving a polynomial worst-case bound for a combined operator in single-objective settings.
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.