论文标题
特定的单对象和多目标进化算法，用于偶然受限的背包问题
Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
论文作者
论文摘要
机会约束的背包问题是经典背包问题的变体，其中每个项目都有重量分布而不是确定性的重量。目的是在所选项目的重量仅超过$α$的较小概率的情况下，最大化所选项目的总利润。在本文中，考虑针对该问题的特定问题的单目标和多目标方法。我们检查了重尾突变的使用，并引入了特定问题的跨界操作员来处理偶然受限的背包问题。单目标进化算法的经验结果表明，与使用经典操作员相比，我们的操作员的有效性。此外，我们引入了一种新的有效的多目标模型，以解决偶然受限的背包问题。我们将此模型与多目标进化算法中的特定问题分频器运算符结合使用来解决问题。我们的实验结果表明，在使用进化多目标算法（例如GSEMO和NSGA-II）中使用该方法时，这会导致显着的性能提高。
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.
