{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:55:21Z","timestamp":1783749321606,"version":"3.55.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031700705","type":"print"},{"value":"9783031700712","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-70071-2_7","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774000},"page":"102-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["How Population Diversity Influences the\u00a0Efficiency of\u00a0Crossover"],"prefix":"10.1007","author":[{"given":"Sacha","family":"Cerf","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-15844-5_1","volume-title":"Parallel Problem Solving from Nature, PPSN XI","author":"S B\u00f6ttcher","year":"2010","unstructured":"B\u00f6ttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the leadingones problem. In: Schaefer, R., Cotta, C., Ko\u0142odziej, J., Rudolph, G. (eds.) Parallel Problem Solving from Nature, PPSN XI, pp. 1\u201310. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15844-5_1"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Cerf, S., Lengler, J.: How population diversity influences the efficiency of crossover. arXiv preprint (2024)","DOI":"10.1007\/978-3-031-70071-2_7"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1109\/TEVC.2017.2745715","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Oliveto, P.S.: Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Trans. Evol. Comput. 22, 720\u2013732 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"7_CR4","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"DC Dang","year":"2017","unstructured":"Dang, D.C., et al.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22(3), 484\u2013497 (2017)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"D Dang","year":"2018","unstructured":"Dang, D., et al.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22, 484\u2013497 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2014.11.028","volume":"567","author":"B Doerr","year":"2015","unstructured":"Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoret. Comput. Sci. 567, 87\u2013104 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR7","unstructured":"Doerr, B., Echarghaoui, A., Jamal, M., Krejca, M.S.: Lasting diversity and superior runtime guarantees for the $$(\\mu +1)$$ genetic algorithm. CoRR abs\/2302.12570 (2023)"},{"key":"7_CR8","doi-asserted-by":"publisher","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":"7_CR9","doi-asserted-by":"publisher","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":"7_CR10","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":"7_CR11","doi-asserted-by":"crossref","unstructured":"Doerr, C.: Complexity theory for discrete black-box optimization heuristics. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 133\u2013212 (2020)","DOI":"10.1007\/978-3-030-29414-4_3"},{"key":"7_CR12","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. Theoret. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Friedrich, T., et al.: Crossover for cardinality constrained optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 1399\u20131407. ACM (2022)","DOI":"10.1145\/3512290.3528713"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/3-540-48481-7_17","volume-title":"Algorithms - ESA\u2019 99","author":"T Jansen","year":"1999","unstructured":"Jansen, T., Wegener, I.: On the analysis of evolutionary algorithms \u2014 a proof that crossover really can help. In: Ne\u0161et\u0159il, J. (ed.) Algorithms - ESA\u2019 99, pp. 184\u2013193. Springer, Berlin, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48481-7_17"},{"issue":"1\u20133","key":"7_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.dam.2004.02.019","volume":"149","author":"T Jansen","year":"2005","unstructured":"Jansen, T., Wegener, I.: Real royal road functions-where crossover provably is essential. Discret. Appl. Math. 149(1\u20133), 111\u2013125 (2005)","journal-title":"Discret. Appl. Math."},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Jorritsma, J., Lengler, J., Sudholt, D.: Comma selection outperforms plus selection on OneMax with randomly planted optima. In: Genetic and Evolutionary Computation Conference (GECCO) (2023)","DOI":"10.1145\/3583131.3590488"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Sudholt, D., Theile, M.: How crossover helps in pseudo-Boolean optimization. In: Proceedings of GECCO\u201911, pp. 989\u2013996. ACM (2011)","DOI":"10.1145\/2001576.2001711"},{"key":"7_CR18","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, 623\u2013642 (2012)","journal-title":"Algorithmica"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1007\/s00500-010-0610-2","volume":"15","author":"PK Lehre","year":"2011","unstructured":"Lehre, P.K., Yao, X.: Crossover can be constructive when computing unique input-output sequences. Soft. Comput. 15, 1675\u20131687 (2011)","journal-title":"Soft. Comput."},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"J Lengler","year":"2020","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_2"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Lengler, J., Opris, A., Sudholt, D.: Analysing equilibrium states for population diversity. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1628\u20131636 (2023)","DOI":"10.1145\/3583131.3590465"},{"key":"7_CR22","unstructured":"Lengler, J., Opris, A., Sudholt, D.: A Tight $$O(4^k\/p_c)$$ runtime bound for a $$(\\mu +1)$$ GA on $$\\text{Jump}_k$$ for realistic crossover probabilities. In: Proceedings of the Genetic and Evolutionary Computation Conference, p to appear (2024)"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Neumann, F., Oliveto, P.S., Rudolph, G., Sudholt, D.: On the effectiveness of crossover for migration in parallel evolutionary algorithms. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 1587\u20131594 (2011)","DOI":"10.1145\/2001576.2001790"},{"key":"7_CR24","doi-asserted-by":"publisher","unstructured":"Oliveto, P.S., He, J., Yao, X.: Analysis of population-based evolutionary algorithms for the vertex cover problem. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 1563\u20131570 (2008). https:\/\/doi.org\/10.1109\/CEC.2008.4631000","DOI":"10.1109\/CEC.2008.4631000"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Oliveto, P.S., Sudholt, D., Witt, C.: Tight bounds on the expected runtime of a standard steady state genetic algorithm. Algorithmica., 1\u201356 (2022)","DOI":"10.1007\/s00453-021-00893-w"},{"key":"7_CR26","unstructured":"Rudolph, G.: Convergence Properties of Evolutionary Algorithms. Verlag Dr, Kov\u01cec (1997)"},{"issue":"3","key":"7_CR27","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2012","unstructured":"Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17(3), 418\u2013435 (2012)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1162\/EVCO_a_00171","volume":"25","author":"D Sudholt","year":"2017","unstructured":"Sudholt, D.: How crossover speeds up building block assembly in genetic algorithms. Evol. Comput. 25, 237\u2013274 (2017)","journal-title":"Evol. Comput."},{"key":"7_CR29","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-030-29414-4_8","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"D Sudholt","year":"2020","unstructured":"Sudholt, D.: The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 359\u2013404. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_8"},{"key":"7_CR30","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-319-91086-4_8","volume-title":"Handbook of Metaheuristics","author":"D Whitley","year":"2019","unstructured":"Whitley, D.: Next generation genetic algorithms: a user\u2019s guide and tutorial. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, pp. 245\u2013274. Springer International Publishing, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-319-91086-4_8"},{"key":"7_CR31","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."},{"issue":"2","key":"7_CR32","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C Witt","year":"2013","unstructured":"Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22(2), 294\u2013318 (2013)","journal-title":"Comb. Probab. Comput."}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-70071-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T21:39:38Z","timestamp":1732743578000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70071-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700705","9783031700712"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70071-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The author do not have conflicting interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"PPSN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Problem Solving from Nature","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hagenberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2024.fh-ooe.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}