{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T06:15:42Z","timestamp":1780467342861,"version":"3.54.1"},"reference-count":35,"publisher":"MIT Press","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>Black-box complexity theory provides lower bounds for the runtime of black-box optimizers like evolutionary algorithms and other search heuristics and serves as an inspiration for the design of new genetic algorithms. Several black-box models covering different classes of algorithms exist, each highlighting a different aspect of the algorithms under considerations. In this work we add to the existing black-box notions a new elitist black-box model, in which algorithms are required to base all decisions solely on (the relative performance of) a fixed number of the best search points sampled so far. Our elitist model thus combines features of the ranking-based and the memory-restricted black-box models with an enforced usage of truncation selection. We provide several examples for which the elitist black-box complexity is exponentially larger than that of the respective complexities in all previous black-box models, thus showing that the elitist black-box complexity can be much closer to the runtime of typical evolutionary algorithms. We also introduce the concept of p-Monte Carlo black-box complexity, which measures the time it takes to optimize a problem with failure probability at most p. Even for small\u00a0 p, the p-Monte Carlo black-box complexity of a function class [Formula: see text] can be smaller by an exponential factor than its typically regarded Las Vegas complexity (which measures the expected time it takes to optimize [Formula: see text]).<\/jats:p>","DOI":"10.1162\/evco_a_00195","type":"journal-article","created":{"date-parts":[[2016,10,4]],"date-time":"2016-10-04T19:49:23Z","timestamp":1475610563000},"page":"587-606","source":"Crossref","is-referenced-by-count":21,"title":["Introducing Elitist Black-Box Models: When Does Elitist Behavior Weaken the Performance of Evolutionary Algorithms?"],"prefix":"10.1162","volume":"25","author":[{"given":"Carola","family":"Doerr","sequence":"first","affiliation":[{"name":"CNRS and Sorbonne Universit\u00e9s, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Department of Computer Science, Institute for Theoretical Computer Science, 8092 Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1527125.1527135","author":"Anil G.","year":"2009","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1142\/7438"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_88"},{"key":"B5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2725494.2725504","author":"Badkobeh G.","year":"2015","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"B7","first-page":"45:35:1","author":"\u010crepin\u0161ek M.","year":"2013","journal-title":"ACM Computing Surveys"},{"key":"B8","first-page":"567:87","author":"Doerr B.","year":"2015","journal-title":"Theoretical Computer Science"},{"key":"B9","first-page":"769","author":"Doerr B.","year":"2014","journal-title":"Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201914)"},{"key":"B10","first-page":"216:275","author":"Doerr B.","year":"2014","journal-title":"Artificial Intelligence"},{"key":"B11","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/1967654.1967669","author":"Doerr B.","year":"2011","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"B12","first-page":"471:84","author":"Doerr B.","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"B13","first-page":"2043","author":"Doerr B.","year":"2011","journal-title":"Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201911)"},{"key":"B14","first-page":"55:658","author":"Doerr B.","year":"2014","journal-title":"Theory of Computing Systems"},{"key":"B15","first-page":"68:571","author":"Doerr B.","year":"2014","journal-title":"Algorithmica"},{"key":"B16","first-page":"545:108","author":"Doerr B.","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"B17","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1145\/2739480.2754654","author":"Doerr C.","year":"2015","journal-title":"Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201915)"},{"key":"B18","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1145\/2739480.2754678","author":"Doerr C.","year":"2015","journal-title":"Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201915)"},{"key":"B19","first-page":"253","author":"Droste S.","year":"2003","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"B20","first-page":"276:51","author":"Droste S.","year":"2002","journal-title":"Theoretical Computer Science"},{"key":"B21","first-page":"39:525","author":"Droste S.","year":"2006","journal-title":"Theory of Computing Systems"},{"key":"B22","first-page":"8:229","author":"Erd\u00f6s P.","year":"1963","journal-title":"Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet K\u00f6zlem\u00e9nyei"},{"key":"B23","first-page":"59:387","author":"Fournier H.","year":"2011","journal-title":"Algorithmica"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2009.17.4.17401"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1145\/1389095.1389277"},{"key":"B26","first-page":"25","author":"J\u00e4gersk\u00fcpper J.","year":"2007","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computational Intelligence"},{"key":"B27","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/2725494.2725507","author":"Jansen T","year":"2015","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"B28","first-page":"64:623","author":"Lehre P. K.","year":"2012","journal-title":"Algorithmica"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1145\/1569901.1570016"},{"key":"B30","first-page":"545:2","author":"Oliveto P. S.","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.028"},{"key":"B32","first-page":"2035","author":"Rowe J.","year":"2011","journal-title":"Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201911)"},{"key":"B33","first-page":"21","volume":"4193","author":"Teytaud O.","year":"2006","journal-title":"Proceedings of Parallel Problem Solving from Nature"},{"key":"B34","first-page":"462","volume":"2439","author":"Ursem R. K.","year":"2002","journal-title":"Proceedings of Parallel Problem Solving from Nature"},{"key":"B35","first-page":"627","volume":"4448","author":"Yang S.","year":"2007","journal-title":"Proceedings of Applications of Evolutionary Computing, EvoWorkshops 2007"},{"key":"B36","first-page":"222","author":"Yao A. C.-C","year":"1977","journal-title":"Proceedings of Foundations of Computer Science"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/evco_a_00195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T09:55:20Z","timestamp":1692525320000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/25\/4\/587-606\/1061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1162\/evco_a_00195"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00195","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}