{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:23:52Z","timestamp":1786980232344,"version":"3.56.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T00:00:00Z","timestamp":1474243200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme (BE)","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":[[2017,6]]},"DOI":"10.1007\/s00453-016-0212-1","type":"journal-article","created":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T09:03:04Z","timestamp":1474275784000},"page":"681-713","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["Towards a Runtime Comparison of Natural and Artificial Evolution"],"prefix":"10.1007","volume":"78","author":[{"given":"Tiago","family":"Paix\u00e3o","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"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":[[2016,9,19]]},"reference":[{"key":"212_CR1","series-title":"Series on Theoretical Computer Science","volume-title":"Theory of Randomized Search Heuristics-Foundations and Recent Developments","year":"2011","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics-Foundations and Recent Developments. Series on Theoretical Computer Science, vol. 1. World Scientific, Singapore (2011)"},{"issue":"29","key":"212_CR2","doi-asserted-by":"publisher","first-page":"10620","DOI":"10.1073\/pnas.1406556111","volume":"111","author":"E Chastain","year":"2014","unstructured":"Chastain, E., Livnat, A., Papadimitriou, C., Vazirani, U.: Algorithms, games, and evolution. Proc. Natl. Acad. Sci. 111(29), 10620\u201310623 (2014)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"212_CR3","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Pavlogiannis, A., Adlam, B., Nowak, M.A.: The time scale of evolutionary innovation. PLoS Comput. Biol. 10(9), 1\u20137 (2014)","DOI":"10.1371\/journal.pcbi.1003818"},{"key":"212_CR4","doi-asserted-by":"publisher","unstructured":"Corus, D., Dang, D.-C., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. In: Parallel Problem Solving from Nature (PPSN), Springer, Berlin, pp. 912\u2013921 (2014)","DOI":"10.1007\/978-3-319-10762-2_90"},{"key":"212_CR5","doi-asserted-by":"publisher","unstructured":"Doerr, B.: Analyzing Randomized Search Heuristics: Tools from Probability Theory. In: [1], pp. 1\u201320. World Scientific, Singapore (2011)","DOI":"10.1142\/9789814282673_0001"},{"key":"212_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44874-8","volume-title":"Introduction to Evolutionary Computing","author":"A\u00a0E Eiben","year":"2015","unstructured":"Eiben, A\u00a0.E., Smith, J\u00a0.E.: Introduction to Evolutionary Computing, 2nd edn. Springer, Berlin (2015)","edition":"2"},{"key":"212_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21822-9","volume-title":"Mathematical Population Genetics 1: Theoretical Introduction","author":"WJ Ewens","year":"2004","unstructured":"Ewens, W.J.: Mathematical Population Genetics 1: Theoretical Introduction, 2nd edn. Springer, New York (2004)","edition":"2"},{"issue":"5","key":"212_CR8","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.2307\/2408444","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"},{"key":"212_CR9","doi-asserted-by":"publisher","unstructured":"J\u00e4gersk\u00fcpper, J., Storch, T.: When the plus strategy outperforms the comma strategy and when not. In: Proceedings of IEEE Foundations of Computational Intelligence (FOCI 2007), pp. 25\u201332. IEEE (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"212_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms. The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms. The Computer Science Perspective. Springer, Berlin (2013)"},{"key":"212_CR11","doi-asserted-by":"publisher","unstructured":"Jansen, T., Oliveto, P.S., Zarges, C.: On the analysis of the immune-inspired B-Cell algorithm for the Vertex Cover problem. In: Proceedings of the International Conference on Artificial Immune Systems (ICARIS \u201911), Springer, Berlin, pp. 117\u2013131 (2011)","DOI":"10.1007\/978-3-642-22371-6_13"},{"issue":"1\u20132","key":"212_CR12","doi-asserted-by":"publisher","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."},{"key":"212_CR13","unstructured":"Johannsen, D.: Random Combinatorial Structures and Randomized Search Heuristics. Ph.D. thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany and the Max-Planck-Institut f\u00fcr Informatik (2010)"},{"issue":"6","key":"212_CR14","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"},{"issue":"4","key":"212_CR15","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00453-012-9616-8","volume":"64","author":"PK Lehre","year":"2012","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64(4), 623\u2013642 (2012)","journal-title":"Algorithmica"},{"issue":"9","key":"212_CR16","doi-asserted-by":"publisher","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. Oper. Res. 35(9), 2750\u20132759 (2008)","journal-title":"Comput. Oper. Res."},{"key":"212_CR17","doi-asserted-by":"publisher","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\u00a0\u201909), pp. 835\u2013842, ACM (2009)","DOI":"10.1145\/1569901.1570016"},{"issue":"1","key":"212_CR18","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 378(1), 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"212_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00453-007-9134-2","volume":"54","author":"F Neumann","year":"2009","unstructured":"Neumann, F., Witt, C.: Runtime analysis of a simple ant colony optimization algorithm. Algorithmica 54(2), 243\u2013255 (2009)","journal-title":"Algorithmica"},{"key":"212_CR20","volume-title":"Bioinspired Computation in Combinatorial Optimization\u2014Algorithms and Their Computational Complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization\u2014Algorithms and Their Computational Complexity. Springer, Berlin (2010)"},{"key":"212_CR21","doi-asserted-by":"publisher","unstructured":"Oliveto, P.S., Sudholt, D.: On the runtime analysis of stochastic ageing mechanisms. In: Proceedings of the 2014 Genetic and Evolutionary Computation Conference (GECCO \u201914), ACM Press, pp. 113\u2013120 (2014)","DOI":"10.1145\/2576768.2598328"},{"issue":"3","key":"212_CR22","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"},{"key":"212_CR23","doi-asserted-by":"publisher","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":"212_CR24","doi-asserted-by":"publisher","unstructured":"Paix\u00e3o, T., Badkobeh, G., Barton, N., \u00c7\u00f6r\u00fc\u015f, 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)","DOI":"10.1016\/j.jtbi.2015.07.011"},{"key":"212_CR25","doi-asserted-by":"publisher","unstructured":"Paix\u00e3o, T., P\u00e9rez\u00a0Heredia, J., Sudholt, D., Trubenov\u00e1, B.: First steps towards a runtime comparison of natural and artificial evolution. In: Proceedings of the 2015 Genetic and Evolutionary Computation Conference (GECCO \u201915), pp. 1455\u20131462, ACM (2015)","DOI":"10.1145\/2739480.2754758"},{"issue":"1","key":"212_CR26","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00453-008-9253-4","volume":"57","author":"J Reichel","year":"2010","unstructured":"Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. Algorithmica 57(1), 187\u2013206 (2010)","journal-title":"Algorithmica"},{"key":"212_CR27","doi-asserted-by":"publisher","unstructured":"Rohlfshagen, P., Lehre, P.K., Yao, X.: Dynamic evolutionary optimisation: an analysis of frequency and magnitude of change. In: Proceedings of the 2009 Genetic and Evolutionary Computation Conference (GECCO \u201909), ACM Press, pp. 1713\u20131720 (2009)","DOI":"10.1145\/1569901.1570131"},{"key":"212_CR28","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 $$ \u03bb ) evolutionary algorithm. Theor. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"212_CR29","doi-asserted-by":"publisher","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. Modell. Algorithms 3(4), 349\u2013366 (2004)","journal-title":"J. Math. Modell. Algorithms"},{"issue":"3","key":"212_CR30","doi-asserted-by":"publisher","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(3), 418\u2013435 (2013)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"4","key":"212_CR31","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"},{"issue":"3","key":"212_CR32","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.jtbi.2007.08.012","volume":"249","author":"A Traulsen","year":"2007","unstructured":"Traulsen, A., Iwasa, Y., Nowak, M.A.: The fastest evolutionary trajectory. J. Theor. Biol. 249(3), 617\u2013623 (2007)","journal-title":"J. Theor. Biol."},{"issue":"1","key":"212_CR33","first-page":"3:1","volume":"56","author":"L\u00a0G Valiant","year":"2009","unstructured":"Valiant, L\u00a0.G.: Evolvability. J. ACM 56(1), 3:1\u20133:21 (2009)","journal-title":"J. ACM"},{"key":"212_CR34","doi-asserted-by":"publisher","unstructured":"Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In: Sarker, R., Mohammadian, M., Yao, X. (eds.) Evolutionary Optimization, volume\u00a048 of International Series in Operations Research & Management Science, chapter\u00a014. Kluwer Academic Publishers, Dordrecht, pp. 349\u2013369 (2003)","DOI":"10.1007\/0-306-48041-7_14"},{"key":"212_CR35","doi-asserted-by":"publisher","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS \u201905), Springer, Berlin, pp. 44\u201356 (2005)","DOI":"10.1007\/978-3-540-31856-9_4"},{"issue":"1","key":"212_CR36","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.tcs.2008.05.011","volume":"403","author":"C Witt","year":"2008","unstructured":"Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theor. Comput. Sci. 403(1), 104\u2013120 (2008)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0212-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0212-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0212-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T16:01:58Z","timestamp":1657296118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0212-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,19]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["212"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0212-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,19]]}}}