Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
This work addresses optimization under uncertainty for operations research and AI applications, but it is incremental as it adapts existing evolutionary methods to a specific problem variant.
The authors tackled the chance-constrained knapsack problem by developing specific single- and multi-objective evolutionary algorithms, introducing heavy-tail mutations and a problem-specific crossover operator, which led to significant performance improvements in algorithms like GSEMO and NSGA-II compared to classical operators.
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, 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 single-objective 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 chance-constrained 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.