[{"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","type":"book_chapter","publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","keyword":["evolutionary algorithms","pseudo-boolean functions","runtime analysis","theory"],"language":[{"iso":"eng"}],"extern":"1","_id":"48862","user_id":"102979","department":[{"_id":"819"}],"place":"New York, NY, USA","year":"2021","citation":{"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.","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.","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.","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.","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.","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} }"},"page":"1–11","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-8352-3"]},"title":"Do Additional Optima Speed up Evolutionary Algorithms?","publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:45:31Z","date_created":"2023-11-14T15:58:55Z","author":[{"first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob"},{"last_name":"Sudholt","full_name":"Sudholt, Dirk","first_name":"Dirk"}]},{"publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","type":"book_chapter","status":"public","abstract":[{"lang":"eng","text":"Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph (NNG) transformation of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. Eventually, a proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features."}],"department":[{"_id":"819"}],"user_id":"102979","_id":"48881","extern":"1","language":[{"iso":"eng"}],"keyword":["automated algorithm selection","graph theory","instance features","normalization","traveling salesperson problem (TSP)"],"publication_identifier":{"isbn":["978-1-4503-8352-3"]},"page":"1–15","citation":{"ieee":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “On the Potential of Normalized TSP Features for Automated Algorithm Selection,” 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–15.","chicago":"Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann, and Pascal Kerschke. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 1–15. New York, NY, USA: Association for Computing Machinery, 2021.","ama":"Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. On the Potential of Normalized TSP Features for Automated Algorithm Selection. In: <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association for Computing Machinery; 2021:1–15.","apa":"Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., &#38; Kerschke, P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm Selection. In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i> (pp. 1–15). Association for Computing Machinery.","mla":"Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–15.","bibtex":"@inbook{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={New York, NY, USA}, title={On the Potential of Normalized TSP Features for Automated Algorithm Selection}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}, year={2021}, pages={1–15} }","short":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–15."},"year":"2021","place":"New York, NY, USA","author":[{"last_name":"Heins","full_name":"Heins, Jonathan","first_name":"Jonathan"},{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"last_name":"Pohl","full_name":"Pohl, Janina","first_name":"Janina"},{"last_name":"Seiler","full_name":"Seiler, Moritz","first_name":"Moritz"},{"full_name":"Trautmann, Heike","last_name":"Trautmann","first_name":"Heike"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"}],"date_created":"2023-11-14T15:58:58Z","date_updated":"2023-12-13T10:47:23Z","publisher":"Association for Computing Machinery","title":"On the Potential of Normalized TSP Features for Automated Algorithm Selection"},{"year":"2021","place":"New York, NY, USA","citation":{"ieee":"A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation,” 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.","chicago":"Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation.” 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.","ama":"Nikfarjam A, Bossek J, Neumann A, Neumann F. Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In: <i>Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association for Computing Machinery; 2021:1–11.","short":"A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, 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.","mla":"Nikfarjam, Adel, et al. “Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation.” <i>Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–11.","bibtex":"@inbook{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York, NY, USA}, title={Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation}, booktitle={Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={1–11} }","apa":"Nikfarjam, A., Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In <i>Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms</i> (pp. 1–11). Association for Computing Machinery."},"page":"1–11","publication_identifier":{"isbn":["978-1-4503-8352-3"]},"title":"Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation","publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:49:59Z","date_created":"2023-11-14T15:59:00Z","author":[{"first_name":"Adel","last_name":"Nikfarjam","full_name":"Nikfarjam, Adel"},{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"first_name":"Aneta","full_name":"Neumann, Aneta","last_name":"Neumann"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"abstract":[{"lang":"eng","text":"Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given problem, but a diverse set of high quality solutions from which a decision maker can choose one for implementation. Currently, there are only a few approaches for computing a diverse solution set for the TSP. Furthermore, almost all of them assume that the optimal solution is known. In this paper, we introduce evolutionary diversity optimisation (EDO) approaches for the TSP that find a diverse set of tours when the optimal tour is known or unknown. We show how to adopt EAX to not only find a high-quality solution but also to maximise the diversity of the population. The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse high-quality tours when the optimal solution for the TSP is known or unknown. A comparison to existing approaches shows that they are clearly outperformed by EAX-EDO."}],"status":"public","type":"book_chapter","publication":"Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms","keyword":["edge assembly crossover (EAX)","evolutionary algorithms","evolutionary diversity optimisation (EDO)","traveling salesperson problem (TSP)"],"language":[{"iso":"eng"}],"extern":"1","_id":"48892","user_id":"102979","department":[{"_id":"819"}]}]