---
_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: Proceedings of the Genetic} and Evolutionary Computation
Conference. GECCO’23. Association for Computing Machinery; 2023:312–320. doi:10.1145/3583131.3590504'
apa: 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. Proceedings of the Genetic} and Evolutionary Computation
Conference, 312–320. https://doi.org/10.1145/3583131.3590504
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={10.1145/3583131.3590504}, 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 Proceedings of the
Genetic} and Evolutionary Computation Conference, 312–320. GECCO’23. New York,
NY, USA: Association for Computing Machinery, 2023. https://doi.org/10.1145/3583131.3590504.'
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 Proceedings of the Genetic} and Evolutionary Computation
Conference, 2023, pp. 312–320, doi: 10.1145/3583131.3590504.'
mla: Marrero, Alejandro, et al. “Generating Diverse and Discriminatory Knapsack
Instances by Searching for Novelty in Variable Dimensions of Feature-Space.” Proceedings
of the Genetic} and Evolutionary Computation Conference, Association for Computing
Machinery, 2023, pp. 312–320, doi:10.1145/3583131.3590504.
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'
...
---
_id: '48861'
abstract:
- lang: eng
text: Generating instances of different properties is key to algorithm selection
methods that differentiate between the performance of different solvers for a
given combinatorial optimization problem. A wide range of methods using evolutionary
computation techniques has been introduced in recent years. With this paper, we
contribute to this area of research by providing a new approach based on quality
diversity (QD) that is able to explore the whole feature space. QD algorithms
allow to create solutions of high quality within a given feature space by splitting
it up into boxes and improving solution quality within each box. We use our QD
approach for the generation of TSP instances to visualize and analyze the variety
of instances differentiating various TSP solvers and compare it to instances generated
by established approaches from the literature.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann F. Exploring the Feature Space of TSP Instances Using Quality
Diversity. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’22. Association for Computing Machinery; 2022:186–194. doi:10.1145/3512290.3528851'
apa: Bossek, J., & Neumann, F. (2022). Exploring the Feature Space of TSP Instances
Using Quality Diversity. Proceedings of the Genetic and Evolutionary Computation
Conference, 186–194. https://doi.org/10.1145/3512290.3528851
bibtex: '@inproceedings{Bossek_Neumann_2022, place={New York, NY, USA}, series={GECCO
’22}, title={Exploring the Feature Space of TSP Instances Using Quality Diversity},
DOI={10.1145/3512290.3528851},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2022}, pages={186–194}, collection={GECCO ’22} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP
Instances Using Quality Diversity.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 186–194. GECCO ’22. New York, NY, USA: Association
for Computing Machinery, 2022. https://doi.org/10.1145/3512290.3528851.'
ieee: 'J. Bossek and F. Neumann, “Exploring the Feature Space of TSP Instances Using
Quality Diversity,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2022, pp. 186–194, doi: 10.1145/3512290.3528851.'
mla: Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP Instances
Using Quality Diversity.” Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, 2022, pp. 186–194, doi:10.1145/3512290.3528851.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2022, pp.
186–194.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:56Z
department:
- _id: '819'
doi: 10.1145/3512290.3528851
extern: '1'
keyword:
- instance features
- instance generation
- quality diversity
- TSP
language:
- iso: eng
page: 186–194
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-9237-2
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’22
status: public
title: Exploring the Feature Space of TSP Instances Using Quality Diversity
type: conference
user_id: '102979'
year: '2022'
...