---
_id: '48886'
abstract:
- lang: eng
  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%.'
author:
- first_name: Alejandro
  full_name: Marrero, Alejandro
  last_name: Marrero
- first_name: Eduardo
  full_name: Segredo, Eduardo
  last_name: Segredo
- first_name: Emma
  full_name: Hart, Emma
  last_name: Hart
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Aneta
  full_name: Neumann, Aneta
  last_name: Neumann
citation:
  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>'
  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>
  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} }'
  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>.'
  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>.'
  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>.
  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.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:49:32Z
department:
- _id: '819'
doi: 10.1145/3583131.3590504
extern: '1'
keyword:
- evolutionary computation
- instance generation
- instance-space analysis
- knapsack problem
- novelty search
language:
- iso: eng
page: 312–320
place: New York, NY, USA
publication: Proceedings of the Genetic} and Evolutionary Computation Conference
publication_identifier:
  isbn:
  - '9798400701191'
publisher: Association for Computing Machinery
series_title: GECCO’23
status: public
title: Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty
  in Variable Dimensions of Feature-Space
type: conference
user_id: '102979'
year: '2023'
...