@inproceedings{48853,
  abstract     = {{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       = {{Bossek, Jakob and Neumann, Aneta and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-8350-9}},
  keywords     = {{evolutionary algorithms, evolutionary diversity optimization, knapsack problem, tailored operators}},
  pages        = {{556–564}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms}}},
  doi          = {{10.1145/3449639.3459364}},
  year         = {{2021}},
}

@inproceedings{48860,
  abstract     = {{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       = {{Bossek, Jakob and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{978-1-4503-8350-9}},
  keywords     = {{evolutionary algorithms, evolutionary diversity optimization, minimum spanning tree, runtime analysis}},
  pages        = {{198–206}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem}}},
  doi          = {{10.1145/3449639.3459363}},
  year         = {{2021}},
}