Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/131347
Citations | ||
Scopus | Web of Scienceยฎ | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Breeding diverse packings for the knapsack problem by means of diversity-tailored evolutionary algorithms |
Author: | Bossek, J. Neumann, A. Neumann, F. |
Citation: | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'21), 2021 / Chicano, F., Krawiec, K. (ed./s), pp.556-564 |
Publisher: | Association for Computing Machinery |
Publisher Place: | New York, NY |
Issue Date: | 2021 |
ISBN: | 9781450383509 |
Conference Name: | Genetic and Evolutionary Computation Conference (GECCO) (10 Jul 2021 - 14 Jul 2021 : virtual online) |
Editor: | Chicano, F. Krawiec, K. |
Statement of Responsibility: | Jakob Bossek, Aneta Neumann, Frank Neumann |
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โ๐) ยท๐๐๐ , 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 (๐ + 1)-EA with initial approximate solutions calculated by awell-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. |
Keywords: | Evolutionary algorithms; tailored operators; evolutionary diversity optimization; knapsack problem |
Rights: | ยฉ 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. |
DOI: | 10.1145/3449639.3459364 |
Grant ID: | http://purl.org/au-research/grants/arc/DP190103894 |
Published version: | https://dl.acm.org/doi/proceedings/10.1145/3449726 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.