{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:59:05Z","timestamp":1783749545938,"version":"3.55.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T00:00:00Z","timestamp":1747267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Investissement d\u2019avenir project","award":["ANR-11-LABX-0056-LMH, LabEx LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH, LabEx LMH"]}]},{"name":"Gaspard Monge Program for optimization, operations research and their interactions with data sciences"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of an algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((1+1)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            evolutionary algorithm and the static, self-adjusting, and heavy-tailed\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((1+(\\lambda,\\lambda))\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            genetic algorithms on the OneMax benchmark. We are optimistic that the question of how to profit from good initial solutions is interesting beyond these first examples.\n          <\/jats:p>","DOI":"10.1145\/3675783","type":"journal-article","created":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T13:19:35Z","timestamp":1719839975000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["First Steps Toward a Runtime Analysis When Starting With a Good Solution"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7906-096X","authenticated-orcid":false,"given":"Denis","family":"Antipov","sequence":"first","affiliation":[{"name":"The University of Adelaide, Adelaide, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7120-8824","authenticated-orcid":false,"given":"Maxim","family":"Buzdalov","sequence":"additional","affiliation":[{"name":"Aberystwyth University, Aberystwyth, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9786-220X","authenticated-orcid":false,"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[{"name":"Laboratoire d\u2019Informatique (LIX), CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,5,15]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1007\/978-3-030-58115-2_39","volume-title":"Proceedings of the International Conference on Parallel Problem Solving From Nature (PPSN \u201920)","author":"Antipov Denis","year":"2020","unstructured":"Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2020. First steps towards a runtime analysis when starting with a good solution. In Proceedings of the International Conference on Parallel Problem Solving From Nature (PPSN \u201920), Part II. Springer, 560\u2013573."},{"key":"e_1_3_2_3_1","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/3449639.3459377","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201921)","author":"Antipov Denis","year":"2021","unstructured":"Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2021. Lazy parameter tuning and control: Choosing all parameters randomly from a power-law distribution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201921). ACM, 1115\u20131123."},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00957-5"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","unstructured":"Denis Antipov Maxim Buzdalov and Benjamin Doerr. 2024a. Code and data for \u201cFirst steps towards a runtime analysis when starting with a good solution\u201d. DOI: 10.5281\/zenodo.11622895","DOI":"10.5281\/zenodo.11622895"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-023-01098-z"},{"key":"e_1_3_2_7_1","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1007\/s00453-020-00731-5","article-title":"A tight runtime analysis for the  \\((\\mu+\\lambda)\\)  EA","volume":"83","author":"Antipov Denis","year":"2021","unstructured":"Denis Antipov and Benjamin Doerr. 2021. A tight runtime analysis for the \\((\\mu+\\lambda)\\) EA. Algorithmica 83 (2021), 1054\u20131095.","journal-title":"Algorithmica"},{"key":"e_1_3_2_8_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/3299904.3340317","volume-title":"Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA \u201919)","author":"Antipov Denis","year":"2019","unstructured":"Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2019. A tight runtime analysis for the \\((1+(\\lambda,\\lambda))\\) GA on LeadingOnes. In Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA \u201919). ACM, 169\u2013182."},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00907-7"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1996312"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1527125.1527134"},{"key":"e_1_3_2_12_1","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/3071178.3071297","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201917)","author":"Buzdalov Maxim","year":"2017","unstructured":"Maxim Buzdalov and Benjamin Doerr. 2017. Runtime analysis of the \\((1+(\\lambda,\\lambda))\\) genetic algorithm on random satisfiable 3-CNF formulas. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201917). ACM, 1343\u20131350."},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00881-0"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00185"},{"key":"e_1_3_2_15_1","doi-asserted-by":"crossref","unstructured":"Benjamin Doerr. 2020. Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Benjamin Doerr and Frank Neumann (Eds.) Springer 1\u201387. Retrieved from https:\/\/arxiv.org\/abs\/1801.06733","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"e_1_3_2_16_1","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1007\/s00453-017-0354-9","article-title":"Optimal static and self-adjusting parameter choices for the  \\((1+(\\lambda,\\lambda))\\)  genetic algorithm","volume":"80","author":"Doerr Benjamin","year":"2018","unstructured":"Benjamin Doerr and Carola Doerr. 2018. Optimal static and self-adjusting parameter choices for the \\((1+(\\lambda,\\lambda))\\) genetic algorithm. Algorithmica 80 (2018), 1658\u20131709.","journal-title":"Algorithmica"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.028"},{"key":"e_1_3_2_18_1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1145\/3321707.3321731","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201919)","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr, Carola Doerr, and Frank Neumann. 2019. Fast re-optimization via structural diversity. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201919). ACM, 233\u2013241."},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.06.014"},{"key":"e_1_3_2_20_1","first-page":"2083","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201911)","author":"Doerr Benjamin","year":"2011","unstructured":"Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. 2011a. Sharp bounds by probability-generating functions and variable drift. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201911). ACM, 2083\u20132090."},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9585-3"},{"key":"e_1_3_2_22_1","first-page":"1203","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201907)","author":"Doerr Benjamin","year":"2007","unstructured":"Benjamin Doerr and Daniel Johannsen. 2007. Adjacency list matchings: An ideal genotype for cycle covers. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201907). ACM, 1203\u20131210."},{"key":"e_1_3_2_23_1","first-page":"759","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201910)","author":"Doerr Benjamin","year":"2010","unstructured":"Benjamin Doerr and Daniel Johannsen. 2010. Edge-based representation beats vertex-based representation in shortest path problems. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201910). ACM, 759\u2013766."},{"key":"e_1_3_2_24_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/1967654.1967669","volume-title":"Proceedings of the Foundations of Genetic Algorithms (FOGA \u201911)","author":"Doerr Benjamin","year":"2011","unstructured":"Benjamin Doerr, Daniel Johannsen, Timo K\u00f6tzing, Per Kristian Lehre, Markus Wagner, and Carola Winzen. 2011b. Faster black-box algorithms through higher arity operators. In Proceedings of the Foundations of Genetic Algorithms (FOGA \u201911). ACM, 163\u2013172."},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.03.015"},{"key":"e_1_3_2_27_1","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1145\/3071178.3071301","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201917)","author":"Doerr Benjamin","year":"2017","unstructured":"Benjamin Doerr, Huu P. Le, R\u00e9gis Makhmara, and Ta D. Nguyen. 2017. Fast genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201917). ACM, 777\u2013784."},{"key":"e_1_3_2_28_1","doi-asserted-by":"crossref","unstructured":"Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization. Springer. Retrieved from http:\/\/www.lix.polytechnique.fr\/Labo\/Benjamin.Doerr\/doerr_neumann_book.html","DOI":"10.1007\/978-3-030-29414-4"},{"key":"e_1_3_2_29_1","doi-asserted-by":"crossref","first-page":"1381","DOI":"10.1145\/3512290.3528812","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201922)","author":"Doerr Benjamin","year":"2022","unstructured":"Benjamin Doerr, Amirhossein Rajabi, and Carsten Witt. 2022. Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201922). ACM, 1381\u20131389."},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1177-z"},{"key":"e_1_3_2_32_1","first-page":"229","article-title":"On Two problems of information theory","volume":"8","author":"Erd\u0151s Paul","year":"1963","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1963. On Two problems of information theory. Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet K\u00f6zlem\u00e9nyei 8 (1963), 229\u2013243.","journal-title":"Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet K\u00f6zlem\u00e9nyei"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/89657"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"e_1_3_2_35_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3564755","article-title":"Theoretical and empirical analysis of parameter control mechanisms in the  \\((1+(\\lambda,\\lambda))\\)  genetic algorithm","volume":"2","author":"Fajardo Mario A. Hevia","year":"2022","unstructured":"Mario A. Hevia Fajardo and Dirk Sudholt. 2022. Theoretical and empirical analysis of parameter control mechanisms in the \\((1+(\\lambda,\\lambda))\\) genetic algorithm. ACM Transactions on Evolutionary Learning and Optimization 2 (2022), 13 1\u201313:39.","journal-title":"ACM Transactions on Evolutionary Learning and Optimization"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666921"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.007"},{"key":"e_1_3_2_39_1","volume-title":"Random Combinatorial Structures and Randomized Search Heuristics","author":"Johannsen Daniel","year":"2010","unstructured":"Daniel Johannsen. 2010. Random Combinatorial Structures and Randomized Search Heuristics. Ph. D. Dissertation. Universit\u00e4t des Saarlandes."},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92918-1"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9616-8"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00168-X"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1108\/17563780910959893"},{"key":"e_1_3_2_44_1","first-page":"15","volume-title":"Proceedings of the Parallel Problem Solving from Nature (PPSN \u201992)","author":"M\u00fchlenbein Heinz","year":"1992","unstructured":"Heinz M\u00fchlenbein. 1992. How genetic algorithms really work: Mutation and hillclimbing. In Proceedings of the Parallel Problem Solving from Nature (PPSN \u201992). Elsevier, 15\u201326."},{"key":"e_1_3_2_45_1","doi-asserted-by":"crossref","unstructured":"Frank Neumann Mojgan Pourhassan and Vahid Roostapour. 2020. Analysis of evolutionary algorithms in dynamic and stochastic environments. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Benjamin Doerr and Frank Neumann (Eds.) Springer 323\u2013357. Retrieved from https:\/\/arxiv.org\/abs\/1806.08547","DOI":"10.1007\/978-3-030-29414-4_7"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.002"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1941919"},{"key":"e_1_3_2_48_1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","article-title":"The choice of the offspring population size in the  \\((1,\\lambda)\\)  evolutionary algorithm","volume":"545","author":"Rowe Jonathan E.","year":"2014","unstructured":"Jonathan E. Rowe and Dirk Sudholt. 2014. The choice of the offspring population size in the \\((1,\\lambda)\\) evolutionary algorithm. Theoretical Computer Science 545 (2014), 20\u201338.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_49_1","first-page":"2035","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201911)","author":"Rowe Jonathan E.","year":"2011","unstructured":"Jonathan E. Rowe and Michael D. Vose. 2011. Unbiased black box search algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201911). ACM, 2035\u20132042."},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0274-8"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731092"},{"key":"e_1_3_2_52_1","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-48224-5_6","volume-title":"Proceedings of the Automata, Languages and Programming (ICALP \u201901)","author":"Wegener Ingo","year":"2001","unstructured":"Ingo Wegener. 2001. Theoretical aspects of evolutionary algorithms. In Proceedings of the Automata, Languages and Programming (ICALP \u201901). Springer, 64\u201378."},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"e_1_3_2_54_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365606776022751"},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-13-5956-9"},{"key":"e_1_3_2_56_1","first-page":"477","volume-title":"Proceedings of the Adventures Between Lower Bounds and Higher Altitudes \u2013 Essays Dedicated to Juraj Hromkovi\u010d on the Occasion of His 60th Birthday","author":"Zych-Pawlewicz Anna","year":"2018","unstructured":"Anna Zych-Pawlewicz. 2018. Reoptimization of NP-hard problems. In Proceedings of the Adventures Between Lower Bounds and Higher Altitudes \u2013 Essays Dedicated to Juraj Hromkovi\u010d on the Occasion of His 60th Birthday. Springer, 477\u2013494."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3675783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3675783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:09Z","timestamp":1750291449000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3675783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,15]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3675783"],"URL":"https:\/\/doi.org\/10.1145\/3675783","relation":{},"ISSN":["2688-3007"],"issn-type":[{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,15]]},"assertion":[{"value":"2023-07-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}