论文标题
基于尾巴绑定目标的动态机会约束的背包问题的进化双目标优化
Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives
论文作者
论文摘要
现实世界中的组合优化问题通常是随机且动态的。因此，必须采用整体方法做出最佳和可靠的决定。在本文中，我们考虑了动态的机会约束的背包问题，其中每个项目的重量是随机的，容量约束随着时间的流逝而动态变化，目标是最大程度地利用总利润，这是总重量超过容量的可能性。我们利用突出的尾巴不平等，例如Chebyshev的不平等，而Chernoff绑定到近似概率约束。我们的关键贡献是引入一个额外的目标，该目标估计了仍然符合机会限制的给定随机解决方案的最小能力。这个目标有助于迎合随机问题的动态变化。我们将单目标进化算法应用于该问题，并展示双目标优化如何有助于解决动态的机会约束问题。
Real-world combinatorial optimization problems are often stochastic and dynamic. Therefore, it is essential to make optimal and reliable decisions with a holistic approach. In this paper, we consider the dynamic chance-constrained knapsack problem where the weight of each item is stochastic, the capacity constraint changes dynamically over time, and the objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We make use of prominent tail inequalities such as Chebyshev's inequality, and Chernoff bound to approximate the probabilistic constraint. Our key contribution is to introduce an additional objective which estimates the minimal capacity bound for a given stochastic solution that still meets the chance constraint. This objective helps to cater for dynamic changes to the stochastic problem. We apply single- and multi-objective evolutionary algorithms to the problem and show how bi-objective optimization can help to deal with dynamic chance-constrained problems.
