[{"publication_identifier":{"isbn":["9798400701191"]},"place":"New York, NY, USA","year":"2023","citation":{"ieee":"J. Bossek and D. Sudholt, “Runtime Analysis of Quality Diversity Algorithms,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2023, pp. 1546–1554, doi: <a href=\"https://doi.org/10.1145/3583131.3590383\">10.1145/3583131.3590383</a>.","chicago":"Bossek, Jakob, and Dirk Sudholt. “Runtime Analysis of Quality Diversity Algorithms.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1546–1554. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3583131.3590383\">https://doi.org/10.1145/3583131.3590383</a>.","ama":"Bossek J, Sudholt D. Runtime Analysis of Quality Diversity Algorithms. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’23. Association for Computing Machinery; 2023:1546–1554. doi:<a href=\"https://doi.org/10.1145/3583131.3590383\">10.1145/3583131.3590383</a>","apa":"Bossek, J., &#38; Sudholt, D. (2023). Runtime Analysis of Quality Diversity Algorithms. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1546–1554. <a href=\"https://doi.org/10.1145/3583131.3590383\">https://doi.org/10.1145/3583131.3590383</a>","mla":"Bossek, Jakob, and Dirk Sudholt. “Runtime Analysis of Quality Diversity Algorithms.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2023, pp. 1546–1554, doi:<a href=\"https://doi.org/10.1145/3583131.3590383\">10.1145/3583131.3590383</a>.","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.","bibtex":"@inproceedings{Bossek_Sudholt_2023, place={New York, NY, USA}, series={GECCO’23}, title={Runtime Analysis of Quality Diversity Algorithms}, DOI={<a href=\"https://doi.org/10.1145/3583131.3590383\">10.1145/3583131.3590383</a>}, 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} }"},"page":"1546–1554","publisher":"Association for Computing Machinery","date_updated":"2023-12-13T10:48:26Z","author":[{"orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"full_name":"Sudholt, Dirk","last_name":"Sudholt","first_name":"Dirk"}],"date_created":"2023-11-14T15:58:57Z","title":"Runtime Analysis of Quality Diversity Algorithms","doi":"10.1145/3583131.3590383","type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"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.","lang":"eng"}],"status":"public","_id":"48872","series_title":"GECCO’23","user_id":"102979","department":[{"_id":"819"}],"keyword":["quality diversity","runtime analysis"],"extern":"1","language":[{"iso":"eng"}]},{"publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:55Z","title":"Exploring the Feature Space of TSP Instances Using Quality Diversity","year":"2022","keyword":["instance features","instance generation","quality diversity","TSP"],"language":[{"iso":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"lang":"eng","text":"Generating instances of different properties is key to algorithm selection methods that differentiate between the performance of different solvers for a given combinatorial optimization problem. A wide range of methods using evolutionary computation techniques has been introduced in recent years. With this paper, we contribute to this area of research by providing a new approach based on quality diversity (QD) that is able to explore the whole feature space. QD algorithms allow to create solutions of high quality within a given feature space by splitting it up into boxes and improving solution quality within each box. We use our QD approach for the generation of TSP instances to visualize and analyze the variety of instances differentiating various TSP solvers and compare it to instances generated by established approaches from the literature."}],"date_updated":"2023-12-13T10:45:56Z","author":[{"id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"doi":"10.1145/3512290.3528851","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-9237-2"]},"place":"New York, NY, USA","citation":{"ama":"Bossek J, Neumann F. Exploring the Feature Space of TSP Instances Using Quality Diversity. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’22. Association for Computing Machinery; 2022:186–194. doi:<a href=\"https://doi.org/10.1145/3512290.3528851\">10.1145/3512290.3528851</a>","chicago":"Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP Instances Using Quality Diversity.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 186–194. GECCO ’22. New York, NY, USA: Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3512290.3528851\">https://doi.org/10.1145/3512290.3528851</a>.","ieee":"J. Bossek and F. Neumann, “Exploring the Feature Space of TSP Instances Using Quality Diversity,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2022, pp. 186–194, doi: <a href=\"https://doi.org/10.1145/3512290.3528851\">10.1145/3512290.3528851</a>.","apa":"Bossek, J., &#38; Neumann, F. (2022). Exploring the Feature Space of TSP Instances Using Quality Diversity. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 186–194. <a href=\"https://doi.org/10.1145/3512290.3528851\">https://doi.org/10.1145/3512290.3528851</a>","mla":"Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP Instances Using Quality Diversity.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2022, pp. 186–194, doi:<a href=\"https://doi.org/10.1145/3512290.3528851\">10.1145/3512290.3528851</a>.","short":"J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2022, pp. 186–194.","bibtex":"@inproceedings{Bossek_Neumann_2022, place={New York, NY, USA}, series={GECCO ’22}, title={Exploring the Feature Space of TSP Instances Using Quality Diversity}, DOI={<a href=\"https://doi.org/10.1145/3512290.3528851\">10.1145/3512290.3528851</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann, Frank}, year={2022}, pages={186–194}, collection={GECCO ’22} }"},"page":"186–194","_id":"48861","user_id":"102979","series_title":"GECCO ’22","department":[{"_id":"819"}],"extern":"1","type":"conference","status":"public"},{"keyword":["Co-evolutionary algorithms","Evolutionary diversity optimisation","Quality diversity","Traveling thief problem"],"language":[{"iso":"eng"}],"abstract":[{"text":"Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. The results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the literature.","lang":"eng"}],"publication":"Parallel Problem Solving from Nature (PPSN XVII)","title":"Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem","publisher":"Springer International Publishing","date_created":"2023-11-14T15:59:00Z","year":"2022","extern":"1","_id":"48894","department":[{"_id":"819"}],"user_id":"102979","series_title":"Lecture Notes in Computer Science","editor":[{"last_name":"Rudolph","full_name":"Rudolph, Günter","first_name":"Günter"},{"first_name":"Anna V.","last_name":"Kononova","full_name":"Kononova, Anna V."},{"first_name":"Hernán","last_name":"Aguirre","full_name":"Aguirre, Hernán"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"},{"first_name":"Gabriela","full_name":"Ochoa, Gabriela","last_name":"Ochoa"},{"last_name":"Tu\\v sar","full_name":"Tu\\v sar, Tea","first_name":"Tea"}],"status":"public","type":"conference","doi":"10.1007/978-3-031-14714-2_17","date_updated":"2023-12-13T10:49:51Z","author":[{"last_name":"Nikfarjam","full_name":"Nikfarjam, Adel","first_name":"Adel"},{"first_name":"Aneta","full_name":"Neumann, Aneta","last_name":"Neumann"},{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"last_name":"Neumann","full_name":"Neumann, Frank","first_name":"Frank"}],"place":"Cham","page":"237–249","citation":{"apa":"Nikfarjam, A., Neumann, A., Bossek, J., &#38; Neumann, F. (2022). Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem. In G. Rudolph, A. V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, &#38; T. Tu\\v sar (Eds.), <i>Parallel Problem Solving from Nature (PPSN XVII)</i> (pp. 237–249). Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">https://doi.org/10.1007/978-3-031-14714-2_17</a>","short":"A. Nikfarjam, A. Neumann, J. Bossek, F. Neumann, in: G. Rudolph, A.V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, T. Tu\\v sar (Eds.), Parallel Problem Solving from Nature (PPSN XVII), Springer International Publishing, Cham, 2022, pp. 237–249.","bibtex":"@inproceedings{Nikfarjam_Neumann_Bossek_Neumann_2022, place={Cham}, series={Lecture Notes in Computer Science}, title={Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem}, DOI={<a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>}, booktitle={Parallel Problem Solving from Nature (PPSN XVII)}, publisher={Springer International Publishing}, author={Nikfarjam, Adel and Neumann, Aneta and Bossek, Jakob and Neumann, Frank}, editor={Rudolph, Günter and Kononova, Anna V. and Aguirre, Hernán and Kerschke, Pascal and Ochoa, Gabriela and Tu\\v sar, Tea}, year={2022}, pages={237–249}, collection={Lecture Notes in Computer Science} }","mla":"Nikfarjam, Adel, et al. “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem.” <i>Parallel Problem Solving from Nature (PPSN XVII)</i>, edited by Günter Rudolph et al., Springer International Publishing, 2022, pp. 237–249, doi:<a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>.","chicago":"Nikfarjam, Adel, Aneta Neumann, Jakob Bossek, and Frank Neumann. “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem.” In <i>Parallel Problem Solving from Nature (PPSN XVII)</i>, edited by Günter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, and Tea Tu\\v sar, 237–249. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2022. <a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">https://doi.org/10.1007/978-3-031-14714-2_17</a>.","ieee":"A. Nikfarjam, A. Neumann, J. Bossek, and F. Neumann, “Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem,” in <i>Parallel Problem Solving from Nature (PPSN XVII)</i>, 2022, pp. 237–249, doi: <a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>.","ama":"Nikfarjam A, Neumann A, Bossek J, Neumann F. Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem. In: Rudolph G, Kononova AV, Aguirre H, Kerschke P, Ochoa G, Tu\\v sar T, eds. <i>Parallel Problem Solving from Nature (PPSN XVII)</i>. Lecture Notes in Computer Science. Springer International Publishing; 2022:237–249. doi:<a href=\"https://doi.org/10.1007/978-3-031-14714-2_17\">10.1007/978-3-031-14714-2_17</a>"},"publication_identifier":{"isbn":["978-3-031-14714-2"]},"publication_status":"published"}]