[{"abstract":[{"text":"Generating new instances via evolutionary methods is commonly used to create new benchmarking data-sets, with a focus on attempting to cover an instance-space as completely as possible. Recent approaches have exploited Quality-Diversity methods to evolve sets of instances that are both diverse and discriminatory with respect to a portfolio of solvers, but these methods can be challenging when attempting to find diversity in a high-dimensional feature-space. We address this issue by training a model based on Principal Component Analysis on existing instances to create a low-dimension projection of the high-dimension feature-vectors, and then apply Novelty Search directly in the new low-dimension space. We conduct experiments to evolve diverse and discriminatory instances of Knapsack Problems, comparing the use of Novelty Search in the original feature-space to using Novelty Search in a low-dimensional projection, and repeat over a given set of dimensions. We find that the methods are complementary: if treated as an ensemble, they collectively provide increased coverage of the space. Specifically, searching for novelty in a low-dimension space contributes 56% of the filled regions of the space, while searching directly in the feature-space covers the remaining 44%.","lang":"eng"}],"extern":"1","publication":"Proceedings of the Genetic} and Evolutionary Computation Conference","department":[{"_id":"819"}],"keyword":["evolutionary computation","instance generation","instance-space analysis","knapsack problem","novelty search"],"type":"conference","date_created":"2023-11-14T15:58:59Z","date_updated":"2023-12-13T10:49:32Z","publication_identifier":{"isbn":["9798400701191"]},"author":[{"last_name":"Marrero","first_name":"Alejandro","full_name":"Marrero, Alejandro"},{"full_name":"Segredo, Eduardo","last_name":"Segredo","first_name":"Eduardo"},{"first_name":"Emma","last_name":"Hart","full_name":"Hart, Emma"},{"id":"102979","orcid":"0000-0002-4121-4668","first_name":"Jakob","last_name":"Bossek","full_name":"Bossek, Jakob"},{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"}],"title":"Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space","year":"2023","doi":"10.1145/3583131.3590504","series_title":"GECCO’23","language":[{"iso":"eng"}],"citation":{"bibtex":"@inproceedings{Marrero_Segredo_Hart_Bossek_Neumann_2023, place={New York, NY, USA}, series={GECCO’23}, title={Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space}, DOI={<a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>}, booktitle={Proceedings of the Genetic} and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Marrero, Alejandro and Segredo, Eduardo and Hart, Emma and Bossek, Jakob and Neumann, Aneta}, year={2023}, pages={312–320}, collection={GECCO’23} }","ama":"Marrero A, Segredo E, Hart E, Bossek J, Neumann A. Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space. In: <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>. GECCO’23. Association for Computing Machinery; 2023:312–320. doi:<a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>","mla":"Marrero, Alejandro, et al. “Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space.” <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2023, pp. 312–320, doi:<a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>.","chicago":"Marrero, Alejandro, Eduardo Segredo, Emma Hart, Jakob Bossek, and Aneta Neumann. “Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space.” In <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, 312–320. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3583131.3590504\">https://doi.org/10.1145/3583131.3590504</a>.","short":"A. Marrero, E. Segredo, E. Hart, J. Bossek, A. Neumann, in: Proceedings of the Genetic} and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2023, pp. 312–320.","ieee":"A. Marrero, E. Segredo, E. Hart, J. Bossek, and A. Neumann, “Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space,” in <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, 2023, pp. 312–320, doi: <a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>.","apa":"Marrero, A., Segredo, E., Hart, E., Bossek, J., &#38; Neumann, A. (2023). Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space. <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, 312–320. <a href=\"https://doi.org/10.1145/3583131.3590504\">https://doi.org/10.1145/3583131.3590504</a>"},"place":"New York, NY, USA","status":"public","user_id":"102979","_id":"48886","publisher":"Association for Computing Machinery","page":"312–320"},{"publication_identifier":{"isbn":["978-1-4503-9237-2"]},"author":[{"id":"102979","first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob"},{"full_name":"Neumann, Frank","first_name":"Frank","last_name":"Neumann"}],"title":"Exploring the Feature Space of TSP Instances Using Quality Diversity","year":"2022","date_updated":"2023-12-13T10:45:56Z","publication_status":"published","language":[{"iso":"eng"}],"series_title":"GECCO ’22","doi":"10.1145/3512290.3528851","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."}],"extern":"1","date_created":"2023-11-14T15:58:55Z","department":[{"_id":"819"}],"keyword":["instance features","instance generation","quality diversity","TSP"],"type":"conference","status":"public","publisher":"Association for Computing Machinery","_id":"48861","page":"186–194","user_id":"102979","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>","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} }","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>.","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>.","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.","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>","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>."},"place":"New York, NY, USA"}]