Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3321707.3321869 | Genetic and Evolutionary Computation Conference |
Keywords | Field | DocType |
Knapsack problem, chance-constrained optimization, evolutionary algorithms | Mathematical optimization,Stochastic optimization,Evolutionary algorithm,Computer science,Evolutionary computation,Chebyshev filter,Knapsack problem,Optimization problem,Chernoff bound | Journal |
Volume | Citations | PageRank |
abs/1902.04767 | 0 | 0.34 |
References | Authors | |
17 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yue Xie | 1 | 0 | 2.37 |
| Oscar Harper | 2 | 0 | 0.34 |
| Hirad Assimi | 3 | 10 | 2.53 |
| Aneta Neumann | 4 | 14 | 12.79 |
| Frank Neumann | 5 | 1727 | 124.28 |