Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136894
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Analysis of Quality Diversity Algorithms for the Knapsack Problem |
Author: | Nikfarjam, A. Viet Do, A. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2022 / Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tusar, T. (ed./s), vol.13399, pp.413-427 |
Publisher: | Springer |
Publisher Place: | Online |
Issue Date: | 2022 |
Series/Report no.: | Lecture Notes in Computer Science; 13399 |
ISBN: | 9783031147203 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (PPSN) (10 Sep 2022 - 14 Sep 2022 : Dortmund, Germany) |
Editor: | Rudolph, G. Kononova, A.V. Aguirre, H. Kerschke, P. Ochoa, G. Tusar, T. |
Statement of Responsibility: | Adel Nikfarjam, Anh Viet Do, Frank Neumann |
Abstract: | 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. |
Keywords: | Quality diversity; Runtime analysis; Dynamic programming |
Rights: | © 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG |
DOI: | 10.1007/978-3-031-14721-0_29 |
Grant ID: | http://purl.org/au-research/grants/arc/DP190103894 http://purl.org/au-research/grants/arc/FT200100536 |
Published version: | https://link.springer.com/book/10.1007/978-3-031-14721-0 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.