{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T02:38:56Z","timestamp":1785551936436,"version":"3.56.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,9,6]],"date-time":"2017-09-06T00:00:00Z","timestamp":1504656000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["618091"],"award-info":[{"award-number":["618091"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M004252\/1"],"award-info":[{"award-number":["EP\/M004252\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["618091"],"award-info":[{"award-number":["618091"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00453-017-0369-2","type":"journal-article","created":{"date-parts":[[2017,9,6]],"date-time":"2017-09-06T21:55:35Z","timestamp":1504734935000},"page":"1604-1633","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism"],"prefix":"10.1007","volume":"80","author":[{"given":"Pietro S.","family":"Oliveto","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tiago","family":"Paix\u00e3o","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4688-182X","authenticated-orcid":false,"given":"Jorge","family":"P\u00e9rez Heredia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barbora","family":"Trubenov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,9,6]]},"reference":[{"issue":"2","key":"369_CR1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0167-6377(94)90065-5","volume":"16","author":"KD Boese","year":"1994","unstructured":"Boese, K.D., Kahng, A.B., Muddu, S.: A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. 16(2), 101\u2013113 (1994)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"369_CR2","first-page":"343","volume":"59","author":"D Corus","year":"2016","unstructured":"Corus, D., He, J., Jansen, T., Oliveto, P.S., Sudholt, D., Zarges, C.: On easiest functions for mutation operators in bio-inspired optimisation. Algorithmica 59(3), 343\u2013368 (2016)","journal-title":"Algorithmica"},{"key":"369_CR3","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Emergence of diversity and its benefits for crossover in genetic algorithms. In: Proceedings of the 14th Parallel Problem Solving from Nature Conference (PPSN XIV), Volume 9921 of LNCS, pp. 890\u2013900. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-45823-6_83"},{"key":"369_CR4","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima with diversity mechanisms and crossover. In: Proceedings of the 2016 Genetic and Evolutionary Computation Conference (GECCO \u201916), Volume 9921, pp. 645\u2013652. ACM Press, New York (2016)","DOI":"10.1145\/2908812.2908956"},{"issue":"3","key":"369_CR5","doi-asserted-by":"crossref","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"},{"key":"369_CR6","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. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"369_CR7","volume-title":"An Introduction to Probability Theory and its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and its Applications. Wiley, New York (1968)"},{"issue":"5","key":"369_CR8","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1111\/j.1558-5646.1984.tb00380.x","volume":"38","author":"JH Gillespie","year":"1984","unstructured":"Gillespie, J.H.: Molecular evolution over the mutational landscape. Evolution 38(5), 1116\u20131129 (1984)","journal-title":"Evolution"},{"issue":"2","key":"369_CR9","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1109\/TEVC.2014.2318025","volume":"19","author":"J He","year":"2015","unstructured":"He, J., Chen, T., Yao, X.: On the easiest and hardest fitness functions. IEEE Trans. Evol. Comput. 19(2), 295\u2013305 (2015)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"1","key":"369_CR10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0004-3702(01)00058-3","volume":"127","author":"J He","year":"2001","unstructured":"He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127(1), 57\u201385 (2001)","journal-title":"Artif. Intell."},{"key":"369_CR11","doi-asserted-by":"crossref","unstructured":"Horn, J., Goldberg, D.E., Deb, K.: Long path problems. In Parallel Problem Solving from Nature (PPSN III), Volume 866 of LNCS, pp. 149\u2013158 (1994)","DOI":"10.1007\/3-540-58484-6_259"},{"key":"369_CR12","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Storch, T.: When the plus strategy outperforms the comma strategyand when not. In: 2007 IEEE Symposium on Foundations of Computational Intelligence, pp. 25\u201332 (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"369_CR13","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."},{"issue":"1","key":"369_CR14","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s00453-002-0940-2","volume":"34","author":"T Jansen","year":"2002","unstructured":"Jansen, T., Wegener, I.: The analysis of evolutionary algorithms\u2014a proof that crossover really can help. Algorithmica 34(1), 47\u201366 (2002)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"369_CR15","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.tcs.2007.06.003","volume":"386","author":"T Jansen","year":"2007","unstructured":"Jansen, T., Wegener, I.: A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation. Theor. Comput. Sci. 386(1\u20132), 73\u201393 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"369_CR16","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(97)00133-9","volume":"82","author":"M Jerrum","year":"1998","unstructured":"Jerrum, M., Sorkin, G.B.: The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82(1\u20133), 155\u2013175 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"369_CR17","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1093\/genetics\/47.6.713","volume":"47","author":"M Kimura","year":"1962","unstructured":"Kimura, M.: On the probability of fixation of mutant genes in a population. Genetics 47(6), 713\u2013719 (1962)","journal-title":"Genetics"},{"key":"369_CR18","unstructured":"Lehre, P.K., Witt, C.: General drift analysis with tail bounds. CoRR (2013). arXiv:1307.2559"},{"key":"369_CR19","doi-asserted-by":"crossref","unstructured":"Merz, P., Freisleben, B.: Memetic algorithms and the fitness landscape of the graph bi-partitioning problem. In: Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V), pp. 765\u2013774. Springer, Berlin (1998)","DOI":"10.1007\/BFb0056918"},{"issue":"3","key":"369_CR20","doi-asserted-by":"crossref","first-page":"747","DOI":"10.2307\/1427186","volume":"18","author":"D Mitra","year":"1986","unstructured":"Mitra, D., Romeo, F., Sangiovanni-Vincentelli, A.: Convergence and finite-time behavior of simulated annealing. Adv. Appl. Probab. 18(3), 747\u2013771 (1986)","journal-title":"Adv. Appl. Probab."},{"key":"369_CR21","doi-asserted-by":"crossref","unstructured":"Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of the 2009 Genetic and Evolutionary Computation Conference (GECCO \u201909), pp. 835\u2013842. ACM Press, New York (2009)","DOI":"10.1145\/1569901.1570016"},{"key":"369_CR22","doi-asserted-by":"crossref","unstructured":"Ochoa, G., Veerapen, N.: Deconstructing the big valley search space hypothesis. In: Proceedings of the 16th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2016), pp. 58\u201373. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-30698-8_5"},{"key":"369_CR23","doi-asserted-by":"crossref","unstructured":"Oliveto, P.S., Lehre, P.K., Neumann, F.: Theoretical analysis of rank-based mutation-combining exploration and exploitation. In: Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC \u201909), pp. 1455\u20131462. IEEE Press, New York (2009)","DOI":"10.1109\/CEC.2009.4983114"},{"key":"369_CR24","doi-asserted-by":"crossref","unstructured":"Oliveto, P.\u00a0S., Paix\u00e3o, T., P\u00e9rez\u00a0Heredia, J., Sudholt, D., Trubenov\u00e1, B.: When non-elitism outperforms elitism for crossing fitness valleys. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO \u201916, pp. 1163\u20131170. ACM, New York (2016)","DOI":"10.1145\/2908812.2908909"},{"key":"369_CR25","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2013.06.015","volume":"545","author":"PS Oliveto","year":"2014","unstructured":"Oliveto, P.S., Witt, C.: On the runtime analysis of the simple genetic algorithm. Theor. Comput. Sci. 545, 2\u201319 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"369_CR26","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theor. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"369_CR27","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.jtbi.2015.07.011","volume":"383","author":"T Paix\u00e3o","year":"2015","unstructured":"Paix\u00e3o, T., Badkobeh, G., Barton, N., Corus, D., Dang, D.-C., Friedrich, T., Lehre, P.K., Sudholt, D., Sutton, A.M., Trubenov\u00e1, B.: Toward a unifying framework for evolutionary processes. J. Theor. Biol. 383, 28\u201343 (2015)","journal-title":"J. Theor. Biol."},{"issue":"2","key":"369_CR28","doi-asserted-by":"crossref","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":"2","key":"369_CR29","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1534\/genetics.116.189340","volume":"205","author":"J P\u00e9rez Heredia","year":"2016","unstructured":"P\u00e9rez Heredia, J., Trubenov\u00e1, B., Sudholt, D., Paix\u00e3o, T.: Selection limits to adaptive walks on correlated landscapes. Genetics 205(2), 803\u2013825 (2016)","journal-title":"Genetics"},{"key":"369_CR30","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1023\/A:1018983524911","volume":"86","author":"C Reeves","year":"1999","unstructured":"Reeves, C.: Landscapes, operators and heuristic search. Ann. Oper. Res. 86, 473\u2013490 (1999)","journal-title":"Ann. Oper. Res."},{"key":"369_CR31","doi-asserted-by":"crossref","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 $$ \u03bb ) evolutionary algorithm. Theor. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"369_CR32","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1162\/evco.1996.4.2.195","volume":"4","author":"G Rudolph","year":"1997","unstructured":"Rudolph, G.: How mutation and selection solve long-path problems in polynomial expected time. Evol. Comput. 4(2), 195\u2013205 (1997)","journal-title":"Evol. Comput."},{"key":"369_CR33","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1145\/42282.46160","volume":"35","author":"GH Sasaki","year":"1988","unstructured":"Sasaki, G.H., Hajek, B.: The time complexity of maximum matching by simulated annealing. J. ACM 35, 387\u2013403 (1988)","journal-title":"J. ACM"},{"issue":"26","key":"369_CR34","doi-asserted-by":"crossref","first-page":"2511","DOI":"10.1016\/j.tcs.2009.03.003","volume":"410","author":"D Sudholt","year":"2009","unstructured":"Sudholt, D.: The impact of parametrization in memetic evolutionary algorithms. Theor. Comput. Sci. 410(26), 2511\u20132528 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"369_CR35","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s00453-009-9384-2","volume":"59","author":"D Sudholt","year":"2011","unstructured":"Sudholt, D.: Hybridizing evolutionary algorithms with variable-depth search to overcome local optima. Algorithmica 59(3), 343\u2013368 (2011)","journal-title":"Algorithmica"},{"key":"369_CR36","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Simulated annealing beats metropolis in combinatorial optimization. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP\u00a0\u201905), Volume 3580 of LNCS, pp. 589\u2013601 (2005)","DOI":"10.1007\/11523468_48"},{"key":"369_CR37","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1146\/annurev.es.26.110195.003125","volume":"26","author":"MC Whitlock","year":"1995","unstructured":"Whitlock, M.C., Phillips, P.C., Moore, F.B.-G., Tonsor, S.J.: Multiple fitness peaks and epistasis. Annu. Rev. Ecol. Syst. 26, 601\u2013629 (1995)","journal-title":"Annu. Rev. Ecol. Syst."},{"issue":"1","key":"369_CR38","first-page":"65","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the ( $$\\mu $$ \u03bc +1) EA on simple pseudo-Boolean functions. Evol. Comput. 14(1), 65\u201386 (2006)","journal-title":"Evol. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0369-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0369-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0369-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T09:25:16Z","timestamp":1659432316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0369-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,6]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["369"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0369-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,6]]}}}