Performance analysis of evolutionary algorithms for the minimum label spanning tree problem

Lai, X., Zhou, Y., He, J. ORCID: 0000-0002-5616-4691 and Zhang, J., 2014. Performance analysis of evolutionary algorithms for the minimum label spanning tree problem. IEEE Transactions on Evolutionary Computation, 18 (6), pp. 860-872. ISSN 1089-778X

[img]
Preview
Text
13639_He.pdf - Post-print

Download (2MB) | Preview

Abstract

A few 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. In this paper, we theoretically analyze the performances of the (1+1) EA, a simple version of EA, and a simple multiobjective evolutionary algorithm called GSEMO on the MLST problem. We reveal that for the MLSTb problem, the (1+1) EA and GSEMO achieve a (b + 1)/2-approximation ratio in expected polynomial runtime with respect to n, the number of nodes, and k, the number of labels. We also find that GSEMO achieves a (2 lnn+1)-approximation ratio for the MLST problem in expected polynomial runtime with respect to 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.

Item Type: Journal article
Publication Title: IEEE Transactions on Evolutionary Computation
Creators: Lai, X., Zhou, Y., He, J. and Zhang, J.
Publisher: Institute of Electrical and Electronics Engineers
Date: 2014
Volume: 18
Number: 6
ISSN: 1089-778X
Identifiers:
NumberType
10.1109/tevc.2013.2291790DOI
Divisions: Schools > School of Science and Technology
Depositing User: Jonathan Gallacher
Date Added: 22 Mar 2019 09:58
Last Modified: 22 Mar 2019 09:58
URI: http://irep.ntu.ac.uk/id/eprint/36134

Actions (login required)

Edit View Edit View

Views

Views per month over past year

Downloads

Downloads per month over past year