Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136720
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | On the use of quality diversity algorithms for the traveling thief problem |
Author: | Nikfarjam, A. Neumann, A. Neumann, F. |
Citation: | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'22), 2022 / Fieldsend, J.E., Wagner, M. (ed./s), pp.260-268 |
Publisher: | Association for Computing Machinery |
Publisher Place: | New York, NY |
Issue Date: | 2022 |
ISBN: | 9781450392372 |
Conference Name: | The Genetic and Evolutionary Computation Conference (GECCO) (9 Jul 2022 - 13 Jul 2022 : virtual online) |
Editor: | Fieldsend, J.E. Wagner, M. |
Statement of Responsibility: | Adel Nikfarjam, Aneta Neumann, Frank Neumann |
Abstract: | In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focusing on only one component. The traveling thief problem (TTP) belongs to this category and is formed by the integration of the traveling salesperson problem (TSP) and the knapsack problem (KP). In this paper, we investigate the inter-dependency of the TSP and the KP by means of quality diversity (QD) approaches. QD algorithms provide a powerful tool not only to obtain high-quality solutions but also to illustrate the distribution of high-performing solutions in the behavioural space. We introduce a MAP-Elite based evolutionary algorithm using well-known TSP and KP search operators, taking the TSP and KP score as behavioural descriptor. Afterwards, we conduct comprehensive experimental studies that show the usefulness of using the QD approach applied to the TTP. First, we provide insights regarding high-quality TTP solutions in the TSP/KP behavioural space. Afterwards, we show that better solutions for the TTP can be obtained by using our QD approach and it can improve the best-known solution for a wide range of TTP instances used for benchmarking in the literature. |
Keywords: | Quality Diversity; Traveling Thief Problem; Map-Elites |
Rights: | © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. |
DOI: | 10.1145/3512290.3528752 |
Grant ID: | http://purl.org/au-research/grants/arc/DP190103894 http://purl.org/au-research/grants/arc/FT200100536 |
Published version: | https://dl.acm.org/doi/proceedings/10.1145/3512290.3528752 |
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.