[{"publication":"IEEE Transactions on Evolutionary Computation","type":"journal_article","status":"public","_id":"63053","department":[{"_id":"819"}],"user_id":"15504","keyword":["Optimization","Evolutionary computation","Hands","Proposals","Convergence","Computational efficiency","Artificial intelligence","Accuracy","Approximation algorithms","Aerospace electronics","Multi-objective optimization","evolutionary algorithms","nearly optimal solutions","multimodal optimization","archiving","continuation"],"language":[{"iso":"eng"}],"year":"2025","page":"1-1","citation":{"ieee":"C. Hernández, A. E. Rodriguez-Fernandez, L. Schäpermeier, O. Cuate, H. Trautmann, and O. Schütze, “An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization,” <i>IEEE Transactions on Evolutionary Computation</i>, pp. 1–1, 2025, doi: <a href=\"https://doi.org/10.1109/TEVC.2025.3637276\">10.1109/TEVC.2025.3637276</a>.","chicago":"Hernández, Carlos, Angel E. Rodriguez-Fernandez, Lennart Schäpermeier, Oliver Cuate, Heike Trautmann, and Oliver Schütze. “An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” <i>IEEE Transactions on Evolutionary Computation</i>, 2025, 1–1. <a href=\"https://doi.org/10.1109/TEVC.2025.3637276\">https://doi.org/10.1109/TEVC.2025.3637276</a>.","ama":"Hernández C, Rodriguez-Fernandez AE, Schäpermeier L, Cuate O, Trautmann H, Schütze O. An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. <i>IEEE Transactions on Evolutionary Computation</i>. Published online 2025:1-1. doi:<a href=\"https://doi.org/10.1109/TEVC.2025.3637276\">10.1109/TEVC.2025.3637276</a>","apa":"Hernández, C., Rodriguez-Fernandez, A. E., Schäpermeier, L., Cuate, O., Trautmann, H., &#38; Schütze, O. (2025). An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. <i>IEEE Transactions on Evolutionary Computation</i>, 1–1. <a href=\"https://doi.org/10.1109/TEVC.2025.3637276\">https://doi.org/10.1109/TEVC.2025.3637276</a>","mla":"Hernández, Carlos, et al. “An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” <i>IEEE Transactions on Evolutionary Computation</i>, 2025, pp. 1–1, doi:<a href=\"https://doi.org/10.1109/TEVC.2025.3637276\">10.1109/TEVC.2025.3637276</a>.","bibtex":"@article{Hernández_Rodriguez-Fernandez_Schäpermeier_Cuate_Trautmann_Schütze_2025, title={An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization}, DOI={<a href=\"https://doi.org/10.1109/TEVC.2025.3637276\">10.1109/TEVC.2025.3637276</a>}, journal={IEEE Transactions on Evolutionary Computation}, author={Hernández, Carlos and Rodriguez-Fernandez, Angel E. and Schäpermeier, Lennart and Cuate, Oliver and Trautmann, Heike and Schütze, Oliver}, year={2025}, pages={1–1} }","short":"C. Hernández, A.E. Rodriguez-Fernandez, L. Schäpermeier, O. Cuate, H. Trautmann, O. Schütze, IEEE Transactions on Evolutionary Computation (2025) 1–1."},"date_updated":"2025-12-12T06:13:51Z","date_created":"2025-12-12T06:13:06Z","author":[{"last_name":"Hernández","full_name":"Hernández, Carlos","first_name":"Carlos"},{"full_name":"Rodriguez-Fernandez, Angel E.","last_name":"Rodriguez-Fernandez","first_name":"Angel E."},{"last_name":"Schäpermeier","full_name":"Schäpermeier, Lennart","first_name":"Lennart"},{"last_name":"Cuate","full_name":"Cuate, Oliver","first_name":"Oliver"},{"first_name":"Heike","full_name":"Trautmann, Heike","id":"100740","last_name":"Trautmann","orcid":"0000-0002-9788-8282"},{"full_name":"Schütze, Oliver","last_name":"Schütze","first_name":"Oliver"}],"title":"An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization","doi":"10.1109/TEVC.2025.3637276"},{"abstract":[{"lang":"eng","text":"Evolutionary algorithms have been shown to obtain good solutions for complex optimization problems in static and dynamic environments. It is important to understand the behaviour of evolutionary algorithms for complex optimization problems that also involve dynamic and/or stochastic components in a systematic way in order to further increase their applicability to real-world problems. We investigate the node weighted traveling salesperson problem (W-TSP), which provides an abstraction of a wide range of weighted TSP problems, in dynamic settings. In the dynamic setting of the problem, items that have to be collected as part of a TSP tour change over time. We first present a dynamic setup for the dynamic W-TSP parameterized by different types of changes that are applied to the set of items to be collected when traversing the tour. Our first experimental investigations study the impact of such changes on resulting optimized tours in order to provide structural insights of optimization solutions. Afterwards, we investigate simple mutation-based evolutionary algorithms and study the impact of the mutation operators and the use of populations with dealing with the dynamic changes to the node weights of the problem."}],"status":"public","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference","keyword":["dynamic optimization","evolutionary algorithms","re-optimization","weighted traveling salesperson problem"],"language":[{"iso":"eng"}],"extern":"1","_id":"48869","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO’23","year":"2023","place":"New York, NY, USA","page":"248–256","citation":{"ama":"Bossek J, Neumann A, Neumann F. On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’23. Association for Computing Machinery; 2023:248–256. doi:<a href=\"https://doi.org/10.1145/3583131.3590384\">10.1145/3583131.3590384</a>","chicago":"Bossek, Jakob, Aneta Neumann, and Frank Neumann. “On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 248–256. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3583131.3590384\">https://doi.org/10.1145/3583131.3590384</a>.","ieee":"J. Bossek, A. Neumann, and F. Neumann, “On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2023, pp. 248–256, doi: <a href=\"https://doi.org/10.1145/3583131.3590384\">10.1145/3583131.3590384</a>.","apa":"Bossek, J., Neumann, A., &#38; Neumann, F. (2023). On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 248–256. <a href=\"https://doi.org/10.1145/3583131.3590384\">https://doi.org/10.1145/3583131.3590384</a>","mla":"Bossek, Jakob, et al. “On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2023, pp. 248–256, doi:<a href=\"https://doi.org/10.1145/3583131.3590384\">10.1145/3583131.3590384</a>.","bibtex":"@inproceedings{Bossek_Neumann_Neumann_2023, place={New York, NY, USA}, series={GECCO’23}, title={On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem}, DOI={<a href=\"https://doi.org/10.1145/3583131.3590384\">10.1145/3583131.3590384</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={2023}, pages={248–256}, collection={GECCO’23} }","short":"J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2023, pp. 248–256."},"publication_identifier":{"isbn":["9798400701191"]},"title":"On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem","doi":"10.1145/3583131.3590384","date_updated":"2023-12-13T10:46:27Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:56Z","author":[{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}]},{"language":[{"iso":"eng"}],"keyword":["Evolutionary algorithms","pseudo-Boolean functions","runtime analysis"],"user_id":"102979","department":[{"_id":"819"}],"_id":"48871","status":"public","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 with polynomial expected optimisation times we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,{$\\lambda$}) EA on OneMax. However, for the one-dimensional Ising model the time to reach Hamming balls of radius (1/2-{$ϵ$})n around optima does not reduce the asymptotic expected optimisation time in the worst case. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.","lang":"eng"}],"type":"journal_article","publication":"Theoretical Computer Science","doi":"10.1016/j.tcs.2023.113757","title":"Do Additional Target Points Speed Up Evolutionary Algorithms?","author":[{"id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Dirk","last_name":"Sudholt","full_name":"Sudholt, Dirk"}],"date_created":"2023-11-14T15:58:56Z","date_updated":"2023-12-13T10:51:07Z","citation":{"ama":"Bossek J, Sudholt D. Do Additional Target Points Speed Up Evolutionary Algorithms? <i>Theoretical Computer Science</i>. Published online 2023:113757. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>","ieee":"J. Bossek and D. Sudholt, “Do Additional Target Points Speed Up Evolutionary Algorithms?,” <i>Theoretical Computer Science</i>, p. 113757, 2023, doi: <a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>.","chicago":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary Algorithms?” <i>Theoretical Computer Science</i>, 2023, 113757. <a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">https://doi.org/10.1016/j.tcs.2023.113757</a>.","bibtex":"@article{Bossek_Sudholt_2023, title={Do Additional Target Points Speed Up Evolutionary Algorithms?}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>}, journal={Theoretical Computer Science}, author={Bossek, Jakob and Sudholt, Dirk}, year={2023}, pages={113757} }","short":"J. Bossek, D. Sudholt, Theoretical Computer Science (2023) 113757.","mla":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary Algorithms?” <i>Theoretical Computer Science</i>, 2023, p. 113757, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">10.1016/j.tcs.2023.113757</a>.","apa":"Bossek, J., &#38; Sudholt, D. (2023). Do Additional Target Points Speed Up Evolutionary Algorithms? <i>Theoretical Computer Science</i>, 113757. <a href=\"https://doi.org/10.1016/j.tcs.2023.113757\">https://doi.org/10.1016/j.tcs.2023.113757</a>"},"page":"113757","year":"2023","publication_identifier":{"issn":["0304-3975"]}},{"doi":"10.1007/978-3-031-14714-2_17","date_updated":"2023-12-13T10:49:51Z","author":[{"first_name":"Adel","full_name":"Nikfarjam, Adel","last_name":"Nikfarjam"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"},{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"place":"Cham","page":"237–249","citation":{"apa":"Nikfarjam, A., Neumann, A., Bossek, J., &#38; Neumann, F. (2022). Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem. In G. Rudolph, A. V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, &#38; T. Tu\\v sar (Eds.), <i>Parallel Problem Solving from Nature (PPSN XVII)</i> (pp. 237–249). Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">https://doi.org/10.1007/978-3-031-14714-2_17</a>","mla":"Nikfarjam, Adel, et al. “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem.” <i>Parallel Problem Solving from Nature (PPSN XVII)</i>, edited by Günter Rudolph et al., Springer International Publishing, 2022, pp. 237–249, doi:<a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>.","short":"A. Nikfarjam, A. Neumann, J. Bossek, F. Neumann, in: G. Rudolph, A.V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, T. Tu\\v sar (Eds.), Parallel Problem Solving from Nature (PPSN XVII), Springer International Publishing, Cham, 2022, pp. 237–249.","bibtex":"@inproceedings{Nikfarjam_Neumann_Bossek_Neumann_2022, place={Cham}, series={Lecture Notes in Computer Science}, title={Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem}, DOI={<a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>}, booktitle={Parallel Problem Solving from Nature (PPSN XVII)}, publisher={Springer International Publishing}, author={Nikfarjam, Adel and Neumann, Aneta and Bossek, Jakob and Neumann, Frank}, editor={Rudolph, Günter and Kononova, Anna V. and Aguirre, Hernán and Kerschke, Pascal and Ochoa, Gabriela and Tu\\v sar, Tea}, year={2022}, pages={237–249}, collection={Lecture Notes in Computer Science} }","ama":"Nikfarjam A, Neumann A, Bossek J, Neumann F. Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem. In: Rudolph G, Kononova AV, Aguirre H, Kerschke P, Ochoa G, Tu\\v sar T, eds. <i>Parallel Problem Solving from Nature (PPSN XVII)</i>. Lecture Notes in Computer Science. Springer International Publishing; 2022:237–249. doi:<a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>","ieee":"A. Nikfarjam, A. Neumann, J. Bossek, and F. Neumann, “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem,” in <i>Parallel Problem Solving from Nature (PPSN XVII)</i>, 2022, pp. 237–249, doi: <a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>.","chicago":"Nikfarjam, Adel, Aneta Neumann, Jakob Bossek, and Frank Neumann. “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem.” In <i>Parallel Problem Solving from Nature (PPSN XVII)</i>, edited by Günter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, and Tea Tu\\v sar, 237–249. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2022. <a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">https://doi.org/10.1007/978-3-031-14714-2_17</a>."},"publication_identifier":{"isbn":["978-3-031-14714-2"]},"publication_status":"published","extern":"1","_id":"48894","department":[{"_id":"819"}],"series_title":"Lecture Notes in Computer Science","user_id":"102979","editor":[{"full_name":"Rudolph, Günter","last_name":"Rudolph","first_name":"Günter"},{"first_name":"Anna V.","full_name":"Kononova, Anna V.","last_name":"Kononova"},{"first_name":"Hernán","full_name":"Aguirre, Hernán","last_name":"Aguirre"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"},{"full_name":"Ochoa, Gabriela","last_name":"Ochoa","first_name":"Gabriela"},{"last_name":"Tu\\v sar","full_name":"Tu\\v sar, Tea","first_name":"Tea"}],"status":"public","type":"conference","title":"Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem","publisher":"Springer International Publishing","date_created":"2023-11-14T15:59:00Z","year":"2022","keyword":["Co-evolutionary algorithms","Evolutionary diversity optimisation","Quality diversity","Traveling thief problem"],"language":[{"iso":"eng"}],"abstract":[{"text":"Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. The results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the literature.","lang":"eng"}],"publication":"Parallel Problem Solving from Nature (PPSN XVII)"},{"keyword":["evolutionary algorithms","evolutionary diversity optimization","knapsack problem","tailored operators"],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","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."}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","title":"Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:54Z","year":"2021","extern":"1","_id":"48853","series_title":"GECCO ’21","user_id":"102979","department":[{"_id":"819"}],"status":"public","type":"conference","doi":"10.1145/3449639.3459364","date_updated":"2023-12-13T10:45:22Z","author":[{"id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"place":"New York, NY, USA","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>","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>.","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>.","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>"},"page":"556–564","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-8350-9"]}},{"title":"Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem","doi":"10.1145/3449639.3459363","date_updated":"2023-12-13T10:45:37Z","publisher":"Association for Computing Machinery","author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"date_created":"2023-11-14T15:58:55Z","place":"New York, NY, USA","year":"2021","page":"198–206","citation":{"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>","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} }","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>","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>.","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>."},"publication_identifier":{"isbn":["978-1-4503-8350-9"]},"publication_status":"published","keyword":["evolutionary algorithms","evolutionary diversity optimization","minimum spanning tree","runtime analysis"],"language":[{"iso":"eng"}],"extern":"1","_id":"48860","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO ’21","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."}],"status":"public","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference"},{"date_updated":"2023-12-13T10:45:31Z","publisher":"Association for Computing Machinery","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979"},{"first_name":"Dirk","full_name":"Sudholt, Dirk","last_name":"Sudholt"}],"date_created":"2023-11-14T15:58:55Z","title":"Do Additional Optima Speed up Evolutionary Algorithms?","publication_identifier":{"isbn":["978-1-4503-8352-3"]},"publication_status":"published","year":"2021","place":"New York, NY, USA","page":"1–11","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.","mla":"Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary Algorithms?” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–11.","short":"J. Bossek, D. Sudholt, in: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–11.","bibtex":"@inbook{Bossek_Sudholt_2021, place={New York, NY, USA}, title={Do Additional Optima Speed up Evolutionary Algorithms?}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2021}, pages={1–11} }","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."},"_id":"48862","department":[{"_id":"819"}],"user_id":"102979","keyword":["evolutionary algorithms","pseudo-boolean functions","runtime analysis","theory"],"extern":"1","language":[{"iso":"eng"}],"publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","type":"book_chapter","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"},{"status":"public","type":"conference","extern":"1","_id":"48876","series_title":"GECCO’21","user_id":"102979","department":[{"_id":"819"}],"place":"New York, NY, USA","citation":{"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.","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>","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>","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>.","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>."},"page":"1423–1432","publication_identifier":{"isbn":["978-1-4503-8351-6"]},"doi":"10.1145/3449726.3463165","date_updated":"2023-12-13T10:47:41Z","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob"},{"last_name":"Wagner","full_name":"Wagner, Markus","first_name":"Markus"}],"abstract":[{"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.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","keyword":["evolutionary algorithms","evolving instances","fitness function","instance hardness","traveling thief problem (TTP)"],"language":[{"iso":"eng"}],"year":"2021","title":"Generating Instances with Performance Differences for More than Just Two Algorithms","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:57Z"},{"publication_identifier":{"isbn":["978-1-4503-8350-9"]},"year":"2021","place":"New York, NY, USA","page":"600–608","citation":{"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>.","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>.","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>","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>","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} }","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.","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>."},"publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:50:06Z","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"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"date_created":"2023-11-14T15:59:00Z","title":"Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem","doi":"10.1145/3449639.3459384","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference","abstract":[{"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.","lang":"eng"}],"status":"public","_id":"48893","department":[{"_id":"819"}],"series_title":"GECCO’21","user_id":"102979","keyword":["evolutionary algorithms","evolutionary diversity optimisation","high-order entropy","traveling salesperson problem"],"language":[{"iso":"eng"}],"extern":"1"},{"publication_identifier":{"isbn":["978-1-4503-8350-9"]},"page":"261–269","citation":{"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>.","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.","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>","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>.","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>.","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>"},"place":"New York, NY, USA","author":[{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"},{"last_name":"Bossek","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_updated":"2023-12-13T10:49:25Z","doi":"10.1145/3449639.3459385","type":"conference","status":"public","department":[{"_id":"819"}],"series_title":"GECCO’21","user_id":"102979","_id":"48891","extern":"1","year":"2021","date_created":"2023-11-14T15:58:59Z","publisher":"Association for Computing Machinery","title":"Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"lang":"eng","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."}],"language":[{"iso":"eng"}],"keyword":["evolutionary algorithms","evolutionary diversity optimisation","sub-modular functions"]},{"publication_identifier":{"isbn":["978-1-4503-8352-3"]},"place":"New York, NY, USA","year":"2021","page":"1–11","citation":{"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.","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.","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.","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} }","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.","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."},"publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:49:59Z","author":[{"last_name":"Nikfarjam","full_name":"Nikfarjam, Adel","first_name":"Adel"},{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"first_name":"Aneta","full_name":"Neumann, Aneta","last_name":"Neumann"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"date_created":"2023-11-14T15:59:00Z","title":"Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation","publication":"Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms","type":"book_chapter","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","_id":"48892","department":[{"_id":"819"}],"user_id":"102979","keyword":["edge assembly crossover (EAX)","evolutionary algorithms","evolutionary diversity optimisation (EDO)","traveling salesperson problem (TSP)"],"language":[{"iso":"eng"}],"extern":"1"},{"type":"journal_article","publication":"Algorithmica","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","_id":"48854","user_id":"102979","department":[{"_id":"819"}],"keyword":["Dynamic optimization","Evolutionary algorithms","Running time analysis"],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0178-4617"]},"issue":"10","year":"2021","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>.","short":"J. Bossek, F. Neumann, P. Peng, D. Sudholt, Algorithmica 83 (2021) 3148–3179.","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>.","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>"},"intvolume":"        83","page":"3148–3179","date_updated":"2023-12-13T10:51:34Z","author":[{"last_name":"Bossek","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"},{"first_name":"Pan","last_name":"Peng","full_name":"Peng, Pan"},{"first_name":"Dirk","full_name":"Sudholt, Dirk","last_name":"Sudholt"}],"date_created":"2023-11-14T15:58:54Z","volume":83,"title":"Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem","doi":"10.1007/s00453-021-00838-3"},{"doi":"10.1145/3377930.3390174","title":"More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization","date_created":"2023-11-14T15:58:53Z","author":[{"orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"},{"first_name":"Pan","full_name":"Peng, Pan","last_name":"Peng"},{"last_name":"Sudholt","full_name":"Sudholt, Dirk","first_name":"Dirk"}],"publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:43:41Z","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>","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>.","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} }","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.","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>"},"page":"1277–1285","place":"New York, NY, USA","year":"2020","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"language":[{"iso":"eng"}],"extern":"1","keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"],"series_title":"GECCO ’20","user_id":"102979","department":[{"_id":"819"}],"_id":"48847","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"}],"type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference"},{"status":"public","type":"conference","extern":"1","series_title":"GECCO ’20","user_id":"102979","department":[{"_id":"819"}],"_id":"48851","citation":{"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>","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>.","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.","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} }","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>.","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>.","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>"},"page":"1286–1294","place":"New York, NY, USA","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"doi":"10.1145/3377930.3390243","author":[{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"full_name":"Casel, Katrin","last_name":"Casel","first_name":"Katrin"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"date_updated":"2023-12-13T10:43:33Z","abstract":[{"lang":"eng","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."}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","language":[{"iso":"eng"}],"keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"],"year":"2020","title":"The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics","date_created":"2023-11-14T15:58:53Z","publisher":"Association for Computing Machinery"},{"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","type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","keyword":["decision making","dynamic optimization","evolutionary algorithms","multi-objective optimization","vehicle routing"],"extern":"1","language":[{"iso":"eng"}],"_id":"48845","series_title":"GECCO ’20","user_id":"102979","department":[{"_id":"819"}],"place":"New York, NY, USA","year":"2020","citation":{"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>.","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>","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>","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} }","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."},"page":"166–174","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"title":"Dynamic Bi-Objective Routing of Multiple Vehicles","doi":"10.1145/3377930.3390146","date_updated":"2023-12-13T10:43:24Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:52Z","author":[{"orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"last_name":"Grimme","full_name":"Grimme, Christian","first_name":"Christian"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"}]},{"doi":"10.1007/978-3-030-58112-1_24","title":"Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions","author":[{"first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_created":"2023-11-14T15:58:54Z","publisher":"Springer-Verlag","date_updated":"2023-12-13T10:44:54Z","citation":{"mla":"Bossek, Jakob, et al. “Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions.” <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, Springer-Verlag, 2020, pp. 346–359, doi:<a href=\"https://doi.org/10.1007/978-3-030-58112-1_24\">10.1007/978-3-030-58112-1_24</a>.","bibtex":"@inproceedings{Bossek_Neumann_Neumann_2020, place={Berlin, Heidelberg}, title={Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-58112-1_24\">10.1007/978-3-030-58112-1_24</a>}, booktitle={Parallel Problem Solving from Nature (PPSN XVI)}, publisher={Springer-Verlag}, author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={346–359} }","short":"J. Bossek, A. Neumann, F. Neumann, in: Parallel Problem Solving from Nature (PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp. 346–359.","apa":"Bossek, J., Neumann, A., &#38; Neumann, F. (2020). Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions. <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, 346–359. <a href=\"https://doi.org/10.1007/978-3-030-58112-1_24\">https://doi.org/10.1007/978-3-030-58112-1_24</a>","chicago":"Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions.” In <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, 346–359. Berlin, Heidelberg: Springer-Verlag, 2020. <a href=\"https://doi.org/10.1007/978-3-030-58112-1_24\">https://doi.org/10.1007/978-3-030-58112-1_24</a>.","ieee":"J. Bossek, A. Neumann, and F. Neumann, “Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions,” in <i>Parallel Problem Solving from Nature (PPSN XVI)</i>, 2020, pp. 346–359, doi: <a href=\"https://doi.org/10.1007/978-3-030-58112-1_24\">10.1007/978-3-030-58112-1_24</a>.","ama":"Bossek J, Neumann A, Neumann F. Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions. In: <i>Parallel Problem Solving from Nature (PPSN XVI)</i>. Springer-Verlag; 2020:346–359. doi:<a href=\"https://doi.org/10.1007/978-3-030-58112-1_24\">10.1007/978-3-030-58112-1_24</a>"},"page":"346–359","place":"Berlin, Heidelberg","year":"2020","publication_status":"published","publication_identifier":{"isbn":["978-3-030-58111-4"]},"language":[{"iso":"eng"}],"extern":"1","keyword":["Evolutionary algorithms","Node weight dependent TSP","Traveling Thief Problem"],"user_id":"102979","department":[{"_id":"819"}],"_id":"48852","status":"public","abstract":[{"lang":"eng","text":"The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. However, many real-world problems are composed of several interacting components. The Traveling Thief Problem (TTP) addresses such interactions by combining two combinatorial optimisation problems, namely the TSP and the Knapsack Problem (KP). Recently, a new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. In this paper, we compare W-TSP and TTP. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function. Our experimental results suggest (1) that the W-TSP often can be solved better using the TTP fitness function and (2) final W-TSP and TTP solutions show different distributions when compared with optimal TSP or weighted greedy solutions."}],"type":"conference","publication":"Parallel Problem Solving from Nature (PPSN XVI)"},{"keyword":["diversity maximisation","evolutionary algorithms","travelling salesperson problem"],"language":[{"iso":"eng"}],"abstract":[{"text":"Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","title":"Evolving Diverse Sets of Tours for the Travelling Salesperson Problem","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:58Z","year":"2020","extern":"1","_id":"48879","user_id":"102979","series_title":"GECCO’20","department":[{"_id":"819"}],"status":"public","type":"conference","doi":"10.1145/3377930.3389844","date_updated":"2023-12-13T10:48:50Z","author":[{"full_name":"Do, Anh Viet","last_name":"Do","first_name":"Anh Viet"},{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Aneta","full_name":"Neumann, Aneta","last_name":"Neumann"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"place":"New York, NY, USA","citation":{"short":"A.V. Do, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 681–689.","mla":"Do, Anh Viet, et al. “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 681–689, doi:<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>.","bibtex":"@inproceedings{Do_Bossek_Neumann_Neumann_2020, place={New York, NY, USA}, series={GECCO’20}, title={Evolving Diverse Sets of Tours for the Travelling Salesperson Problem}, DOI={<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Do, Anh Viet and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={681–689}, collection={GECCO’20} }","apa":"Do, A. V., Bossek, J., Neumann, A., &#38; Neumann, F. (2020). Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 681–689. <a href=\"https://doi.org/10.1145/3377930.3389844\">https://doi.org/10.1145/3377930.3389844</a>","ama":"Do AV, Bossek J, Neumann A, Neumann F. Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’20. Association for Computing Machinery; 2020:681–689. doi:<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>","ieee":"A. V. Do, J. Bossek, A. Neumann, and F. Neumann, “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 681–689, doi: <a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>.","chicago":"Do, Anh Viet, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 681–689. GECCO’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3389844\">https://doi.org/10.1145/3377930.3389844</a>."},"page":"681–689","publication_identifier":{"isbn":["978-1-4503-7128-5"]}},{"doi":"10.1145/3377930.3390168","title":"Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem","author":[{"full_name":"Roostapour, Vahid","last_name":"Roostapour","first_name":"Vahid"},{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"date_created":"2023-11-14T15:59:00Z","date_updated":"2023-12-13T10:49:38Z","publisher":"Association for Computing Machinery","citation":{"apa":"Roostapour, V., Bossek, J., &#38; Neumann, F. (2020). Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, 551–559. <a href=\"https://doi.org/10.1145/3377930.3390168\">https://doi.org/10.1145/3377930.3390168</a>","bibtex":"@inproceedings{Roostapour_Bossek_Neumann_2020, place={New York, NY, USA}, series={{GECCO} ’20}, title={Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>}, booktitle={Proceedings of the 2020 Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Roostapour, Vahid and Bossek, Jakob and Neumann, Frank}, year={2020}, pages={551–559}, collection={{GECCO} ’20} }","short":"V. Roostapour, J. Bossek, F. Neumann, in: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 551–559.","mla":"Roostapour, Vahid, et al. “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 551–559, doi:<a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>.","ama":"Roostapour V, Bossek J, Neumann F. Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. In: <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>. {GECCO} ’20. Association for Computing Machinery; 2020:551–559. doi:<a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>","chicago":"Roostapour, Vahid, Jakob Bossek, and Frank Neumann. “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” In <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, 551–559. {GECCO} ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390168\">https://doi.org/10.1145/3377930.3390168</a>.","ieee":"V. Roostapour, J. Bossek, and F. Neumann, “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem,” in <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, 2020, pp. 551–559, doi: <a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>."},"page":"551–559","place":"New York, NY, USA","year":"2020","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"extern":"1","language":[{"iso":"eng"}],"keyword":["biased mutation","evolutionary algorithms","minimum spanning tree problem","runtime analysis"],"series_title":"{GECCO} ’20","user_id":"102979","department":[{"_id":"819"}],"_id":"48895","status":"public","abstract":[{"text":"Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if \"heavy\" edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound - as unbiased mutation - in the worst case and benefits from bias if the circumstances are favorable.","lang":"eng"}],"type":"conference","publication":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference"},{"place":"New York, NY, USA","citation":{"apa":"Bossek, J., Neumann, F., Peng, P., &#38; Sudholt, D. (2019). Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1443–1451. <a href=\"https://doi.org/10.1145/3321707.3321792\">https://doi.org/10.1145/3321707.3321792</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, 2019, pp. 1443–1451.","mla":"Bossek, Jakob, et al. “Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2019, pp. 1443–1451, doi:<a href=\"https://doi.org/10.1145/3321707.3321792\">10.1145/3321707.3321792</a>.","bibtex":"@inproceedings{Bossek_Neumann_Peng_Sudholt_2019, place={New York, NY, USA}, series={GECCO ’19}, title={Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring}, DOI={<a href=\"https://doi.org/10.1145/3321707.3321792\">10.1145/3321707.3321792</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={2019}, pages={1443–1451}, collection={GECCO ’19} }","ama":"Bossek J, Neumann F, Peng P, Sudholt D. Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’19. Association for Computing Machinery; 2019:1443–1451. doi:<a href=\"https://doi.org/10.1145/3321707.3321792\">10.1145/3321707.3321792</a>","chicago":"Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1443–1451. GECCO ’19. New York, NY, USA: Association for Computing Machinery, 2019. <a href=\"https://doi.org/10.1145/3321707.3321792\">https://doi.org/10.1145/3321707.3321792</a>.","ieee":"J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2019, pp. 1443–1451, doi: <a href=\"https://doi.org/10.1145/3321707.3321792\">10.1145/3321707.3321792</a>."},"page":"1443–1451","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-6111-8"]},"doi":"10.1145/3321707.3321792","date_updated":"2023-12-13T10:42:37Z","author":[{"orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"},{"first_name":"Dirk","last_name":"Sudholt","full_name":"Sudholt, Dirk"}],"status":"public","type":"conference","extern":"1","_id":"48843","user_id":"102979","series_title":"GECCO ’19","department":[{"_id":"819"}],"year":"2019","title":"Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:52Z","abstract":[{"text":"We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical graph coloring problem 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. This includes the (1+1) EA and RLS in a setting where the number of colors is bounded and we are minimizing the number of conflicts as well as iterated local search algorithms that use an unbounded color palette and aim to use the smallest colors and - as a consequence - 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. Furthermore, we show how to speed up computations by using problem specific operators concentrating on parts of the graph where changes have occurred.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"],"language":[{"iso":"eng"}]},{"title":"Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement","doi":"10.1145/2739480.2754673","date_updated":"2023-12-13T10:40:30Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:51Z","author":[{"first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob"},{"last_name":"Bischl","full_name":"Bischl, Bernd","first_name":"Bernd"},{"full_name":"Wagner, Tobias","last_name":"Wagner","first_name":"Tobias"},{"last_name":"Rudolph","full_name":"Rudolph, Günter","first_name":"Günter"}],"place":"New York, NY, USA","year":"2015","page":"1319–1326","citation":{"apa":"Bossek, J., Bischl, B., Wagner, T., &#38; Rudolph, G. (2015). Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1319–1326. <a href=\"https://doi.org/10.1145/2739480.2754673\">https://doi.org/10.1145/2739480.2754673</a>","short":"J. Bossek, B. Bischl, T. Wagner, G. Rudolph, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2015, pp. 1319–1326.","mla":"Bossek, Jakob, et al. “Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2015, pp. 1319–1326, doi:<a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>.","bibtex":"@inproceedings{Bossek_Bischl_Wagner_Rudolph_2015, place={New York, NY, USA}, series={GECCO ’15}, title={Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement}, DOI={<a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Bischl, Bernd and Wagner, Tobias and Rudolph, Günter}, year={2015}, pages={1319–1326}, collection={GECCO ’15} }","ama":"Bossek J, Bischl B, Wagner T, Rudolph G. Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’15. Association for Computing Machinery; 2015:1319–1326. doi:<a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>","chicago":"Bossek, Jakob, Bernd Bischl, Tobias Wagner, and Günter Rudolph. “Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1319–1326. GECCO ’15. New York, NY, USA: Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2739480.2754673\">https://doi.org/10.1145/2739480.2754673</a>.","ieee":"J. Bossek, B. Bischl, T. Wagner, and G. Rudolph, “Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2015, pp. 1319–1326, doi: <a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>."},"publication_identifier":{"isbn":["978-1-4503-3472-3"]},"publication_status":"published","keyword":["evolutionary algorithms","model-based optimization","parameter tuning"],"language":[{"iso":"eng"}],"extern":"1","_id":"48838","department":[{"_id":"819"}],"series_title":"GECCO ’15","user_id":"102979","abstract":[{"lang":"eng","text":"The majority of algorithms can be controlled or adjusted by parameters. Their values can substantially affect the algorithms’ performance. Since the manual exploration of the parameter space is tedious – even for few parameters – several automatic procedures for parameter tuning have been proposed. Recent approaches also take into account some characteristic properties of the problem instances, frequently termed instance features. Our contribution is the proposal of a novel concept for feature-based algorithm parameter tuning, which applies an approximating surrogate model for learning the continuous feature-parameter mapping. To accomplish this, we learn a joint model of the algorithm performance based on both the algorithm parameters and the instance features. The required data is gathered using a recently proposed acquisition function for model refinement in surrogate-based optimization: the profile expected improvement. This function provides an avenue for maximizing the information required for the feature-parameter mapping, i.e., the mapping from instance features to the corresponding optimal algorithm parameters. The approach is validated by applying the tuner to exemplary evolutionary algorithms and problems, for which theoretically grounded or heuristically determined feature-parameter mappings are available."}],"status":"public","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference"}]