Performance Analysis on Evolutionary Algorithms for the Minimum Label Spanning Tree Problem

Abstract

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.

References in corpus (1)

• On the approximation ability of evolutionary optimization with application to minimum set cover

Cited by in corpus (6)

• A Theoretical Assessment of Solution Quality in Evolutionary Algorithms for the Knapsack Problem
• An Analytic Expression of Relative Approximation Error for a Class of Evolutionary Algorithms
• A Novel Genetic Algorithm using Helper Objectives for the 0-1 Knapsack Problem
• The Sampling-and-Learning Framework: A Statistical View of Evolutionary Algorithms
• Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem
• Error Analysis of Elitist Randomized Search Heuristics