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.
翻译:在处理机器人、游戏和组合优化等领域的问题时,质量多样性算法已证明非常成功,其目的是为所谓基本问题行为空间的不同区域最大限度地提高解决办法的质量。在本文中,我们应用质量多样性算法模式模拟关于 knapsack 问题的动态编程行为,并首次对QD 算法进行运行时间分析。我们表明,它们能够在预期的假极时内计算出最佳解决办法,并揭示导致完全多元随机近距离方案(FPRAS)的参数设置。我们实验性调查从行为空间构建的解决办法的角度以及获得最佳解决办法所需的运行时间的角度评估了古典基准设置的不同方法。