[{"doi":"10.3390/app12189094","title":"Process-Oriented Stream Classification Pipeline: A Literature Review","volume":12,"author":[{"last_name":"Clever","full_name":"Clever, Lena","first_name":"Lena"},{"first_name":"Janina Susanne","full_name":"Pohl, Janina Susanne","last_name":"Pohl"},{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"},{"full_name":"Trautmann, Heike","id":"100740","orcid":"0000-0002-9788-8282","last_name":"Trautmann","first_name":"Heike"}],"date_created":"2023-08-04T07:17:23Z","date_updated":"2024-06-10T12:02:17Z","page":"1–44","intvolume":"        12","citation":{"mla":"Clever, Lena, et al. “Process-Oriented Stream Classification Pipeline: A Literature Review.” <i>Applied Sciences</i>, vol. 12, no. 8, 2022, pp. 1–44, doi:<a href=\"https://doi.org/10.3390/app12189094\">10.3390/app12189094</a>.","bibtex":"@article{Clever_Pohl_Bossek_Kerschke_Trautmann_2022, title={Process-Oriented Stream Classification Pipeline: A Literature Review}, volume={12}, DOI={<a href=\"https://doi.org/10.3390/app12189094\">10.3390/app12189094</a>}, number={8}, journal={Applied Sciences}, author={Clever, Lena and Pohl, Janina Susanne and Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike}, year={2022}, pages={1–44} }","short":"L. Clever, J.S. Pohl, J. Bossek, P. Kerschke, H. Trautmann, Applied Sciences 12 (2022) 1–44.","apa":"Clever, L., Pohl, J. S., Bossek, J., Kerschke, P., &#38; Trautmann, H. (2022). Process-Oriented Stream Classification Pipeline: A Literature Review. <i>Applied Sciences</i>, <i>12</i>(8), 1–44. <a href=\"https://doi.org/10.3390/app12189094\">https://doi.org/10.3390/app12189094</a>","chicago":"Clever, Lena, Janina Susanne Pohl, Jakob Bossek, Pascal Kerschke, and Heike Trautmann. “Process-Oriented Stream Classification Pipeline: A Literature Review.” <i>Applied Sciences</i> 12, no. 8 (2022): 1–44. <a href=\"https://doi.org/10.3390/app12189094\">https://doi.org/10.3390/app12189094</a>.","ieee":"L. Clever, J. S. Pohl, J. Bossek, P. Kerschke, and H. Trautmann, “Process-Oriented Stream Classification Pipeline: A Literature Review,” <i>Applied Sciences</i>, vol. 12, no. 8, pp. 1–44, 2022, doi: <a href=\"https://doi.org/10.3390/app12189094\">10.3390/app12189094</a>.","ama":"Clever L, Pohl JS, Bossek J, Kerschke P, Trautmann H. Process-Oriented Stream Classification Pipeline: A Literature Review. <i>Applied Sciences</i>. 2022;12(8):1–44. doi:<a href=\"https://doi.org/10.3390/app12189094\">10.3390/app12189094</a>"},"year":"2022","issue":"8","language":[{"iso":"eng"}],"department":[{"_id":"34"},{"_id":"819"}],"user_id":"15504","_id":"46309","status":"public","abstract":[{"text":"Due to the rise of continuous data-generating applications, analyzing data streams has gained increasing attention over the past decades. A core research area in stream data is stream classification, which categorizes or detects data points within an evolving stream of observations. Areas of stream classification are diverse—ranging, e.g., from monitoring sensor data to analyzing a wide range of (social) media applications. Research in stream classification is related to developing methods that adapt to the changing and potentially volatile data stream. It focuses on individual aspects of the stream classification pipeline, e.g., designing suitable algorithm architectures, an efficient train and test procedure, or detecting so-called concept drifts. As a result of the many different research questions and strands, the field is challenging to grasp, especially for beginners. This survey explores, summarizes, and categorizes work within the domain of stream classification and identifies core research threads over the past few years. It is structured based on the stream classification process to facilitate coordination within this complex topic, including common application scenarios and benchmarking data sets. Thus, both newcomers to the field and experts who want to widen their scope can gain (additional) insight into this research area and find starting points and pointers to more in-depth literature on specific issues and research directions in the field.","lang":"eng"}],"publication":"Applied Sciences","type":"journal_article"},{"year":"2022","place":"Cham","page":"192–206","citation":{"short":"J. Heins, J. Rook, L. Schäpermeier, P. Kerschke, J. Bossek, H. Trautmann, in: G. Rudolph, A. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, T. Tušar (Eds.), Parallel Problem Solving from Nature — PPSN XVII, Springer International Publishing, Cham, 2022, pp. 192–206.","bibtex":"@inproceedings{Heins_Rook_Schäpermeier_Kerschke_Bossek_Trautmann_2022, place={Cham}, title={BBE: Basin-Based Evaluation of Multimodal Multi-objective Optimization Problems}, booktitle={Parallel Problem Solving from Nature — PPSN XVII}, publisher={Springer International Publishing}, author={Heins, J and Rook, J and Schäpermeier, L and Kerschke, P and Bossek, Jakob and Trautmann, Heike}, editor={Rudolph, G and Kononova, AV and Aguirre, H and Kerschke, P and Ochoa, G and Tušar, T}, year={2022}, pages={192–206} }","mla":"Heins, J., et al. “BBE: Basin-Based Evaluation of Multimodal Multi-Objective Optimization Problems.” <i>Parallel Problem Solving from Nature — PPSN XVII</i>, edited by G Rudolph et al., Springer International Publishing, 2022, pp. 192–206.","ama":"Heins J, Rook J, Schäpermeier L, Kerschke P, Bossek J, Trautmann H. BBE: Basin-Based Evaluation of Multimodal Multi-objective Optimization Problems. In: Rudolph G, Kononova A, Aguirre H, Kerschke P, Ochoa G, Tušar T, eds. <i>Parallel Problem Solving from Nature — PPSN XVII</i>. Springer International Publishing; 2022:192–206.","apa":"Heins, J., Rook, J., Schäpermeier, L., Kerschke, P., Bossek, J., &#38; Trautmann, H. (2022). BBE: Basin-Based Evaluation of Multimodal Multi-objective Optimization Problems. In G. Rudolph, A. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, &#38; T. Tušar (Eds.), <i>Parallel Problem Solving from Nature — PPSN XVII</i> (pp. 192–206). Springer International Publishing.","ieee":"J. Heins, J. Rook, L. Schäpermeier, P. Kerschke, J. Bossek, and H. Trautmann, “BBE: Basin-Based Evaluation of Multimodal Multi-objective Optimization Problems,” in <i>Parallel Problem Solving from Nature — PPSN XVII</i>, 2022, pp. 192–206.","chicago":"Heins, J, J Rook, L Schäpermeier, P Kerschke, Jakob Bossek, and Heike Trautmann. “BBE: Basin-Based Evaluation of Multimodal Multi-Objective Optimization Problems.” In <i>Parallel Problem Solving from Nature — PPSN XVII</i>, edited by G Rudolph, AV Kononova, H Aguirre, P Kerschke, G Ochoa, and T Tušar, 192–206. Cham: Springer International Publishing, 2022."},"publication_identifier":{"isbn":["978-3-031-14714-2"]},"title":"BBE: Basin-Based Evaluation of Multimodal Multi-objective Optimization Problems","publisher":"Springer International Publishing","date_updated":"2024-06-10T12:02:35Z","date_created":"2023-08-04T07:10:52Z","author":[{"full_name":"Heins, J","last_name":"Heins","first_name":"J"},{"full_name":"Rook, J","last_name":"Rook","first_name":"J"},{"first_name":"L","full_name":"Schäpermeier, L","last_name":"Schäpermeier"},{"last_name":"Kerschke","full_name":"Kerschke, P","first_name":"P"},{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"id":"100740","full_name":"Trautmann, Heike","orcid":"0000-0002-9788-8282","last_name":"Trautmann","first_name":"Heike"}],"editor":[{"last_name":"Rudolph","full_name":"Rudolph, G","first_name":"G"},{"full_name":"Kononova, AV","last_name":"Kononova","first_name":"AV"},{"first_name":"H","last_name":"Aguirre","full_name":"Aguirre, H"},{"first_name":"P","full_name":"Kerschke, P","last_name":"Kerschke"},{"first_name":"G","last_name":"Ochoa","full_name":"Ochoa, G"},{"last_name":"Tušar","full_name":"Tušar, T","first_name":"T"}],"status":"public","publication":"Parallel Problem Solving from Nature — PPSN XVII","type":"conference","language":[{"iso":"eng"}],"_id":"46302","department":[{"_id":"34"},{"_id":"819"}],"user_id":"15504"},{"title":"On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems","publisher":"Association for Computing Machinery","date_created":"2023-08-04T07:14:24Z","year":"2022","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Hardness of Multi-Objective (MO) continuous optimization problems results from an interplay of various problem characteristics, e. g. the degree of multi-modality. We present a benchmark study of classical and diversity focused optimizers on multi-modal MO problems based on automated algorithm configuration. We show the large effect of the latter and investigate the trade-off between convergence in objective space and diversity in decision space."}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","doi":"10.1145/3520304.3528998","date_updated":"2026-02-19T15:12:35Z","author":[{"first_name":"J","last_name":"Rook","full_name":"Rook, J"},{"orcid":"0000-0002-9788-8282","last_name":"Trautmann","full_name":"Trautmann, Heike","id":"100740","first_name":"Heike"},{"orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"last_name":"Grimme","full_name":"Grimme, C","first_name":"C"}],"place":"New York, NY, USA","page":"356–359","citation":{"bibtex":"@inproceedings{Rook_Trautmann_Bossek_Grimme_2022, place={New York, NY, USA}, series={GECCO ’22}, title={On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems}, DOI={<a href=\"https://doi.org/10.1145/3520304.3528998\">10.1145/3520304.3528998</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion}, publisher={Association for Computing Machinery}, author={Rook, J and Trautmann, Heike and Bossek, Jakob and Grimme, C}, editor={Fieldsend, J and Wagner, M.}, year={2022}, pages={356–359}, collection={GECCO ’22} }","mla":"Rook, J., et al. “On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems.” <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, edited by J Fieldsend and M. Wagner, Association for Computing Machinery, 2022, pp. 356–359, doi:<a href=\"https://doi.org/10.1145/3520304.3528998\">10.1145/3520304.3528998</a>.","short":"J. Rook, H. Trautmann, J. Bossek, C. Grimme, in: J. Fieldsend, M. Wagner (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, New York, NY, USA, 2022, pp. 356–359.","apa":"Rook, J., Trautmann, H., Bossek, J., &#38; Grimme, C. (2022). On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems. In J. Fieldsend &#38; M. Wagner (Eds.), <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i> (pp. 356–359). Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3520304.3528998\">https://doi.org/10.1145/3520304.3528998</a>","ama":"Rook J, Trautmann H, Bossek J, Grimme C. On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems. In: Fieldsend J, Wagner M, eds. <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>. GECCO ’22. Association for Computing Machinery; 2022:356–359. doi:<a href=\"https://doi.org/10.1145/3520304.3528998\">10.1145/3520304.3528998</a>","ieee":"J. Rook, H. Trautmann, J. Bossek, and C. Grimme, “On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 2022, pp. 356–359, doi: <a href=\"https://doi.org/10.1145/3520304.3528998\">10.1145/3520304.3528998</a>.","chicago":"Rook, J, Heike Trautmann, Jakob Bossek, and C Grimme. “On the Potential of Automated Algorithm Configuration on Multi-Modal Multi-Objective Optimization Problems.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, edited by J Fieldsend and M. Wagner, 356–359. GECCO ’22. New York, NY, USA: Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3520304.3528998\">https://doi.org/10.1145/3520304.3528998</a>."},"publication_identifier":{"isbn":["9781450392686"]},"_id":"46305","department":[{"_id":"34"},{"_id":"819"}],"user_id":"14972","series_title":"GECCO ’22","editor":[{"first_name":"J","last_name":"Fieldsend","full_name":"Fieldsend, J"},{"full_name":"Wagner, M.","last_name":"Wagner","first_name":"M."}],"status":"public","type":"conference"},{"page":"556–564","citation":{"short":"J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp. 556–564.","mla":"Bossek, Jakob, et al. “Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2021, pp. 556–564, doi:<a href=\"https://doi.org/10.1145/3449639.3459364\">10.1145/3449639.3459364</a>.","bibtex":"@inproceedings{Bossek_Neumann_Neumann_2021, place={New York, NY, USA}, series={GECCO ’21}, title={Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms}, DOI={<a href=\"https://doi.org/10.1145/3449639.3459364\">10.1145/3449639.3459364</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={556–564}, collection={GECCO ’21} }","apa":"Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 556–564. <a href=\"https://doi.org/10.1145/3449639.3459364\">https://doi.org/10.1145/3449639.3459364</a>","chicago":"Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 556–564. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3449639.3459364\">https://doi.org/10.1145/3449639.3459364</a>.","ieee":"J. Bossek, A. Neumann, and F. Neumann, “Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2021, pp. 556–564, doi: <a href=\"https://doi.org/10.1145/3449639.3459364\">10.1145/3449639.3459364</a>.","ama":"Bossek J, Neumann A, Neumann F. Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’21. Association for Computing Machinery; 2021:556–564. doi:<a href=\"https://doi.org/10.1145/3449639.3459364\">10.1145/3449639.3459364</a>"},"place":"New York, NY, USA","publication_identifier":{"isbn":["978-1-4503-8350-9"]},"publication_status":"published","doi":"10.1145/3449639.3459364","author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_updated":"2023-12-13T10:45:22Z","status":"public","type":"conference","extern":"1","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO ’21","_id":"48853","year":"2021","title":"Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms","date_created":"2023-11-14T15:58:54Z","publisher":"Association for Computing Machinery","abstract":[{"text":"In practise, it is often desirable to provide the decision-maker with a rich set of diverse solutions of decent quality instead of just a single solution. In this paper we study evolutionary diversity optimization for the knapsack problem (KP). Our goal is to evolve a population of solutions that all have a profit of at least (1 - {$ϵ$}) {$\\cdot$} OPT, where OPT is the value of an optimal solution. Furthermore, they should differ in structure with respect to an entropy-based diversity measure. To this end we propose a simple ({$\\mu$} + 1)-EA with initial approximate solutions calculated by a well-known FPTAS for the KP. We investigate the effect of different standard mutation operators and introduce biased mutation and crossover which puts strong probability on flipping bits of low and/or high frequency within the population. An experimental study on different instances and settings shows that the proposed mutation operators in most cases perform slightly inferior in the long term, but show strong benefits if the number of function evaluations is severely limited.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","language":[{"iso":"eng"}],"keyword":["evolutionary algorithms","evolutionary diversity optimization","knapsack problem","tailored operators"]},{"place":"Berlin, Heidelberg","page":"40–54","citation":{"mla":"Bossek, Jakob, et al. “Exact Counting And~Sampling of Optima for the Knapsack Problem.” <i>Learning and Intelligent Optimization</i>, Springer-Verlag, 2021, pp. 40–54, doi:<a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>.","short":"J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization, Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54.","bibtex":"@inproceedings{Bossek_Neumann_Neumann_2021, place={Berlin, Heidelberg}, title={Exact Counting and~Sampling of Optima for the Knapsack Problem}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>}, booktitle={Learning and Intelligent Optimization}, publisher={Springer-Verlag}, author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={40–54} }","apa":"Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Exact Counting and~Sampling of Optima for the Knapsack Problem. <i>Learning and Intelligent Optimization</i>, 40–54. <a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">https://doi.org/10.1007/978-3-030-92121-7_4</a>","ieee":"J. Bossek, A. Neumann, and F. Neumann, “Exact Counting and~Sampling of Optima for the Knapsack Problem,” in <i>Learning and Intelligent Optimization</i>, 2021, pp. 40–54, doi: <a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>.","chicago":"Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Exact Counting And~Sampling of Optima for the Knapsack Problem.” In <i>Learning and Intelligent Optimization</i>, 40–54. Berlin, Heidelberg: Springer-Verlag, 2021. <a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">https://doi.org/10.1007/978-3-030-92121-7_4</a>.","ama":"Bossek J, Neumann A, Neumann F. Exact Counting and~Sampling of Optima for the Knapsack Problem. In: <i>Learning and Intelligent Optimization</i>. Springer-Verlag; 2021:40–54. doi:<a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>"},"publication_identifier":{"isbn":["978-3-030-92120-0"]},"publication_status":"published","doi":"10.1007/978-3-030-92121-7_4","date_updated":"2023-12-13T10:45:14Z","author":[{"id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"status":"public","type":"conference","extern":"1","_id":"48855","department":[{"_id":"819"}],"user_id":"102979","year":"2021","title":"Exact Counting and~Sampling of Optima for the Knapsack Problem","publisher":"Springer-Verlag","date_created":"2023-11-14T15:58:54Z","abstract":[{"lang":"eng","text":"Computing sets of high quality solutions has gained increasing interest in recent years. In this paper, we investigate how to obtain sets of optimal solutions for the classical knapsack problem. We present an algorithm to count exactly the number of optima to a zero-one knapsack problem instance. In addition, we show how to efficiently sample uniformly at random from the set of all global optima. In our experimental study, we investigate how the number of optima develops for classical random benchmark instances dependent on their generator parameters. We find that the number of global optima can increase exponentially for practically relevant classes of instances with correlated weights and profits which poses a justification for the considered exact counting problem."}],"publication":"Learning and Intelligent Optimization","keyword":["Dynamic programming","Exact counting","Sampling","Zero-one knapsack problem"],"language":[{"iso":"eng"}]},{"date_created":"2023-11-14T15:58:55Z","author":[{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_updated":"2023-12-13T10:45:37Z","publisher":"Association for Computing Machinery","doi":"10.1145/3449639.3459363","title":"Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem","publication_identifier":{"isbn":["978-1-4503-8350-9"]},"publication_status":"published","page":"198–206","citation":{"short":"J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp. 198–206.","mla":"Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2021, pp. 198–206, doi:<a href=\"https://doi.org/10.1145/3449639.3459363\">10.1145/3449639.3459363</a>.","bibtex":"@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO ’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem}, DOI={<a href=\"https://doi.org/10.1145/3449639.3459363\">10.1145/3449639.3459363</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann, Frank}, year={2021}, pages={198–206}, collection={GECCO ’21} }","apa":"Bossek, J., &#38; Neumann, F. (2021). Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 198–206. <a href=\"https://doi.org/10.1145/3449639.3459363\">https://doi.org/10.1145/3449639.3459363</a>","ama":"Bossek J, Neumann F. Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:<a href=\"https://doi.org/10.1145/3449639.3459363\">10.1145/3449639.3459363</a>","chicago":"Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 198–206. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3449639.3459363\">https://doi.org/10.1145/3449639.3459363</a>.","ieee":"J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2021, pp. 198–206, doi: <a href=\"https://doi.org/10.1145/3449639.3459363\">10.1145/3449639.3459363</a>."},"place":"New York, NY, USA","year":"2021","department":[{"_id":"819"}],"series_title":"GECCO ’21","user_id":"102979","_id":"48860","extern":"1","language":[{"iso":"eng"}],"keyword":["evolutionary algorithms","evolutionary diversity optimization","minimum spanning tree","runtime analysis"],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference","status":"public","abstract":[{"lang":"eng","text":"In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of {$\\mu$} = 2 fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple ({$\\mu$} + 1)-EA can effectively compute a diversified population of spanning trees of high quality."}]},{"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","year":"2021","place":"New York, NY, USA","page":"1–11","citation":{"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.","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.","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} }","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.","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."},"publication_identifier":{"isbn":["978-1-4503-8352-3"]},"publication_status":"published","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","id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"first_name":"Dirk","full_name":"Sudholt, Dirk","last_name":"Sudholt"}]},{"title":"On the Potential of Normalized TSP Features for Automated Algorithm Selection","date_created":"2023-11-14T15:58:58Z","author":[{"first_name":"Jonathan","full_name":"Heins, Jonathan","last_name":"Heins"},{"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"},{"first_name":"Moritz","last_name":"Seiler","full_name":"Seiler, Moritz"},{"last_name":"Trautmann","full_name":"Trautmann, Heike","first_name":"Heike"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"}],"date_updated":"2023-12-13T10:47:23Z","publisher":"Association for Computing Machinery","citation":{"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.","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.","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} }","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.","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.","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.","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."},"page":"1–15","place":"New York, NY, USA","year":"2021","publication_identifier":{"isbn":["978-1-4503-8352-3"]},"language":[{"iso":"eng"}],"extern":"1","keyword":["automated algorithm selection","graph theory","instance features","normalization","traveling salesperson problem (TSP)"],"user_id":"102979","department":[{"_id":"819"}],"_id":"48881","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."}],"type":"book_chapter","publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms"},{"status":"public","type":"conference","extern":"1","user_id":"102979","series_title":"GECCO’21","department":[{"_id":"819"}],"_id":"48876","citation":{"apa":"Bossek, J., &#38; Wagner, M. (2021). Generating Instances with Performance Differences for More than Just Two Algorithms. <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 1423–1432. <a href=\"https://doi.org/10.1145/3449726.3463165\">https://doi.org/10.1145/3449726.3463165</a>","bibtex":"@inproceedings{Bossek_Wagner_2021, place={New York, NY, USA}, series={GECCO’21}, title={Generating Instances with Performance Differences for More than Just Two Algorithms}, DOI={<a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Wagner, Markus}, year={2021}, pages={1423–1432}, collection={GECCO’21} }","mla":"Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, Association for Computing Machinery, 2021, pp. 1423–1432, doi:<a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>.","short":"J. Bossek, M. Wagner, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1423–1432.","ama":"Bossek J, Wagner M. Generating Instances with Performance Differences for More than Just Two Algorithms. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>. GECCO’21. Association for Computing Machinery; 2021:1423–1432. doi:<a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>","ieee":"J. Bossek and M. Wagner, “Generating Instances with Performance Differences for More than Just Two Algorithms,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 2021, pp. 1423–1432, doi: <a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>.","chicago":"Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 1423–1432. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3449726.3463165\">https://doi.org/10.1145/3449726.3463165</a>."},"page":"1423–1432","place":"New York, NY, USA","publication_identifier":{"isbn":["978-1-4503-8351-6"]},"doi":"10.1145/3449726.3463165","author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"first_name":"Markus","full_name":"Wagner, Markus","last_name":"Wagner"}],"date_updated":"2023-12-13T10:47:41Z","abstract":[{"lang":"eng","text":"In recent years, Evolutionary Algorithms (EAs) have frequently been adopted to evolve instances for optimization problems that pose difficulties for one algorithm while being rather easy for a competitor and vice versa. Typically, this is achieved by either minimizing or maximizing the performance difference or ratio which serves as the fitness function. Repeating this process is useful to gain insights into strengths/weaknesses of certain algorithms or to build a set of instances with strong performance differences as a foundation for automatic per-instance algorithm selection or configuration. We contribute to this branch of research by proposing fitness-functions to evolve instances that show large performance differences for more than just two algorithms simultaneously. As a proof-of-principle, we evolve instances of the multi-component Traveling Thief Problem (TTP) for three incomplete TTP-solvers. Our results point out that our strategies are promising, but unsurprisingly their success strongly relies on the algorithms’ performance complementarity."}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","language":[{"iso":"eng"}],"keyword":["evolutionary algorithms","evolving instances","fitness function","instance hardness","traveling thief problem (TTP)"],"year":"2021","title":"Generating Instances with Performance Differences for More than Just Two Algorithms","date_created":"2023-11-14T15:58:57Z","publisher":"Association for Computing Machinery"},{"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference","status":"public","abstract":[{"lang":"eng","text":"Computing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In this paper, we employ a population diversity measure, called the high-order entropy measure, in an evolutionary algorithm to compute a diverse set of high-quality solutions for the Traveling Salesperson Problem. In contrast to previous studies, our approach allows diversifying segments of tours containing several edges based on the entropy measure. We examine the resulting evolutionary diversity optimisation approach precisely in terms of the final set of solutions and theoretical properties. Experimental results show significant improvements compared to a recently proposed edge-based diversity optimisation approach when working with a large population of solutions or long segments."}],"department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO’21","_id":"48893","language":[{"iso":"eng"}],"extern":"1","keyword":["evolutionary algorithms","evolutionary diversity optimisation","high-order entropy","traveling salesperson problem"],"publication_identifier":{"isbn":["978-1-4503-8350-9"]},"page":"600–608","citation":{"chicago":"Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 600–608. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3449639.3459384\">https://doi.org/10.1145/3449639.3459384</a>.","ieee":"A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2021, pp. 600–608, doi: <a href=\"https://doi.org/10.1145/3449639.3459384\">10.1145/3449639.3459384</a>.","ama":"Nikfarjam A, Bossek J, Neumann A, Neumann F. Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’21. Association for Computing Machinery; 2021:600–608. doi:<a href=\"https://doi.org/10.1145/3449639.3459384\">10.1145/3449639.3459384</a>","short":"A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp. 600–608.","bibtex":"@inproceedings{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York, NY, USA}, series={GECCO’21}, title={Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem}, DOI={<a href=\"https://doi.org/10.1145/3449639.3459384\">10.1145/3449639.3459384</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={600–608}, collection={GECCO’21} }","mla":"Nikfarjam, Adel, et al. “Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2021, pp. 600–608, doi:<a href=\"https://doi.org/10.1145/3449639.3459384\">10.1145/3449639.3459384</a>.","apa":"Nikfarjam, A., Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 600–608. <a href=\"https://doi.org/10.1145/3449639.3459384\">https://doi.org/10.1145/3449639.3459384</a>"},"place":"New York, NY, USA","year":"2021","date_created":"2023-11-14T15:59:00Z","author":[{"first_name":"Adel","full_name":"Nikfarjam, Adel","last_name":"Nikfarjam"},{"id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob"},{"last_name":"Neumann","full_name":"Neumann, Aneta","first_name":"Aneta"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"date_updated":"2023-12-13T10:50:06Z","publisher":"Association for Computing Machinery","doi":"10.1145/3449639.3459384","title":"Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem"},{"type":"conference","status":"public","_id":"48891","series_title":"GECCO’21","user_id":"102979","department":[{"_id":"819"}],"extern":"1","publication_identifier":{"isbn":["978-1-4503-8350-9"]},"place":"New York, NY, USA","citation":{"short":"A. Neumann, J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp. 261–269.","mla":"Neumann, Aneta, et al. “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2021, pp. 261–269, doi:<a href=\"https://doi.org/10.1145/3449639.3459385\">10.1145/3449639.3459385</a>.","bibtex":"@inproceedings{Neumann_Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO’21}, title={Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions}, DOI={<a href=\"https://doi.org/10.1145/3449639.3459385\">10.1145/3449639.3459385</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Neumann, Aneta and Bossek, Jakob and Neumann, Frank}, year={2021}, pages={261–269}, collection={GECCO’21} }","apa":"Neumann, A., Bossek, J., &#38; Neumann, F. (2021). Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 261–269. <a href=\"https://doi.org/10.1145/3449639.3459385\">https://doi.org/10.1145/3449639.3459385</a>","ama":"Neumann A, Bossek J, Neumann F. Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’21. Association for Computing Machinery; 2021:261–269. doi:<a href=\"https://doi.org/10.1145/3449639.3459385\">10.1145/3449639.3459385</a>","ieee":"A. Neumann, J. Bossek, and F. Neumann, “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2021, pp. 261–269, doi: <a href=\"https://doi.org/10.1145/3449639.3459385\">10.1145/3449639.3459385</a>.","chicago":"Neumann, Aneta, Jakob Bossek, and Frank Neumann. “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 261–269. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3449639.3459385\">https://doi.org/10.1145/3449639.3459385</a>."},"page":"261–269","date_updated":"2023-12-13T10:49:25Z","author":[{"last_name":"Neumann","full_name":"Neumann, Aneta","first_name":"Aneta"},{"full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"doi":"10.1145/3449639.3459385","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"text":"Submodular functions allow to model many real-world optimisation problems. This paper introduces approaches for computing diverse sets of high quality solutions for submodular optimisation problems with uniform and knapsack constraints. We first present diversifying greedy sampling approaches and analyse them with respect to the diversity measured by entropy and the approximation quality of the obtained solutions. Afterwards, we introduce an evolutionary diversity optimisation (EDO) approach to further improve diversity of the set of solutions. We carry out experimental investigations on popular submodular benchmark problems and analyse trade-offs in terms of solution quality and diversity of the resulting solution sets.","lang":"eng"}],"keyword":["evolutionary algorithms","evolutionary diversity optimisation","sub-modular functions"],"language":[{"iso":"eng"}],"year":"2021","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:59Z","title":"Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions"},{"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","publication":"Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms","type":"book_chapter","keyword":["edge assembly crossover (EAX)","evolutionary algorithms","evolutionary diversity optimisation (EDO)","traveling salesperson problem (TSP)"],"extern":"1","language":[{"iso":"eng"}],"_id":"48892","department":[{"_id":"819"}],"user_id":"102979","place":"New York, NY, USA","year":"2021","page":"1–11","citation":{"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.","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.","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.","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.","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} }"},"publication_identifier":{"isbn":["978-1-4503-8352-3"]},"title":"Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation","date_updated":"2023-12-13T10:49:59Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:59:00Z","author":[{"last_name":"Nikfarjam","full_name":"Nikfarjam, Adel","first_name":"Adel"},{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"},{"last_name":"Neumann","full_name":"Neumann, Frank","first_name":"Frank"}]},{"title":"Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem","doi":"10.1007/s00453-021-00838-3","date_updated":"2023-12-13T10:51:34Z","volume":83,"date_created":"2023-11-14T15:58:54Z","author":[{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"},{"first_name":"Pan","last_name":"Peng","full_name":"Peng, Pan"},{"first_name":"Dirk","last_name":"Sudholt","full_name":"Sudholt, Dirk"}],"year":"2021","intvolume":"        83","page":"3148–3179","citation":{"ama":"Bossek J, Neumann F, Peng P, Sudholt D. Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem. <i>Algorithmica</i>. 2021;83(10):3148–3179. doi:<a href=\"https://doi.org/10.1007/s00453-021-00838-3\">10.1007/s00453-021-00838-3</a>","chicago":"Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.” <i>Algorithmica</i> 83, no. 10 (2021): 3148–3179. <a href=\"https://doi.org/10.1007/s00453-021-00838-3\">https://doi.org/10.1007/s00453-021-00838-3</a>.","ieee":"J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem,” <i>Algorithmica</i>, vol. 83, no. 10, pp. 3148–3179, 2021, doi: <a href=\"https://doi.org/10.1007/s00453-021-00838-3\">10.1007/s00453-021-00838-3</a>.","mla":"Bossek, Jakob, et al. “Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.” <i>Algorithmica</i>, vol. 83, no. 10, 2021, pp. 3148–3179, doi:<a href=\"https://doi.org/10.1007/s00453-021-00838-3\">10.1007/s00453-021-00838-3</a>.","short":"J. Bossek, F. Neumann, P. Peng, D. Sudholt, Algorithmica 83 (2021) 3148–3179.","bibtex":"@article{Bossek_Neumann_Peng_Sudholt_2021, title={Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem}, volume={83}, DOI={<a href=\"https://doi.org/10.1007/s00453-021-00838-3\">10.1007/s00453-021-00838-3</a>}, number={10}, journal={Algorithmica}, author={Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}, year={2021}, pages={3148–3179} }","apa":"Bossek, J., Neumann, F., Peng, P., &#38; Sudholt, D. (2021). Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem. <i>Algorithmica</i>, <i>83</i>(10), 3148–3179. <a href=\"https://doi.org/10.1007/s00453-021-00838-3\">https://doi.org/10.1007/s00453-021-00838-3</a>"},"publication_identifier":{"issn":["0178-4617"]},"issue":"10","keyword":["Dynamic optimization","Evolutionary algorithms","Running time analysis"],"language":[{"iso":"eng"}],"_id":"48854","department":[{"_id":"819"}],"user_id":"102979","abstract":[{"text":"We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. The (1+1) Evolutionary Algorithm and RLS operate in a setting where the number of colors is bounded and we are minimizing the number of conflicts. Iterated local search algorithms use an unbounded color palette and aim to use the smallest colors and, consequently, the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i.e., starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. We further show that tailoring mutation operators to parts of the graph where changes have occurred can significantly reduce the expected reoptimization time. In most settings the expected reoptimization time for such tailored algorithms is linear in the number of added edges. However, tailored algorithms cannot prevent exponential times in settings where the original algorithm is inefficient.","lang":"eng"}],"status":"public","publication":"Algorithmica","type":"journal_article"},{"year":"2021","place":"Dornbirn, Austria","page":"1–15","citation":{"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  for Computing Machinery Association (Ed.), <i>Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI)</i> (pp. 1–15). Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3450218.3477308\">https://doi.org/10.1145/3450218.3477308</a>","short":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in:  for Computing Machinery Association (Ed.), Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI), Association for Computing Machinery, Dornbirn, Austria, 2021, pp. 1–15.","mla":"Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” <i>Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI)</i>, edited by for Computing Machinery Association, Association for Computing Machinery, 2021, pp. 1–15, doi:<a href=\"https://doi.org/10.1145/3450218.3477308\">10.1145/3450218.3477308</a>.","bibtex":"@inproceedings{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={Dornbirn, Austria}, title={On the Potential of Normalized TSP Features for Automated Algorithm Selection}, DOI={<a href=\"https://doi.org/10.1145/3450218.3477308\">10.1145/3450218.3477308</a>}, booktitle={Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI)}, publisher={Association for Computing Machinery}, author={Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}, editor={Computing Machinery Association, for}, year={2021}, pages={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 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI)</i>, edited by for Computing Machinery Association, 1–15. Dornbirn, Austria: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3450218.3477308\">https://doi.org/10.1145/3450218.3477308</a>.","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 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI)</i>, 2021, pp. 1–15, doi: <a href=\"https://doi.org/10.1145/3450218.3477308\">10.1145/3450218.3477308</a>.","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: Computing Machinery Association  for, ed. <i>Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI)</i>. Association for Computing Machinery; 2021:1–15. doi:<a href=\"https://doi.org/10.1145/3450218.3477308\">10.1145/3450218.3477308</a>"},"date_updated":"2024-06-10T11:57:04Z","publisher":"Association for Computing Machinery","author":[{"first_name":"Jonathan","last_name":"Heins","full_name":"Heins, Jonathan"},{"orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"first_name":"Janina","last_name":"Pohl","full_name":"Pohl, Janina"},{"first_name":"Moritz","last_name":"Seiler","full_name":"Seiler, Moritz","id":"105520"},{"first_name":"Heike","last_name":"Trautmann","orcid":"0000-0002-9788-8282","full_name":"Trautmann, Heike","id":"100740"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"}],"date_created":"2023-08-04T07:23:57Z","title":"On the Potential of Normalized TSP Features for Automated Algorithm Selection","doi":"10.1145/3450218.3477308","publication":"Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI)","type":"conference","editor":[{"last_name":"Computing Machinery Association","full_name":"Computing Machinery Association, for","first_name":"for"}],"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."}],"status":"public","_id":"46313","department":[{"_id":"34"},{"_id":"819"}],"user_id":"15504","language":[{"iso":"eng"}]},{"series_title":"GECCO ’20","user_id":"102979","department":[{"_id":"819"}],"_id":"48847","language":[{"iso":"eng"}],"extern":"1","keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"],"type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","status":"public","abstract":[{"text":"Dynamic optimization problems have gained significant attention in evolutionary computation as evolutionary algorithms (EAs) can easily adapt to changing environments. We show that EAs can solve the graph coloring problem for bipartite graphs more efficiently by using dynamic optimization. In our approach the graph instance is given incrementally such that the EA can reoptimize its coloring when a new edge introduces a conflict. We show that, when edges are inserted in a way that preserves graph connectivity, Randomized Local Search (RLS) efficiently finds a proper 2-coloring for all bipartite graphs. This includes graphs for which RLS and other EAs need exponential expected time in a static optimization scenario. We investigate different ways of building up the graph by popular graph traversals such as breadth-first-search and depth-first-search and analyse the resulting runtime behavior. We further show that offspring populations (e. g. a (1 + {$\\lambda$}) RLS) lead to an exponential speedup in {$\\lambda$}. Finally, an island model using 3 islands succeeds in an optimal time of {$\\Theta$}(m) on every m-edge bipartite graph, outperforming offspring populations. This is the first example where an island model guarantees a speedup that is not bounded in the number of islands.","lang":"eng"}],"date_created":"2023-11-14T15:58:53Z","author":[{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"},{"full_name":"Sudholt, Dirk","last_name":"Sudholt","first_name":"Dirk"}],"publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:43:41Z","doi":"10.1145/3377930.3390174","title":"More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"citation":{"chicago":"Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1277–1285. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390174\">https://doi.org/10.1145/3377930.3390174</a>.","ieee":"J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 1277–1285, doi: <a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>.","ama":"Bossek J, Neumann F, Peng P, Sudholt D. More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:1277–1285. doi:<a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>","apa":"Bossek, J., Neumann, F., Peng, P., &#38; Sudholt, D. (2020). More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1277–1285. <a href=\"https://doi.org/10.1145/3377930.3390174\">https://doi.org/10.1145/3377930.3390174</a>","bibtex":"@inproceedings{Bossek_Neumann_Peng_Sudholt_2020, place={New York, NY, USA}, series={GECCO ’20}, title={More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}, year={2020}, pages={1277–1285}, collection={GECCO ’20} }","mla":"Bossek, Jakob, et al. “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 1277–1285, doi:<a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>.","short":"J. Bossek, F. Neumann, P. Peng, D. Sudholt, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 1277–1285."},"page":"1277–1285","year":"2020","place":"New York, NY, USA"},{"date_updated":"2023-12-13T10:43:53Z","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob"},{"last_name":"Doerr","full_name":"Doerr, Carola","first_name":"Carola"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"},{"last_name":"Neumann","full_name":"Neumann, Aneta","first_name":"Aneta"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"doi":"10.1007/978-3-030-58112-1_8","publication_identifier":{"isbn":["978-3-030-58111-4"]},"publication_status":"published","place":"Berlin, Heidelberg","page":"111–124","citation":{"ama":"Bossek J, Doerr C, Kerschke P, Neumann A, Neumann F. Evolving Sampling Strategies for One-Shot Optimization Tasks. In: <i>Parallel Problem Solving from Nature (PPSN XVI)</i>. Springer-Verlag; 2020:111–124. doi:<a href=\"https://doi.org/10.1007/978-3-030-58112-1_8\">10.1007/978-3-030-58112-1_8</a>","ieee":"J. Bossek, C. Doerr, P. Kerschke, A. Neumann, and F. Neumann, “Evolving Sampling Strategies for One-Shot Optimization Tasks,” in <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, 2020, pp. 111–124, doi: <a href=\"https://doi.org/10.1007/978-3-030-58112-1_8\">10.1007/978-3-030-58112-1_8</a>.","chicago":"Bossek, Jakob, Carola Doerr, Pascal Kerschke, Aneta Neumann, and Frank Neumann. “Evolving Sampling Strategies for One-Shot Optimization Tasks.” In <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, 111–124. Berlin, Heidelberg: Springer-Verlag, 2020. <a href=\"https://doi.org/10.1007/978-3-030-58112-1_8\">https://doi.org/10.1007/978-3-030-58112-1_8</a>.","short":"J. Bossek, C. Doerr, P. Kerschke, A. Neumann, F. Neumann, in: Parallel Problem Solving from Nature (PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp. 111–124.","mla":"Bossek, Jakob, et al. “Evolving Sampling Strategies for One-Shot Optimization Tasks.” <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, Springer-Verlag, 2020, pp. 111–124, doi:<a href=\"https://doi.org/10.1007/978-3-030-58112-1_8\">10.1007/978-3-030-58112-1_8</a>.","bibtex":"@inproceedings{Bossek_Doerr_Kerschke_Neumann_Neumann_2020, place={Berlin, Heidelberg}, title={Evolving Sampling Strategies for One-Shot Optimization Tasks}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-58112-1_8\">10.1007/978-3-030-58112-1_8</a>}, booktitle={Parallel Problem Solving from Nature (PPSN XVI)}, publisher={Springer-Verlag}, author={Bossek, Jakob and Doerr, Carola and Kerschke, Pascal and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={111–124} }","apa":"Bossek, J., Doerr, C., Kerschke, P., Neumann, A., &#38; Neumann, F. (2020). Evolving Sampling Strategies for One-Shot Optimization Tasks. <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, 111–124. <a href=\"https://doi.org/10.1007/978-3-030-58112-1_8\">https://doi.org/10.1007/978-3-030-58112-1_8</a>"},"_id":"48849","department":[{"_id":"819"}],"user_id":"102979","extern":"1","type":"conference","status":"public","publisher":"Springer-Verlag","date_created":"2023-11-14T15:58:53Z","title":"Evolving Sampling Strategies for One-Shot Optimization Tasks","year":"2020","keyword":["Continuous optimization","Fully parallel search","One-shot optimization","Regression","Surrogate-assisted optimization"],"language":[{"iso":"eng"}],"publication":"Parallel Problem Solving from Nature (PPSN XVI)","abstract":[{"text":"One-shot optimization tasks require to determine the set of solution candidates prior to their evaluation, i.e., without possibility for adaptive sampling. We consider two variants, classic one-shot optimization (where our aim is to find at least one solution of high quality) and one-shot regression (where the goal is to fit a model that resembles the true problem as well as possible). For both tasks it seems intuitive that well-distributed samples should perform better than uniform or grid-based samples, since they show a better coverage of the decision space. In practice, quasi-random designs such as Latin Hypercube Samples and low-discrepancy point sets are indeed very commonly used designs for one-shot optimization tasks. We study in this work how well low star discrepancy correlates with performance in one-shot optimization. Our results confirm an advantage of low-discrepancy designs, but also indicate the correlation between discrepancy values and overall performance is rather weak. We then demonstrate that commonly used designs may be far from optimal. More precisely, we evolve 24 very specific designs that each achieve good performance on one of our benchmark problems. Interestingly, we find that these specifically designed samples yield surprisingly good performance across the whole benchmark set. Our results therefore give strong indication that significant performance gains over state-of-the-art one-shot sampling techniques are possible, and that evolutionary algorithms can be an efficient means to evolve these.","lang":"eng"}]},{"publication_identifier":{"isbn":["978-1-4503-7128-5"]},"publication_status":"published","page":"1286–1294","citation":{"chicago":"Bossek, Jakob, Katrin Casel, Pascal Kerschke, and Frank Neumann. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1286–1294. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390243\">https://doi.org/10.1145/3377930.3390243</a>.","ieee":"J. Bossek, K. Casel, P. Kerschke, and F. Neumann, “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 1286–1294, doi: <a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>.","ama":"Bossek J, Casel K, Kerschke P, Neumann F. The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:1286–1294. doi:<a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>","short":"J. Bossek, K. Casel, P. Kerschke, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 1286–1294.","mla":"Bossek, Jakob, et al. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 1286–1294, doi:<a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>.","bibtex":"@inproceedings{Bossek_Casel_Kerschke_Neumann_2020, place={New York, NY, USA}, series={GECCO ’20}, title={The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Casel, Katrin and Kerschke, Pascal and Neumann, Frank}, year={2020}, pages={1286–1294}, collection={GECCO ’20} }","apa":"Bossek, J., Casel, K., Kerschke, P., &#38; Neumann, F. (2020). The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1286–1294. <a href=\"https://doi.org/10.1145/3377930.3390243\">https://doi.org/10.1145/3377930.3390243</a>"},"place":"New York, NY, USA","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob"},{"first_name":"Katrin","full_name":"Casel, Katrin","last_name":"Casel"},{"full_name":"Kerschke, Pascal","last_name":"Kerschke","first_name":"Pascal"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"date_updated":"2023-12-13T10:43:33Z","doi":"10.1145/3377930.3390243","type":"conference","status":"public","department":[{"_id":"819"}],"series_title":"GECCO ’20","user_id":"102979","_id":"48851","extern":"1","year":"2020","date_created":"2023-11-14T15:58:53Z","publisher":"Association for Computing Machinery","title":"The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"text":"Several important optimization problems in the area of vehicle routing can be seen as variants of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the Traveling Thief Problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.","lang":"eng"}],"language":[{"iso":"eng"}],"keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"]},{"publication_status":"published","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"place":"New York, NY, USA","year":"2020","citation":{"apa":"Bossek, J., Grimme, C., &#38; Trautmann, H. (2020). Dynamic Bi-Objective Routing of Multiple Vehicles. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 166–174. <a href=\"https://doi.org/10.1145/3377930.3390146\">https://doi.org/10.1145/3377930.3390146</a>","mla":"Bossek, Jakob, et al. “Dynamic Bi-Objective Routing of Multiple Vehicles.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 166–174, doi:<a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>.","short":"J. Bossek, C. Grimme, H. Trautmann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 166–174.","bibtex":"@inproceedings{Bossek_Grimme_Trautmann_2020, place={New York, NY, USA}, series={GECCO ’20}, title={Dynamic Bi-Objective Routing of Multiple Vehicles}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Grimme, Christian and Trautmann, Heike}, year={2020}, pages={166–174}, collection={GECCO ’20} }","ama":"Bossek J, Grimme C, Trautmann H. Dynamic Bi-Objective Routing of Multiple Vehicles. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:166–174. doi:<a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>","chicago":"Bossek, Jakob, Christian Grimme, and Heike Trautmann. “Dynamic Bi-Objective Routing of Multiple Vehicles.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 166–174. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390146\">https://doi.org/10.1145/3377930.3390146</a>.","ieee":"J. Bossek, C. Grimme, and H. Trautmann, “Dynamic Bi-Objective Routing of Multiple Vehicles,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 166–174, doi: <a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>."},"page":"166–174","date_updated":"2023-12-13T10:43:24Z","publisher":"Association for Computing Machinery","author":[{"orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"first_name":"Christian","last_name":"Grimme","full_name":"Grimme, Christian"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"}],"date_created":"2023-11-14T15:58:52Z","title":"Dynamic Bi-Objective Routing of Multiple Vehicles","doi":"10.1145/3377930.3390146","type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"lang":"eng","text":"In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier."}],"status":"public","_id":"48845","user_id":"102979","series_title":"GECCO ’20","department":[{"_id":"819"}],"keyword":["decision making","dynamic optimization","evolutionary algorithms","multi-objective optimization","vehicle routing"],"extern":"1","language":[{"iso":"eng"}]},{"extern":"1","language":[{"iso":"eng"}],"_id":"48844","department":[{"_id":"819"}],"user_id":"102979","abstract":[{"text":"The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard combinatorial optimization problems. The two sophisticated heuristic solvers LKH and EAX and respective (restart) variants manage to calculate close-to optimal or even optimal solutions, also for large instances with several thousand nodes in reasonable time. In this work we extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers based on empirical runtime distributions leading to an increased understanding of solver behaviour and the respective relation to problem hardness. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality. Insights on intersection points of performances offer huge potential for the construction of hybridized solvers depending on instance features. Moreover, instance features tailored to anytime performance and corresponding performance indicators will highly improve automated algorithm selection models by including comprehensive information on solver quality.","lang":"eng"}],"status":"public","publication":"2020 IEEE Congress on Evolutionary Computation (CEC)","type":"conference","title":"Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection","doi":"10.1109/CEC48606.2020.9185613","date_updated":"2023-12-13T10:43:16Z","publisher":"IEEE Press","author":[{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"full_name":"Kerschke, Pascal","last_name":"Kerschke","first_name":"Pascal"},{"first_name":"Heike","last_name":"Trautmann","full_name":"Trautmann, Heike"}],"date_created":"2023-11-14T15:58:52Z","year":"2020","place":"Glasgow, United Kingdom","page":"1–8","citation":{"apa":"Bossek, J., Kerschke, P., &#38; Trautmann, H. (2020). Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection. <i>2020 IEEE Congress on Evolutionary Computation (CEC)</i>, 1–8. <a href=\"https://doi.org/10.1109/CEC48606.2020.9185613\">https://doi.org/10.1109/CEC48606.2020.9185613</a>","mla":"Bossek, Jakob, et al. “Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection.” <i>2020 IEEE Congress on Evolutionary Computation (CEC)</i>, IEEE Press, 2020, pp. 1–8, doi:<a href=\"https://doi.org/10.1109/CEC48606.2020.9185613\">10.1109/CEC48606.2020.9185613</a>.","bibtex":"@inproceedings{Bossek_Kerschke_Trautmann_2020, place={Glasgow, United Kingdom}, title={Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection}, DOI={<a href=\"https://doi.org/10.1109/CEC48606.2020.9185613\">10.1109/CEC48606.2020.9185613</a>}, booktitle={2020 IEEE Congress on Evolutionary Computation (CEC)}, publisher={IEEE Press}, author={Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike}, year={2020}, pages={1–8} }","short":"J. Bossek, P. Kerschke, H. Trautmann, in: 2020 IEEE Congress on Evolutionary Computation (CEC), IEEE Press, Glasgow, United Kingdom, 2020, pp. 1–8.","ama":"Bossek J, Kerschke P, Trautmann H. Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection. In: <i>2020 IEEE Congress on Evolutionary Computation (CEC)</i>. IEEE Press; 2020:1–8. doi:<a href=\"https://doi.org/10.1109/CEC48606.2020.9185613\">10.1109/CEC48606.2020.9185613</a>","ieee":"J. Bossek, P. Kerschke, and H. Trautmann, “Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection,” in <i>2020 IEEE Congress on Evolutionary Computation (CEC)</i>, 2020, pp. 1–8, doi: <a href=\"https://doi.org/10.1109/CEC48606.2020.9185613\">10.1109/CEC48606.2020.9185613</a>.","chicago":"Bossek, Jakob, Pascal Kerschke, and Heike Trautmann. “Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection.” In <i>2020 IEEE Congress on Evolutionary Computation (CEC)</i>, 1–8. Glasgow, United Kingdom: IEEE Press, 2020. <a href=\"https://doi.org/10.1109/CEC48606.2020.9185613\">https://doi.org/10.1109/CEC48606.2020.9185613</a>."},"publication_status":"published"},{"doi":"10.1145/3377930.3390155","author":[{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"first_name":"Carola","full_name":"Doerr, Carola","last_name":"Doerr"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"}],"date_updated":"2023-12-13T10:44:01Z","citation":{"ieee":"J. Bossek, C. Doerr, and P. Kerschke, “Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 778–786, doi: <a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>.","chicago":"Bossek, Jakob, Carola Doerr, and Pascal Kerschke. “Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 778–786. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390155\">https://doi.org/10.1145/3377930.3390155</a>.","ama":"Bossek J, Doerr C, Kerschke P. Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:778–786. doi:<a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>","apa":"Bossek, J., Doerr, C., &#38; Kerschke, P. (2020). Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 778–786. <a href=\"https://doi.org/10.1145/3377930.3390155\">https://doi.org/10.1145/3377930.3390155</a>","mla":"Bossek, Jakob, et al. “Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 778–786, doi:<a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>.","short":"J. Bossek, C. Doerr, P. Kerschke, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 778–786.","bibtex":"@inproceedings{Bossek_Doerr_Kerschke_2020, place={New York, NY, USA}, series={GECCO ’20}, title={Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Doerr, Carola and Kerschke, Pascal}, year={2020}, pages={778–786}, collection={GECCO ’20} }"},"page":"778–786","place":"New York, NY, USA","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"extern":"1","user_id":"102979","series_title":"GECCO ’20","department":[{"_id":"819"}],"_id":"48850","status":"public","type":"conference","title":"Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB","date_created":"2023-11-14T15:58:53Z","publisher":"Association for Computing Machinery","year":"2020","language":[{"iso":"eng"}],"keyword":["continuous black-box optimization","design of experiments","initial design","sequential model-based optimization"],"abstract":[{"text":"Sequential model-based optimization (SMBO) approaches are algorithms for solving problems that require computationally or otherwise expensive function evaluations. The key design principle of SMBO is a substitution of the true objective function by a surrogate, which is used to propose the point(s) to be evaluated next. SMBO algorithms are intrinsically modular, leaving the user with many important design choices. Significant research efforts go into understanding which settings perform best for which type of problems. Most works, however, focus on the choice of the model, the acquisition function, and the strategy used to optimize the latter. The choice of the initial sampling strategy, however, receives much less attention. Not surprisingly, quite diverging recommendations can be found in the literature. We analyze in this work how the size and the distribution of the initial sample influences the overall quality of the efficient global optimization (EGO) algorithm, a well-known SMBO approach. While, overall, small initial budgets using Halton sampling seem preferable, we also observe that the performance landscape is rather unstructured. We furthermore identify several situations in which EGO performs unfavorably against random sampling. Both observations indicate that an adaptive SMBO design could be beneficial, making SMBO an interesting test-bed for automated algorithm design.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference"}]