{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:47Z","timestamp":1777596107596,"version":"3.51.4"},"reference-count":37,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> We give a detailed analysis of the optimization time of the [Formula: see text]-Evolutionary Algorithm under two simple fitness functions (OneMax and LeadingOnes). The problem has been approached in the evolutionary algorithm literature in various ways and with different degrees of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is based on an asymptotic resolution of the underlying recurrences and can also be extended to characterize the corresponding limiting distributions. While most of our approximations can be derived by simple heuristic calculations based on the idea of matched asymptotics, the rigorous justifications are challenging and require a delicate error analysis. <\/jats:p>","DOI":"10.1162\/evco_a_00212","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T18:52:49Z","timestamp":1497984769000},"page":"299-345","source":"Crossref","is-referenced-by-count":20,"title":["Probabilistic Analysis of the (1+1)-Evolutionary Algorithm"],"prefix":"10.1162","volume":"26","author":[{"given":"Hsien-Kuei","family":"Hwang","sequence":"first","affiliation":[{"name":"Institute of Statistical Science & Institute of Information Science, Academia Sinica, Taipei 115, Taiwan"}]},{"given":"Alois","family":"Panholzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Diskrete Mathematik und Geometrie, Technische      Universit\u00e4t Wien, Wiedner Hauptstra\u00dfe 8-10\/104, 1040 Wien, Austria"}]},{"given":"Nicolas","family":"Rolin","sequence":"additional","affiliation":[{"name":"LIPN, Institut Galil\u00e9e, Universit\u00e9 Paris 13, 93430, Villetaneuse,      France"}]},{"given":"Tsung-Hsi","family":"Tsai","sequence":"additional","affiliation":[{"name":"Institute of Statistical Science, Academia Sinica, Taipei 115, Taiwan"}]},{"given":"Wei-Mei","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Electronic and Computer Engineering, National Taiwan University of      Science and Technology, Taipei 106, Taiwan"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1142\/7438"},{"key":"B2","first-page":"85","volume-title":"Parallel Problem Solving from Nature","author":"B\u00e4ck T","year":"1992"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00137-8"},{"key":"B4","first-page":"1","volume":"6238","author":"B\u00f6ttcher S.","year":"2010","journal-title":"Parallel Problem Solving from Nature"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2006.1597059"},{"key":"B6","volume-title":"Asymptotic methods in analysis","author":"de Bruijn N. G","year":"1981","edition":"3"},{"key":"B7","volume-title":"Multi-objective optimization using evolutionary algorithms","author":"Deb K","year":"2001"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598359"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1145\/2463372.2463480"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830749"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Doerr, B.,         Fouz, M., and         Witt,\n      C. (2011).       Sharp bounds by probability-generating functions and variable       drift. In Genetic and Evolutionary Computation (GECCO        2011), pp. 2083\u20132090.       ACM Press.","DOI":"10.1145\/2001576.2001856"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586097"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"B14","first-page":"1","author":"Doerr C.","year":"2016","journal-title":"Algorithmica"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1998.700079"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1999.7.2.173"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2002.800886"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00381-8"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1887\/0750308958\/b386c85"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0179"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1110381369"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13075-0_54"},{"key":"B26","first-page":"15","volume-title":"Parallel Problem Solving from Nature","author":"M\u00fchlenbein H","year":"1992"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9134-2"},{"key":"B28","volume-title":"Bioinspired computation in combinatorial optimization\u2014Algorithms and their computational complexity","author":"Neumann F.","year":"2010"},{"key":"B29","first-page":"1063","volume-title":"Handbook of combinatorics","volume":"1","author":"Odlyzko A. M.","year":"1995"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15844-5_13"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2012.2202241"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.002"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511802256"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.013"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1142\/S0219530514500286"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.010"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/evco_a_00212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:57Z","timestamp":1615586337000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/26\/2\/299-345\/1203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1162\/evco_a_00212"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00212","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}