论文标题
分析背包问题的质量多样性算法
Analysis of Quality Diversity Algorithms for the Knapsack Problem
论文作者
论文摘要
在处理机器人技术，游戏和组合优化等领域的问题时，质量多样性（QD）算法已被证明非常成功。它们的目的是最大程度地提高基本问题所谓行为空间不同区域的解决方案的质量。在本文中，我们应用QD范式来模拟背包问题上的动态编程行为，并提供对QD算法的第一个运行时分析。我们表明，他们能够在预期的伪多项式时间内计算最佳解决方案，并揭示导致完全多项式随机近似方案（FPRAS）的参数设置。我们的实验研究根据在行为空间中构建的解决方案以及获得最佳解决方案所需的运行时评估了经典基准集的不同方法。
Quality diversity (QD) algorithms have been shown to be very successful when dealing with problems in areas such as robotics, games and combinatorial optimization. They aim to maximize the quality of solutions for different regions of the so-called behavioural space of the underlying problem. In this paper, we apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem, and provide a first runtime analysis of QD algorithms. We show that they are able to compute an optimal solution within expected pseudo-polynomial time, and reveal parameter settings that lead to a fully polynomial randomised approximation scheme (FPRAS). Our experimental investigations evaluate the different approaches on classical benchmark sets in terms of solutions constructed in the behavioural space as well as the runtime needed to obtain an optimal solution.
