Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP

Moritz Vinzent Seiler, Jeroen Rook, Jonathan Heins, Oliver Ludger Preuß, Jakob Bossek, Heike Trautmann

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

Abstract

Automated Algorithm Configuration (AAC) usually takes a global perspective: it identifies a parameter configuration for an (optimization) algorithm that maximizes a performance metric over a set of instances. However, the optimal choice of parameters strongly depends on the instance at hand and should thus be calculated on a per-instance basis. We explore the potential of Per-Instance Algorithm Configuration (PIAC) by using Reinforcement Learning (RL). To this end, we propose a novel PIAC approach that is based on deep neural networks. We apply it to predict configurations for the Lin-Kernighan heuristic (LKH) for the Traveling Salesperson Problem (TSP) individually for every single instance. To train our PIAC approach, we create a large set of 100 000 TSP instances with 2 000 nodes each - currently the largest benchmark set to the best of our knowledge. We compare our approach to the state-of-the-art AAC method Sequential Model-based Algorithm Configuration (SMAC). The results show that our PIAC approach outperforms this baseline on both the newly created instance set and established instance sets.
Original languageEnglish
Title of host publication2023 IEEE Symposium Series on Computational Intelligence (SSCI)
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages361-368
Number of pages8
ISBN (Electronic)978-1-6654-3065-4, 978-1-6654-3064-7 (USB)
DOIs
Publication statusPublished - 2023
EventIEEE Symposium Series on Computational Intelligence,SSCI 2023 - Mexico City, Mexico
Duration: 5 Dec 20238 Dec 2023

Publication series

NameIEEE Symposium Series on Computational Intelligence
PublisherIEEE
Volume2023
ISSN (Print)2770-0097
ISSN (Electronic)2472-8322

Conference

ConferenceIEEE Symposium Series on Computational Intelligence,SSCI 2023
Abbreviated titleSSCI 2023
Country/TerritoryMexico
CityMexico City
Period5/12/238/12/23

Keywords

  • Per-Instance algorithm configuration
  • Traveling salesperson problem
  • Reinforcement learning
  • 2024 OA procedure

Fingerprint

Dive into the research topics of 'Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP'. Together they form a unique fingerprint.

Cite this