--- _id: '48872' abstract: - lang: eng text: Quality diversity (QD) is a branch of evolutionary computation that gained increasing interest in recent years. The Map-Elites QD approach defines a feature space, i.e., a partition of the search space, and stores the best solution for each cell of this space. We study a simple QD algorithm in the context of pseudo-Boolean optimisation on the "number of ones" feature space, where the ith cell stores the best solution amongst those with a number of ones in [(i - 1)k, ik - 1]. Here k is a granularity parameter 1 {$\leq$} k {$\leq$} n+1. We give a tight bound on the expected time until all cells are covered for arbitrary fitness functions and for all k and analyse the expected optimisation time of QD on OneMax and other problems whose structure aligns favourably with the feature space. On combinatorial problems we show that QD finds a (1 - 1/e)-approximation when maximising any monotone sub-modular function with a single uniform cardinality constraint efficiently. Defining the feature space as the number of connected components of a connected graph, we show that QD finds a minimum spanning tree in expected polynomial 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. Runtime Analysis of Quality Diversity Algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO’23. Association for Computing Machinery; 2023:1546–1554. doi:10.1145/3583131.3590383' apa: Bossek, J., & Sudholt, D. (2023). Runtime Analysis of Quality Diversity Algorithms. Proceedings of the Genetic and Evolutionary Computation Conference, 1546–1554. https://doi.org/10.1145/3583131.3590383 bibtex: '@inproceedings{Bossek_Sudholt_2023, place={New York, NY, USA}, series={GECCO’23}, title={Runtime Analysis of Quality Diversity Algorithms}, DOI={10.1145/3583131.3590383}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2023}, pages={1546–1554}, collection={GECCO’23} }' chicago: 'Bossek, Jakob, and Dirk Sudholt. “Runtime Analysis of Quality Diversity Algorithms.” In Proceedings of the Genetic and Evolutionary Computation Conference, 1546–1554. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023. https://doi.org/10.1145/3583131.3590383.' ieee: 'J. Bossek and D. Sudholt, “Runtime Analysis of Quality Diversity Algorithms,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2023, pp. 1546–1554, doi: 10.1145/3583131.3590383.' mla: Bossek, Jakob, and Dirk Sudholt. “Runtime Analysis of Quality Diversity Algorithms.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2023, pp. 1546–1554, doi:10.1145/3583131.3590383. short: 'J. Bossek, D. Sudholt, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2023, pp. 1546–1554.' date_created: 2023-11-14T15:58:57Z date_updated: 2023-12-13T10:48:26Z department: - _id: '819' doi: 10.1145/3583131.3590383 extern: '1' keyword: - quality diversity - runtime analysis language: - iso: eng page: 1546–1554 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: Runtime Analysis of Quality Diversity Algorithms 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: '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: '48895' abstract: - lang: eng 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. author: - first_name: Vahid full_name: Roostapour, Vahid last_name: Roostapour - 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: 'Roostapour V, Bossek J, Neumann F. Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference. {GECCO} ’20. Association for Computing Machinery; 2020:551–559. doi:10.1145/3377930.3390168' apa: Roostapour, V., Bossek, J., & Neumann, F. (2020). Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. Proceedings of the 2020 Genetic and Evolutionary Computation Conference, 551–559. https://doi.org/10.1145/3377930.3390168 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={10.1145/3377930.3390168}, 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} }' 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 Proceedings of the 2020 Genetic and Evolutionary Computation Conference, 551–559. {GECCO} ’20. New York, NY, USA: Association for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390168.' 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 Proceedings of the 2020 Genetic and Evolutionary Computation Conference, 2020, pp. 551–559, doi: 10.1145/3377930.3390168.' mla: Roostapour, Vahid, et al. “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2020, pp. 551–559, doi:10.1145/3377930.3390168. 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.' date_created: 2023-11-14T15:59:00Z date_updated: 2023-12-13T10:49:38Z department: - _id: '819' doi: 10.1145/3377930.3390168 extern: '1' keyword: - biased mutation - evolutionary algorithms - minimum spanning tree problem - runtime analysis language: - iso: eng page: 551–559 place: New York, NY, USA publication: Proceedings of the 2020 Genetic and Evolutionary Computation Conference publication_identifier: isbn: - 978-1-4503-7128-5 publisher: Association for Computing Machinery series_title: '{GECCO} ’20' status: public title: Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem type: conference user_id: '102979' year: '2020' ... --- _id: '48870' abstract: - lang: eng text: The edge coloring problem asks for an assignment of colors to edges of a graph such that no two incident edges share the same color and the number of colors is minimized. It is known that all graphs with maximum degree {$\Delta$} can be colored with {$\Delta$} or {$\Delta$} + 1 colors, but it is NP-hard to determine whether {$\Delta$} colors are sufficient. We present the first runtime analysis of evolutionary algorithms (EAs) for the edge coloring problem. Simple EAs such as RLS and (1+1) EA efficiently find (2{$\Delta$} - 1)-colorings on arbitrary graphs and optimal colorings for even and odd cycles, paths, star graphs and arbitrary trees. A partial analysis for toroids also suggests efficient runtimes in bipartite graphs with many cycles. Experiments support these findings and investigate additional graph classes such as hypercubes, complete graphs and complete bipartite graphs. Theoretical and experimental results suggest that simple EAs find optimal colorings for all these graph classes in expected time O({$\Delta\mathscrl$}2m log m), where m is the number of edges and {$\mathscrl$} is the length of the longest simple path in the graph. 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. Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem. In: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. FOGA ’19. Association for Computing Machinery; 2019:102–115. doi:10.1145/3299904.3340311' apa: Bossek, J., & Sudholt, D. (2019). Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem. Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 102–115. https://doi.org/10.1145/3299904.3340311 bibtex: '@inproceedings{Bossek_Sudholt_2019, place={New York, NY, USA}, series={FOGA ’19}, title={Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem}, DOI={10.1145/3299904.3340311}, booktitle={Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2019}, pages={102–115}, collection={FOGA ’19} }' chicago: 'Bossek, Jakob, and Dirk Sudholt. “Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem.” In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 102–115. FOGA ’19. New York, NY, USA: Association for Computing Machinery, 2019. https://doi.org/10.1145/3299904.3340311.' ieee: 'J. Bossek and D. Sudholt, “Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem,” in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2019, pp. 102–115, doi: 10.1145/3299904.3340311.' mla: Bossek, Jakob, and Dirk Sudholt. “Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem.” Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, 2019, pp. 102–115, doi:10.1145/3299904.3340311. short: 'J. Bossek, D. Sudholt, in: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2019, pp. 102–115.' date_created: 2023-11-14T15:58:56Z date_updated: 2023-12-13T10:46:12Z department: - _id: '819' doi: 10.1145/3299904.3340311 extern: '1' keyword: - edge coloring problem - runtime analysis language: - iso: eng page: 102–115 place: New York, NY, USA publication: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms publication_identifier: isbn: - 978-1-4503-6254-2 publication_status: published publisher: Association for Computing Machinery series_title: FOGA ’19 status: public title: Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem type: conference user_id: '102979' year: '2019' ...