---
_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: <i>Proceedings
    of the Genetic and Evolutionary Computation Conference</i>. GECCO ’21. Association
    for Computing Machinery; 2021:556–564. doi:<a href="https://doi.org/10.1145/3449639.3459364">10.1145/3449639.3459364</a>'
  apa: Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Breeding Diverse Packings
    for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.
    <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 556–564.
    <a href="https://doi.org/10.1145/3449639.3459364">https://doi.org/10.1145/3449639.3459364</a>
  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={<a href="https://doi.org/10.1145/3449639.3459364">10.1145/3449639.3459364</a>},
    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 <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>,
    556–564. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021.
    <a href="https://doi.org/10.1145/3449639.3459364">https://doi.org/10.1145/3449639.3459364</a>.'
  ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Breeding Diverse Packings for the
    Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms,” in <i>Proceedings
    of the Genetic and Evolutionary Computation Conference</i>, 2021, pp. 556–564,
    doi: <a href="https://doi.org/10.1145/3449639.3459364">10.1145/3449639.3459364</a>.'
  mla: Bossek, Jakob, et al. “Breeding Diverse Packings for the Knapsack Problem by
    Means of Diversity-Tailored Evolutionary Algorithms.” <i>Proceedings of the Genetic
    and Evolutionary Computation Conference</i>, Association for Computing Machinery,
    2021, pp. 556–564, doi:<a href="https://doi.org/10.1145/3449639.3459364">10.1145/3449639.3459364</a>.
  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'
...