# Analysis of Quality Diversity Algorithms for the Knapsack Problem

arXiv: https://arxiv.org/abs/2207.14037 · HTML: https://mlsanity.com/paper/2207.14037/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2022.

## Built on by (most cited first, 2 of 2)

- [Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax](https://mlsanity.com/paper/2307.07248/) (2023)
- [Trust Region-Based Bayesian Optimisation to Discover Diverse Solutions](https://mlsanity.com/paper/2511.00750/) (2025)

## Abstract (arXiv)

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.