{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:16:49Z","timestamp":1760203009357},"reference-count":55,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>A decent number of lower bounds for non-elitist population-based evolutionary algorithms has been shown by now. Most of them are technically demanding due to the (hard to avoid) use of negative drift theorems\u2014general results which translate an expected movement away from the target into a high hitting time. We propose a simple negative drift theorem for multiplicative drift scenarios and show that it can simplify existing analyses. We discuss in more detail Lehre's (2010) negative drift in populations method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms for discrete search spaces. Together with other arguments, we obtain an alternative and simpler proof of this result, which also strengthens and simplifies this method. In particular, now only three of the five technical conditions of the previous result have to be verified. The lower bounds we obtain are explicit instead of only asymptotic. This allows us to compute concrete lower bounds for concrete algorithms, but also enables us to show that super-polynomial runtimes appear already when the reproduction rate is only a (1-\u03c9(n-1\/2)) factor below the threshold. For the special case of algorithms using standard bit mutation with a random mutation rate (called uniform mixing in the language of hyper-heuristics), we prove the result stated by Dang and Lehre (2016b) and extend it to mutation rates other than \u0398(1\/n), which includes the heavy-tailed mutation operator proposed by Doerr et al. (2017). We finally use our method and a novel domination argument to show an exponential lower bound for the runtime of the mutation-only simple genetic algorithm on OneMax for arbitrary population size.<\/jats:p>","DOI":"10.1162\/evco_a_00283","type":"journal-article","created":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T20:36:50Z","timestamp":1605559010000},"page":"305-329","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":13,"title":["Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative\n                    Multiplicative Drift"],"prefix":"10.1162","volume":"29","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"Laboratoire d'Informatique (LIX), CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris, Palaiseau, 92128, France doerr@lix.polytechnique.fr"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2021,6,1]]},"reference":[{"key":"2021060116343135700_B1","first-page":"1268","volume-title":"Genetic and Evolutionary\n                            Computation Conference (GECCO)","author":"Antipov","year":"2020"},{"key":"2021060116343135700_B2","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1007\/978-3-030-58115-2_39","volume-title":"Parallel Problem Solving from Nature, Part\n                        II","author":"Antipov","year":"2020"},{"key":"2021060116343135700_B3","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/978-3-030-58115-2_38","volume-title":"Parallel Problem Solving from Nature, Part\n                        II","author":"Antipov","year":"2020"},{"key":"2021060116343135700_B4","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1145\/3205455.3205627","volume-title":"Genetic\n                            and Evolutionary Computation Conference (GECCO)","author":"Antipov","year":"2018"},{"key":"2021060116343135700_B5","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1145\/3321707.3321838","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Antipov","year":"2019"},{"key":"2021060116343135700_B6","first-page":"39:1092","article-title":"A new approach for analyzing average\n                        time complexity of population-based evolutionary algorithms on unimodal\n                        problems","author":"Chen","year":"2009","journal-title":"IEEE Transactions on Systems, Man,\n                            and Cybernetics, Part B"},{"key":"2021060116343135700_B7","first-page":"22:707","article-title":"Level-based analysis of genetic algorithms and other search\n                        processes","author":"Corus","year":"2018","journal-title":"IEEE Transactions on Evolutionary\n                            Computation"},{"key":"2021060116343135700_B8","first-page":"75:428","article-title":"Runtime analysis of non-elitist populations: From classical\n                        optimisation to partial information","author":"Dang","year":"2016","journal-title":"Algorithmica"},{"key":"2021060116343135700_B9","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1007\/978-3-319-45823-6_75","volume-title":"Parallel Problem Solving\n                            from Nature","author":"Dang","year":"2016"},{"key":"2021060116343135700_B10","first-page":"773:115","article-title":"Analyzing randomized search heuristics\n                        via stochastic domination","author":"Doerr","year":"2019","journal-title":"Theoretical\n                            Computer Science"},{"key":"2021060116343135700_B11","first-page":"25","volume-title":"Foundations of Genetic Algorithms","author":"Doerr","year":"2019"},{"key":"2021060116343135700_B12","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.1145\/3377930.3389823","article-title":"Does comma selection help to cope with\n                        local optima?","author":"Doerr","year":"2020","journal-title":"Genetic and Evolutionary\n                            Computation Conference (GECCO)"},{"key":"2021060116343135700_B13","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1007\/978-3-030-58115-2_43","volume-title":"Parallel Problem Solving from Nature, Part\n                        II","author":"Doerr","year":"2020"},{"key":"2021060116343135700_B14","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1007\/978-3-030-58115-2_42","volume-title":"Parallel Problem Solving from Nature, Part\n                        II","author":"Doerr","year":"2020"},{"key":"2021060116343135700_B15","first-page":"1","article-title":"Probabilistic tools for the analysis of\n                        randomized optimization heuristics","author":"Doerr","year":"2020","journal-title":"Theory of evolutionary computation: Recent developments\n                            in discrete optimization"},{"key":"2021060116343135700_B16","article-title":"Runtime analysis of evolutionary\n                        algorithms via symmetry arguments","author":"Doerr","year":"2020","journal-title":"CoRR"},{"key":"2021060116343135700_B17","first-page":"65:224","article-title":"Adaptive drift analysis","author":"Doerr","year":"2013","journal-title":"Algorithmica"},{"key":"2021060116343135700_B18","first-page":"19:673","article-title":"Tight analysis of the (1 + 1)-EA for the\n                        single source shortest path problem","author":"Doerr","year":"2011","journal-title":"Evolutionary Computation"},{"key":"2021060116343135700_B19","first-page":"64:673","article-title":"Multiplicative drift\n                        analysis","author":"Doerr","year":"2012","journal-title":"Algorithmica"},{"key":"2021060116343135700_B20","doi-asserted-by":"crossref","first-page":"1470","DOI":"10.1145\/3321707.3321819","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Doerr","year":"2019"},{"key":"2021060116343135700_B21","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1145\/3071178.3071301","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Doerr","year":"2017"},{"key":"2021060116343135700_B22","first-page":"247","volume-title":"Genetic and\n                            Evolutionary Computation Conference (GECCO)","author":"Doerr","year":"2009"},{"key":"2021060116343135700_B23","first-page":"2704","volume-title":"Conference of the IEEE Industrial Electronics\n                            Society","author":"Droste","year":"2000"},{"key":"2021060116343135700_B24","first-page":"276:51","article-title":"On the analysis of the (1+1)\n                        evolutionary algorithm","author":"Droste","year":"2002","journal-title":"Theoretical Computer\n                            Science"},{"key":"2021060116343135700_B25","article-title":"Evolutionary algorithms and submodular\n                        functions: Benefits of heavy-tailed mutations","author":"Friedrich","year":"2018","journal-title":"CoRR"},{"key":"2021060116343135700_B26","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-319-99253-2_11","volume-title":"Parallel Problem Solving from Nature, Part\n                        I","author":"Friedrich","year":"2018"},{"key":"2021060116343135700_B27","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1145\/3205455.3205515","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Friedrich","year":"2018"},{"key":"2021060116343135700_B28","author":"Goldberg","year":"1989","journal-title":"Genetic algorithms in search, optimization and machine\n                            learning"},{"key":"2021060116343135700_B29","first-page":"13:502","article-title":"Hitting-time and occupation-time bounds\n                        implied by drift analysis with applications","author":"Hajek","year":"1982","journal-title":"Advances in Applied Probability"},{"key":"2021060116343135700_B30","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1145\/1389095.1389277","volume-title":"Genetic and Evolutionary\n                            Computation Conference (GECCO)","author":"Happ","year":"2008"},{"key":"2021060116343135700_B31","first-page":"127:51","article-title":"Drift analysis and average time\n                        complexity of evolutionary algorithms","author":"He","year":"2001","journal-title":"Artificial Intelligence"},{"key":"2021060116343135700_B32","first-page":"41","volume-title":"Parallel Problem Solving from\n                            Nature","author":"J\u00e4gersk\u00fcpper","year":"2008"},{"key":"2021060116343135700_B33","first-page":"25","volume-title":"Foundations\n                            of Computational Intelligence","author":"J\u00e4gersk\u00fcpper","year":"2007"},{"key":"2021060116343135700_B34","author":"Johannsen","year":"2010","journal-title":"Random combinatorial structures and\n                            randomized search heuristics"},{"key":"2021060116343135700_B35","first-page":"75:490","article-title":"Concentration of first hitting times\n                        under additive drift","author":"K\u00f6tzing","year":"2016","journal-title":"Algorithmica"},{"key":"2021060116343135700_B36","first-page":"244","volume-title":"Parallel Problem Solving from Nature","author":"Lehre","year":"2010"},{"key":"2021060116343135700_B37","first-page":"2075","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Lehre","year":"2011"},{"key":"2021060116343135700_B38","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","article-title":"Drift analysis","author":"Lengler","year":"2020","journal-title":"Theory of evolutionary computation: Recent developments\n                            in discrete optimization"},{"key":"2021060116343135700_B39","first-page":"27:643","article-title":"Drift analysis and evolutionary\n                        algorithms revisited","author":"Lengler","year":"2018","journal-title":"Combinatorics,\n                            Probability & Computing"},{"key":"2021060116343135700_B40","doi-asserted-by":"crossref","first-page":"1423","DOI":"10.1145\/3067695.3082507","volume-title":"Genetic and Evolutionary Computation Conference (GECCO),\n                            Companion Material","author":"Mironovich","year":"2017"},{"key":"2021060116343135700_B41","first-page":"2:243","article-title":"Theoretical analysis of local search\n                        strategies to optimize network communication subject to preserving the total\n                        number of links","author":"Mitavskiy","year":"2009","journal-title":"International Journal on\n                            Intelligent Computing and Cybernetics"},{"key":"2021060116343135700_B42","first-page":"835","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Neumann","year":"2009"},{"key":"2021060116343135700_B43","first-page":"82","volume-title":"Parallel Problem Solving from Nature","author":"Oliveto","year":"2008"},{"key":"2021060116343135700_B44","first-page":"59:369","article-title":"Simplified drift analysis for proving\n                        lower bounds in evolutionary computation","author":"Oliveto","year":"2011","journal-title":"Algorithmica"},{"key":"2021060116343135700_B45","article-title":"Erratum: Simplified drift analysis for\n                        proving lower bounds in evolutionary computation","author":"Oliveto","year":"2012","journal-title":"CoRR"},{"key":"2021060116343135700_B46","first-page":"1341","volume-title":"Genetic and Evolutionary\n                            Computation Conference (GECCO)","author":"Oliveto","year":"2012"},{"key":"2021060116343135700_B47","first-page":"545:2","article-title":"On the runtime analysis of the simple\n                        genetic algorithm","author":"Oliveto","year":"2014","journal-title":"Theoretical Computer\n                            Science"},{"key":"2021060116343135700_B48","first-page":"605:21","article-title":"Improved time complexity analysis of the\n                        simple genetic algorithm","author":"Oliveto","year":"2015","journal-title":"Theoretical\n                            Computer Science"},{"key":"2021060116343135700_B49","first-page":"545:20","article-title":"The choice of the offspring population\n                        size in the (1, \u03bb) evolutionary algorithm","author":"Rowe","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"2021060116343135700_B50","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1145\/3321707.3321848","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Sutton","year":"2019"},{"key":"2021060116343135700_B51","first-page":"14:65","article-title":"Runtime analysis of the (\u03bc + 1)\n                        EA on simple pseudo-Boolean functions","author":"Witt","year":"2006","journal-title":"Evolutionary Computation"},{"key":"2021060116343135700_B52","first-page":"22:294","article-title":"Tight bounds on the optimization time of\n                        a randomized search heuristic on linear functions","author":"Witt","year":"2013","journal-title":"Combinatorics, Probability &\n                        Computing"},{"key":"2021060116343135700_B53","first-page":"81:632","article-title":"Upper bounds on the running time of the\n                        univariate marginal distribution algorithm on OneMax","author":"Witt","year":"2019","journal-title":"Algorithmica"},{"key":"2021060116343135700_B54","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-319-95957-3_4","volume-title":"Intelligent Computing Methodologies, Part\n                        III","author":"Wu","year":"2018"},{"key":"2021060116343135700_B55","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/978-3-030-58115-2_49","volume-title":"Parallel Problem Solving from Nature, Part\n                        II","author":"Ye","year":"2020"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/direct.mit.edu\/evco\/article-pdf\/29\/2\/305\/1921051\/evco_a_00283.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/direct.mit.edu\/evco\/article-pdf\/29\/2\/305\/1921051\/evco_a_00283.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T01:49:37Z","timestamp":1622598577000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/29\/2\/305\/97359\/Lower-Bounds-for-Non-Elitist-Evolutionary"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":55,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,6,1]]},"published-print":{"date-parts":[[2021,6,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00283","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021]]},"published":{"date-parts":[[2021]]}}}