A Pareto-Beneficial Sub-Tree Mutation for the Multi-Criteria Minimum Spanning Tree Problem

While finding minimum-cost spanning trees (MST) in undirected graphs is solvable in polynomial time, the multi-criteria minimum spanning tree problem (mcMST) is NP-hard. Interestingly, the mcMST problem has not been in focus of evolutionary computation research for a long period of time, although, its relevance for real world problems is easy to see. The available and most notable approaches by Zhou and Gen as well as by Knowles and Corne concentrate on solution encoding and on fairly dated selection mechanisms. In this work, we revisit the mcMST and focus on the mutation operators as exploratory components of evolutionary algorithms neglected so far. We investigate optimal solution characteristics to discuss current mutation strategies, identify shortcomings of these operators, and propose a sub-tree based operator which offers what we term Pareto-beneficial behavior: ensuring convergence and diversity at the same time. The operator is empirically evaluated inside modern standard evolutionary meta-heuristics for multi-criteria optimization and compared to hitherto applied mutation operators in the context of mcMST.