--- _id: '63053' author: - first_name: Carlos full_name: Hernández, Carlos last_name: Hernández - first_name: Angel E. full_name: Rodriguez-Fernandez, Angel E. last_name: Rodriguez-Fernandez - first_name: Lennart full_name: Schäpermeier, Lennart last_name: Schäpermeier - first_name: Oliver full_name: Cuate, Oliver last_name: Cuate - first_name: Heike full_name: Trautmann, Heike id: '100740' last_name: Trautmann orcid: 0000-0002-9788-8282 - first_name: Oliver full_name: Schütze, Oliver last_name: Schütze citation: 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. IEEE Transactions on Evolutionary Computation. Published online 2025:1-1. doi:10.1109/TEVC.2025.3637276 apa: Hernández, C., Rodriguez-Fernandez, A. E., Schäpermeier, L., Cuate, O., Trautmann, H., & Schütze, O. (2025). An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. IEEE Transactions on Evolutionary Computation, 1–1. https://doi.org/10.1109/TEVC.2025.3637276 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={10.1109/TEVC.2025.3637276}, 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} }' 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.” IEEE Transactions on Evolutionary Computation, 2025, 1–1. https://doi.org/10.1109/TEVC.2025.3637276. 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,” IEEE Transactions on Evolutionary Computation, pp. 1–1, 2025, doi: 10.1109/TEVC.2025.3637276.' mla: Hernández, Carlos, et al. “An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” IEEE Transactions on Evolutionary Computation, 2025, pp. 1–1, doi:10.1109/TEVC.2025.3637276. 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_created: 2025-12-12T06:13:06Z date_updated: 2025-12-12T06:13:51Z department: - _id: '819' doi: 10.1109/TEVC.2025.3637276 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 page: 1-1 publication: IEEE Transactions on Evolutionary Computation status: public title: An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization type: journal_article user_id: '15504' year: '2025' ... --- _id: '56221' author: - first_name: Angel E. full_name: Rodriguez-Fernandez, Angel E. last_name: Rodriguez-Fernandez - first_name: Lennart full_name: Schäpermeier, Lennart last_name: Schäpermeier - first_name: Carlos full_name: Hernández, Carlos last_name: Hernández - first_name: Pascal full_name: Kerschke, Pascal last_name: Kerschke - first_name: Heike full_name: Trautmann, Heike id: '100740' last_name: Trautmann orcid: 0000-0002-9788-8282 - first_name: Oliver full_name: Schütze, Oliver last_name: Schütze citation: ama: Rodriguez-Fernandez AE, Schäpermeier L, Hernández C, Kerschke P, Trautmann H, Schütze O. Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. IEEE Transactions on Evolutionary Computation. Published online 2024:1-1. doi:10.1109/TEVC.2024.3458855 apa: Rodriguez-Fernandez, A. E., Schäpermeier, L., Hernández, C., Kerschke, P., Trautmann, H., & Schütze, O. (2024). Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. IEEE Transactions on Evolutionary Computation, 1–1. https://doi.org/10.1109/TEVC.2024.3458855 bibtex: '@article{Rodriguez-Fernandez_Schäpermeier_Hernández_Kerschke_Trautmann_Schütze_2024, title={Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization}, DOI={10.1109/TEVC.2024.3458855}, journal={IEEE Transactions on Evolutionary Computation}, author={Rodriguez-Fernandez, Angel E. and Schäpermeier, Lennart and Hernández, Carlos and Kerschke, Pascal and Trautmann, Heike and Schütze, Oliver}, year={2024}, pages={1–1} }' chicago: Rodriguez-Fernandez, Angel E., Lennart Schäpermeier, Carlos Hernández, Pascal Kerschke, Heike Trautmann, and Oliver Schütze. “Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” IEEE Transactions on Evolutionary Computation, 2024, 1–1. https://doi.org/10.1109/TEVC.2024.3458855. ieee: 'A. E. Rodriguez-Fernandez, L. Schäpermeier, C. Hernández, P. Kerschke, H. Trautmann, and O. Schütze, “Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization,” IEEE Transactions on Evolutionary Computation, pp. 1–1, 2024, doi: 10.1109/TEVC.2024.3458855.' mla: Rodriguez-Fernandez, Angel E., et al. “Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” IEEE Transactions on Evolutionary Computation, 2024, pp. 1–1, doi:10.1109/TEVC.2024.3458855. short: A.E. Rodriguez-Fernandez, L. Schäpermeier, C. Hernández, P. Kerschke, H. Trautmann, O. Schütze, IEEE Transactions on Evolutionary Computation (2024) 1–1. date_created: 2024-09-24T08:01:14Z date_updated: 2024-09-24T08:01:47Z doi: 10.1109/TEVC.2024.3458855 keyword: - Optimization - Evolutionary computation - Approximation algorithms - Benchmark testing - Vectors - Surveys - Pareto optimization - multi-objective optimization - evolutionary computation - multimodal optimization - local solutions language: - iso: eng page: 1-1 publication: IEEE Transactions on Evolutionary Computation status: public title: Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization type: journal_article user_id: '15504' year: '2024' ... --- _id: '48869' 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. author: - 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 - first_name: Frank full_name: Neumann, Frank last_name: Neumann 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: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO’23. Association for Computing Machinery; 2023:248–256. doi:10.1145/3583131.3590384' apa: Bossek, J., Neumann, A., & Neumann, F. (2023). On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem. Proceedings of the Genetic and Evolutionary Computation Conference, 248–256. https://doi.org/10.1145/3583131.3590384 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={10.1145/3583131.3590384}, 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} }' 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 Proceedings of the Genetic and Evolutionary Computation Conference, 248–256. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023. https://doi.org/10.1145/3583131.3590384.' 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 Proceedings of the Genetic and Evolutionary Computation Conference, 2023, pp. 248–256, doi: 10.1145/3583131.3590384.' mla: Bossek, Jakob, et al. “On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2023, pp. 248–256, doi:10.1145/3583131.3590384. 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.' date_created: 2023-11-14T15:58:56Z date_updated: 2023-12-13T10:46:27Z department: - _id: '819' doi: 10.1145/3583131.3590384 extern: '1' keyword: - dynamic optimization - evolutionary algorithms - re-optimization - weighted traveling salesperson problem language: - iso: eng page: 248–256 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - '9798400701191' publisher: Association for Computing Machinery series_title: GECCO’23 status: public title: On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem type: conference user_id: '102979' year: '2023' ... --- _id: '48871' abstract: - lang: eng text: 'Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT{$\cup$}S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions with polynomial expected optimisation times we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,{$\lambda$}) EA on OneMax. However, for the one-dimensional Ising model the time to reach Hamming balls of radius (1/2-{$ϵ$})n around optima does not reduce the asymptotic expected optimisation time in the worst case. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.' author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Dirk full_name: Sudholt, Dirk last_name: Sudholt citation: ama: Bossek J, Sudholt D. Do Additional Target Points Speed Up Evolutionary Algorithms? Theoretical Computer Science. Published online 2023:113757. doi:10.1016/j.tcs.2023.113757 apa: Bossek, J., & Sudholt, D. (2023). Do Additional Target Points Speed Up Evolutionary Algorithms? Theoretical Computer Science, 113757. https://doi.org/10.1016/j.tcs.2023.113757 bibtex: '@article{Bossek_Sudholt_2023, title={Do Additional Target Points Speed Up Evolutionary Algorithms?}, DOI={10.1016/j.tcs.2023.113757}, journal={Theoretical Computer Science}, author={Bossek, Jakob and Sudholt, Dirk}, year={2023}, pages={113757} }' chicago: Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary Algorithms?” Theoretical Computer Science, 2023, 113757. https://doi.org/10.1016/j.tcs.2023.113757. ieee: 'J. Bossek and D. Sudholt, “Do Additional Target Points Speed Up Evolutionary Algorithms?,” Theoretical Computer Science, p. 113757, 2023, doi: 10.1016/j.tcs.2023.113757.' mla: Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary Algorithms?” Theoretical Computer Science, 2023, p. 113757, doi:10.1016/j.tcs.2023.113757. short: J. Bossek, D. Sudholt, Theoretical Computer Science (2023) 113757. date_created: 2023-11-14T15:58:56Z date_updated: 2023-12-13T10:51:07Z department: - _id: '819' doi: 10.1016/j.tcs.2023.113757 keyword: - Evolutionary algorithms - pseudo-Boolean functions - runtime analysis language: - iso: eng page: '113757' publication: Theoretical Computer Science publication_identifier: issn: - 0304-3975 status: public title: Do Additional Target Points Speed Up Evolutionary Algorithms? type: journal_article user_id: '102979' year: '2023' ... --- _id: '52127' abstract: - lang: eng text: This report documents the program and the outcomes of Dagstuhl Seminar 23161 "Pushing the Limits of Computational Combinatorial Constructions". In this Dagstuhl Seminar, we focused on computational methods for challenging problems in combinatorial construction. This includes algorithms for construction of combinatorial objects with prescribed symmetry, for isomorph-free exhaustive generation, and for combinatorial search. Examples of specific algorithmic techniques are tactical decomposition, the Kramer-Mesner method, algebraic methods, graph isomorphism software, isomorph-free generation, clique-finding methods, heuristic search, SAT solvers, and combinatorial optimization. There was an emphasis on problems involving graphs, designs and codes, also including topics in related fields such as finite geometry, graph decomposition, Hadamard matrices, Latin squares, and q-analogs of designs and codes. author: - first_name: Lucia full_name: Moura, Lucia last_name: Moura - first_name: Anamari full_name: Nakic, Anamari last_name: Nakic - first_name: Patric full_name: Östergård, Patric last_name: Östergård - first_name: Alfred full_name: Wassermann, Alfred last_name: Wassermann - first_name: Charlene full_name: Weiß, Charlene id: '70420' last_name: Weiß citation: ama: Moura L, Nakic A, Östergård P, Wassermann A, Weiß C. Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161). Vol 13, Issue 4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023:40-57. doi:10.4230/DagRep.13.4.40 apa: Moura, L., Nakic, A., Östergård, P., Wassermann, A., & Weiß, C. (2023). Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161) (Vols. 13, Issue 4, pp. 40–57). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/DagRep.13.4.40 bibtex: '@book{Moura_Nakic_Östergård_Wassermann_Weiß_2023, series={Dagstuhl Reports}, title={Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161)}, volume={13, Issue 4}, DOI={10.4230/DagRep.13.4.40}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, author={Moura, Lucia and Nakic, Anamari and Östergård, Patric and Wassermann, Alfred and Weiß, Charlene}, year={2023}, pages={40–57}, collection={Dagstuhl Reports} }' chicago: Moura, Lucia, Anamari Nakic, Patric Östergård, Alfred Wassermann, and Charlene Weiß. Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161). Vol. 13, Issue 4. Dagstuhl Reports. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/DagRep.13.4.40. ieee: L. Moura, A. Nakic, P. Östergård, A. Wassermann, and C. Weiß, Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161), vol. 13, Issue 4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 40–57. mla: Moura, Lucia, et al. Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 40–57, doi:10.4230/DagRep.13.4.40. short: L. Moura, A. Nakic, P. Östergård, A. Wassermann, C. Weiß, Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. date_created: 2024-02-27T15:44:41Z date_updated: 2024-02-27T15:48:12Z doi: 10.4230/DagRep.13.4.40 keyword: - automorphism groups - combinatorial algorithms - finite geometries - subspace designs language: - iso: eng page: 40-57 publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik series_title: Dagstuhl Reports status: public title: Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161) type: report user_id: '70420' volume: 13, Issue 4 year: '2023' ... --- _id: '33490' abstract: - lang: eng text: Algorithmic fairness in Information Systems (IS) is a concept that aims to mitigate systematic discrimination and bias in automated decision-making. However, previous research argued that different fairness criteria are often incompatible. In hiring, AI is used to assess and rank applicants according to their fit for vacant positions. However, various types of bias also exist for AI-based algorithms (e.g., using biased historical data). To reduce AI’s bias and thereby unfair treatment, we conducted a systematic literature review to identify suitable strategies for the context of hiring. We identified nine fundamental articles in this context and extracted four types of approaches to address unfairness in AI, namely pre-process, in-process, post-process, and feature selection. Based on our findings, we (a) derived a research agenda for future studies and (b) proposed strategies for practitioners who design and develop AIs for hiring purposes. author: - first_name: Jonas full_name: Rieskamp, Jonas id: '77643' last_name: Rieskamp - first_name: Lennart full_name: Hofeditz, Lennart last_name: Hofeditz - first_name: Milad full_name: Mirbabaie, Milad id: '88691' last_name: Mirbabaie - first_name: Stefan full_name: Stieglitz, Stefan last_name: Stieglitz citation: ama: 'Rieskamp J, Hofeditz L, Mirbabaie M, Stieglitz S. Approaches to Improve Fairness when Deploying AI-based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research. In: Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS). ; 2023.' apa: Rieskamp, J., Hofeditz, L., Mirbabaie, M., & Stieglitz, S. (2023). Approaches to Improve Fairness when Deploying AI-based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research. Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS). Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS). bibtex: '@inproceedings{Rieskamp_Hofeditz_Mirbabaie_Stieglitz_2023, title={Approaches to Improve Fairness when Deploying AI-based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research}, booktitle={Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS)}, author={Rieskamp, Jonas and Hofeditz, Lennart and Mirbabaie, Milad and Stieglitz, Stefan}, year={2023} }' chicago: Rieskamp, Jonas, Lennart Hofeditz, Milad Mirbabaie, and Stefan Stieglitz. “Approaches to Improve Fairness When Deploying AI-Based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research.” In Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS), 2023. ieee: J. Rieskamp, L. Hofeditz, M. Mirbabaie, and S. Stieglitz, “Approaches to Improve Fairness when Deploying AI-based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research,” presented at the Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS), 2023. mla: Rieskamp, Jonas, et al. “Approaches to Improve Fairness When Deploying AI-Based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research.” Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS), 2023. short: 'J. Rieskamp, L. Hofeditz, M. Mirbabaie, S. Stieglitz, in: Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS), 2023.' conference: end_date: 2023-01-06 name: Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS) start_date: 2023-01-03 date_created: 2022-09-27T12:39:12Z date_updated: 2023-02-06T14:39:51Z keyword: - fairness in AI - SLR - hiring - AI implementation - AI-based algorithms language: - iso: eng main_file_link: - url: https://hdl.handle.net/10125/102654 publication: Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS) status: public title: Approaches to Improve Fairness when Deploying AI-based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research type: conference user_id: '77643' year: '2023' ... --- _id: '48894' abstract: - lang: eng 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. author: - first_name: Adel full_name: Nikfarjam, Adel last_name: Nikfarjam - first_name: Aneta full_name: Neumann, Aneta last_name: Neumann - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: 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. Parallel Problem Solving from Nature (PPSN XVII). Lecture Notes in Computer Science. Springer International Publishing; 2022:237–249. doi:10.1007/978-3-031-14714-2_17' apa: Nikfarjam, A., Neumann, A., Bossek, J., & Neumann, F. (2022). Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem. In G. Rudolph, A. V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, & T. Tu\v sar (Eds.), Parallel Problem Solving from Nature (PPSN XVII) (pp. 237–249). Springer International Publishing. https://doi.org/10.1007/978-3-031-14714-2_17 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={10.1007/978-3-031-14714-2_17}, 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} }' chicago: 'Nikfarjam, Adel, Aneta Neumann, Jakob Bossek, and Frank Neumann. “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem.” In Parallel Problem Solving from Nature (PPSN XVII), 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. https://doi.org/10.1007/978-3-031-14714-2_17.' ieee: 'A. Nikfarjam, A. Neumann, J. Bossek, and F. Neumann, “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem,” in Parallel Problem Solving from Nature (PPSN XVII), 2022, pp. 237–249, doi: 10.1007/978-3-031-14714-2_17.' mla: Nikfarjam, Adel, et al. “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem.” Parallel Problem Solving from Nature (PPSN XVII), edited by Günter Rudolph et al., Springer International Publishing, 2022, pp. 237–249, doi:10.1007/978-3-031-14714-2_17. 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.' date_created: 2023-11-14T15:59:00Z date_updated: 2023-12-13T10:49:51Z department: - _id: '819' doi: 10.1007/978-3-031-14714-2_17 editor: - first_name: Günter full_name: Rudolph, Günter last_name: Rudolph - first_name: Anna V. full_name: Kononova, Anna V. last_name: Kononova - first_name: Hernán full_name: Aguirre, Hernán last_name: Aguirre - first_name: Pascal full_name: Kerschke, Pascal last_name: Kerschke - first_name: Gabriela full_name: Ochoa, Gabriela last_name: Ochoa - first_name: Tea full_name: Tu\v sar, Tea last_name: Tu\v sar extern: '1' keyword: - Co-evolutionary algorithms - Evolutionary diversity optimisation - Quality diversity - Traveling thief problem language: - iso: eng page: 237–249 place: Cham publication: Parallel Problem Solving from Nature (PPSN XVII) publication_identifier: isbn: - 978-3-031-14714-2 publication_status: published publisher: Springer International Publishing series_title: Lecture Notes in Computer Science status: public title: Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem type: conference user_id: '102979' year: '2022' ... --- _id: '22510' abstract: - lang: eng text: 'Over the past decades, the Gathering problem, which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O(nd) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i.e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art.' author: - first_name: Shouwei full_name: Li, Shouwei last_name: Li - first_name: Christine full_name: Markarian, Christine last_name: Markarian - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Pavel full_name: Podlipyan, Pavel last_name: Podlipyan citation: ama: Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. A continuous strategy for collisionless gathering. Theoretical Computer Science. 2021;852:41-60. doi:10.1016/j.tcs.2020.10.037 apa: Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan, P. (2021). A continuous strategy for collisionless gathering. Theoretical Computer Science, 852, 41–60. https://doi.org/10.1016/j.tcs.2020.10.037 bibtex: '@article{Li_Markarian_Meyer auf der Heide_Podlipyan_2021, title={A continuous strategy for collisionless gathering}, volume={852}, DOI={10.1016/j.tcs.2020.10.037}, journal={Theoretical Computer Science}, author={Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2021}, pages={41–60} }' chicago: 'Li, Shouwei, Christine Markarian, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “A Continuous Strategy for Collisionless Gathering.” Theoretical Computer Science 852 (2021): 41–60. https://doi.org/10.1016/j.tcs.2020.10.037.' ieee: S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan, “A continuous strategy for collisionless gathering,” Theoretical Computer Science, vol. 852, pp. 41–60, 2021. mla: Li, Shouwei, et al. “A Continuous Strategy for Collisionless Gathering.” Theoretical Computer Science, vol. 852, 2021, pp. 41–60, doi:10.1016/j.tcs.2020.10.037. short: S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, Theoretical Computer Science 852 (2021) 41–60. date_created: 2021-06-28T09:24:15Z date_updated: 2022-01-06T06:55:35Z department: - _id: '63' doi: 10.1016/j.tcs.2020.10.037 intvolume: ' 852' keyword: - Local algorithms - Distributed algorithms - Collisionless gathering - Mobile robots - Multiagent system language: - iso: eng page: 41-60 publication: Theoretical Computer Science publication_identifier: issn: - 0304-3975 publication_status: published status: public title: A continuous strategy for collisionless gathering type: journal_article user_id: '15415' volume: 852 year: '2021' ... --- _id: '22511' abstract: - lang: eng text: "In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O(n2) for gathering in two dimensions Euclidean space, and Θ(n) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i.e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this “collisionless property” of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the “collisionless property” holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center algorithms.\r\n" author: - first_name: Shouwei full_name: Li, Shouwei last_name: Li - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Pavel full_name: Podlipyan, Pavel last_name: Podlipyan citation: ama: Li S, Meyer auf der Heide F, Podlipyan P. The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots. Theoretical Computer Science. 2021;852:29-40. doi:10.1016/j.tcs.2020.11.009 apa: Li, S., Meyer auf der Heide, F., & Podlipyan, P. (2021). The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots. Theoretical Computer Science, 852, 29–40. https://doi.org/10.1016/j.tcs.2020.11.009 bibtex: '@article{Li_Meyer auf der Heide_Podlipyan_2021, title={The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots}, volume={852}, DOI={10.1016/j.tcs.2020.11.009}, journal={Theoretical Computer Science}, author={Li, Shouwei and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2021}, pages={29–40} }' chicago: 'Li, Shouwei, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “The Impact of the Gabriel Subgraph of the Visibility Graph on the Gathering of Mobile Autonomous Robots.” Theoretical Computer Science 852 (2021): 29–40. https://doi.org/10.1016/j.tcs.2020.11.009.' ieee: S. Li, F. Meyer auf der Heide, and P. Podlipyan, “The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots,” Theoretical Computer Science, vol. 852, pp. 29–40, 2021. mla: Li, Shouwei, et al. “The Impact of the Gabriel Subgraph of the Visibility Graph on the Gathering of Mobile Autonomous Robots.” Theoretical Computer Science, vol. 852, 2021, pp. 29–40, doi:10.1016/j.tcs.2020.11.009. short: S. Li, F. Meyer auf der Heide, P. Podlipyan, Theoretical Computer Science 852 (2021) 29–40. date_created: 2021-06-28T09:34:45Z date_updated: 2022-01-06T06:55:35Z department: - _id: '63' doi: 10.1016/j.tcs.2020.11.009 intvolume: ' 852' keyword: - Local algorithms - Distributed algorithms - Collisionless gathering - Mobile robots - Multiagent system language: - iso: eng page: 29-40 publication: Theoretical Computer Science publication_identifier: issn: - 0304-3975 publication_status: published status: public title: The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots type: journal_article user_id: '15415' volume: 852 year: '2021' ... --- _id: '46318' abstract: - lang: eng text: 'Multi-objective (MO) optimization, i.e., the simultaneous optimization of multiple conflicting objectives, is gaining more and more attention in various research areas, such as evolutionary computation, machine learning (e.g., (hyper-)parameter optimization), or logistics (e.g., vehicle routing). Many works in this domain mention the structural problem property of multimodality as a challenge from two classical perspectives: (1) finding all globally optimal solution sets, and (2) avoiding to get trapped in local optima. Interestingly, these streams seem to transfer many traditional concepts of single-objective (SO) optimization into claims, assumptions, or even terminology regarding the MO domain, but mostly neglect the understanding of the structural properties as well as the algorithmic search behavior on a problem’s landscape. However, some recent works counteract this trend, by investigating the fundamentals and characteristics of MO problems using new visualization techniques and gaining surprising insights. Using these visual insights, this work proposes a step towards a unified terminology to capture multimodality and locality in a broader way than it is usually done. This enables us to investigate current research activities in multimodal continuous MO optimization and to highlight new implications and promising research directions for the design of benchmark suites, the discovery of MO landscape features, the development of new MO (or even SO) optimization algorithms, and performance indicators. For all these topics, we provide a review of ideas and methods but also an outlook on future challenges, research potential and perspectives that result from recent developments.' author: - first_name: Christian full_name: Grimme, Christian last_name: Grimme - first_name: Pascal full_name: Kerschke, Pascal last_name: Kerschke - first_name: Pelin full_name: Aspar, Pelin last_name: Aspar - first_name: Heike full_name: Trautmann, Heike id: '100740' last_name: Trautmann orcid: 0000-0002-9788-8282 - first_name: Mike full_name: Preuss, Mike last_name: Preuss - first_name: André H. full_name: Deutz, André H. last_name: Deutz - first_name: Hao full_name: Wang, Hao last_name: Wang - first_name: Michael full_name: Emmerich, Michael last_name: Emmerich citation: ama: 'Grimme C, Kerschke P, Aspar P, et al. Peeking beyond peaks: Challenges and research potentials of continuous multimodal multi-objective optimization. Computers & Operations Research. 2021;136:105489. doi:https://doi.org/10.1016/j.cor.2021.105489' apa: 'Grimme, C., Kerschke, P., Aspar, P., Trautmann, H., Preuss, M., Deutz, A. H., Wang, H., & Emmerich, M. (2021). Peeking beyond peaks: Challenges and research potentials of continuous multimodal multi-objective optimization. Computers & Operations Research, 136, 105489. https://doi.org/10.1016/j.cor.2021.105489' bibtex: '@article{Grimme_Kerschke_Aspar_Trautmann_Preuss_Deutz_Wang_Emmerich_2021, title={Peeking beyond peaks: Challenges and research potentials of continuous multimodal multi-objective optimization}, volume={136}, DOI={https://doi.org/10.1016/j.cor.2021.105489}, journal={Computers & Operations Research}, author={Grimme, Christian and Kerschke, Pascal and Aspar, Pelin and Trautmann, Heike and Preuss, Mike and Deutz, André H. and Wang, Hao and Emmerich, Michael}, year={2021}, pages={105489} }' chicago: 'Grimme, Christian, Pascal Kerschke, Pelin Aspar, Heike Trautmann, Mike Preuss, André H. Deutz, Hao Wang, and Michael Emmerich. “Peeking beyond Peaks: Challenges and Research Potentials of Continuous Multimodal Multi-Objective Optimization.” Computers & Operations Research 136 (2021): 105489. https://doi.org/10.1016/j.cor.2021.105489.' ieee: 'C. Grimme et al., “Peeking beyond peaks: Challenges and research potentials of continuous multimodal multi-objective optimization,” Computers & Operations Research, vol. 136, p. 105489, 2021, doi: https://doi.org/10.1016/j.cor.2021.105489.' mla: 'Grimme, Christian, et al. “Peeking beyond Peaks: Challenges and Research Potentials of Continuous Multimodal Multi-Objective Optimization.” Computers & Operations Research, vol. 136, 2021, p. 105489, doi:https://doi.org/10.1016/j.cor.2021.105489.' short: C. Grimme, P. Kerschke, P. Aspar, H. Trautmann, M. Preuss, A.H. Deutz, H. Wang, M. Emmerich, Computers & Operations Research 136 (2021) 105489. date_created: 2023-08-04T07:28:34Z date_updated: 2023-10-16T12:58:42Z department: - _id: '34' - _id: '819' doi: https://doi.org/10.1016/j.cor.2021.105489 intvolume: ' 136' keyword: - Multimodal optimization - Multi-objective continuous optimization - Landscape analysis - Visualization - Benchmarking - Theory - Algorithms language: - iso: eng page: '105489' publication: Computers & Operations Research publication_identifier: issn: - 0305-0548 status: public title: 'Peeking beyond peaks: Challenges and research potentials of continuous multimodal multi-objective optimization' type: journal_article user_id: '15504' volume: 136 year: '2021' ... --- _id: '48853' 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. author: - 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 - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: ama: 'Bossek J, Neumann A, Neumann F. Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO ’21. Association for Computing Machinery; 2021:556–564. doi:10.1145/3449639.3459364' apa: Bossek, J., Neumann, A., & Neumann, F. (2021). Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms. Proceedings of the Genetic and Evolutionary Computation Conference, 556–564. https://doi.org/10.1145/3449639.3459364 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={10.1145/3449639.3459364}, 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} }' chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.” In Proceedings of the Genetic and Evolutionary Computation Conference, 556–564. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459364.' ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2021, pp. 556–564, doi: 10.1145/3449639.3459364.' mla: Bossek, Jakob, et al. “Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2021, pp. 556–564, doi:10.1145/3449639.3459364. 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.' date_created: 2023-11-14T15:58:54Z date_updated: 2023-12-13T10:45:22Z department: - _id: '819' doi: 10.1145/3449639.3459364 extern: '1' keyword: - evolutionary algorithms - evolutionary diversity optimization - knapsack problem - tailored operators language: - iso: eng page: 556–564 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-8350-9 publication_status: published publisher: Association for Computing Machinery series_title: GECCO ’21 status: public title: Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms type: conference user_id: '102979' year: '2021' ... --- _id: '48860' 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. author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: ama: 'Bossek J, Neumann F. Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:10.1145/3449639.3459363' apa: Bossek, J., & Neumann, F. (2021). Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem. Proceedings of the Genetic and Evolutionary Computation Conference, 198–206. https://doi.org/10.1145/3449639.3459363 bibtex: '@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO ’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem}, DOI={10.1145/3449639.3459363}, 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} }' chicago: 'Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem.” In Proceedings of the Genetic and Evolutionary Computation Conference, 198–206. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459363.' ieee: 'J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2021, pp. 198–206, doi: 10.1145/3449639.3459363.' mla: Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2021, pp. 198–206, doi:10.1145/3449639.3459363. 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.' date_created: 2023-11-14T15:58:55Z date_updated: 2023-12-13T10:45:37Z department: - _id: '819' doi: 10.1145/3449639.3459363 extern: '1' keyword: - evolutionary algorithms - evolutionary diversity optimization - minimum spanning tree - runtime analysis language: - iso: eng page: 198–206 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-8350-9 publication_status: published publisher: Association for Computing Machinery series_title: GECCO ’21 status: public title: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem type: conference user_id: '102979' year: '2021' ... --- _id: '48862' abstract: - lang: eng text: 'Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT {$\cup$} S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions 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.' author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Dirk full_name: Sudholt, Dirk last_name: Sudholt citation: ama: 'Bossek J, Sudholt D. Do Additional Optima Speed up Evolutionary Algorithms? In: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery; 2021:1–11.' apa: Bossek, J., & Sudholt, D. (2021). Do Additional Optima Speed up Evolutionary Algorithms? In Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (pp. 1–11). Association for Computing Machinery. 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} }' chicago: 'Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary Algorithms?” In Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 1–11. New York, NY, USA: Association for Computing Machinery, 2021.' ieee: 'J. Bossek and D. Sudholt, “Do Additional Optima Speed up Evolutionary Algorithms?,” in Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–11.' mla: Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary Algorithms?” Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 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.' date_created: 2023-11-14T15:58:55Z date_updated: 2023-12-13T10:45:31Z department: - _id: '819' extern: '1' keyword: - evolutionary algorithms - pseudo-boolean functions - runtime analysis - theory language: - iso: eng page: 1–11 place: New York, NY, USA publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms publication_identifier: isbn: - 978-1-4503-8352-3 publication_status: published publisher: Association for Computing Machinery status: public title: Do Additional Optima Speed up Evolutionary Algorithms? type: book_chapter user_id: '102979' year: '2021' ... --- _id: '48876' 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. 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 citation: ama: 'Bossek J, Wagner M. Generating Instances with Performance Differences for More than Just Two Algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO’21. Association for Computing Machinery; 2021:1423–1432. doi:10.1145/3449726.3463165' apa: Bossek, J., & Wagner, M. (2021). Generating Instances with Performance Differences for More than Just Two Algorithms. Proceedings of the Genetic and Evolutionary Computation Conference Companion, 1423–1432. https://doi.org/10.1145/3449726.3463165 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={10.1145/3449726.3463165}, 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} }' chicago: 'Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” In Proceedings of the Genetic and Evolutionary Computation Conference Companion, 1423–1432. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449726.3463165.' ieee: 'J. Bossek and M. Wagner, “Generating Instances with Performance Differences for More than Just Two Algorithms,” in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2021, pp. 1423–1432, doi: 10.1145/3449726.3463165.' mla: Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, 2021, pp. 1423–1432, doi:10.1145/3449726.3463165. 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.' date_created: 2023-11-14T15:58:57Z date_updated: 2023-12-13T10:47:41Z department: - _id: '819' doi: 10.1145/3449726.3463165 extern: '1' keyword: - evolutionary algorithms - evolving instances - fitness function - instance hardness - traveling thief problem (TTP) language: - iso: eng page: 1423–1432 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion publication_identifier: isbn: - 978-1-4503-8351-6 publisher: Association for Computing Machinery series_title: GECCO’21 status: public title: Generating Instances with Performance Differences for More than Just Two Algorithms type: conference user_id: '102979' year: '2021' ... --- _id: '48893' 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. author: - first_name: Adel full_name: Nikfarjam, Adel last_name: Nikfarjam - 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 - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO’21. Association for Computing Machinery; 2021:600–608. doi:10.1145/3449639.3459384' apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. Proceedings of the Genetic and Evolutionary Computation Conference, 600–608. https://doi.org/10.1145/3449639.3459384 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={10.1145/3449639.3459384}, 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} }' chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” In Proceedings of the Genetic and Evolutionary Computation Conference, 600–608. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459384.' ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2021, pp. 600–608, doi: 10.1145/3449639.3459384.' mla: Nikfarjam, Adel, et al. “Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2021, pp. 600–608, doi:10.1145/3449639.3459384. 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.' date_created: 2023-11-14T15:59:00Z date_updated: 2023-12-13T10:50:06Z department: - _id: '819' doi: 10.1145/3449639.3459384 extern: '1' keyword: - evolutionary algorithms - evolutionary diversity optimisation - high-order entropy - traveling salesperson problem language: - iso: eng page: 600–608 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-8350-9 publisher: Association for Computing Machinery series_title: GECCO’21 status: public title: Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem type: conference user_id: '102979' year: '2021' ... --- _id: '48891' 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. author: - first_name: Aneta full_name: Neumann, Aneta last_name: Neumann - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: ama: 'Neumann A, Bossek J, Neumann F. Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO’21. Association for Computing Machinery; 2021:261–269. doi:10.1145/3449639.3459385' apa: Neumann, A., Bossek, J., & Neumann, F. (2021). Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions. Proceedings of the Genetic and Evolutionary Computation Conference, 261–269. https://doi.org/10.1145/3449639.3459385 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={10.1145/3449639.3459385}, 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} }' chicago: 'Neumann, Aneta, Jakob Bossek, and Frank Neumann. “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.” In Proceedings of the Genetic and Evolutionary Computation Conference, 261–269. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459385.' ieee: 'A. Neumann, J. Bossek, and F. Neumann, “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2021, pp. 261–269, doi: 10.1145/3449639.3459385.' mla: Neumann, Aneta, et al. “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2021, pp. 261–269, doi:10.1145/3449639.3459385. 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.' date_created: 2023-11-14T15:58:59Z date_updated: 2023-12-13T10:49:25Z department: - _id: '819' doi: 10.1145/3449639.3459385 extern: '1' keyword: - evolutionary algorithms - evolutionary diversity optimisation - sub-modular functions language: - iso: eng page: 261–269 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-8350-9 publisher: Association for Computing Machinery series_title: GECCO’21 status: public title: Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions type: conference user_id: '102979' year: '2021' ... --- _id: '48892' 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. author: - first_name: Adel full_name: Nikfarjam, Adel last_name: Nikfarjam - 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 - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In: Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery; 2021:1–11.' apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms (pp. 1–11). Association for Computing Machinery. 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} }' 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 Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms, 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 Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms, New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–11.' mla: Nikfarjam, Adel, et al. “Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation.” Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms, 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.' date_created: 2023-11-14T15:59:00Z date_updated: 2023-12-13T10:49:59Z department: - _id: '819' extern: '1' keyword: - edge assembly crossover (EAX) - evolutionary algorithms - evolutionary diversity optimisation (EDO) - traveling salesperson problem (TSP) language: - iso: eng page: 1–11 place: New York, NY, USA publication: Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms publication_identifier: isbn: - 978-1-4503-8352-3 publisher: Association for Computing Machinery status: public title: Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation type: book_chapter user_id: '102979' year: '2021' ... --- _id: '48854' abstract: - lang: eng 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. author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Frank full_name: Neumann, Frank last_name: Neumann - first_name: Pan full_name: Peng, Pan last_name: Peng - first_name: Dirk full_name: Sudholt, Dirk last_name: Sudholt citation: ama: Bossek J, Neumann F, Peng P, Sudholt D. Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem. Algorithmica. 2021;83(10):3148–3179. doi:10.1007/s00453-021-00838-3 apa: Bossek, J., Neumann, F., Peng, P., & Sudholt, D. (2021). Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem. Algorithmica, 83(10), 3148–3179. https://doi.org/10.1007/s00453-021-00838-3 bibtex: '@article{Bossek_Neumann_Peng_Sudholt_2021, title={Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem}, volume={83}, DOI={10.1007/s00453-021-00838-3}, number={10}, journal={Algorithmica}, author={Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}, year={2021}, pages={3148–3179} }' chicago: 'Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.” Algorithmica 83, no. 10 (2021): 3148–3179. https://doi.org/10.1007/s00453-021-00838-3.' ieee: 'J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem,” Algorithmica, vol. 83, no. 10, pp. 3148–3179, 2021, doi: 10.1007/s00453-021-00838-3.' mla: Bossek, Jakob, et al. “Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.” Algorithmica, vol. 83, no. 10, 2021, pp. 3148–3179, doi:10.1007/s00453-021-00838-3. short: J. Bossek, F. Neumann, P. Peng, D. Sudholt, Algorithmica 83 (2021) 3148–3179. date_created: 2023-11-14T15:58:54Z date_updated: 2023-12-13T10:51:34Z department: - _id: '819' doi: 10.1007/s00453-021-00838-3 intvolume: ' 83' issue: '10' keyword: - Dynamic optimization - Evolutionary algorithms - Running time analysis language: - iso: eng page: 3148–3179 publication: Algorithmica publication_identifier: issn: - 0178-4617 status: public title: Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem type: journal_article user_id: '102979' volume: 83 year: '2021' ... --- _id: '48847' abstract: - lang: eng 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. author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Frank full_name: Neumann, Frank last_name: Neumann - first_name: Pan full_name: Peng, Pan last_name: Peng - first_name: Dirk full_name: Sudholt, Dirk last_name: Sudholt citation: ama: 'Bossek J, Neumann F, Peng P, Sudholt D. More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO ’20. Association for Computing Machinery; 2020:1277–1285. doi:10.1145/3377930.3390174' apa: Bossek, J., Neumann, F., Peng, P., & Sudholt, D. (2020). More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization. Proceedings of the Genetic and Evolutionary Computation Conference, 1277–1285. https://doi.org/10.1145/3377930.3390174 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={10.1145/3377930.3390174}, 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} }' chicago: 'Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.” In Proceedings of the Genetic and Evolutionary Computation Conference, 1277–1285. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390174.' ieee: 'J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2020, pp. 1277–1285, doi: 10.1145/3377930.3390174.' mla: Bossek, Jakob, et al. “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2020, pp. 1277–1285, doi:10.1145/3377930.3390174. 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.' date_created: 2023-11-14T15:58:53Z date_updated: 2023-12-13T10:43:41Z department: - _id: '819' doi: 10.1145/3377930.3390174 extern: '1' keyword: - dynamic optimization - evolutionary algorithms - running time analysis - theory language: - iso: eng page: 1277–1285 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-7128-5 publication_status: published publisher: Association for Computing Machinery series_title: GECCO ’20 status: public title: More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization type: conference user_id: '102979' year: '2020' ... --- _id: '48851' 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. author: - first_name: Jakob full_name: Bossek, Jakob id: '102979' last_name: Bossek orcid: 0000-0002-4121-4668 - first_name: Katrin full_name: Casel, Katrin last_name: Casel - first_name: Pascal full_name: Kerschke, Pascal last_name: Kerschke - first_name: Frank full_name: Neumann, Frank last_name: Neumann citation: ama: 'Bossek J, Casel K, Kerschke P, Neumann F. The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO ’20. Association for Computing Machinery; 2020:1286–1294. doi:10.1145/3377930.3390243' apa: 'Bossek, J., Casel, K., Kerschke, P., & Neumann, F. (2020). The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. Proceedings of the Genetic and Evolutionary Computation Conference, 1286–1294. https://doi.org/10.1145/3377930.3390243' 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={10.1145/3377930.3390243}, 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} }' chicago: 'Bossek, Jakob, Katrin Casel, Pascal Kerschke, and Frank Neumann. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” In Proceedings of the Genetic and Evolutionary Computation Conference, 1286–1294. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390243.' ieee: 'J. Bossek, K. Casel, P. Kerschke, and F. Neumann, “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2020, pp. 1286–1294, doi: 10.1145/3377930.3390243.' mla: 'Bossek, Jakob, et al. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2020, pp. 1286–1294, doi:10.1145/3377930.3390243.' 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.' date_created: 2023-11-14T15:58:53Z date_updated: 2023-12-13T10:43:33Z department: - _id: '819' doi: 10.1145/3377930.3390243 extern: '1' keyword: - dynamic optimization - evolutionary algorithms - running time analysis - theory language: - iso: eng page: 1286–1294 place: New York, NY, USA publication: Proceedings of the Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-7128-5 publication_status: published publisher: Association for Computing Machinery series_title: GECCO ’20 status: public title: 'The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics' type: conference user_id: '102979' year: '2020' ...