Generalised Kruskal Mutation for the Multi-Objective Minimum Spanning Tree Problem

Bossek J; Grimme C

Abstract

Approximating the Pareto-set of the multi-objective minimum spanning tree problem (moMST) is a challenging task, which was tackled multiple times over the last decades, also by applying evolutionary approaches. A very recent work introduced two novel and strongly problem-tailored sub-graph based mutation operators embedded in NSGA-II. The authors show that these operators excel on a large set of problem instances in terms of convergence speed and approximation quality. Essentially, these operators replace sub-trees of solution candidates by applying Kruskal's well-known MST algorithm to a sub-graph of the input graph reduced to scalar edge weights via weighted-sum scalarisation. This work changes the perspective on the working principle of these operators and proposes a more general construction framework. We show that the before mentioned operators can be embedded into this framework, which 'rewires' sub-trees using a generalisation of Kruskal's algorithm. Additionally, we introduce several improvements to the operators reducing their running time significantly without deteriorating their effectiveness, introduce a novel mutation operator, which utilises the framework in an insertion-first approach (contrary to the other operators), and derive theoretical runtime bounds for all considered operators. A short benchmark study demonstrates the effectiveness of the introduced approach.

Keywords
evolutionary algorithms, multi-objective optimisation, tailored mutation operators, minimum spanning tree problem