Evolutionary algorithms for the chance-constrained knapsack problem

Simple item page
dc.contributor.authorXie, Y.
dc.contributor.authorHarper, O.
dc.contributor.authorAssimi, H.
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.conferenceGECCO '19: Genetic and Evolutionary Computation Conference (13 Jul 2019 - 17 Jul 2019 : Prague Czech Republic)
dc.contributor.editorAuger, A.
dc.contributor.editorStützle, T.
dc.date.issued2019
dc.description.abstractEvolutionary 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.
dc.description.statementofresponsibilityXue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, Frank Neumann
dc.identifier.citationProceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, July 13-17, 2019, 2019 / Auger, A., Stützle, T. (ed./s), vol.abs/1902.04767, pp.338-346
dc.identifier.doi10.1145/3321707.3321869
dc.identifier.isbn9781 450361118
dc.identifier.orcidXie, Y. [0000-0002-7959-4563]
dc.identifier.orcidAssimi, H. [0000-0002-0548-2921]
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/126043
dc.language.isoen
dc.publisherACM
dc.publisher.placeNew York
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401
dc.rights© 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.
dc.source.urihttps://doi.org/10.1145/3321707.3321869
dc.subjectKnapsack problem, chance-constrained optimization, evolutionary algorithms
dc.titleEvolutionary algorithms for the chance-constrained knapsack problem
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
hdl_126043.pdf
Size:
299.19 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download

Collections

Computer Science publications