Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem

Moritz V Seiler, Janina Pohl, Jakob Bossek, Pascal Kerschke, Heike Trautmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 1000 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.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI
Subtitle of host publication16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part I
EditorsThomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, Heike Trautmann
Pages48-64
Number of pages17
ISBN (Electronic)978-3-030-58112-1
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event16th International Conference on Parallel Problem Solving from Nature, PPSN 2020 - Virtual Event
Duration: 5 Sep 20209 Sep 2020
Conference number: 16

Publication series

NameLecture Notes in Computer Science
Volume12269

Conference

Conference16th International Conference on Parallel Problem Solving from Nature, PPSN 2020
Abbreviated titlePPSN 2020
CityVirtual Event
Period5/09/209/09/20

Fingerprint

Dive into the research topics of 'Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem'. Together they form a unique fingerprint.

Cite this