Skip to main content

Research Repository

Advanced Search

Generating diverse and discriminatory knapsack instances by searching for novelty in variable dimensions of feature-space

Marrero, Alejandro; Segredo, Eduardo; Hart, Emma; Bossek, Jakob; Neumann, Aneta

Authors

Alejandro Marrero

Eduardo Segredo

Jakob Bossek

Aneta Neumann



Abstract

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%.

Citation

Marrero, A., Segredo, E., Hart, E., Bossek, J., & Neumann, A. (2023). Generating diverse and discriminatory knapsack instances by searching for novelty in variable dimensions of feature-space. In GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference (312-320). https://doi.org/10.1145/3583131.3590504

Conference Name GECCO 2023
Conference Location Lisbon, Portugal
Start Date Jul 15, 2023
End Date Apr 18, 2023
Acceptance Date Mar 31, 2023
Online Publication Date Jul 12, 2023
Publication Date 2023-07
Deposit Date Apr 26, 2023
Publicly Available Date Mar 28, 2024
Publisher Association for Computing Machinery (ACM)
Pages 312-320
Book Title GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference
ISBN 9798400701191
DOI https://doi.org/10.1145/3583131.3590504
Keywords Instance generation, instance-space analysis, knapsack problem, novelty search, evolutionary computation

Files

Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space (accepted version) (1.2 Mb)
PDF







You might also like



Downloadable Citations