---
_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: '48853'
abstract:
- lang: eng
text: In practise, it is often desirable to provide the decision-maker with a rich
set of diverse solutions of decent quality instead of just a single solution.
In this paper we study evolutionary diversity optimization for the knapsack problem
(KP). Our goal is to evolve a population of solutions that all have a profit of
at least (1 - {$ϵ$}) {$\cdot$} OPT, where OPT is the value of an optimal solution.
Furthermore, they should differ in structure with respect to an entropy-based
diversity measure. To this end we propose a simple ({$\mu$} + 1)-EA with initial
approximate solutions calculated by a well-known FPTAS for the KP. We investigate
the effect of different standard mutation operators and introduce biased mutation
and crossover which puts strong probability on flipping bits of low and/or high
frequency within the population. An experimental study on different instances
and settings shows that the proposed mutation operators in most cases perform
slightly inferior in the long term, but show strong benefits if the number of
function evaluations is severely limited.
author:
- 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
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. Breeding Diverse Packings for the Knapsack
Problem by Means of Diversity-Tailored Evolutionary Algorithms. In: Proceedings
of the Genetic and Evolutionary Computation Conference. GECCO ’21. Association
for Computing Machinery; 2021:556–564. doi:10.1145/3449639.3459364'
apa: Bossek, J., Neumann, A., & Neumann, F. (2021). Breeding Diverse Packings
for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.
Proceedings of the Genetic and Evolutionary Computation Conference, 556–564.
https://doi.org/10.1145/3449639.3459364
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2021, place={New York, NY, USA},
series={GECCO ’21}, title={Breeding Diverse Packings for the Knapsack Problem
by Means of Diversity-Tailored Evolutionary Algorithms}, DOI={10.1145/3449639.3459364},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Aneta and Neumann, Frank}, year={2021}, pages={556–564}, collection={GECCO ’21}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Breeding Diverse Packings
for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.”
In Proceedings of the Genetic and Evolutionary Computation Conference,
556–564. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021.
https://doi.org/10.1145/3449639.3459364.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Breeding Diverse Packings for the
Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2021, pp. 556–564,
doi: 10.1145/3449639.3459364.'
mla: Bossek, Jakob, et al. “Breeding Diverse Packings for the Knapsack Problem by
Means of Diversity-Tailored Evolutionary Algorithms.” Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
2021, pp. 556–564, doi:10.1145/3449639.3459364.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2021, pp. 556–564.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:45:22Z
department:
- _id: '819'
doi: 10.1145/3449639.3459364
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- knapsack problem
- tailored operators
language:
- iso: eng
page: 556–564
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’21
status: public
title: Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored
Evolutionary Algorithms
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48855'
abstract:
- lang: eng
text: Computing sets of high quality solutions has gained increasing interest in
recent years. In this paper, we investigate how to obtain sets of optimal solutions
for the classical knapsack problem. We present an algorithm to count exactly the
number of optima to a zero-one knapsack problem instance. In addition, we show
how to efficiently sample uniformly at random from the set of all global optima.
In our experimental study, we investigate how the number of optima develops for
classical random benchmark instances dependent on their generator parameters.
We find that the number of global optima can increase exponentially for practically
relevant classes of instances with correlated weights and profits which poses
a justification for the considered exact counting problem.
author:
- 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
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. Exact Counting and~Sampling of Optima for
the Knapsack Problem. In: Learning and Intelligent Optimization. Springer-Verlag;
2021:40–54. doi:10.1007/978-3-030-92121-7_4'
apa: Bossek, J., Neumann, A., & Neumann, F. (2021). Exact Counting and~Sampling
of Optima for the Knapsack Problem. Learning and Intelligent Optimization,
40–54. https://doi.org/10.1007/978-3-030-92121-7_4
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2021, place={Berlin, Heidelberg},
title={Exact Counting and~Sampling of Optima for the Knapsack Problem}, DOI={10.1007/978-3-030-92121-7_4},
booktitle={Learning and Intelligent Optimization}, publisher={Springer-Verlag},
author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={40–54}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Exact Counting And~Sampling
of Optima for the Knapsack Problem.” In Learning and Intelligent Optimization,
40–54. Berlin, Heidelberg: Springer-Verlag, 2021. https://doi.org/10.1007/978-3-030-92121-7_4.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Exact Counting and~Sampling of Optima
for the Knapsack Problem,” in Learning and Intelligent Optimization, 2021,
pp. 40–54, doi: 10.1007/978-3-030-92121-7_4.'
mla: Bossek, Jakob, et al. “Exact Counting And~Sampling of Optima for the Knapsack
Problem.” Learning and Intelligent Optimization, Springer-Verlag, 2021,
pp. 40–54, doi:10.1007/978-3-030-92121-7_4.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization,
Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:45:14Z
department:
- _id: '819'
doi: 10.1007/978-3-030-92121-7_4
extern: '1'
keyword:
- Dynamic programming
- Exact counting
- Sampling
- Zero-one knapsack problem
language:
- iso: eng
page: 40–54
place: Berlin, Heidelberg
publication: Learning and Intelligent Optimization
publication_identifier:
isbn:
- 978-3-030-92120-0
publication_status: published
publisher: Springer-Verlag
status: public
title: Exact Counting and~Sampling of Optima for the Knapsack Problem
type: conference
user_id: '102979'
year: '2021'
...