{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T14:03:24Z","timestamp":1767967404413,"version":"3.49.0"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a function<jats:italic>f<\/jats:italic>: {0,1}<jats:italic><jats:sup>n<\/jats:sup><\/jats:italic>\u2192 \u211d. The algorithm starts with a random search point \u03be \u2208 {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>, and in each round it flips each bit of \u03be with probability<jats:italic>c<\/jats:italic>\/<jats:italic>n<\/jats:italic>independently at random, where<jats:italic>c<\/jats:italic>&gt; 0 is a fixed constant. The thus created offspring \u03be' replaces \u03be if and only if<jats:italic>f<\/jats:italic>(\u03be') \u2265<jats:italic>f<\/jats:italic>(\u03be). The analysis of the runtime of this simple algorithm for monotone and for linear functions turned out to be highly non-trivial. In this paper we review known results and provide new and self-contained proofs of partly stronger results.<\/jats:p>","DOI":"10.1017\/s0963548318000275","type":"journal-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T11:02:15Z","timestamp":1529492535000},"page":"643-666","source":"Crossref","is-referenced-by-count":49,"title":["Drift Analysis and Evolutionary Algorithms Revisited"],"prefix":"10.1017","volume":"27","author":[{"given":"J.","family":"LENGLER","sequence":"first","affiliation":[]},{"given":"A.","family":"STEGER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"S0963548318000275_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"},{"key":"S0963548318000275_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9387-z"},{"key":"S0963548318000275_ref15","unstructured":"M\u00fchlenbein H. (1992) How genetic algorithms really work: Mutation and hillclimbing. In PPSN 1992: 2nd International Conference on Parallel Problem Solving from Nature, Elsevier, pp. 15\u201326."},{"key":"S0963548318000275_ref11","doi-asserted-by":"crossref","unstructured":"Jansen T. (2007) On the brittleness of evolutionary algorithms. In FOGA 2007: 9th International Workshop on Foundations of Genetic Algorithms, Springer, pp. 54\u201369.","DOI":"10.1007\/978-3-540-73482-6_4"},{"key":"S0963548318000275_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9396-y"},{"key":"S0963548318000275_ref9","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000023417.31393.c7"},{"key":"S0963548318000275_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.048"},{"key":"S0963548318000275_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"S0963548318000275_ref3","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00055"},{"key":"S0963548318000275_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9585-3"},{"key":"S0963548318000275_ref1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195099713.001.0001","volume-title":"Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms","author":"B\u00e4ck","year":"1996"},{"key":"S0963548318000275_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00094-4"},{"key":"S0963548318000275_ref17","unstructured":"Oliveto P. S. and Witt C. (2012) Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation. arXiv:1211.7184"},{"key":"S0963548318000275_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0048-0"},{"key":"S0963548318000275_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"S0963548318000275_ref14","doi-asserted-by":"publisher","DOI":"10.1108\/17563780910959893"},{"key":"S0963548318000275_ref12","unstructured":"Johannsen D. (2010) Random combinatorial structures and randomized search heuristics. PhD thesis, Universit\u00e4t des Saarlandes."},{"key":"S0963548318000275_ref7","doi-asserted-by":"publisher","DOI":"10.2307\/1426671"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T00:47:01Z","timestamp":1661474821000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000275\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S0963548318000275"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000275","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,20]]}}}