[{"status":"public","type":"conference","extern":"1","series_title":"GECCO’23","user_id":"102979","department":[{"_id":"819"}],"_id":"48886","citation":{"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 <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, 2023, pp. 312–320, doi: <a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>.","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 <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, 312–320. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3583131.3590504\">https://doi.org/10.1145/3583131.3590504</a>.","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: <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>. GECCO’23. Association for Computing Machinery; 2023:312–320. doi:<a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>","apa":"Marrero, A., Segredo, E., Hart, E., Bossek, J., &#38; Neumann, A. (2023). Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space. <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, 312–320. <a href=\"https://doi.org/10.1145/3583131.3590504\">https://doi.org/10.1145/3583131.3590504</a>","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.","mla":"Marrero, Alejandro, et al. “Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space.” <i>Proceedings of the Genetic} and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2023, pp. 312–320, doi:<a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>.","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={<a href=\"https://doi.org/10.1145/3583131.3590504\">10.1145/3583131.3590504</a>}, 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} }"},"page":"312–320","place":"New York, NY, USA","publication_identifier":{"isbn":["9798400701191"]},"doi":"10.1145/3583131.3590504","author":[{"last_name":"Marrero","full_name":"Marrero, Alejandro","first_name":"Alejandro"},{"last_name":"Segredo","full_name":"Segredo, Eduardo","first_name":"Eduardo"},{"full_name":"Hart, Emma","last_name":"Hart","first_name":"Emma"},{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"}],"date_updated":"2023-12-13T10:49:32Z","abstract":[{"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%.","lang":"eng"}],"publication":"Proceedings of the Genetic} and Evolutionary Computation Conference","language":[{"iso":"eng"}],"keyword":["evolutionary computation","instance generation","instance-space analysis","knapsack problem","novelty search"],"year":"2023","title":"Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space","date_created":"2023-11-14T15:58:59Z","publisher":"Association for Computing Machinery"},{"year":"2021","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:54Z","title":"Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","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."}],"keyword":["evolutionary algorithms","evolutionary diversity optimization","knapsack problem","tailored operators"],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-1-4503-8350-9"]},"publication_status":"published","place":"New York, NY, USA","page":"556–564","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>","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>.","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>","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.","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} }"},"date_updated":"2023-12-13T10:45:22Z","author":[{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"last_name":"Neumann","full_name":"Neumann, Aneta","first_name":"Aneta"},{"last_name":"Neumann","full_name":"Neumann, Frank","first_name":"Frank"}],"doi":"10.1145/3449639.3459364","type":"conference","status":"public","_id":"48853","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO ’21","extern":"1"},{"date_created":"2023-11-14T15:58:54Z","publisher":"Springer-Verlag","title":"Exact Counting and~Sampling of Optima for the Knapsack Problem","year":"2021","language":[{"iso":"eng"}],"keyword":["Dynamic programming","Exact counting","Sampling","Zero-one knapsack problem"],"publication":"Learning and Intelligent Optimization","abstract":[{"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.","lang":"eng"}],"author":[{"full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob"},{"first_name":"Aneta","last_name":"Neumann","full_name":"Neumann, Aneta"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_updated":"2023-12-13T10:45:14Z","doi":"10.1007/978-3-030-92121-7_4","publication_identifier":{"isbn":["978-3-030-92120-0"]},"publication_status":"published","page":"40–54","citation":{"ieee":"J. Bossek, A. Neumann, and F. Neumann, “Exact Counting and~Sampling of Optima for the Knapsack Problem,” in <i>Learning and Intelligent Optimization</i>, 2021, pp. 40–54, doi: <a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>.","chicago":"Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Exact Counting And~Sampling of Optima for the Knapsack Problem.” In <i>Learning and Intelligent Optimization</i>, 40–54. Berlin, Heidelberg: Springer-Verlag, 2021. <a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">https://doi.org/10.1007/978-3-030-92121-7_4</a>.","ama":"Bossek J, Neumann A, Neumann F. Exact Counting and~Sampling of Optima for the Knapsack Problem. In: <i>Learning and Intelligent Optimization</i>. Springer-Verlag; 2021:40–54. doi:<a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>","apa":"Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Exact Counting and~Sampling of Optima for the Knapsack Problem. <i>Learning and Intelligent Optimization</i>, 40–54. <a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">https://doi.org/10.1007/978-3-030-92121-7_4</a>","mla":"Bossek, Jakob, et al. “Exact Counting And~Sampling of Optima for the Knapsack Problem.” <i>Learning and Intelligent Optimization</i>, Springer-Verlag, 2021, pp. 40–54, doi:<a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>.","bibtex":"@inproceedings{Bossek_Neumann_Neumann_2021, place={Berlin, Heidelberg}, title={Exact Counting and~Sampling of Optima for the Knapsack Problem}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-92121-7_4\">10.1007/978-3-030-92121-7_4</a>}, booktitle={Learning and Intelligent Optimization}, publisher={Springer-Verlag}, author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={40–54} }","short":"J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization, Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54."},"place":"Berlin, Heidelberg","department":[{"_id":"819"}],"user_id":"102979","_id":"48855","extern":"1","type":"conference","status":"public"}]