Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/126043
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: Evolutionary algorithms for the chance-constrained knapsack problem
Author: Xie, Y.
Harper, O.
Assimi, H.
Neumann, A.
Neumann, F.
Citation: GECCO '19: Proceedings of the 2019 Genetic and Evolutionary Computation Conference, 2019 / vol.abs/1902.04767, pp.338-346
Publisher: ACM
Publisher Place: New York
Issue Date: 2019
ISBN: 9781450361118
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (13 Jul 2019 - 17 Jul 2019 : Prague, Czech Republic)
Statement of
Responsibility: 
Xue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, Frank Neumann
Abstract: Evolutionary algorithms have been widely used for a range of stochastic optimization problems. In most studies, the goal is to optimize the expected quality of the solution. Motivated by real-world problems where constraint violations have extremely disruptive effects, we consider a variant of the knapsack problem where the profit is maximized under the constraint that the knapsack capacity bound is violated with a small probability of at most α. This problem is known as chance-constrained knapsack problem and chance-constrained optimization problems have so far gained little attention in the evolutionary computation literature. We show how to use popular deviation inequalities such as Chebyshev's inequality and Chernoff bounds as part of the solution evaluation when tackling these problems by evolutionary algorithms and compare the effectiveness of our algorithms on a wide range of chance-constrained knapsack instances.
Keywords: Knapsack problem, chance-constrained optimization, evolutionary algorithms
Rights: © 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.
RMID: 1000000501
DOI: 10.1145/3321707.3321869
Grant ID: http://purl.org/au-research/grants/arc/DP160102401
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
hdl_126043.pdfAccepted version299.19 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.