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 $\alpha$. 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.
翻译:进化算法被广泛用于一系列随机优化问题。 在大多数研究中, 目标是优化解决方案的预期质量。 受约束性违规具有极端破坏性效应的现实世界问题所驱动, 我们考虑Knapack问题的一个变式, 其利润在 knapsack 能力约束受约束的制约下最大化, 其可能性很小, 最多为$\ alpha$。 这个问题被称为受风险限制的 knapack 问题和受风险限制的优化问题, 迄今在进化计算文献中很少引起注意。 我们展示了在通过进化算法解决这些问题时如何使用切比谢夫的不平等和Chernoff 界限等流行的偏差不平等作为解决方案评估的一部分, 并比较我们在一系列受风险限制的Knapack 实例上的算法的有效性 。