{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T15:27:14Z","timestamp":1759937234659},"reference-count":43,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1162\/evco_a_00200","type":"journal-article","created":{"date-parts":[[2016,12,13]],"date-time":"2016-12-13T19:48:41Z","timestamp":1481658521000},"page":"707-723","source":"Crossref","is-referenced-by-count":9,"title":["Performance Analysis of Evolutionary Algorithms for Steiner Tree Problems"],"prefix":"10.1162","volume":"25","author":[{"given":"Xinsheng","family":"Lai","sequence":"first","affiliation":[{"name":"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"}]},{"given":"Yuren","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Data and Computer Science, Sun Yat-sen University, Guangzhou, 510006, China"}]},{"given":"Xiaoyun","family":"Xia","sequence":"additional","affiliation":[{"name":"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"}]},{"given":"Qingfu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2008.2012167"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.016"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"B6","first-page":"170","author":"Chlebik M.","year":"2002","journal-title":"Proceedings of the 8th Scandinavian Workshop on Algorithm Theory"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"B8","first-page":"425:17","author":"Doerr B.","year":"2012","journal-title":"Theoretical Computer Science"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00003"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"B12","first-page":"415","author":"Giel O.","year":"2003","journal-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science"},{"key":"B13","first-page":"272","author":"Haghighat A. T.","year":"2002","journal-title":"Proceedings of the First EurAsian Conference on Information and Communication Technology"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00381-8"},{"key":"B16","first-page":"231","author":"Hesser J.","year":"1989","journal-title":"Proceedings of the 3rd International Conference on Genetic Algorithms"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220105"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666921"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/2460239.2460248"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1109\/4235.974841"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1993.69"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.08.005"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.12.009"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9370-8"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.002"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2009.2014362"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"B29","first-page":"559","author":"Pr\u00f6mel H. J.","year":"1997","journal-title":"Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science"},{"key":"B30","first-page":"204:99","author":"Qian C.","year":"2013","journal-title":"Artificial Intelligence"},{"key":"B31","volume-title":"Genetic algorithms and genetic programming at Stanford 2002","author":"Rabkin M.","year":"2002"},{"key":"B32","first-page":"742","author":"Rajagopalan S.","year":"1999","journal-title":"Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1080\/0020739830140103"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00210-2"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"issue":"14","key":"B36","author":"Sadeghi A.","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"B37","first-page":"1105","author":"Sutton A. M.","year":"2012","journal-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence"},{"issue":"6","key":"B38","first-page":"573","volume":"24","author":"Takahashi H.","year":"1980","journal-title":"Mathematica Japonica"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00192-9"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90225-6"},{"key":"B41","first-page":"44","author":"Witt C","year":"2005","journal-title":"Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science"},{"key":"B42","first-page":"180-181:20","author":"Yu Y.","year":"2012","journal-title":"Artificial Intelligence"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.11.002"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/evco_a_00200","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:54Z","timestamp":1615586334000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/25\/4\/707-723\/1057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1162\/evco_a_00200"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00200","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}