Randomized heuristic repair for large-scale multidimensional knapsack problem

多维背包问题（MKP）是一个NP难度的组合优化问题，其解决方案是确定不违反容量约束的最大总利润物品的子集。由于其困难程度，大规模的MKP实例通常是元启发式的目标，这种情况下有效的可行性维护策略至关重要。1998年，Chu和Beasley提出了一种有效的启发式修复方法，这种方法对于最近的元启发式仍然具有相关性。然而，由于其确定性本质，该启发式提供的解决方案的多样性不足以进行长时间的运行。因此，寻找新的解决方案会在一段时间后停止。本文提出了一种基于效率的随机化策略，用于启发式修复，增加修复后解决方案的变异性，而不会降低质量，并改善整体结果。

解决问题：该论文试图通过提出一种基于效率的随机化策略来改进多维背包问题的启发式修复算法，以增加解的多样性和搜索效率。该问题是NP难问题，需要进行元启发式算法的优化。

关键思路：论文提出了一种基于效率的随机化策略，用于改进多维背包问题的启发式修复算法，以增加解的多样性和搜索效率。这种策略将根据效率指标对可行解进行排序，并在修复过程中随机选择一个可行解进行修复。

其他亮点：论文通过实验验证了该策略的有效性，并与其他算法进行了比较。实验结果表明，该策略可以显著提高算法的搜索效率和解的多样性，而不会降低解的质量。论文还提供了数据集和开源代码，以便其他研究人员可以重现和扩展这项工作。

相关研究：最近的相关研究包括：1. A Hybrid Genetic Algorithm for the Multidimensional Knapsack Problem; 2. A Scatter Search for the Multidimensional Knapsack Problem with Setup Costs; 3. An Effective Evolutionary Algorithm for the Multidimensional Knapsack Problem.