Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem|
|Citation:||Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO'20), 2020 / pp.271-279|
|Publisher:||Association for Computing Machinery|
|Publisher Place:||New York|
|Conference Name:||Genetic and Evolutionary Computation Conference (GECCO) (08 Jul 2020 - 12 Jul 2020 : Cancun, Mexico)|
|Yue Xie, Aneta Neumann, Frank Neumann|
|Abstract:||The chance-constrained knapsack problem is a variant of the classical knapsack problem where each item has a weight distribution instead of a deterministic weight. The objective is to maximize the total profit of the selected items under the condition that the weight of the selected items only exceeds the given weight bound with a small probability of . In this paper, we consider problem-specific single-objective and multi-objective approaches for the problem. We examine the use of heavy-tail mutations and introduce a problem-specific crossover operator to deal with the chance-constrained knapsack problem. Empirical results for singleobjective evolutionary algorithms show the effectiveness of our operators compared to the use of classical operators. Moreover, we introduce a new effective multi-objective model for the chanceconstrained knapsack problem. We use this model in combination with the problem-specific crossover operator in multi-objective evolutionary algorithms to solve the problem. Our experimental results show that this leads to significant performance improvements when using the approach in evolutionary multi-objective algorithms such as GSEMO and NSGA-II.|
|Keywords:||Knapsack problem; chance-constrained optimization; heavy-tail mutation operator; crossover operator; evolutionary algorithms|
|Rights:||© 2020 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.|
|Appears in Collections:||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.