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

Bossek J; Grimme C


Zusammenfassung

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.

Schlüsselwörter
evolutionary algorithms, multi-objective optimisation, tailored mutation operators, minimum spanning tree problem



Publikationstyp
Forschungsartikel in Sammelband (Konferenz)

Begutachtet
Ja

Publikationsstatus
Veröffentlicht

Jahr
2024

Konferenz
Genetic and Evolutionary Computation Conference

Konferenzort
Melbourne

Buchtitel
Proceedings of the Genetic and Evolutionary Computation Conference

Herausgeber
Xiaodong Li; Julia Handl

Erste Seite
133–141

Letzte Seite
133–141

Reihe
GECCO '24

Verlag
Association for Computing Machinery

Ort
New York, NY, USA

ISBN
9798400704949

DOI

Gesamter Text