Details zu Publikationen

A case study of algorithm selection for the traveling thief problem

verfasst von
Markus Wagner, Marius Lindauer, Mustafa Mısır, Samadhi Nallaperuma, Frank Hutter
Abstract

Many real-world problems are composed of several interacting components. In order to facilitate research on such interactions, the Traveling Thief Problem (TTP) was created in 2013 as the combination of two well-understood combinatorial optimization problems. With this article, we contribute in four ways. First, we create a comprehensive dataset that comprises the performance data of 21 TTP algorithms on the full original set of 9720 TTP instances. Second, we define 55 characteristics for all TPP instances that can be used to select the best algorithm on a per-instance basis. Third, we use these algorithms and features to construct the first algorithm portfolios for TTP, clearly outperforming the single best algorithm. Finally, we study which algorithms contribute most to this portfolio.

Externe Organisation(en)
University of Adelaide
Albert-Ludwigs-Universität Freiburg
Nanjing University of Aeronautics and Astronautics
The University of Sheffield
Typ
Artikel
Journal
Journal of heuristics
Band
24
Seiten
295-320
Anzahl der Seiten
26
ISSN
1381-1231
Publikationsdatum
06.2018
Publikationsstatus
Veröffentlicht
Peer-reviewed
Ja
ASJC Scopus Sachgebiete
Software, Information systems, Computernetzwerke und -kommunikation, Steuerung und Optimierung, Managementlehre und Operations Resarch, Artificial intelligence
Elektronische Version(en)
https://arxiv.org/abs/1609.00462 (Zugang: Offen)
https://doi.org/10.1007/s10732-017-9328-y (Zugang: Geschlossen)