  In the area of evolutionary computation the calculation of diverse sets of
high-quality solutions to a given optimization problem has gained momentum in
recent years under the term evolutionary diversity optimization. Theoretical
insights into the working principles of baseline evolutionary algorithms for
diversity optimization are still rare. In this paper we study the well-known
Minimum Spanning Tree problem (MST) in the context of diversity optimization
where population diversity is measured by the sum of pairwise edge overlaps.
Theoretical results provide insights into the fitness landscape of the MST
diversity optimization problem pointing out that even for a population of
$\mu=2$ fitness plateaus (of constant length) can be reached, but nevertheless
diverse sets can be calculated in polynomial time. We supplement our
theoretical results with a series of experiments for the unconstrained and
constraint case where all solutions need to fulfill a minimal quality
threshold. Our results show that a simple $(\mu+1)$-EA can effectively compute
a diversified population of spanning trees of high quality.
