Alejandro Marrero
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). 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
Computational Thinking and User Interfaces: A Systematic Review
(2022)
Journal Article
How do young students get enthusiastic about computational thinking activities?
(2021)
Conference Proceeding
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search