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

IEEE Symposium Series on Computational Intelligence (SSCI), pp. 361–368

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.

Authors 6

1. Moritz Vinzent Seiler
   Affiliation as printed

   University of Münster,Data Science: Statistics and Optimization,Münster,Germany

2. Jeroen Rook

   University of Twente

   Affiliation as printed

   University of Twente,Data Management and Biometrics,Enschede,Netherlands

   Data Management and Biometrics, University of Twente, Enschede, Netherlands

3. Jonathan Heins

   Technische Universität Dresden

   Affiliation as printed

   TU Dresden,Big Data Analytics in Transportation,Dresden,Germany

   Big Data Analytics in Transportation, TU Dresden, Dresden, Germany

4. Oliver Ludger Preuß
   Affiliation as printed

   University of Münster,Data Science: Statistics and Optimization,Münster,Germany

5. Jakob Bossek Aachen Chair for AI Methodology (AIM)

   RWTH Aachen University

   Affiliation as printed

   Aachen University,Chair for AI Methodology RWTH,Aachen,Germany

   Chair for AI Methodology RWTH, Aachen University, Aachen, Germany

6. Heike Trautmann
   Affiliation as printed

   University of Münster,Data Science: Statistics and Optimization,Münster,Germany