On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem

Evolutionary Computation, vol. 32, pp. 143–175

Abstract

We contribute to the efficient approximation of the Pareto-set for the classical NP-hard multiobjective minimum spanning tree problem (moMST) adopting evolutionary computation. More precisely, by building upon preliminary work, we analyze the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph. We prove runtime complexity results for the introduced operators and investigate the desirable Pareto-beneficial property. This property states that mutants cannot be dominated by their parent. Moreover, we perform an extensive experimental benchmark study to showcase the operator's practical suitability. Our results confirm that the sub-graph-based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs with different shapes of the Pareto-front.

Authors 2

1. Jakob Bossek corresponding Aachen Department of Computer Science AI Methodology

   RWTH Aachen University

   Affiliation as printed

   AI Methodology, Department of Computer Science, RWTH Aachen University, Germany bossek@aim.rwth-aachen.de

2. Christian Grimme corresponding

   University of Münster

   Affiliation as printed

   Statistics and Optimization, Department of Information Systems, University of Münster, Germany christian.grimme@wi.uni-muenster.de