We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Performance Analysis of Evolutionary Algorithms for Steiner Tree Problems.
- Authors
Xinsheng Lai; Yuren Zhou; Xiaoyun Xia; Qingfu Zhang
- 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 O(r(r + s - 1) · wmax ), where r, s, and wmax 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.
- Subjects
PROGRAMMING languages; EVOLUTIONARY algorithms; MACHINE learning; BIPARTITE graphs; STEINER systems
- Publication
Evolutionary Computation, 2017, Vol 25, Issue 4, p707
- ISSN
1063-6560
- Publication type
Article
- DOI
10.1162/EVCO_a_00200