论文标题
寻找和探索0-1多维背包问题的有希望的搜索空间
Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem
论文作者
论文摘要
0-1多维背包问题（MKP）是许多工程应用程序的经典NP-HARD组合优化问题。在本文中，我们提出了一种新颖的算法，将进化计算与精确算法结合使用，以求解0-1 MKP。它维护一组解决方案，并利用人群中的信息来提取良好的部分任务。为了找到高质量的解决方案，应用了精确的算法来探索良好的部分分配指定的有希望的搜索空间。新解决方案用于更新人口。因此，随着人口的改善，良好的部分任务朝着更好的方向发展。使用常用基准组进行的广泛实验表明，我们的算法的表现优于最新的启发式算法，TPTEA和DQPSO以及商业求解器CPLEX。它找到了比现有算法更好的解决方案，并为10个大型和硬实例提供了新的下限。
The 0-1 Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computation with the exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. To find high-quality solutions, an exact algorithm is applied to explore the promising search space specified by the good partial assignments. The new solutions are used to update the population. Thus, the good partial assignments evolve towards a better direction with the improvement of the population. Extensive experimentation with commonly used benchmark sets shows that our algorithm outperforms the state-of-the-art heuristic algorithms, TPTEA and DQPSO, as well as the commercial solver CPlex. It finds better solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances.
