{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:59Z","timestamp":1759638299920,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030581145"},{"type":"electronic","value":"9783030581152"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-58115-2_42","type":"book-chapter","created":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T22:02:51Z","timestamp":1598997771000},"page":"604-618","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Lower Bounds for Non-elitist Evolutionary Algorithms via Negative Multiplicative Drift"],"prefix":"10.1007","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,2]]},"reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Fang, J., Hetet, T.: Runtime analysis for the $${(\\mu +\\lambda )}$$ EA optimizing OneMax. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1459\u20131466. ACM (2018)","DOI":"10.1145\/3205455.3205627"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Yang, Q.: The efficiency threshold for the offspring population size of the $${(\\mu ,\\lambda )}$$ EA. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1461\u20131469. ACM (2019)","DOI":"10.1145\/3321707.3321838"},{"key":"42_CR3","doi-asserted-by":"publisher","first-page":"1092","DOI":"10.1109\/TSMCB.2008.2012167","volume":"39","author":"T Chen","year":"2009","unstructured":"Chen, T., He, J., Sun, G., Chen, G., Yao, X.: A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. IEEE Trans. Syst. Man Cybern. Part B 39, 1092\u20131106 (2009)","journal-title":"IEEE Trans. Syst. Man Cybern. Part B"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Dang, D., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evol. Comput. 22, 707\u2013719 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","volume":"75","author":"D Dang","year":"2016","unstructured":"Dang, D., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75, 428\u2013461 (2016)","journal-title":"Algorithmica"},{"key":"42_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/978-3-319-45823-6_75","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN XIV","author":"D-C Dang","year":"2016","unstructured":"Dang, D.-C., Lehre, P.K.: Self-adaptation of mutation rates in non-elitist populations. In: Handl, J., Hart, E., Lewis, P.R., L\u00f3pez-Ib\u00e1\u00f1ez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 803\u2013813. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-45823-6_75"},{"key":"42_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","volume":"773","author":"B Doerr","year":"2019","unstructured":"Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theoret. Comput. Sci. 773, 115\u2013137 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B.: An exponential lower bound for the runtime of the compact genetic algorithm on jump functions. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 25\u201333. ACM (2019)","DOI":"10.1145\/3299904.3340304"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Does comma selection help to cope with local optima? In: Genetic and Evolutionary Computation Conference, GECCO 2020. ACM (2020, to appear)","DOI":"10.1145\/3377930.3389823"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Lower bounds for non-elitist evolutionary algorithms via negative multiplicative drift. CoRR abs\/2004.01274 (2020)","DOI":"10.1162\/evco_a_00283"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Runtime analysis of evolutionary algorithms via symmetry arguments. CoRR abs\/2006.04663 (2020)","DOI":"10.1145\/3449726.3462720"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65, 224\u2013250 (2013)","journal-title":"Algorithmica"},{"key":"42_CR13","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00f6tzing, T.: Multiplicative up-drift. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1470\u20131478. ACM (2019)","DOI":"10.1145\/3321707.3321819"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Doerr, B., Theile, M.: Improved analysis methods for crossover-based algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2009, pp. 247\u2013254. ACM (2009)","DOI":"10.1145\/1569901.1569937"},{"key":"42_CR16","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"502","DOI":"10.2307\/1426671","volume":"13","author":"B Hajek","year":"1982","unstructured":"Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 13, 502\u2013525 (1982)","journal-title":"Adv. Appl. Probab."},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitness-proportional selection for optimizing linear functions. In: Genetic and Evolutionary Computation Conference, GECCO 2008, pp. 953\u2013960. ACM (2008)","DOI":"10.1145\/1389095.1389277"},{"key":"42_CR19","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0004-3702(01)00058-3","volume":"127","author":"J He","year":"2001","unstructured":"He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 51\u201381 (2001)","journal-title":"Artif. Intell."},{"key":"42_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-87700-4_5","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN X","author":"J J\u00e4gersk\u00fcpper","year":"2008","unstructured":"J\u00e4gersk\u00fcpper, J.: A blend of Markov-chain and drift analysis. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 41\u201351. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87700-4_5"},{"key":"42_CR21","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Storch, T.: When the plus strategy outperforms the comma strategy and when not. In: Foundations of Computational Intelligence, FOCI 2007, pp. 25\u201332. IEEE (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"42_CR22","unstructured":"Johannsen, D.: Random combinatorial structures and randomized search heuristics. Ph.D. thesis, Universit\u00e4t des Saarlandes (2010)"},{"key":"42_CR23","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","volume":"75","author":"T K\u00f6tzing","year":"2016","unstructured":"K\u00f6tzing, T.: Concentration of first hitting times under additive drift. Algorithmica 75, 490\u2013506 (2016)","journal-title":"Algorithmica"},{"key":"42_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-15844-5_25","volume-title":"Parallel Problem Solving from Nature, PPSN XI","author":"PK Lehre","year":"2010","unstructured":"Lehre, P.K.: Negative drift in populations. In: Schaefer, R., Cotta, C., Ko\u0142odziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 244\u2013253. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15844-5_25"},{"key":"42_CR25","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Fitness-levels for non-elitist populations. In: Genetic and Evolutionary Computation Conference, GECCO 2011, pp. 2075\u20132082. ACM (2011)","DOI":"10.1145\/2001576.2001855"},{"key":"42_CR26","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer, Cham (2020). https:\/\/arxiv.org\/abs\/1712.00964"},{"key":"42_CR27","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548318000275","volume":"27","author":"J Lengler","year":"2018","unstructured":"Lengler, J., Steger, A.: Drift analysis and evolutionary algorithms revisited. Comb. Probab. Comput. 27, 643\u2013666 (2018)","journal-title":"Comb. Probab. Comput."},{"key":"42_CR28","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1108\/17563780910959893","volume":"2","author":"B Mitavskiy","year":"2009","unstructured":"Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybern. 2, 243\u2013284 (2009)","journal-title":"Int. J. Intell. Comput. Cybern."},{"key":"42_CR29","doi-asserted-by":"crossref","unstructured":"Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Genetic and Evolutionary Computation Conference, GECCO 2009, pp. 835\u2013842. ACM (2009)","DOI":"10.1145\/1569901.1570016"},{"key":"42_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-540-87700-4_9","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN X","author":"PS Oliveto","year":"2008","unstructured":"Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82\u201391. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87700-4_9"},{"key":"42_CR31","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00453-010-9387-z","volume":"59","author":"PS Oliveto","year":"2011","unstructured":"Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59, 369\u2013386 (2011)","journal-title":"Algorithmica"},{"key":"42_CR32","unstructured":"Oliveto, P.S., Witt, C.: Erratum: simplified drift analysis for proving lower bounds in evolutionary computation. CoRR abs\/1211.7184 (2012)"},{"key":"42_CR33","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2013.06.015","volume":"545","author":"PS Oliveto","year":"2014","unstructured":"Oliveto, P.S., Witt, C.: On the runtime analysis of the simple genetic algorithm. Theoret. Comput. Sci. 545, 2\u201319 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR34","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theoret. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR35","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","volume":"545","author":"JE Rowe","year":"2014","unstructured":"Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1, $$\\lambda $$) evolutionary algorithm. Theoret. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR36","doi-asserted-by":"crossref","unstructured":"Sutton, A.M., Witt, C.: Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1515\u20131522. ACM (2019)","DOI":"10.1145\/3321707.3321848"},{"key":"42_CR37","first-page":"65","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the ($$\\mu $$ + 1) EA on simple pseudo-Boolean functions. Evol. Comput. 14, 65\u201386 (2006)","journal-title":"Evol. Comput."},{"key":"42_CR38","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C Witt","year":"2013","unstructured":"Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22, 294\u2013318 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"42_CR39","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1007\/s00453-018-0463-0","volume":"81","author":"C Witt","year":"2019","unstructured":"Witt, C.: Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax. Algorithmica 81, 632\u2013667 (2019)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVI"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-58115-2_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,15]],"date-time":"2022-11-15T21:28:12Z","timestamp":1668547692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-58115-2_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030581145","9783030581152"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58115-2_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"2 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PPSN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Problem Solving from Nature","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Leiden","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2020.liacs.leidenuniv.nl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"268","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"99","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}