{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:38:15Z","timestamp":1759941495118,"version":"3.37.3"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,4]]},"abstract":"Abstract<\/jats:title>We analyse the performance of well-known evolutionary algorithms, the $$(1+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0EA and the $$(1+\\lambda )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0EA, in the prior noise model, where in each fitness evaluation the search point is altered before the evaluation with probability\u00a0p<\/jats:italic>. We present refined results for the expected optimisation time of these algorithms on the function Leading-Ones<\/jats:sc>, where bits have to be optimised in sequence. Previous work showed that the $$(1+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0EA on Leading-Ones<\/jats:sc> runs in polynomial expected time if $$p = O((\\log n)\/n^2)$$<\/jats:tex-math>\n \n p<\/mml:mi>\n =<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \/<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and needs superpolynomial expected time if $$p = \\omega ((\\log n)\/n)$$<\/jats:tex-math>\n \n p<\/mml:mi>\n =<\/mml:mo>\n \u03c9<\/mml:mi>\n (<\/mml:mo>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n \/<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, leaving a huge gap for which no results were known. We close this gap by showing that the expected optimisation time is $$\\varTheta (n^2) \\cdot \\exp (\\varTheta (\\min \\{pn^2, n\\}))$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n exp<\/mml:mo>\n \n (<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n min<\/mml:mo>\n \n {<\/mml:mo>\n p<\/mml:mi>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n ,<\/mml:mo>\n n<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all $$p \\le 1\/2$$<\/jats:tex-math>\n \n p<\/mml:mi>\n \u2264<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, allowing for the first time to locate the threshold between polynomial and superpolynomial expected times at $$p = \\varTheta ((\\log n)\/n^2)$$<\/jats:tex-math>\n \n p<\/mml:mi>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \/<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Hence the $$(1+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0EA on Leading-Ones<\/jats:sc> is surprisingly sensitive to noise. We also show that offspring populations of size $$\\lambda \\ge 3.42\\log n$$<\/jats:tex-math>\n \n \u03bb<\/mml:mi>\n \u2265<\/mml:mo>\n 3.42<\/mml:mn>\n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can effectively deal with much higher noise than known before. Finally, we present an example of a rugged landscape where prior noise can help to escape from local optima by blurring the landscape and allowing a hill climber to see the underlying gradient. We prove that in this particular setting noise can have a highly beneficial effect on performance.<\/jats:p>","DOI":"10.1007\/s00453-020-00671-0","type":"journal-article","created":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T06:02:22Z","timestamp":1579932142000},"page":"976-1011","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6020-1646","authenticated-orcid":false,"given":"Dirk","family":"Sudholt","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"key":"671_CR1","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2015.04.008","volume":"605","author":"Y Akimoto","year":"2015","unstructured":"Akimoto, Y., Astete-Morales, S., Teytaud, O.: Analysis of runtime of optimization algorithms for noisy functions over discrete codomains. Theor. Comput. Sci. 605, 42\u201350 (2015)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Badkobeh, G., Lehre, P.K., Sudholt, D.: Black-box complexity of parallel search with distributed populations. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201915), pp. 3\u201315. ACM Press, New York (2015)","key":"671_CR2","DOI":"10.1145\/2725494.2725504"},{"doi-asserted-by":"crossref","unstructured":"Baswana, S., Biswas, S., Doerr, B., Friedrich, T., Kurur, P.P., Neumann, F.: Computing single source shortest paths using single-objective fitness functions. In: Proceedings of FOGA\u201909, pp. 59\u201366. ACM Press, New York (2009)","key":"671_CR3","DOI":"10.1145\/1527125.1527134"},{"issue":"2","key":"671_CR4","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0045-7825(99)00386-2","volume":"186","author":"H-G Beyer","year":"2000","unstructured":"Beyer, H.-G.: Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Comput. Methods Appl. Mech. Eng. 186(2), 239\u2013267 (2000)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"671_CR5","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-319-99259-4_14","volume-title":"Parallel Problem Solving from Nature\u2014PPSN XV","author":"C Bian","year":"2018","unstructured":"Bian, C., Qian, C., Tang, K.: Towards a running time analysis of the $$(1+1)$$-EA for OneMax and LeadingOnes under general bit-wise noise. In: Auger, A., Fonseca, C.M., Louren\u00e7o, N., Machado, P., Paquete, L., Whitley, D. (eds.) Parallel Problem Solving from Nature\u2014PPSN XV, pp. 165\u2013177. Springer, Cham (2018)"},{"issue":"2","key":"671_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s11047-008-9098-4","volume":"8","author":"L Bianchi","year":"2009","unstructured":"Bianchi, L., Dorigo, M., Gambardella, L.M., Gutjahr, W.J.: A survey on metaheuristics for stochastic combinatorial optimization. Nat. Comput. 8(2), 239\u2013287 (2009)","journal-title":"Nat. Comput."},{"doi-asserted-by":"crossref","unstructured":"Covantes\u00a0Osuna, E., Gao, W., Neumann, F., Sudholt, D.: Speeding up evolutionary multi-objective optimisation through diversity-based parent selection. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201917), pp. 553\u2013560. ACM, New York (2017)","key":"671_CR7","DOI":"10.1145\/3071178.3080294"},{"key":"671_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s10878-006-9036-2","volume":"14","author":"V Cutello","year":"2007","unstructured":"Cutello, V., Nicosia, G., Pavone, M.: An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem. J. Comb. Optim. 14, 9\u201333 (2007)","journal-title":"J. Comb. Optim."},{"doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Lehre, P.K.: Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201915), pp. 62\u201368. ACM, New York (2015)","key":"671_CR9","DOI":"10.1145\/2725494.2725508"},{"issue":"3","key":"671_CR10","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","volume":"75","author":"D-C Dang","year":"2016","unstructured":"Dang, D.-C., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75(3), 428\u2013461 (2016)","journal-title":"Algorithmica"},{"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: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201918), pp. 1467\u20131474. ACM, New York (2018)","key":"671_CR11","DOI":"10.1145\/3205455.3205563"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Gnewuch, M., Hebbinghaus, N., Neumann, F.: A rigorous view on neutrality. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC\u201907), pp. 2591\u20132597 (2007)","key":"671_CR12","DOI":"10.1109\/CEC.2007.4424797"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Jansen, T., Klein, C.: Comparing global and local mutations on bit strings. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908), pp. 929\u2013936. ACM, New York (2008)","key":"671_CR13","DOI":"10.1145\/1389095.1389274"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Hota, A., K\u00f6tzing, T.: Ants easily solve stochastic shortest path problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201912), pp. 17\u201324 (2012)","key":"671_CR14","DOI":"10.1145\/2330163.2330167"},{"issue":"1","key":"671_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/EVCO_a_00055","volume":"21","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Mutation rate matters even when optimizing monotonic functions. Evol. Comput. 21(1), 1\u201321 (2013)","journal-title":"Evol. Comput."},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Kodric, B., Voigt, M.: Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In: Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC\u201913), pp. 432\u2013439 (2013)","key":"671_CR16","DOI":"10.1109\/CEC.2013.6557601"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Sudholt, D., Witt, C.: When do evolutionary algorithms optimize separable functions in parallel? In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201913), pp. 51\u201364. ACM, New York (2013)","key":"671_CR17","DOI":"10.1145\/2460239.2460245"},{"doi-asserted-by":"crossref","unstructured":"Droste, S.: Analysis of the $$(1+1)$$ EA for a noisy OneMax. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), pp. 1088\u20131099. Springer, Berlin (2004)","key":"671_CR18","DOI":"10.1007\/978-3-540-24854-5_107"},{"issue":"1\u20132","key":"671_CR19","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. Theor. Comput. Sci. 276(1\u20132), 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Feldmann, M., K\u00f6tzing, T.: Optimizing expected path lengths with ant colony optimization using fitness proportional update. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201913), pp. 65\u201374. ACM, New York (2013)","key":"671_CR20","DOI":"10.1145\/2460239.2460246"},{"doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: Robustness of ant colony optimization to noise. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201915), pp. 17\u201324. ACM, New York (2015)","key":"671_CR21","DOI":"10.1145\/2739480.2754723"},{"issue":"3","key":"671_CR22","first-page":"477","volume":"21","author":"T Friedrich","year":"2017","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: The compact genetic algorithm is efficient under extreme Gaussian noise. IEEE Trans. Evol. Comput. 21(3), 477\u2013490 (2017)","journal-title":"IEEE Trans. Evol. Comput."},{"unstructured":"Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: Proceedings of the 2003 Congress on Evolutionary Computation (CEC\u201903), vol. 3, pp. 1918\u20131925 (2003)","key":"671_CR23"},{"issue":"3","key":"671_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1162\/EVCO_a_00013","volume":"18","author":"O Giel","year":"2010","unstructured":"Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimisation. Evol. Comput. 18(3), 335\u2013356 (2010)","journal-title":"Evol. Comput."},{"issue":"3","key":"671_CR25","doi-asserted-by":"publisher","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(3), 462\u2013489 (2016)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Storch, T.: When the plus strategy outperforms the comma strategy and when not. In: Proceedings of the IEEE Symposium on Foundations of Computational Intelligence, FOCI 2007, pp. 25\u201332. IEEE, New York (2007)","key":"671_CR26","DOI":"10.1109\/FOCI.2007.372143"},{"issue":"1","key":"671_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco.2010.18.1.18101","volume":"18","author":"T Jansen","year":"2010","unstructured":"Jansen, T., Sudholt, D.: Analysis of an asymmetric mutation operator. Evol. Comput. 18(1), 1\u201326 (2010)","journal-title":"Evol. Comput."},{"key":"671_CR28","doi-asserted-by":"publisher","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."},{"issue":"3","key":"671_CR29","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00453-010-9403-3","volume":"59","author":"M Jebalia","year":"2011","unstructured":"Jebalia, M., Auger, A., Hansen, N.: Log-linear convergence and divergence of the scale-invariant $$(1+1)$$-ES in noisy environments. Algorithmica 59(3), 425\u2013460 (2011)","journal-title":"Algorithmica"},{"issue":"3","key":"671_CR30","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1109\/TEVC.2005.846356","volume":"9","author":"Y Jin","year":"2005","unstructured":"Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments\u2014a survey. IEEE Trans. Evol. Comput. 9(3), 303\u2013317 (2005)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"7","key":"671_CR31","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1007\/s00500-013-0991-0","volume":"17","author":"J L\u00e4ssig","year":"2013","unstructured":"L\u00e4ssig, J., Sudholt, D.: Design and analysis of migration in parallel evolutionary algorithms. Soft. Comput. 17(7), 1121\u20131144 (2013)","journal-title":"Soft. Comput."},{"issue":"2","key":"671_CR32","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TEVC.2004.823470","volume":"8","author":"M Laumanns","year":"2004","unstructured":"Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Trans. Evol. Comput. 8(2), 170\u2013182 (2004)","journal-title":"IEEE Trans. Evol. Comput."},{"unstructured":"Lehre, P.K., Witt, C.: General drift analysis with tail bounds (2013). CoRR. arXiv:1307.2559","key":"671_CR33"},{"issue":"4","key":"671_CR34","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(4), 643\u2013666 (2018)","journal-title":"Comb. Probab. Comput."},{"key":"671_CR35","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/058","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2008","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, New York (2008)"},{"doi-asserted-by":"crossref","unstructured":"Meyer-Nieberg, S., Beyer, H.-G.: Why noise may be good: additive noise on the sharp ridge. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908), pp. 511\u2013518. ACM, New York (2008)","key":"671_CR36","DOI":"10.1145\/1389095.1389192"},{"key":"671_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"key":"671_CR38","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.tcs.2014.06.023","volume":"561","author":"AQ Nguyen","year":"2015","unstructured":"Nguyen, A.Q., Sutton, A.M., Neumann, F.: Population size matters: rigorous runtime results for maximizing the hypervolume indicator. Theor. Comput. Sci. 561, 24\u201336 (2015)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Nguyen, P.T.H., Sudholt, D.: Memetic algorithms beat evolutionary algorithms on the class of hurdle problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201918), pp. 1071\u20131078. ACM, New York (2018)","key":"671_CR39","DOI":"10.1145\/3205455.3205456"},{"doi-asserted-by":"crossref","unstructured":"Ochoa, G., Veerapen, N.: Deconstructing the big valley search space hypothesis. In: Proceedings of Evolutionary Computation in Combinatorial Optimization (EvoCOP\u00a02016), pp. 58\u201373. Springer, New York (2016)","key":"671_CR40","DOI":"10.1007\/978-3-319-30698-8_5"},{"doi-asserted-by":"crossref","unstructured":"Oliveto, P.S., Sudholt, D.: On the runtime analysis of stochastic ageing mechanisms. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2014), pp. 113\u2013120. ACM Press, New York (2014)","key":"671_CR41","DOI":"10.1145\/2576768.2598328"},{"issue":"3","key":"671_CR42","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(3), 369\u2013386 (2011)","journal-title":"Algorithmica"},{"unstructured":"Oliveto, P.S., Witt, C.: Erratum: simplified drift analysis for proving lower bounds in evolutionary computation. ArXiv e-prints (2012)","key":"671_CR43"},{"issue":"2","key":"671_CR44","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s00453-016-0212-1","volume":"78","author":"T Paix\u00e3o","year":"2017","unstructured":"Paix\u00e3o, T., P\u00e9rez Heredia, J., Sudholt, D., Trubenov\u00e1, B.: Towards a runtime comparison of natural and artificial evolution. Algorithmica 78(2), 681\u2013713 (2017)","journal-title":"Algorithmica"},{"issue":"1","key":"671_CR45","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2004.03.038","volume":"320","author":"A Pr\u00fcgel-Bennett","year":"2004","unstructured":"Pr\u00fcgel-Bennett, A.: When a genetic algorithm outperforms hill-climbing. Theor. Comput. Sci. 320(1), 135\u2013153 (2004)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Prugel-Bennett, A., Rowe, J., Shapiro, J.: Run-time analysis of population-based evolutionary algorithm in noisy environments. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201915), pp. 69\u201375. ACM, New York (2015)","key":"671_CR46","DOI":"10.1145\/2725494.2725498"},{"key":"671_CR47","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.artint.2013.09.002","volume":"204","author":"C Qian","year":"2013","unstructured":"Qian, C., Yu, Y., Zhou, Z.-H.: An analysis on recombination in multi-objective evolutionary optimization. Artif. Intell. 204, 99\u2013119 (2013)","journal-title":"Artif. Intell."},{"key":"671_CR48","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1007\/s00453-018-0488-4","volume":"81","author":"C Qian","year":"2018","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 (2018)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Qian, C., Bian, C., Yu, Y., Tang, K., Yao, X.: Analysis of noisy evolutionary optimization when sampling fails. In: Proceedings of the 20th ACM Conference on Genetic and Evolutionary Computation (GECCO\u201918), pp. 1507\u20131514 (2018)","key":"671_CR49","DOI":"10.1145\/3205455.3205643"},{"issue":"2","key":"671_CR50","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1162\/evco_a_00201","volume":"26","author":"C Qian","year":"2018","unstructured":"Qian, C., Yu, Y., Tang, K., Jin, Y., Yao, X., Zhou, Z.-H.: On the effectiveness of sampling for evolutionary optimization in noisy environments. Evol. Comput. 26(2), 237\u2013267 (2018)","journal-title":"Evol. Comput."},{"issue":"1","key":"671_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco_a_00170","volume":"26","author":"C Qian","year":"2018","unstructured":"Qian, C., Yu, Y., Zhou, Z.-H.: Analyzing evolutionary optimization in noisy environments. Evol. Comput. 26(1), 1\u201341 (2018)","journal-title":"Evol. Comput."},{"doi-asserted-by":"crossref","unstructured":"Rana, S., Whitley, L.D., Cogswell, R.: Searching in the presence of noise. In: Proceedings of PPSN IV, pp. 198\u2013207. Springer, Berlin (1996)","key":"671_CR52","DOI":"10.1007\/3-540-61723-X_984"},{"key":"671_CR53","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1023\/A:1018983524911","volume":"86","author":"CR Reeves","year":"1999","unstructured":"Reeves, C.R.: Landscapes, operators and heuristic search. Ann. Oper. Res. 86, 473\u2013490 (1999)","journal-title":"Ann. Oper. Res."},{"key":"671_CR54","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. Theor. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Sudholt, D.: On the robustness of evolutionary algorithms to noise: refined results and an example where noise helps. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018), pp. 1523\u20131530. ACM, New York (2018)","key":"671_CR55","DOI":"10.1145\/3205455.3205595"},{"issue":"4","key":"671_CR56","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00453-011-9606-2","volume":"64","author":"D Sudholt","year":"2012","unstructured":"Sudholt, D., Thyssen, C.: A simple ant colony optimizer for stochastic shortest path problems. Algorithmica 64(4), 643\u2013672 (2012)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00671-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00671-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00671-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,21]],"date-time":"2021-03-21T07:03:46Z","timestamp":1616310226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00671-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,25]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["671"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00671-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,25]]},"assertion":[{"value":"3 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}