@inproceedings{48886,
  abstract     = {{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       = {{Marrero, Alejandro and Segredo, Eduardo and Hart, Emma and Bossek, Jakob and Neumann, Aneta}},
  booktitle    = {{Proceedings of the Genetic} and Evolutionary Computation Conference}},
  isbn         = {{9798400701191}},
  keywords     = {{evolutionary computation, instance generation, instance-space analysis, knapsack problem, novelty search}},
  pages        = {{312–320}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space}}},
  doi          = {{10.1145/3583131.3590504}},
  year         = {{2023}},
}

@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{48855,
  abstract     = {{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       = {{Bossek, Jakob and Neumann, Aneta and Neumann, Frank}},
  booktitle    = {{Learning and Intelligent Optimization}},
  isbn         = {{978-3-030-92120-0}},
  keywords     = {{Dynamic programming, Exact counting, Sampling, Zero-one knapsack problem}},
  pages        = {{40–54}},
  publisher    = {{Springer-Verlag}},
  title        = {{{Exact Counting and~Sampling of Optima for the Knapsack Problem}}},
  doi          = {{10.1007/978-3-030-92121-7_4}},
  year         = {{2021}},
}