Evolutionary Algorithms for the Chance-Constrained Knapsack Problem

원문 초록

Evolutionary algorithms have been applied to a wide range of stochastic problems. Motivated by real-world problems where constraint violations have disruptive effects, this paper considers the chance-constrained knapsack problem (CCKP) which is a variance of the binary knapsack problem. The problem aims to maximize the profit of selected items under a constraint that the knapsack capacity bound is violated with a small probability. To tackle the chance constraint, we introduce how to construct surrogate functions by applying well-known deviation inequalities such as Chebyshev's inequality and Chernoff bounds. Furthermore, we investigate the performance of several deterministic approaches and introduce a single- and multi-objective evolutionary algorithm to solve the CCKP. In the experiment section, we evaluate and compare the deterministic approaches and evolutionary algorithms on a wide range of instances. Our experimental results show that a multi-objective evolutionary algorithm outperforms its single-objective formulation for all instances and performance better than deterministic approaches according to the computation time. Furthermore, our investigation points out in which circumstances to favour Chebyshev's inequality or the Chernoff bound when dealing with the CCKP.