[{"doi":"10.1016/j.tcs.2023.113757","title":"Do Additional Target Points Speed Up Evolutionary Algorithms?","author":[{"id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob"},{"last_name":"Sudholt","full_name":"Sudholt, Dirk","first_name":"Dirk"}],"date_created":"2023-11-14T15:58:56Z","date_updated":"2023-12-13T10:51:07Z","citation":{"mla":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary Algorithms?” <i>Theoretical Computer Science</i>, 2023, p. 113757, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>.","bibtex":"@article{Bossek_Sudholt_2023, title={Do Additional Target Points Speed Up Evolutionary Algorithms?}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>}, journal={Theoretical Computer Science}, author={Bossek, Jakob and Sudholt, Dirk}, year={2023}, pages={113757} }","short":"J. Bossek, D. Sudholt, Theoretical Computer Science (2023) 113757.","apa":"Bossek, J., &#38; Sudholt, D. (2023). Do Additional Target Points Speed Up Evolutionary Algorithms? <i>Theoretical Computer Science</i>, 113757. <a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">https://doi.org/10.1016/j.tcs.2023.113757</a>","ama":"Bossek J, Sudholt D. Do Additional Target Points Speed Up Evolutionary Algorithms? <i>Theoretical Computer Science</i>. Published online 2023:113757. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>","ieee":"J. Bossek and D. Sudholt, “Do Additional Target Points Speed Up Evolutionary Algorithms?,” <i>Theoretical Computer Science</i>, p. 113757, 2023, doi: <a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>.","chicago":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary Algorithms?” <i>Theoretical Computer Science</i>, 2023, 113757. <a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">https://doi.org/10.1016/j.tcs.2023.113757</a>."},"page":"113757","year":"2023","publication_identifier":{"issn":["0304-3975"]},"language":[{"iso":"eng"}],"keyword":["Evolutionary algorithms","pseudo-Boolean functions","runtime analysis"],"user_id":"102979","department":[{"_id":"819"}],"_id":"48871","status":"public","abstract":[{"lang":"eng","text":"Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT{$\\cup$}S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions with polynomial expected optimisation times we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,{$\\lambda$}) EA on OneMax. However, for the one-dimensional Ising model the time to reach Hamming balls of radius (1/2-{$ϵ$})n around optima does not reduce the asymptotic expected optimisation time in the worst case. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time."}],"type":"journal_article","publication":"Theoretical Computer Science"},{"abstract":[{"text":"Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT {$\\cup$} S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,{$\\lambda$}) EA on One-Max. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.","lang":"eng"}],"status":"public","publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","type":"book_chapter","keyword":["evolutionary algorithms","pseudo-boolean functions","runtime analysis","theory"],"language":[{"iso":"eng"}],"extern":"1","_id":"48862","department":[{"_id":"819"}],"user_id":"102979","place":"New York, NY, USA","year":"2021","page":"1–11","citation":{"chicago":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary Algorithms?” In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 1–11. New York, NY, USA: Association for Computing Machinery, 2021.","ieee":"J. Bossek and D. Sudholt, “Do Additional Optima Speed up Evolutionary Algorithms?,” in <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–11.","ama":"Bossek J, Sudholt D. Do Additional Optima Speed up Evolutionary Algorithms? In: <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association for Computing Machinery; 2021:1–11.","apa":"Bossek, J., &#38; Sudholt, D. (2021). Do Additional Optima Speed up Evolutionary Algorithms? In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i> (pp. 1–11). Association for Computing Machinery.","mla":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary Algorithms?” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–11.","short":"J. Bossek, D. Sudholt, in: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–11.","bibtex":"@inbook{Bossek_Sudholt_2021, place={New York, NY, USA}, title={Do Additional Optima Speed up Evolutionary Algorithms?}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2021}, pages={1–11} }"},"publication_identifier":{"isbn":["978-1-4503-8352-3"]},"publication_status":"published","title":"Do Additional Optima Speed up Evolutionary Algorithms?","date_updated":"2023-12-13T10:45:31Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:55Z","author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"full_name":"Sudholt, Dirk","last_name":"Sudholt","first_name":"Dirk"}]}]