title: Performance Analysis of Evolutionary Algorithms for Steiner Tree Problems.
abstract: The Steiner tree problem (STP) aims to determine some Steiner nodes such that the minimum spanning tree over these Steiner nodes and a given set of special nodes has the minimum weight, which is NP-hard. STP includes several important cases. The Steiner tree problem in graphs (GSTP) is one of them. Many heuristics have been proposed for STP, and some of them have proved to be performance guarantee approximation algorithms for this problem. Since evolutionary algorithms (EAs) are general and popular randomized heuristics, it is significant to investigate the performance of EAs for STP. Several empirical investigations have shown that EAs are efficient for STP. However, up to now, there is no theoretical work on the performance of EAs for STP. In this article, we reveal that the (1+1) EA achieves 3/2-approximation ratio for STP in a special class of quasi-bipartite graphs in expected runtime [Formula: see text], where [Formula: see text], [Formula: see text], and [Formula: see text] are, respectively, the number of Steiner nodes, the number of special nodes, and the largest weight among all edges in the input graph. We also show that the (1+1) EA is better than two other heuristics on two GSTP instances, and the (1+1) EA may be inefficient on a constructed GSTP instance.
authors.affiliation: School of Mathematics and Computer Science, Shangrao Normal University, Shangrao, 334001, China; School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510006, China xsl2011_jx@163.com.
authors.forename: Xinsheng
authors.initials: X
authors.lastname: Lai
authors.affiliation: School of Data and Computer Science, Sun Yat-sen University, Guangzhou, 510006, China yrzhou@scut.edu.cn.
authors.forename: Yuren
authors.initials: Y
authors.lastname: Zhou
authors.affiliation: College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing, 314001, China; School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510006, China scutxxy@gmail.com.
authors.forename: Xiaoyun
authors.initials: X
authors.lastname: Xia
authors.affiliation: Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR qingfu.zhang@cityu.edu.hk.
authors.forename: Qingfu
authors.initials: Q
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D036262:Empirical Research; D000066506:Heuristics
keywords: Steiner tree; approximation ratio; computational complexity; evolutionary algorithms; multi-objective