Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Deep learning as a competitive feature-free approach for automated algorithm selection on the traveling salesperson problem
Author: Seiler, M.
Pohl, J.
Bossek, J.
Kerschke, P.
Trautmann, H.
Citation: Lecture Notes in Artificial Intelligence, 2020 / Bäck, T., Preuss, M., Deutz, A.H., Wang, H., Doerr, C., Emmerich, M.T.M., Trautmann, H. (ed./s), vol.12269, pp.48-64
Publisher: Springer Nature
Publisher Place: Switzerland
Issue Date: 2020
Series/Report no.: Lecture Notes in Computer Science; 12269
ISBN: 9783030581114
ISSN: 0302-9743
Conference Name: International Conference on Parallel Problem Solving from Nature (PPSN) (5 Sep 2020 - 9 Sep 2020 : Leiden, The Netherlands)
Editor: Bäck, T.
Preuss, M.
Deutz, A.H.
Wang, H.
Doerr, C.
Emmerich, M.T.M.
Trautmann, H.
Statement of
Moritz Seiler, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike Trautmann
Abstract: In this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithm selection (AS). We evolve instances with 1 000 nodes where the solvers show strongly different performance profiles. These instances serve as a basis for an exploratory study on the identification of well-discriminating problem characteristics (features). Our results in a nutshell: we show that even though (1) promising features exist, (2) these are in line with previous results from the literature, and (3) models trained with these features are more accurate than models adopting sophisticated feature selection methods, the advantage is not close to the virtual best solver in terms of penalized average runtime and so is the performance gain over the single best solver. However, we show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results and thus shows huge potential for future studies.
Keywords: Automated algorithm selection; Traveling Salesperson Problem; Feature-based approaches; Deep learning
Rights: © Springer Nature Switzerland AG 2020
DOI: 10.1007/978-3-030-58112-1_4
Published version:
Appears in Collections:Aurora harvest 8
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.