{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:59:05Z","timestamp":1783749545944,"version":"3.55.0"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T00:00:00Z","timestamp":1651104000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T00:00:00Z","timestamp":1651104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-11-LABX-0056-LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["FR 2988\/17-1"],"award-info":[{"award-number":["FR 2988\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\gamma _{i,j}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u03b3<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>i<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$0 \\le i &lt; j \\le n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>i<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>j<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on <jats:sc>LeadingOnes<\/jats:sc>. (ii) A lower bound for the run time of the (1+1) EA on <jats:sc>OneMax<\/jats:sc>, tight apart from an <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) term. (iii) A lower bound for the run time of the (1+1) EA on long <jats:italic>k<\/jats:italic>-paths (which differs slightly from the previous result due to a small error in the latter). We also prove a tighter lower bound for the run time of the (1+1) EA on jump functions by showing that, regardless of the jump size, only with probability <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(2^{-n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mrow>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the algorithm can avoid to jump over the valley of low fitness.\n<\/jats:p>","DOI":"10.1007\/s00453-022-00952-w","type":"journal-article","created":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T12:03:42Z","timestamp":1651147422000},"page":"367-395","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Lower Bounds from Fitness Levels Made Easy"],"prefix":"10.1007","volume":"86","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timo","family":"K\u00f6tzing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,28]]},"reference":[{"key":"952_CR1","first-page":"560","volume-title":"Parallel problem solving from nature, PPSN 2020, Part II.","author":"Denis Antipov","year":"2020","unstructured":"Antipov, Denis, Buzdalov, Maxim, Benjamin, Doerr: First steps towards a runtime analysis when starting with a good solution. In: Parallel problem solving from nature, PPSN 2020, Part II., pp. 560\u2013573. Springer, Cham (2020)"},{"key":"952_CR2","doi-asserted-by":"crossref","unstructured":"Antipov, Denis, Buzdalov, Maxim, Doerr Benjamin: Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1115\u20131123. ACM (2021)","DOI":"10.1145\/3449639.3459377"},{"key":"952_CR3","doi-asserted-by":"crossref","unstructured":"Antipov, Denis, Doerr, Benjamin: Runtime analysis of a heavy-tailed $$(1+(\\lambda , \\lambda ))$$ genetic algorithm on jump functions. In Parallel Problem Solving From Nature, PPSN 2020, Part\u00a0II, pp. 545\u2013559. Springer, (2020)","DOI":"10.1007\/978-3-030-58115-2_38"},{"key":"952_CR4","unstructured":"Antipov, Denis, Doerr, Benjamin, Karavaev, Vitalii: The $$(1 + (\\lambda ,\\lambda ))$$ GA is even faster on multimodal problems. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1259\u20131267. ACM, (2020)"},{"key":"952_CR5","unstructured":"Benbaki Riade, Benomar Ziyad, Doerr Benjamin: A rigorous runtime analysis of the 2-MMAS$$_{\\rm ib }$$ on jump functions: ant colony optimizers can cope well with local optima. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 4\u201313. ACM, (2021)"},{"key":"952_CR6","doi-asserted-by":"crossref","unstructured":"Buzdalov, Maxim, Doerr, Benjamin, Doerr, Carola, Vinokurov, Dmitry: Fixed-target runtime analysis. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1295\u20131303. ACM, (2020)","DOI":"10.1145\/3377930.3390184"},{"key":"952_CR7","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, S\u00fcntje, Doerr, Benjamin, Neumann, Frank: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Parallel Problem Solving from Nature, PPSN 2010, pp. 1\u201310. Springer, (2010)","DOI":"10.1007\/978-3-642-15844-5_1"},{"key":"952_CR8","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","volume":"22","author":"Dogan Corus","year":"2018","unstructured":"Corus, Dogan, Dang, Duc-Cuong., Eremeev, Anton V., Lehre, Per Kristian: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evolut. Comput. 22, 707\u2013719 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"952_CR9","doi-asserted-by":"crossref","unstructured":"Corus, Dogan, Oliveto, Pietro\u00a0S., Yazdani, Donya: On the runtime analysis of the Opt-IA artificial immune system. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 83\u201390. ACM, (2017)","DOI":"10.1145\/3071178.3079194"},{"key":"952_CR10","doi-asserted-by":"crossref","unstructured":"Corus, Dogan, Oliveto, Pietro\u00a0S., Yazdani, Donya: Fast artificial immune systems. In: Parallel Problem Solving from Nature, PPSN 2018, Part II, pp. 67\u201378. Springer, (2018)","DOI":"10.1007\/978-3-319-99259-4_6"},{"key":"952_CR11","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-015-0019-5","volume":"75","author":"Benjamin Doerr","year":"2016","unstructured":"Doerr, Benjamin, Doerr, Carola: The impact of random initialization on the runtime of randomized search heuristics. Algorithmica 75, 529\u2013553 (2016)","journal-title":"Algorithmica"},{"key":"952_CR12","doi-asserted-by":"publisher","first-page":"1732","DOI":"10.1007\/s00453-017-0341-1","volume":"80","author":"Benjamin Doerr","year":"2018","unstructured":"Doerr, Benjamin, Doerr, Carola, K\u00f6tzing, Timo: Static and self-adjusting mutation strengths for multi-valued decision variables. Algorithmica 80, 1732\u20131768 (2018)","journal-title":"Algorithmica"},{"key":"952_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.06.014","volume":"801","author":"Benjamin Doerr","year":"2020","unstructured":"Doerr, Benjamin, Doerr, Carola, Yang, Jing: Optimal parameter choices via precise black-box analysis. Theor. Comput. Sci. 801, 1\u201334 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR14","doi-asserted-by":"crossref","unstructured":"Dang, Duc-Cuong, Friedrich, Tobias, K\u00f6tzing, Timo, Krejca, Martin\u00a0S., Lehre, Per\u00a0Kristian, Oliveto, Pietro\u00a0S., Sudholt, Dirk, Sutton, Andrew\u00a0M.: Escaping local optima with diversity mechanisms and crossover. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 645\u2013652. ACM, 2016","DOI":"10.1145\/2908812.2908956"},{"key":"952_CR15","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"Duc-Cuong Dang","year":"2018","unstructured":"Dang, Duc-Cuong., Friedrich, Tobias, K\u00f6tzing, Timo, Krejca, Martin S., Lehre, Per Kristian, Oliveto, Pietro S., Sudholt, Dirk, Sutton, Andrew M.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22, 484\u2013497 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"952_CR16","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, Fouz, Mahmoud, Witt, Carsten: Quasirandom evolutionary algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2010, pp. 1457\u20131464. ACM (2010)","DOI":"10.1145\/1830483.1830749"},{"key":"952_CR17","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, Fouz, Mahmoud, Witt, Carsten: Sharp bounds by probability-generating functions and variable drift. In: Genetic and Evolutionary Computation Conference, GECCO 2011, pp. 2083\u20132090. ACM (2011)","DOI":"10.1145\/2001576.2001856"},{"key":"952_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1162\/evco.1998.6.2.185","volume":"6","author":"Stefan Droste","year":"1998","unstructured":"Droste, Stefan, Jansen, Thomas, Wegener, Ingo: A rigorous complexity analysis of the $${(1+1)}$$ evolutionary algorithm for separable functions with boolean inputs. Evol. Comput. 6, 185\u2013196 (1998)","journal-title":"Evol. Comput."},{"key":"952_CR19","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"Stefan Droste","year":"2002","unstructured":"Droste, Stefan, Jansen, Thomas, Wegener, Ingo: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR20","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"Benjamin Doerr","year":"2012","unstructured":"Doerr, Benjamin, Johannsen, Daniel, Winzen, Carola: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"952_CR21","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, Jansen, Thomas, Witt, Carsten, Zarges, Christine: A method to derive fixed budget results from expected optimisation times. In: Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 1581\u20131588. ACM (2013)","DOI":"10.1145\/2463372.2463565"},{"key":"952_CR22","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, K\u00f6tzing, Timo: Multiplicative up-drift. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1470\u20131478. ACM (2019)","DOI":"10.1145\/3321707.3321819"},{"key":"952_CR23","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, K\u00f6tzing, Timo: Lower bounds from fitness levels made easy. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1142\u20131150. ACM (2021)","DOI":"10.1145\/3449639.3459352"},{"key":"952_CR24","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.tcs.2020.01.011","volume":"816","author":"Benjamin Doerr","year":"2020","unstructured":"Doerr, Benjamin, K\u00f6tzing, Timo, Gregor Lagodzinski, J.A., Lengler, Johannes: The impact of lexicographic parsimony pressure for ORDER\/MAJORITY on the run time. Theor. Comput. Sci. 816, 144\u2013168 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR25","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","volume":"75","author":"Duc-Cuong Dang","year":"2016","unstructured":"Dang, Duc-Cuong., Lehre, Per Kristian: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75, 428\u2013461 (2016)","journal-title":"Algorithmica"},{"key":"952_CR26","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, Le, Huu\u00a0Phuoc, Makhmara, R\u00e9gis, Nguyen, Ta\u00a0Duy: Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777\u2013784. ACM (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"952_CR27","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","volume":"773","author":"Benjamin Doerr","year":"2019","unstructured":"Doerr, Benjamin: Analyzing randomized search heuristics via stochastic domination. Theor. Comput. Sci. 773, 115\u2013137 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR28","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin: Does comma selection help to cope with local optima?. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1304\u20131313. ACM (2020)","DOI":"10.1145\/3377930.3389823"},{"key":"952_CR29","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin: Probabilistic tools for the analysis of randomized optimization heuristics. In: Benjamin Doerr and Frank Neumann (ed.), Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer, 2020. Also available at arxiv: 1801.06733","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"952_CR30","doi-asserted-by":"crossref","unstructured":"Doerr, Benjamin, Zheng, Weijie: Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In: Conference on Artificial Intelligence, AAAI 2021, pp. 12293\u201312301. AAAI Press (2021)","DOI":"10.1609\/aaai.v35i14.17459"},{"key":"952_CR31","volume-title":"An introduction to probability theory and its applications","author":"William Feller","year":"1968","unstructured":"Feller, William: An introduction to probability theory and its applications, vol. I, 3rd edn. Wiley, Amsterdam (1968)","edition":"3"},{"key":"952_CR32","doi-asserted-by":"crossref","unstructured":"Feldmann, Matthias, K\u00f6tzing, Timo: Optimizing expected path lengths with ant colony optimization using fitness proportional update. In: Foundations of Genetic Algorithms, FOGA 2013, pp. 65\u201374. ACM (2013)","DOI":"10.1145\/2460239.2460246"},{"key":"952_CR33","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1162\/evco.1999.7.2.173","volume":"7","author":"Josselin Garnier","year":"1999","unstructured":"Garnier, Josselin, Kallel, Leila, Schoenauer, Marc: Rigorous hitting times for binary mutations. Evol. Comput. 7, 173\u2013203 (1999)","journal-title":"Evol. Comput."},{"key":"952_CR34","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00453-016-0214-z","volume":"78","author":"Christian Gie\u00dfen","year":"2017","unstructured":"Gie\u00dfen, Christian, Witt, Carsten: The interplay of population size and mutation probability in the $${(1 + \\lambda )}$$ EA on OneMax. Algorithmica 78, 587\u2013609 (2017)","journal-title":"Algorithmica"},{"key":"952_CR35","doi-asserted-by":"publisher","first-page":"1710","DOI":"10.1007\/s00453-017-0360-y","volume":"80","author":"Christian Gie\u00dfen","year":"2018","unstructured":"Gie\u00dfen, Christian, Witt, Carsten: Optimal mutation rates for the $${(1 + \\lambda )}$$ EA on OneMax through asymptotically tight drift analysis. Algorithmica 80, 1710\u20131731 (2018)","journal-title":"Algorithmica"},{"key":"952_CR36","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1162\/evco_a_00212","volume":"26","author":"Hsien-Kuei Hwang","year":"2018","unstructured":"Hwang, Hsien-Kuei., Panholzer, Alois, Rolin, Nicolas, Tsai, Tsung-Hsi., Chen, Wei-Mei.: Probabilistic analysis of the (1+1)-evolutionary algorithm. Evol. Comput. 26, 299\u2013345 (2018)","journal-title":"Evol. Comput."},{"key":"952_CR37","doi-asserted-by":"crossref","unstructured":"Hwang, Hsien-Kuei, Witt, Carsten: Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 1\u201312. ACM (2019)","DOI":"10.1145\/3299904.3340302"},{"key":"952_CR38","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0004-3702(01)00058-3","volume":"127","author":"Jun He","year":"2001","unstructured":"He, Jun, Yao, Xin: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 51\u201381 (2001)","journal-title":"Artif. Intell."},{"key":"952_CR39","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.tcs.2007.02.042","volume":"379","author":"Jens J\u00e4gersk\u00fcpper","year":"2007","unstructured":"J\u00e4gersk\u00fcpper, Jens: Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theor. Comput. Sci. 379, 329\u2013347 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR40","unstructured":"Johannsen, Daniel: Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universit\u00e4t des Saarlandes, (2010)"},{"key":"952_CR41","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00453-002-0940-2","volume":"34","author":"Thomas Jansen","year":"2002","unstructured":"Jansen, Thomas, Wegener, Ingo: The analysis of evolutionary algorithms - a proof that crossover really can help. Algorithmica 34, 47\u201366 (2002)","journal-title":"Algorithmica"},{"key":"952_CR42","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.tcs.2013.06.007","volume":"545","author":"Thomas Jansen","year":"2014","unstructured":"Jansen, Thomas, Zarges, Christine: Performance analysis of randomised search heuristics operating with a fixed budget. Theor. Comput. Sci. 545, 39\u201358 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR43","doi-asserted-by":"crossref","unstructured":"Lehre, Per\u00a0Kristian: Negative drift in populations. In: Parallel Problem Solving from Nature, PPSN 2010, pp. 244\u2013253. Springer, (2010)","DOI":"10.1007\/978-3-642-15844-5_25"},{"key":"952_CR44","doi-asserted-by":"crossref","unstructured":"Lehre, Per\u00a0Kristian: 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":"952_CR45","doi-asserted-by":"crossref","unstructured":"Lengler, Johannes: Drift analysis. In Benjamin Doerr and Frank Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer, (2020). Also available at arXiv:1712.00964","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"952_CR46","doi-asserted-by":"crossref","unstructured":"Lissovoi, Andrei, Oliveto, Pietro\u00a0S., Warwicker, John\u00a0Alasdair: On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation. In: Conference on Artificial Intelligence, AAAI 2019, pp. 2322\u20132329. AAAI Press, (2019)","DOI":"10.1609\/aaai.v33i01.33012322"},{"key":"952_CR47","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1162\/EVCO_a_00114","volume":"22","author":"J\u00f6rg L\u00e4ssig","year":"2014","unstructured":"L\u00e4ssig, J\u00f6rg., Sudholt, Dirk: General upper bounds on the runtime of parallel evolutionary algorithms. Evol. Comput. 22, 405\u2013437 (2014)","journal-title":"Evol. Comput."},{"key":"952_CR48","doi-asserted-by":"crossref","unstructured":"Lehre, Per\u00a0Kristian, Witt, Carsten: Concentrated hitting times of randomized search heuristics with variable drift. In: International Symposium on Algorithms and Computation, ISAAC 2014, pp. 686\u2013697. Springer, (2014)","DOI":"10.1007\/978-3-319-13075-0_54"},{"key":"952_CR49","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1108\/17563780910959893","volume":"2","author":"Boris Mitavskiy","year":"2009","unstructured":"Mitavskiy, Boris, Rowe, Jonathan E., Cannings, Chris: 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":"952_CR50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626630","volume-title":"Tweedie. Markov chains and stochastic stability.","author":"Sean Meyn","year":"2009","unstructured":"Meyn, Sean: Tweedie. Markov chains and stochastic stability. Cambridge University Press, Richard (2009)"},{"key":"952_CR51","doi-asserted-by":"crossref","unstructured":"Rowe, Jonathan\u00a0E., Aishwaryaprajna: The benefits and limitations of voting mechanisms in evolutionary optimisation. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 34\u201342. ACM, (2019)","DOI":"10.1145\/3299904.3340305"},{"key":"952_CR52","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1162\/evco.1996.4.2.195","volume":"4","author":"G\u00fcnter Rudolph","year":"1996","unstructured":"Rudolph, G\u00fcnter.: How mutation and selection solve long path problems in polynomial expected time. Evol. Comput. 4, 195\u2013205 (1996)","journal-title":"Evol. Comput."},{"key":"952_CR53","volume-title":"Convergence properties of evolutionary algorithms","author":"G\u00fcnter Rudolph","year":"1997","unstructured":"Rudolph, G\u00fcnter.: Convergence properties of evolutionary algorithms. Verlag Dr, Kov\u01cec (1997)"},{"key":"952_CR54","doi-asserted-by":"crossref","unstructured":"Rajabi, Amirhossein, Witt, Carsten: Self-adjusting evolutionary algorithms for multimodal optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1314\u20131322. ACM, (2020)","DOI":"10.1145\/3377930.3389833"},{"key":"952_CR55","doi-asserted-by":"crossref","unstructured":"Rajabi, Amirhossein, Witt, Carsten: Stagnation detection in highly multimodal fitness landscapes. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1178\u20131186. ACM, (2021)","DOI":"10.1145\/3449639.3459336"},{"key":"952_CR56","doi-asserted-by":"crossref","unstructured":"Rajabi, Amirhossein, Witt, Carsten: Stagnation detection with randomized local search. In: Evolutionary Computation in Combinatorial Optimization, EvoCOP 2021, pp. 152\u2013168. Springer, (2021)","DOI":"10.1007\/978-3-030-72904-2_10"},{"key":"952_CR57","doi-asserted-by":"publisher","first-page":"2511","DOI":"10.1016\/j.tcs.2009.03.003","volume":"410","author":"Dirk Sudholt","year":"2009","unstructured":"Sudholt, Dirk: The impact of parametrization in memetic evolutionary algorithms. Theor. Comput. Sci. 410, 2511\u20132528 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"952_CR58","doi-asserted-by":"crossref","unstructured":"Sudholt, Dirk: General lower bounds for the running time of evolutionary algorithms. In: Parallel Problem Solving from Nature, PPSN 2010, Part I, pp. 124\u2013133. Springer, (2010)","DOI":"10.1007\/978-3-642-15844-5_13"},{"key":"952_CR59","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"Dirk Sudholt","year":"2013","unstructured":"Sudholt, Dirk: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17, 418\u2013435 (2013)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"952_CR60","doi-asserted-by":"crossref","unstructured":"Wegener, Ingo: Theoretical aspects of evolutionary algorithms. In: Automata, Languages and Programming, ICALP 2001, pp. 64\u201378. Springer, (2001)","DOI":"10.1007\/3-540-48224-5_6"},{"key":"952_CR61","doi-asserted-by":"crossref","unstructured":"Wegener, Ingo: Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Ruhul Sarker, Masoud Mohammadian, and Xin Yao (ed.), Evolutionary Optimization, pp. 349\u2013369. Kluwer, (2002)","DOI":"10.1007\/0-306-48041-7_14"},{"key":"952_CR62","first-page":"65","volume":"14","author":"Carsten Witt","year":"2006","unstructured":"Witt, Carsten: Runtime analysis of the ($$\\mu $$ + 1) EA on simple pseudo-Boolean functions. Evol. Comput. 14, 65\u201386 (2006)","journal-title":"Evol. Comput."},{"key":"952_CR63","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"Carsten Witt","year":"2013","unstructured":"Witt, Carsten: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probab. Comput. 22, 294\u2013318 (2013)","journal-title":"Combinatorics, Probab. Comput."},{"key":"952_CR64","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.ipl.2013.09.013","volume":"114","author":"Carsten Witt","year":"2014","unstructured":"Witt, Carsten: Fitness levels with tail bounds for the analysis of randomized search heuristics. Inf. Process. Lett. 114, 38\u201341 (2014)","journal-title":"Inf. Process. Lett."},{"key":"952_CR65","doi-asserted-by":"crossref","unstructured":"Whitley, Darrell, Varadarajan, Swetha, Hirsch, Rachel, Mukhopadhyay, Anirban: Exploration and exploitation without mutation: solving the jump function in $${\\Theta (n)}$$ time. In: Parallel Problem Solving from Nature, PPSN 2018, Part II, pp. 55\u201366. Springer, (2018)","DOI":"10.1007\/978-3-319-99259-4_5"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00952-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00952-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00952-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T09:08:49Z","timestamp":1706087329000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00952-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,28]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["952"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00952-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,28]]},"assertion":[{"value":"2 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}