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

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, July). Generating diverse and discriminatory knapsack instances by searching for novelty in variable dimensions of feature-space. Presented at GECCO 2023, Lisbon, Portugal

• Presentation Conference Type: Conference Paper (published)
• Conference Name: GECCO 2023
• 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: Apr 26, 2023
• 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