Performance Analysis on Evolutionary Algorithms for the Minimum Label Spanning Tree Problem
This provides theoretical guarantees for EAs on a combinatorial optimization problem, addressing a gap in understanding for researchers in evolutionary computation and algorithm design, though it is incremental as it builds on prior experimental work.
The paper theoretically analyzes the performance of evolutionary algorithms (EAs) on the minimum label spanning tree (MLST) problem, showing that the (1+1) EA and GSEMO achieve approximation ratios of (b+1)/2 and 2ln(n) in expected polynomial times, and outperform local search algorithms on specific instances.
Some experimental investigations have shown that evolutionary algorithms (EAs) are efficient for the minimum label spanning tree (MLST) problem. However, we know little about that in theory. As one step towards this issue, we theoretically analyze the performances of the (1+1) EA, a simple version of EAs, and a multi-objective evolutionary algorithm called GSEMO on the MLST problem. We reveal that for the MLST$_{b}$ problem the (1+1) EA and GSEMO achieve a $\frac{b+1}{2}$-approximation ratio in expected polynomial times of $n$ the number of nodes and $k$ the number of labels. We also show that GSEMO achieves a $(2ln(n))$-approximation ratio for the MLST problem in expected polynomial time of $n$ and $k$. At the same time, we show that the (1+1) EA and GSEMO outperform local search algorithms on three instances of the MLST problem. We also construct an instance on which GSEMO outperforms the (1+1) EA.