---
_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: '48860'
abstract:
- lang: eng
text: In the area of evolutionary computation the calculation of diverse sets of
high-quality solutions to a given optimization problem has gained momentum in
recent years under the term evolutionary diversity optimization. Theoretical insights
into the working principles of baseline evolutionary algorithms for diversity
optimization are still rare. In this paper we study the well-known Minimum Spanning
Tree problem (MST) in the context of diversity optimization where population diversity
is measured by the sum of pairwise edge overlaps. Theoretical results provide
insights into the fitness landscape of the MST diversity optimization problem
pointing out that even for a population of {$\mu$} = 2 fitness plateaus (of constant
length) can be reached, but nevertheless diverse sets can be calculated in polynomial
time. We supplement our theoretical results with a series of experiments for the
unconstrained and constraint case where all solutions need to fulfill a minimal
quality threshold. Our results show that a simple ({$\mu$} + 1)-EA can effectively
compute a diversified population of spanning trees of high quality.
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. Evolutionary Diversity Optimization and the Minimum Spanning
Tree Problem. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:10.1145/3449639.3459363'
apa: Bossek, J., & Neumann, F. (2021). Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem. Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. https://doi.org/10.1145/3449639.3459363
bibtex: '@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO
’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem}, DOI={10.1145/3449639.3459363},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2021}, pages={198–206}, collection={GECCO ’21} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization
and the Minimum Spanning Tree Problem.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. GECCO ’21. New York, NY, USA: Association
for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459363.'
ieee: 'J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum
Spanning Tree Problem,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2021, pp. 198–206, doi: 10.1145/3449639.3459363.'
mla: Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 198–206,
doi:10.1145/3449639.3459363.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp.
198–206.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:37Z
department:
- _id: '819'
doi: 10.1145/3449639.3459363
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- minimum spanning tree
- runtime analysis
language:
- iso: eng
page: 198–206
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: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
type: conference
user_id: '102979'
year: '2021'
...