conference paper Alejandro Marrero author Eduardo Segredo author Emma Hart author Jakob Bossek author 1029790000-0002-4121-4668 Aneta Neumann author 819 department 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%. Association for Computing Machinery2023 eng evolutionary computationinstance generationinstance-space analysisknapsack problemnovelty search 979840070119110.1145/3583131.3590504 312–320 yes 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>. @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} } 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> 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>. 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> 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>. 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. 488862023-11-14T15:58:59Z2023-12-13T10:49:32Z