  Evolutionary algorithms (EAs) are general-purpose problem solvers that
usually perform an unbiased search. This is reasonable and desirable in a
black-box scenario. For combinatorial optimization problems, often more
knowledge about the structure of optimal solutions is given, which can be
leveraged by means of biased search operators. We consider the Minimum Spanning
Tree (MST) problem in a single- and multi-objective version, and introduce a
biased mutation, which puts more emphasis on the selection of edges of low rank
in terms of low domination number. We present example graphs where the biased
mutation can significantly speed up the expected runtime until (Pareto-)optimal
solutions are found. On the other hand, we demonstrate that bias can lead to
exponential runtime if heavy edges are necessarily part of an optimal solution.
However, on general graphs in the single-objective setting, we show that a
combined mutation operator which decides for unbiased or biased edge selection
in each step with equal probability exhibits a polynomial upper bound -- as
unbiased mutation -- in the worst case and benefits from bias if the
circumstances are favorable.
