EUVIMEDEUVIMED entdecken
Crossref

On the Use of Quality Diversity Algorithms for the Travelling Thief Problem

Adel Nikfarjam, Aneta Neumann, Frank Neumann

ACM Transactions on Evolutionary Learning and Optimization · 30.06.2024 · 4 (2) · 1-22

DOI: 10.1145/3641109 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Evolutionary Learning and Optimization, online erschienen am 08.06.2024. Verfasst von Adel Nikfarjam und 2 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 61 Literaturangaben. Gefördert von: Australian Research Council, South Australian Government, Research Consortium “Unlocking Complex Resources through Lean Processing”.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 travelling thief problem (TTP) belongs to this category and is formed by the integration of the travelling 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 multi-dimensional archive of phenotypic elites (MAP-Elites) based evolutionary algorithm using well-known TSP and KP search operators, taking the TSP and KP score as the behavioural descriptor. MAP-Elites algorithms are QD-based techniques to explore high-performing solutions in a behavioural space. 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 number of TTP instances used for benchmarking in the literature.

Förderung

  • Australian Research Council
  • South Australian Government
  • Research Consortium “Unlocking Complex Resources through Lean Processing”

Zitieren

APA

Nikfarjam, A., Neumann, A., & Neumann, F. (2024). On the Use of Quality Diversity Algorithms for the Travelling Thief Problem. ACM Transactions on Evolutionary Learning and Optimization, 4(2), 1-22. https://doi.org/10.1145/3641109

Vancouver

Nikfarjam A, Neumann A, Neumann F. On the Use of Quality Diversity Algorithms for the Travelling Thief Problem. ACM Transactions on Evolutionary Learning and Optimization. 2024;4(2):1-22. doi:10.1145/3641109

BibTeX
@article{Nikfarjam2024,
  author = {Nikfarjam, Adel and Neumann, Aneta and Neumann, Frank},
  title = {On the Use of Quality Diversity Algorithms for the Travelling Thief Problem},
  journal = {ACM Transactions on Evolutionary Learning and Optimization},
  year = {2024},
  volume = {4},
  number = {2},
  pages = {1--22},
  doi = {10.1145/3641109}
}
Kostenlos starten →