Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/126990
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem
Author: Xie, Y.
Neumann, A.
Neumann, F.
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
Issue Date: 2020
ISBN: 9781450371285
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (08 Jul 2020 - 12 Jul 2020 : Cancun, Mexico)
Statement of
Responsibility: 
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.
RMID: 1000020933
DOI: 10.1145/3377930.3390162
Grant ID: http://purl.org/au-research/grants/arc/DP160102401
Published version: https://dl.acm.org/doi/proceedings/10.1145/3377930
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.