Runtime analysis of evolutionary multi-objective algorithms optimising the degree and diameter of spanning trees

Abstract

Motivated by the telecommunication network design, we study the problem of finding diverse set of minimum spanning trees of a certain complete graph based on the two features which are maximum degree and diameter. In this study, we examine a simple multi-objective EA, GSEMO, in solving the two problems where we maximise or minimise the two features at the same time.With a rigorous runtime analysis, we provide understanding of how GSEMO optimize the set of minimum spanning trees in these two different feature spaces.