Inexact Sorting in the USGS Operator for the Bi-Objective Minimum Spanning Tree Problem
Abstract
The minimum spanning tree problem (MST) is a well-studied optimisation problem on graphs with countless applications, e.g., in network design. Contrary to the classic MST, the multi-objective MST is intractable as the number of optimal trade-off solutions can grow exponentially with the number of nodes. Approaching
the problem with evolutionary algorithms showed good results in the past. Recently, Bossek & Grimme [3] introduced a general sub-graph based framework for mutation operator design; at the core a generalised version of Kruskal’s algorithm is used. Operators designed this way showed both excellent performance and fast convergence to the Pareto-front on a rich set of instances. However, those operators are rather time-consuming, as they include edge cost sorting during the built-in Kruskal step. We build upon this work and replace the exact sorting adopted in the USGS-F mutator – the best-performing operator – with i) linear-time sorting and ii) partial-sorting. Both methods improve the asymptotic worst-case runtime. Experiments show that both modifications perform similarly to the vanilla USGS-F with respect to performance indicators while confirming lower (empirical) running times.
Keywords
Combinatorial optimisation; multi-objective optimisation; minimum spanning tree problem; tailored mutation