{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T15:10:37Z","timestamp":1721920237058},"reference-count":92,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Investissements d'avenir project","award":["ANR-11-LABX-0056-LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s00453-024-01232-5","type":"journal-article","created":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T03:36:44Z","timestamp":1715312204000},"page":"2479-2518","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus"],"prefix":"10.1007","volume":"86","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew James","family":"Kelley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,10]]},"reference":[{"key":"1232_CR1","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.dam.2019.01.007","volume":"260","author":"P Afshani","year":"2019","unstructured":"Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K.G.: The query complexity of a permutation-based variant of Mastermind. Discrete Appl. Math. 260, 28\u201350 (2019)","journal-title":"Discrete Appl. Math."},{"key":"1232_CR2","volume-title":"Theory of Randomized Search Heuristics","year":"2011","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics. World Scientific Publishing, Singapore (2011)"},{"key":"1232_CR3","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/3469800","volume":"1","author":"D Antipov","year":"2021","unstructured":"Antipov, D., Doerr, B.: Precise runtime analysis for plateau functions. ACM Trans. Evol. Learn. Optim. 1, 13:1-13:28 (2021)","journal-title":"ACM Trans. Evol. Learn. Optim."},{"key":"1232_CR4","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Karavaev, V.: A tight runtime analysis for the $${(1 + (\\lambda ,\\lambda ))}$$ GA on LeadingOnes. Foundations of Genetic Algorithms, FOGA 2019, pp. 169\u2013182. ACM (2019)","DOI":"10.1145\/3299904.3340317"},{"key":"1232_CR5","doi-asserted-by":"crossref","unstructured":"Bambury, H., Bultel, A., Doerr, B.: Generalized jump functions. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1124\u20131132. ACM (2021)","DOI":"10.1145\/3449639.3459367"},{"key":"1232_CR6","doi-asserted-by":"crossref","first-page":"1762","DOI":"10.1007\/s00453-021-00881-0","volume":"84","author":"M Buzdalov","year":"2022","unstructured":"Buzdalov, M., Doerr, B., Doerr, C., Vinokurov, D.: Fixed-target runtime analysis. Algorithmica 84, 1762\u20131793 (2022)","journal-title":"Algorithmica"},{"key":"1232_CR7","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, S., Doerr, B., Neumann, F.: 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":"1232_CR8","doi-asserted-by":"crossref","unstructured":"Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: Do additional objectives make a problem harder? In: Genetic and Evolutionary Computation Conference, GECCO 2007, pp. 765\u2013772. ACM (2007)","DOI":"10.1145\/1276958.1277114"},{"key":"1232_CR9","doi-asserted-by":"crossref","unstructured":"Badkobeh, G., Lehre, P.K., Sudholt, D.: Unbiased black-box complexity of parallel search. In: Parallel Problem Solving from Nature, PPSN 2014, pp. 892\u2013901. Springer (2014)","DOI":"10.1007\/978-3-319-10762-2_88"},{"key":"1232_CR10","doi-asserted-by":"crossref","unstructured":"Bian, C., Qian, C., Jiang, W., Tang, K.: Towards a running time analysis of the (1+1)-EA for OneMax and LeadingOnes under general bit-wise noise. In: Parallel Problem Solving from Nature, PPSN 2018, Part II, pp. 165\u2013177. Springer (2018)","DOI":"10.1007\/978-3-319-99259-4_14"},{"key":"1232_CR11","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Dang, D.C., 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":"1232_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1162\/EVCO_a_00130","volume":"23","author":"F Chicano","year":"2015","unstructured":"Chicano, F., Sutton, A.M., Whitley, L.D., Alba, E.: Fitness probability distribution of bit-flip mutation. Evol. Comput. 23, 217\u2013248 (2015)","journal-title":"Evol. Comput."},{"key":"1232_CR13","doi-asserted-by":"crossref","first-page":"3108","DOI":"10.1007\/s00453-021-00854-3","volume":"83","author":"B Doerr","year":"2021","unstructured":"Doerr, B., Doerr, C., Lengler, J.: Self-adjusting mutation rates with provably optimal success rules. Algorithmica 83, 3108\u20133147 (2021)","journal-title":"Algorithmica"},{"key":"1232_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Neumann., F.: Fast re-optimization via structural diversity. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 233\u2013241. ACM (2019)","DOI":"10.1145\/3321707.3321731"},{"key":"1232_CR15","doi-asserted-by":"crossref","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":"1232_CR16","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.tcs.2010.10.035","volume":"425","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. Theoret. Comput. Sci. 425, 17\u201333 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR17","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1162\/evco.2007.15.4.401","volume":"15","author":"B Doerr","year":"2007","unstructured":"Doerr, B., Hebbinghaus, N., Neumann, F.: Speeding up evolutionary algorithms through asymmetric mutation operators. Evol. Comput. 15, 401\u2013410 (2007)","journal-title":"Evol. Comput."},{"key":"1232_CR18","doi-asserted-by":"crossref","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":"1232_CR19","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","volume":"39","author":"S Droste","year":"2006","unstructured":"Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39, 525\u2013544 (2006)","journal-title":"Theory Comput. Syst."},{"key":"1232_CR20","doi-asserted-by":"crossref","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":"1232_CR21","doi-asserted-by":"crossref","unstructured":"Doerr, B., Jansen, T., Witt, C., Zarges, C.: 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":"1232_CR22","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00fcnnemann, M.: Royal road functions and the (1\u00a0+\u00a0$$\\lambda $$) evolutionary algorithm: almost no speed-up from larger offspring populations. In: Congress on Evolutionary Computation, CEC 2013, pp. 424\u2013431. IEEE (2013)","DOI":"10.1109\/CEC.2013.6557600"},{"key":"1232_CR23","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1109\/TEVC.2019.2956633","volume":"24","author":"B Doerr","year":"2020","unstructured":"Doerr, B., Krejca, M.S.: Significance-based estimation-of-distribution algorithms. IEEE Trans. Evol. Comput. 24, 1025\u20131034 (2020)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"1232_CR24","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00f6tzing, T.: 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":"1232_CR25","doi-asserted-by":"crossref","first-page":"3017","DOI":"10.1007\/s00453-020-00775-7","volume":"83","author":"B Doerr","year":"2021","unstructured":"Doerr, B., K\u00f6tzing, T.: Multiplicative up-drift. Algorithmica 83, 3017\u20133058 (2021)","journal-title":"Algorithmica"},{"key":"1232_CR26","doi-asserted-by":"crossref","unstructured":"Doerr, B., Kelley, A.J.: Fourier analysis meets runtime analysis: precise runtimes on plateaus. In: Genetic and Evolutionary Computation Conference, GECCO 2023. ACM (2023). To appear","DOI":"10.1145\/3583131.3590393"},{"key":"1232_CR27","doi-asserted-by":"crossref","unstructured":"Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777\u2013784. ACM (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"1232_CR28","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1007\/s00453-018-0507-5","volume":"81","author":"DC Dang","year":"2019","unstructured":"Dang, D.C., Lehre, P.K., Nguyen, P.T.: Level-based analysis of the univariate marginal distribution algorithm. Algorithmica 81, 668\u2013702 (2019)","journal-title":"Algorithmica"},{"key":"1232_CR29","doi-asserted-by":"crossref","unstructured":"Doerr, B., Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1015\u20131022. ACM (2018)","DOI":"10.1145\/3205455.3205611"},{"key":"1232_CR30","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F., (eds).: Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization. Springer (2020). http:\/\/www.lix.polytechnique.fr\/Labo\/Benjamin.Doerr\/doerr_neumann_book.html","DOI":"10.1007\/978-3-030-29414-4"},{"key":"1232_CR31","doi-asserted-by":"crossref","unstructured":"Dang-Nhu, R., Dardinier, T., Doerr, B., Izacard, G., Nogneng, D.: A new analysis method for evolutionary optimization of dynamic and noisy objective functions. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1467\u20131474. ACM (2018)","DOI":"10.1145\/3205455.3205563"},{"key":"1232_CR32","doi-asserted-by":"crossref","first-page":"1629","DOI":"10.1016\/j.tcs.2010.12.030","volume":"412","author":"B Doerr","year":"2011","unstructured":"Doerr, B., Neumann, F., Sudholt, D., Witt, C.: Runtime analysis of the 1-ANT ant colony optimizer. Theoret. Comput. Sci. 412, 1629\u20131644 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR33","doi-asserted-by":"crossref","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":"1232_CR34","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds), Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer (2020). arXiv:1801.06733","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"1232_CR35","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.tcs.2020.09.032","volume":"851","author":"B Doerr","year":"2021","unstructured":"Doerr, B.: Exponential upper bounds for the runtime of randomized search heuristics. Theoret. Comput. Sci. 851, 24\u201338 (2021)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR36","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1162\/evco_a_00283","volume":"29","author":"B Doerr","year":"2021","unstructured":"Doerr, B.: Lower bounds for non-elitist evolutionary algorithms via negative multiplicative drift. Evol. Comput. 29, 305\u2013329 (2021)","journal-title":"Evol. Comput."},{"key":"1232_CR37","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1007\/s00453-020-00780-w","volume":"83","author":"B Doerr","year":"2021","unstructured":"Doerr, B.: The runtime of the compact genetic algorithm on Jump functions. Algorithmica 83, 3059\u20133107 (2021)","journal-title":"Algorithmica"},{"key":"1232_CR38","doi-asserted-by":"crossref","unstructured":"Droste, S.: Analysis of the (1+1) EA for a dynamically changing OneMax-variant. In: Congress on Evolutionary Computation, CEC 2002, pp. 55\u201360. IEEE (2002)","DOI":"10.1007\/3-540-45105-6_103"},{"key":"1232_CR39","doi-asserted-by":"crossref","unstructured":"Doerr, B., Sudholt, D., Witt, C.: When do evolutionary algorithms optimize separable functions in parallel? In: Foundations of Genetic Algorithms, FOGA 2013, pp. 48\u201359. ACM (2013)","DOI":"10.1145\/2460239.2460245"},{"key":"1232_CR40","doi-asserted-by":"crossref","unstructured":"Doerr, B., Winzen, C.: Black-box complexity: breaking the O(n log n) barrier of LeadingOnes. In: International Conference on Artificial Evolution, EA 2011, pp. 205\u2013216. Springer (2012)","DOI":"10.1007\/978-3-642-35533-2_18"},{"key":"1232_CR41","doi-asserted-by":"crossref","unstructured":"Doerr, C., Wagner, M.: Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 943\u2013950. ACM (2018)","DOI":"10.1145\/3205455.3205560"},{"key":"1232_CR42","doi-asserted-by":"crossref","DOI":"10.1016\/j.asoc.2019.106027","volume":"88","author":"C Doerr","year":"2020","unstructured":"Doerr, C., Ye, F., Horesh, N., Wang, H., Shir, O.M., B\u00e4ck, T.: Benchmarking discrete optimization heuristics with iohprofiler. Appl. Soft Comput. 88, 106027 (2020)","journal-title":"Appl. Soft Comput."},{"key":"1232_CR43","doi-asserted-by":"crossref","unstructured":"Doerr, B., Zheng, W.: 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":"1232_CR44","doi-asserted-by":"crossref","unstructured":"Eremeev, A.V.: On non-elitist evolutionary algorithms optimizing fitness functions with a plateau. In: Mathematical Optimization Theory and Operations Research, MOTOR 2020, pp. 329\u2013342. Springer (2020)","DOI":"10.1007\/978-3-030-49988-4_23"},{"key":"1232_CR45","doi-asserted-by":"crossref","DOI":"10.1016\/j.biosystems.2020.104312","volume":"200","author":"AV Eremeev","year":"2021","unstructured":"Eremeev, A.V., Spirov, A.V.: Modeling SELEX for regulatory regions using Royal Road and Royal Staircase fitness functions. Biosystems 200, 104312 (2021)","journal-title":"Biosystems"},{"key":"1232_CR46","doi-asserted-by":"crossref","first-page":"2455","DOI":"10.1016\/j.tcs.2008.08.021","volume":"410","author":"T Friedrich","year":"2009","unstructured":"Friedrich, T., Hebbinghaus, N., Neumann, F.: Comparison of simple diversity mechanisms on plateau functions. Theoret. Comput. Sci. 410, 2455\u20132462 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR47","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1016\/j.tcs.2009.06.020","volume":"411","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., Hebbinghaus, N., Neumann, F.: Plateaus can be harder in multi-objective optimization. Theoret. Comput. Sci. 411, 854\u2013864 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR48","doi-asserted-by":"crossref","unstructured":"Friedrich, t., K\u00f6tzing, t., Krejca, M.S.: EDAs cannot be balanced and stable. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 1139\u20131146. ACM (2016)","DOI":"10.1145\/2908812.2908895"},{"key":"1232_CR49","unstructured":"Garrett, P.: Fourier analysis on finite abelian groups. Preprint. Available at https:\/\/www-users.cse.umn.edu\/~garrett\/m\/mfms\/notes_c\/fin_ab_fourier.pdf (2012)"},{"key":"1232_CR50","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/s00453-015-0072-0","volume":"75","author":"C Gie\u00dfen","year":"2016","unstructured":"Gie\u00dfen, C., K\u00f6tzing, T.: Robustness of populations in stochastic environments. Algorithmica 75, 462\u2013489 (2016)","journal-title":"Algorithmica"},{"key":"1232_CR51","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1162\/evco.1999.7.2.173","volume":"7","author":"J Garnier","year":"1999","unstructured":"Garnier, J., Kallel, L., Schoenauer, M.: Rigorous hitting times for binary mutations. Evol. Comput. 7, 173\u2013203 (1999)","journal-title":"Evol. Comput."},{"key":"1232_CR52","doi-asserted-by":"crossref","unstructured":"Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Symposium on Theoretical Aspects of Computer Science, STACS 2003, pp. 415\u2013426. Springer (2003)","DOI":"10.1007\/3-540-36494-3_37"},{"key":"1232_CR53","first-page":"51","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":"1232_CR54","doi-asserted-by":"crossref","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective. Springer (2013)","DOI":"10.1007\/978-3-642-17339-4"},{"key":"1232_CR55","doi-asserted-by":"crossref","unstructured":"Jansen, T.: On the black-box complexity of example functions: the real jump function. In: Foundations of Genetic Algorithms, FOGA 2015, pp. 16\u201324. ACM (2015)","DOI":"10.1145\/2725494.2725507"},{"key":"1232_CR56","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1162\/106365605774666921","volume":"13","author":"T Jansen","year":"2005","unstructured":"Jansen, T., De Jong, K.A., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evol. Comput. 13, 413\u2013440 (2005)","journal-title":"Evol. Comput."},{"key":"1232_CR57","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1109\/4235.974841","volume":"5","author":"T Jansen","year":"2001","unstructured":"Jansen, T., Wegener, I.: Evolutionary algorithms\u2014how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. Evol. Comput. 5, 589\u2013599 (2001)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"1232_CR58","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.tcs.2013.06.007","volume":"545","author":"T Jansen","year":"2014","unstructured":"Jansen, T., Zarges, C.: Performance analysis of randomised search heuristics operating with a fixed budget. Theoret. Comput. Sci. 545, 39\u201358 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR59","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Witt, C.: Improved fixed-budget results via drift analysis. In: Parallel Problem Solving from Nature, PPSN 2020, Part II, pp. 648\u2013660. Springer (2020)","DOI":"10.1007\/978-3-030-58115-2_45"},{"key":"1232_CR60","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":"1232_CR61","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 154\u2013168. ACM (2019)","DOI":"10.1145\/3299904.3340316"},{"key":"1232_CR62","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes. Algorithmica 83, 3238\u20133280 (2021)","DOI":"10.1007\/s00453-021-00862-3"},{"key":"1232_CR63","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1162\/evco_a_00258","volume":"28","author":"A Lissovoi","year":"2020","unstructured":"Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: Simple hyper-heuristics control the neighbourhood size of randomised local search optimally for LeadingOnes. Evol. Comput. 28, 437\u2013461 (2020)","journal-title":"Evol. Comput."},{"key":"1232_CR64","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Qin, X.: More precise runtime analyses of non-elitist EAs in uncertain environments. In: Genetic and Evolutionary Computation Conference, 2021, pp. 1160\u20131168. ACM (2021)","DOI":"10.1145\/3449639.3459312"},{"key":"1232_CR65","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1162\/EVCO_a_00114","volume":"22","author":"J L\u00e4ssig","year":"2014","unstructured":"L\u00e4ssig, J., Sudholt, D.: General upper bounds on the runtime of parallel evolutionary algorithms. Evol. Comput. 22, 405\u2013437 (2014)","journal-title":"Evol. Comput."},{"key":"1232_CR66","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1017\/S0963548320000565","volume":"30","author":"PK Lehre","year":"2021","unstructured":"Lehre, P.K., Witt, C.: Tail bounds on hitting times of randomized search heuristics using variable drift analysis. Comb. Probab. Comput. 30, 550\u2013569 (2021)","journal-title":"Comb. Probab. Comput."},{"key":"1232_CR67","unstructured":"Mitchell, M., Forrest, S., Holland, J.H.: The royal road for genetic algorithms: fitness landscapes and GA performance. In: European Conference on Artificial Life (ECAL 1991), pp. 245\u2013254. MIT Press (1992)"},{"key":"1232_CR68","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087\u20131092 (1953)","journal-title":"J. Chem. Phys."},{"key":"1232_CR69","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1162\/EVCO_a_00169","volume":"25","author":"A Moraglio","year":"2017","unstructured":"Moraglio, A., Sudholt, D.: Principled design and runtime analysis of abstract convex evolutionary search. Evol. Comput. 25, 205\u2013236 (2017)","journal-title":"Evol. Comput."},{"key":"1232_CR70","unstructured":"M\u00fchlenbein, H.: How genetic algorithms really work: mutation and hillclimbing. In: Parallel Problem Solving from Nature, PPSN 1992, pp. 15\u201326. Elsevier (1992)"},{"key":"1232_CR71","doi-asserted-by":"crossref","first-page":"2750","DOI":"10.1016\/j.cor.2006.12.009","volume":"35","author":"F Neumann","year":"2008","unstructured":"Neumann, F.: Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Comput. OR 35, 2750\u20132759 (2008)","journal-title":"Comput. OR"},{"key":"1232_CR72","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s11721-008-0023-3","volume":"3","author":"F Neumann","year":"2009","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intell. 3, 35\u201368 (2009)","journal-title":"Swarm Intell."},{"key":"1232_CR73","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoret. Comput. Sci. 378, 32\u201340 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR74","doi-asserted-by":"crossref","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization\u2014Algorithms and Their Computational Complexity. Springer (2010)","DOI":"10.1007\/978-3-642-16544-3"},{"key":"1232_CR75","doi-asserted-by":"crossref","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":"1232_CR76","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/s00453-018-0488-4","volume":"81","author":"C Qian","year":"2019","unstructured":"Qian, C., Bian, C., Jiang, W., Tang, K.: Running time analysis of the $${(1+1)}$$-EA for OneMax and LeadingOnes under bit-wise noise. Algorithmica 81, 749\u2013795 (2019)","journal-title":"Algorithmica"},{"key":"1232_CR77","volume-title":"Convergence Properties of Evolutionary Algorithms","author":"G Rudolph","year":"1997","unstructured":"Rudolph, G.: Convergence Properties of Evolutionary Algorithms. Verlag Dr, Kov\u01cec (1997)"},{"key":"1232_CR78","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1162\/1063656043138941","volume":"12","author":"JE Rowe","year":"2004","unstructured":"Rowe, J.E., Vose, M.D., Wright, A.H.: Structural search spaces and genetic operators. Evol. Comput. 12, 461\u2013493 (2004)","journal-title":"Evol. Comput."},{"key":"1232_CR79","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1162\/EVCO_a_00098","volume":"21","author":"AW Sutton","year":"2013","unstructured":"Sutton, A.W., Chicano, F., Whitley, L.D.: Fitness function distributions over generalized search neighborhoods in the q-ary hypercube. Evol. Comput. 21, 561\u2013590 (2013)","journal-title":"Evol. Comput."},{"key":"1232_CR80","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1023\/B:JMMA.0000049379.14872.f5","volume":"3","author":"J Scharnow","year":"2004","unstructured":"Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms 3, 349\u2013366 (2004)","journal-title":"J. Math. Model. Algorithms"},{"key":"1232_CR81","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2013","unstructured":"Sudholt, D.: 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":"1232_CR82","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1007\/s00453-020-00671-0","volume":"83","author":"D Sudholt","year":"2021","unstructured":"Sudholt, D.: Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial. Algorithmica 83, 976\u20131011 (2021)","journal-title":"Algorithmica"},{"key":"1232_CR83","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1023\/A:1010928206141","volume":"45","author":"E van Nimwegen","year":"2001","unstructured":"van Nimwegen, E., Crutchfield, J.P.: Optimizing epochal evolutionary search: population-size dependent theory. Mach. Learn. 45, 77\u2013114 (2001)","journal-title":"Mach. Learn."},{"key":"1232_CR84","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1162\/evco.1998.6.3.253","volume":"6","author":"MD Vose","year":"1998","unstructured":"Vose, M.D., Wright, A.H.: The simple genetic algorithm and the walsh transform: part I, theory. Evol. Comput. 6, 253\u2013273 (1998)","journal-title":"Evol. Comput."},{"key":"1232_CR85","doi-asserted-by":"crossref","unstructured":"Wegener, I.: 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":"1232_CR86","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":"1232_CR87","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.ipl.2013.09.013","volume":"114","author":"C Witt","year":"2014","unstructured":"Witt, C.: 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":"1232_CR88","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.tcs.2022.08.014","volume":"940","author":"C Witt","year":"2023","unstructured":"Witt, C.: How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys. Theoret. Comput. Sci. 940, 18\u201342 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"1232_CR89","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1017\/S0963548304006650","volume":"14","author":"I Wegener","year":"2005","unstructured":"Wegener, I., Witt, C.: On the optimization of monotone polynomials by simple randomized search heuristics. Combin. Probab. Comput. 14, 225\u2013247 (2005)","journal-title":"Combin. Probab. Comput."},{"key":"1232_CR90","doi-asserted-by":"crossref","unstructured":"Wang, S., Zheng, W., Doerr, B.: Choosing the right algorithm with hints from complexity theory. In: International Joint Conference on Artificial Intelligence, IJCAI 2021, pp. 1697\u20131703. ijcai.org (2021)","DOI":"10.24963\/ijcai.2021\/234"},{"key":"1232_CR91","unstructured":"Zhang, C.: Formulas for hitting times and cover times for random walks on groups. arXiv:2302.01963 (2023)"},{"key":"1232_CR92","doi-asserted-by":"crossref","unstructured":"Zhou, Z.-H., Yang, Y., Qian, C.: Advances in Theories and Algorithms. Springer, Evolutionary Learning (2019)","DOI":"10.1007\/978-981-13-5956-9"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01232-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01232-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01232-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T14:40:32Z","timestamp":1721918432000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01232-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":92,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1232"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01232-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]},"assertion":[{"value":"23 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}