{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T07:48:19Z","timestamp":1721634499153},"reference-count":27,"publisher":"MIT Press","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>We analyze the unbiased black-box complexities of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is [Formula: see text], that is, when only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values [Formula: see text] and n are blanked out, polynomial time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a [Formula: see text] fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not only by comparing the fitnesses of the competing search points but also by taking into account the (empirical) expected fitnesses of their offspring.<\/jats:p>","DOI":"10.1162\/evco_a_00158","type":"journal-article","created":{"date-parts":[[2015,7,2]],"date-time":"2015-07-02T14:23:56Z","timestamp":1435847036000},"page":"641-670","source":"Crossref","is-referenced-by-count":11,"title":["Unbiased Black-Box Complexities of Jump Functions"],"prefix":"10.1162","volume":"23","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carola","family":"Doerr","sequence":"additional","affiliation":[{"name":"CNRS and Sorbonne Universit\u00e9s, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"K\u00f6tzing","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Universit\u00e4t Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","first-page":"1","volume":"6238","author":"B\u00f6ttcher S.","year":"2010","journal-title":"Parallel Problem Solving from Nature"},{"key":"B2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-319-16468-7_18","volume":"9026","author":"Buzdalov M.","year":"2015","journal-title":"Evolutionary Computation in Combinatorial Optimization"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1142\/9789814282673_0001"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598359"},{"key":"B5","first-page":"567:87","author":"Doerr B.","year":"2015","journal-title":"Theoretical Computer Science"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598341"},{"key":"B7","first-page":"216:275","author":"Doerr B.","year":"2014","journal-title":"Artificial Intelligence"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1145\/1967654.1967669"},{"key":"B9","first-page":"471:84","author":"Doerr B.","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001851"},{"key":"B11","first-page":"441","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science","author":"Doerr B.","year":"2012"},{"key":"B12","first-page":"68:571","author":"Doerr B.","year":"2014","journal-title":"Algorithmica"},{"key":"B13","first-page":"545:108","author":"Doerr B.","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"B14","first-page":"276:51","author":"Droste S.","year":"2002","journal-title":"Theoretical Computer Science"},{"key":"B15","first-page":"39:525","author":"Droste S.","year":"2006","journal-title":"Theory of Computing Systems"},{"key":"B16","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":"B18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/2725494.2725507"},{"key":"B20","first-page":"34:47","author":"Jansen T.","year":"2002","journal-title":"Algorithmica"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830747"},{"key":"B22","first-page":"64:623","author":"Lehre P. K.","year":"2012","journal-title":"Algorithmica"},{"key":"B23","first-page":"26:350","author":"Panconesi A.","year":"1997","journal-title":"SIAM Journal on Computing"},{"key":"B24","first-page":"62:26","author":"Robbins H.","year":"1955","journal-title":"American Mathematical Monthly"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001850"},{"key":"B26","first-page":"17:418","author":"Sudholt D.","year":"2013","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"B27","first-page":"21","volume":"6238","author":"Teytaud O.","year":"2006","journal-title":"Parallel Problem Solving from Nature"},{"key":"B28","first-page":"22:294","author":"Witt C.","year":"2013","journal-title":"Combinatorics, Probability and Computing"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T23:28:12Z","timestamp":1691796492000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/23\/4\/641-670\/1029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1162\/EVCO_a_00158"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00158","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}