2023 IEEE Symposium Series on Computational Intelligence (SSCI)
Mexico City, Mexico. December 5-8, 2023

2023 IEEE Symposium Series on Computational Intelligence (SSCI) | 978-1-6654-3065-4/23/$31.00 ©2023 IEEE | DOI: 10.1109/SSCI52147.2023.10372008

Using Reinforcement Learning for Per-Instance
Algorithm Configuration on the TSP
1st Moritz Vinzent Seiler

2nd Jeroen Rook

3rd Jonathan Heins

Data Science: Statistics and Optimization
University of Münster
Münster, Germany
moritz.seiler@uni-muenster.de

Data Management and Biometrics
University of Twente
Enschede, Netherlands
j.g.rook@utwente.nl

Big Data Analytics in Transportation
TU Dresden
Dresden, Germany
jonathan.heins@tu-dresden.de

4th Oliver Ludger Preuß

5th Jakob Bossek

6th Heike Trautmann

Data Science: Statistics and Optimization
University of Münster
Münster, Germany
oliver.preuss@uni-muenster.de

Chair for AI Methodology
RWTH Aachen University
Aachen, Germany
bossek@aim.rwth-aachen.de

Data Science: Statistics and Optimization
Universities of Münster/TwenteMünster/Enschede, Germany/Netherlands
trautmann@wi.uni-muenster.de

Abstract—Automated Algorithm Configuration (AAC) usuallytakes a global perspective: it identifies a parameter configuration for an (optimization) algorithm that maximizes aperformance 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 thisend, we propose a novel PIAC approach that is based on deepneural 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 ourapproach to the state-of-the-art AAC method Sequential Modelbased Algorithm Configuration (SMAC). The results show that
our PIAC approach outperforms this baseline on both the newly
created instance set and established instance sets.
Index Terms—Per-Instance Algorithm Configuration, Traveling Salesperson Problem, Deep Reinforcement Learning

I. I NTRODUCTION AND R ELATED W ORK
A Euclidean Traveling Salesperson Problem (TSP) instance consists of a set of nodes/cities and pairwise distances
between these nodes. The optimization problem then is tofind the shortest route through all cities such that every city isvisited exactly once. The TSP is one of the classical N P-hardcombinatorial optimization problems and is highly relevantin transportation logistics, circuit board design, and manyother disciplines. A plethora of algorithmic approaches havebeen developed for the TSP. One can differentiate between
exact solvers that guarantee to find a globally optimal solution, e.g. Concorde [1], Branch & Bound approaches [2],or naive exhaustive enumeration, and inexact solvers, e.g.
Edge-Assembly-Crossover (EAX) [3] and the Lin–Kernighan
Heuristic (LKH) [4].
LKH defined the state-of-the-art in inexact TSP solving fora long period of time. It employs a variable-depth approach

978-0-7381-4409-2/23/$31.00 ©2023 IEEE

Fig. 1. Visualization of the World TSP Instance with 1 904 711 cities.
The best-known tour so far has length 7 515 755 956 and was found by
LKH (see https://www.math.uwaterloo.ca/tsp/world/ for more details). The
100 000 centroids for generating the instances are highlighted in orange
while all other cities are shown in blue. The generated instances may overlap
but differ in the local features. Please see Section II for more details.

to generate intricate local search moves by constructing asequence of edge exchanges based on heuristics. In 2015,
Dubois et al. [5] introduced an enhancement incorporating
restarts. More recently, EAX as an evolutionary algorithm
utilizing improved versions of both local and global variantsof the edge assembly crossover operator turned out to behighly competitive, specifically in its restart variant.
The complementarity of both solvers and their restartvariants on well-known and commonly used benchmark data
sets such as Random Uniform Euclidean (RUE), clusteredinstances (Netgen) [6], Morphed [6], TSPLib, National,
and VLSI, was shown in [7] and exploited for building
a high-performing per-instance Automated Algorithm Selection (AAS, [8]) model to automatically decide on thebest-suited solver for a given TSP instance. This trained
selector significantly outperformed the Single Best Solver
EAX(+restart). For AAS model training numerical, resp.
tabular, features characterizing instance properties are commonly used stemming from the feature sets TSPMeta [9],UBC [10] and Pihera [11], e.g. based on statistics of the361
1

Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

PC 3 (8.3%)
PC 4 (5.6%)

PC 5 (4.1%)

distance matrix or properties of minimum spanning trees or
k-nearest neighbor graphs.
While, commonly, AAS on TSP focuses on minimizing
computational runtime until the instance is solved to optimality, Bossek et al. [12] also considered anytime behavior
of inexact TSP solvers based on the concept of empirical
runtime distributions. As the main outcome, the performanceranking of solvers is heavily influenced by the specificlevel of approximation quality that is prioritized. The bestsuited inexact TSP solver is highly dependent on the desired approximation level with LKH and its variants being
highly competitive at the early and medium stages of the
optimization phase, giving rise to a huge potential for solver
hybridization and, in particular, algorithm configuration to
improve convergence to optimality.
Since TSP solvers, like LKH and EAX, have performanceaffecting parameters, multiple (potentially infinite) distinct
variants of each solver exist, with each variant considered asa separate solver in the domain of AAS. Yet, in the context
of Automated Algorithm Configuration (AAC), these variants
are referred to as configurations. Therefore and orthogonal
to AAS, AAC aims to find the one static configurationthat yields the overall best average performance over all
instances it is expected to solve, efficiently. Styles andHoos [13] showed that applying AAC to LKH considerably
improved performance compared to LKH with the default
configuration on TSPLib as well as the potential for scaling
performance. Their analysis did not focus on the actual foundconfigurations, which prevents us from including them in
our analysis. More recently, Rasku et al. [14] conducted an
extensive empirical study on the effectiveness of different
AAC methods to configure solvers for the Vehicle Routing
Problem, a generalization of TSP. They showed that AAC
in the VRP domain yields significant improvements andthey recommended using Sequential Model-Based Algorithm
Configuration (SMAC) [15] in this domain.
Based on the successes of AAS and AAC, we bridge thetwo domains by proposing two novel Per-Instance Algorithm
Configuration (PIAC) [16] approaches for LKH where both
approaches learn a model that determines the best configuration for every instance individually out of the infinitely
large pool of variants. The latter property prevents us fromusing supervised learning. Instead, we utilize Reinforcement
Learning to accomplish this task. Other existing PIACs are,to our knowledge, limited. Popular approaches [17], [18]build a portfolio of complementary configurations which isthen deployed as an AAS framework. These portfolios areusually limited to only a few configurations of the complete
configuration space and are therefore not considered ascomplete PIAC approaches.
Both our PIAC approaches utilize deep learning, where
one is a Multi-Layer Perceptron (MLP), which relies on
numerical instance features, and the other approach is aTransformer model that directly takes the Euclidean city
coordinates as input [19]. A detailed description of both
approaches and how they are fitted is given in Section III.

−20

−10

0

10

20

30

Fig. 2. Distribution of the different instance classes in the feature space
represented by the first five PCs with the percentage of explained variancegiven in brackets. The first two PCs cover a combined variance of 36.5%
while the first seven cover a large fraction of 54.5% of the variance in total.

Since training deep learning models requires large training
sets and most TSP benchmark sets are of limited size, we also
introduce a new diverse benchmark set in Section II, which
is based on subsets of the World TSP instance. In Section IV
we conduct an empirical study on the effectiveness of our
PIAC approaches and compare their performance against
static configurations. Finally, in Section VI, we discuss theresults and set directions for future work.
II. I NSTANCE DATASET
One important premise for deep learning but especiallywhen used in combination with reinforcement learning ishaving a large set of training- and validation data. Recent
papers on AAS or AAC for the TSP domain usually considered rather small instance sets — between several hundred toa few thousand cities [7], [20], [21]. We found this to be far
too small for our research task and, therefore, opted for a
sophisticated approach to create a large and representative setof TSP instances. Several works have proposed approaches
to generate diverse instances such as RUE, Netgen [6],Morphed [6], and Evolved [22]. Evolved, for example, uses
an evolutionary algorithm that maximizes the performance
ratio of two competitive solvers while yielding featurediverse instances. Yet, we found that these generators areeither quite costly (e.g. Evolved) or not really diverse (e.g.
RUE or Netgen). Thus, we aimed for a different approach bysampling from a large, complex TSP instance as a donator.

362
2
Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

To sub-sample a large instance into many smaller ones,
we first defined a set of m starting points and then sampled
for every starting point its k − 1 nearest cities. This would
result in m instances with k cities, each. However, there is achance (even if the donator instance is sufficiently large) thatthe instances would overlap at their boundaries.To avoid theseoverlapping instances being too similar, one can increase thenumber of nearest cities (e.g. 2 × k − 1) and then randomly
sample k cities. This way, instances would still overlap but
they would differ in the local structure. We aimed for m =100 000 instances in total, giving us a large set of instances
for training (75 000) and validation (25 000). In addition, we
prefer larger instances of 2 000 cities to increase difficulty.
Example instances can be found in Figure 2.1
We took one of the largest available TSP instances as the
donator instance: the World TSP. It consists of 1 904 711
cities around the world, and the current best found optimal
tour has length 7 515 755 956 using LKH2 . The coordinatesof the cities are given in degrees of longitude and latitude.
We used 100 000-means clustering algorithm in combination
with the haversine distance [23], the angular distance oftwo points on a sphere, to evenly spread the centroids
around the TSP World instance. Afterward, the centroids
were used as starting points for the subsampling procedure.
To avoid overlapping, we considered the 4 999 closest pointsof every starting point and uniformly at random sampled
k = 2 000 cities from these 5 000 (the starting point plus
its 4 999 nearest neighbors), randomly. These 2 000 cities
were then merged into one new TSP instance. Further, we
mapped the cities into a Cartesian space with a size of
1 000 000 × 1 000 000.
Next, we executed Concorde on every instance to findthe optimal tour with a cutoff time of one day. For 99 998
instances, Concorde returned the optimal tour within one day.
However for two instances, subset_world_29974.tsp
and subset_world_60919.tsp, Concorde was unable
to find an optimal tour even within an increased cutoff timeof seven days. Hence, we approximated the optimal tour
by executing EAX with default settings 100 times on bothinstances and considering the respective best-found tour as
optimal.
We analyzed the generated instances from a qualitative andquantitative standpoint. Visualizing the instances yields many
complex structures: e.g. uniformly distributed, grid-like distributed, and clusters of cities (see Figure 3). To quantify thediversity captured by our instances, we compare their distribution in feature space with instances used in previous studies, namely RUE, Netgen, Morphed, and Evolved instances.
To this end, using the R package salesperson [24] wecompute all TSPMeta [9] and Pihera [11] features as well as
most UBC [10] features (excluding the cost-intensive local
search probing features and branch & bound features asthese are not implemented in salesperson), for all of our
1 Upon acceptance, we will publish the dataset for open use.
2 See https://www.math.uwaterloo.ca/tsp/world/ for more information on

the World TSP instance.

instances and all other instances with a node size of 2 000.
These features are numeric values with supposedly describe
the characteristics of a TSP instance and are determinedfor each TSP instance individually. Note that there areapproaches to normalize TSP instance features [21], [25]with regard to the node and bounding box size which would
allow a comparison with different instances. However, many
features are still only available in their unnormalized versions until now. This results in potentially missing important
instance information. Consequently, we use unnormalizedversions of all features in this study. The instances of thesame group were found to be very similar with regard totheir normalized feature distribution disregarding the size inboth normalization studies. Thus, comparing our instancesin the unnormalized feature space with instances of the same
size is representative.
Assessing the distribution of instances regarding individual
dimensions of the complete feature space with the dashboard
provided in [21], we found that our instances exhibit diversity, capturing the main properties of all other instancegroups. To visually represent these findings, we performeda Principal Component Analysis (PCA) with all instancesand depict the results in Figure 2. The distribution of our instances across the most important principal components (PC)covers those of all other instance groups. An exception tothis are a few Netgen and Morphed instances in PC 4 which
however accounts only for 5.4% of the total variance. Thisshows that our instances are diverse, representative andcover a larger area of the feature space than previous classes
of instances.
III. M ETHODOLOGYLKH exhibits a large set of parameters that influence its
performance. In this setting, we define performance as thecomputational runtime, measured in CPU time, to find the optimal tour. If LKH fails to find the optimal tour within a given
time limit (cutoff time), it will receive a penalty. We choose
the Penalized Quantile Runtime 10 (PQR10) score [26] tomeasure the performance of LKH. The PQR10 score isdefined as the median runtime over multiple runs if morethan 50% of the runs were successful. Otherwise, the PQR10score is 10-times the cutoff time. We choose the PQR10score over the Penalized Average Runtime 10 (PAR10) score
as we found it to be more robust against timeouts, which
is supported by the results in [27]. Usually, ten solver runs
are considered as a standard to compute PQR10 and also
PAR10 scores. Yet, we found that during training it is often
more advantageous to execute less than ten runs and spend
the spared time on evaluating more configurations without
increasing the total number of LKH runs. Note that forvalidation we always consider the PQR10 score with exactly
ten runs and seeds ∈ [1, 10] to yield comparable results.
In the following, we differentiate between Full-set Algorithm Configuration and Per-instance Algorithm Configuration. Thereafter, we will compare both approaches against363
3
Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

Fig. 3. Selected examples of the generated instances. From left to right: similar to a RUE instance, RUE-like with grid-like structures, more structured
but without strong clusters and with strong clusters.

TABLE IW E CONSIDERED THE FOLLOWING PARAMETER SPACE FOR LKH.
E X C E S S IS A CONTINUOUS PARAMETER THAT LIES WITHIN 0 AND 1 AND
1
DEFAULTS TO n WITH n BEING THE NUMBER OF CITIES . Y ET, E X C E S S
IS USUALLY VERY BENEFICIAL CLOSE TO 0. T HE OTHER SEVEN
PARAMETERS ARE DISCRETE . N O N S E Q U E N T I A L M O V E T Y P E IS THE
ONLY CONSTRAINED PARAMETERS . I T MUST BE SET LARGER OR EQUAL
TO THE M O V E T Y P E .
Parameter

Specification

Excess]0, 1]

1n

Gain23{Yes, No}

Yes

{1, . . . , 10,
1 Symmetric, . . . , 10 Symmetric}

5

Max Candidates

Default

i.e. the best configuration at that time. A new configuration isrejected when it yields a worse PQR10 score on the instances
it ran on than the incumbent. When the new configuration isevaluated on all the same instances as the incumbent andyields a lower PQR10 score, it becomes the new incumbent.
In the BO phase, promising new configurations are discovered. Here, a surrogate model, fitted on the performed
evaluations during intensification, is used to predict the mean
PQR10 score of a configuration over all the instances. The
surrogate model uses tabular instance features as described in
Section II and a configuration as input. By using local- andrandom search techniques, new configurations are discovered
and ranked based on their Expected Improvement (EI). To
favor exploration, this ranked list of configurations is interleaved with randomly sampled configurations. For a moredetailed description of SMAC, we refer to [15].

{2, . . . , 5,
3 Special, 5 Special}

5{Default, 4, . . . , 10}Move Type + Patching A+Patching B − 1

Patching A{1, 2,
1 Restricted, 2 Restricted,
1 Extended, 2 Extended}1

Patching C{0, . . . , 2,
0 Restricted, . . . , 2 Restricted,
0 Extended, . . . , 2 Extended}0

B. Per-Instance Algorithm Configuration{0, . . . , 10}0Contrary to the full-set algorithm configuration, PIAC aims
to find an optimal policy πθ∗ ∈ Π with learnable weights θthat outputs for every instance i ∈ I an optimal configuration
λ∗i ∈ Λ, individually. Formally, one can define the policy asπθ : I → Λ. Hence, the overall goal can be defined as finding
1X
PQR10 (LKHπθ (i) , i).
πθ∗ = arg minπθ ∈ΠnMove Type
Nonsequential
Move Type

Population Size

one another on the novel dataset as well as standard test setsfrom the literature.
A. Full-set Algorithm Configuration
The parameter space Λ of LKH holds all possible parameter configurations λ, which is the Cartesian product over all
the individual parameters – described in Table I, excluding
possible constraints on different parameter combinations.
Given a set I of n instances with |I| = n the goal of full-set
AAC [28] is to find one optimal configuration λ∗ ∈ Λ thatminimizes the aggregated PQR10 score, i.e. formally1X
λ∗ = arg minλ∈Λ
PQR10 (LKHλ , i).
ni∈IThe notation PQR10 (LKHλ , i) means that the PQR10score is measured over multiple runs of LKH with j random
seeds and configuration λ on instance i ∈ I. In this work, thegoal is to minimize the mean PQR10 score over all instances.
We use SMAC [15] as state-of-the-art in this domain to findthe best global configuration. SMAC alternates between twophases; intensification and Bayesian optimization (BO).
During intensification, new configurations are iteratively
evaluated on instances and compared against the incumbent,i∈I

In our case, πθ is learned by a deep learning model.
Therefore, we train a policy model with learnable weights
θ that – in its ideal case – predicts πθ∗ : i → λ∗i given any
instance i. Further, we consider two different scenarios: (1)the policy model takes tabular TSP-features as input (samefeatures as for SMAC) (feature-based), and (2) the policy
model takes the raw instance as input (feature-free) (seeFigure 4). More on this will be discussed in Chapter III-B.
In total, we consider 1 140 480 possible different discrete configurations, and one additional parameter, Excess,which is continuous (see Table I). Therefore, it is impossible
to test every single feasible configuration on every instanceto create a reliable training dataset but instead, we rely on
reinforcement learning (see Figure 4). We tested different
strategies and we found that Proximal Policy Optimization (PPO) [29] works best for our setting. We use the loss
function L as defined by the authors. In most reinforcement
settings, a roll-out or run consists of multiple time-steps. In

364
4Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

GPU Node:
Raw Coords.
xor

DL ModelTSP-Features

Worker:Update model

ComputePQR10 Score

Config:Excess: 0.1973
GAIN23: YES
MOVE_TYPE: 4 SP.
POP_SIZE: 7

Use predicted config

Execute LKH

Repeat with j random seeds

Fig. 4. The reinforcement learning process with distributed workers.
First, the GPU node takes one training instance and predicts the “best”
configuration. Afterward, the configuration and instance are sent to one freeworker, where the instance is solved j times with j different seeds by LKH.
Last, the PQR10-score is computed to update the model. Note: the DL model
can be feature-free or feature-based.

our scenario, we do not have any time-steps as we consider
the optimization process of LKH as a single time-step. Hence,
we can simplify the loss function toL(θ) = −1 · min r(θ) · Âi , clip (r(θ), 0.8, 1.2) · Âi (1)r(θ) =πθ (λ∗i | i).
πold (λ∗i | i)(2)Here, r is the ratio between the current policy πθ and theold policy πold . The clipping function prevents from moving
too quickly toward a promising policy. We used the default
clipping parameters (0.8 as lower and 1.2 as upper boundary)as proposed in [29]. Next, Â is the advantage defined as
Âi = Bi − Rπi ,iwhere Rπi ,i = PQR10 (LKHπθ (i) , i) and Bi =PQR10 (LKH, i) with the default configuration. In otherwords, the advantage measures the absolute benefit of thecurrent policy πθ compared to the default configuration. πold
is the old policy that was used previously to determine
PQR10 (LKHπ(i) , i). Note, that sampling a new configuration from πθ and updating the parameters θ are two different
processes.
In most Actor-Critics-based [30] reinforcement learning
approaches, the baseline (usually referred to as V ) is learned
and predicted by the model. In our scenario, however, Bi is
the PQR10 score of the default configuration on instance i
which is stable and does not need to be learned by the model.
Hence, we only consider an Actor in our setting.
IV. E XPERIMENTS
A. Experimental set-up for SMAC
For the full-set configuration, we performed 15 independent, randomly seeded runs of SMAC3 [31], with each awall time budget of 24h and 8 parallel workers. We used the
AlgorithmConfigurationFacade in SMAC3, whichclosely follows the described procedure in [15]. Only the
proportion of wall time budget for finding new configurations
was set to 30% instead of 50%. We uniformly at random

sampled 5 000 instances — which are 6.67% of all training
instances — without replacement from the training set to
reduce the computational load for predicting the PQR10 over
all instances in the BO phase of SMAC. The surrogate model
uses pre-computed tabular instance features to improve its
predictive performance. From the 15 resulting incumbent
configurations, we selected the configuration with the lowest
PQR10 score after evaluating them on all 5 000 instances.
In total, 6 906 different configurations were consideredand 150 202 times a configuration was evaluated. The final
incumbents were on average evaluated on 191 instances.
B. Experimental set-up for Reinforcement Learning
For the two per-instance configuration approaches (featurebased and feature-free), we used 500 distributed workers
with a maximum wall time of 24h each (see Figure 4 for avisualization of the distributed training process). The modeland its learnable weights θ are located on a single server
called the GPU Node. During training and also validation,
the GPU Node takes a random instance i from the training or
validation set and applies the model with the current policyπθ to receive a configuration λ∗i . The tuple (i, λ∗i ) is sent
to a free worker which then applies LKH with j random
seeds (j sampled from {1, . . . , 10}) and configuration λ∗i on
instance i. The worker then may need up to 20 minutes todetermine Rπi ,i — in the case of j = 10 and ten timeouts.
πold are stored at the GPU Node for later use. Afterwards,
the worker will send Rπi ,i to the GPU node were the set
Bi := {i, πold , (Rπi ,i )} is stored in a replay buffer. For
training, a batch is sampled from the replay buffer to update
the current policy πθ using the process described in Chapter
III-B.
We used a Multi-Layer Perceptron (MLP) with a ResNetlike [32] structure for the feature-based model (see Figure 5,a). The model receives all 167 standard TSP features (zstandardized based on the training set) as input [9]–[11].
As 21 features contain missing values, we performed mean
imputation for these features and added 21 additional featuresthat indicate whether a missing value was imputed. In total,
the MLP model received 188 input features. Further, the MLP
model consists of twelve ResNet layers with 576 hiddenfeatures. Two fully-connected layers with also 576 hiddenfeatures are used as the model’s stem. Last, we used theGated Linear Unit (GLU) [33] as the activation function
throughout the model. As the GLU activation requires two
neurons per output feature, we doubled the number of hidden
neurons to 1 152 which is then reduced to 576 by the GLU
activation.
For the feature-free model, we used a Transformer-basedarchitecture very similar to [19] but with additional FeedForward layers after the Multi-Head Attentions (see Figure 5b). Further, we pre-trained the model on the training instancesby masking randomly some of the k-Nearest-Neighbor clusters of the embedding layer. The pre-training helps the model
to pre-learn some important characteristics of TSP instances.

365
5
Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

×9

LayerNorm

Linear + GLU+

Avg. PoolingLinear + Dropout

LayerNorm+

Linear + GLU

MHA

Move_Type

LayerNorm

Gain23

LinearxLinear + GLU

ExcessLinearLinear + GLU

LinearkNN Embedding

LayerNorm+

Linear + GLU

Linear + Dropout

LayerNorm

Linear + GLU

Linear + GLU

Linear + GLU

xLinearExcessLinearGain23

LinearMove_Type

×6

a)

b)

Fig. 5. This Figure illustrates the two used deep learning topologies: a) shows the feature-based approach, that takes the numerical TSP-features as input,
with nine ResNet-blocks. b) is a feature-free approach, that only takes raw coordinates as input, with six Multi-head Attention and Feed-Forward blocks.

The last layer consists of multiple fully-connected layers— one for every parameter. If the parameter is categorical,
the corresponding layer has one neuron per category anda LogSoftmax as the activation function. The outputs are
the log probabilities which can be used directly in Equation (2) to compute the ratio. For continuous parameters,
the corresponding layer contains two output neurons with
Softplus activation — one for the alpha and one for thebeta of a Beta distribution as it is proposed in [34]. The
Beta distribution has two nice properties: 1) it is bounded to[0, 1] and can, hence, be scaled to any other range with afinite upper and lower bound, and 2) the probability functionof a beta distribution can have a variety of different shapes— ranging from bathtub-like shapes to normal-like or loglike shapes. The log probabilities for continuous parameters
are calculated as outlined in [34]. Further, we used linear
scaling of the search space with a lower bound of 10 1000
and upper bound of 1 — exactly the same upper and lower
bound as it was used for SMAC. Yet, we did not log10 -scale
the search space as we found that this decreases the training
performance of the deep learning models.
During training, the algorithm samples from the output
distributions. This guarantees the exploration of different
policies. However, during evaluation, the maximum of thelog probability for categorical parameters is used, and themean of the Beta-distribution for continuous parameters.
This ensures a deterministic behavior of the model during
validation.
Last, we used Adam with Weight Decay (AdamW) [35]with a learning rate of 1e−4, a batch size of 64, and a replay
buffer size of 8 192 as it is commonly done. We found that
two LKH runs in the first epoch are sufficient to train themodel as the model predicts mostly random configurations.
Yet, when the model becomes more sophisticated in its
decisions, one has to increase the number of LKH runs toperform more accurate updates. We found that training withmore than five runs does not yield any benefits. Therefore,
the sweat-spot between training speed and accurate updates
are j = 2 in the first epoch and j = 5 for all others.
V. R ESULTS & D ISCUSSION
Table II presents the mean PQR10 scores and timeout percentage of the default configuration, the static configuration
obtained with SMAC, and our two RL-based PIAC methods;
MLP (feature-based) and Transformers (feature-free). For

each dataset, all approaches are robustly ranked, i.e., ranked
with statistical guarantees [36]. The robust ranking works
as follows; For each instance set, multiple replicas (10 000)
are created using resampling. Over these resulting bootstrap
samples the average PQR10 scores are computed and theapproach which scored best in most of the bootstrap samples
is ranked first. Then, all approaches that are not significantly
worse (with α = 0.05) are also ranked first. The procedurecontinues with the remaining approaches until all approaches
are assigned a rank.
For the feature-based PIAC approach (MLP), we provide
the results including feature costs. The costs reflect the timethat is required to compute the TSP-features for an instance athand. Note, that we do not include the runtime of the deeplearning models themselves. We found it to be impossible
in the current state to compare deep learning models thatare optimized to be executed on GPUs with the runtimeof LKH that is optimized to be executed on a single CPU
core. However, there is a lot of research into reducing andsimplifying trained deep learning models such that thesecomplex models can be efficiently executed on small devices
like mobile phones or even micro-controllers. Yet, we argue
that these topics are out of scope for this paper and leavethat for feature work.
In Table II it becomes evident that all used approaches
clearly improve the baseline performance of LKH withdefault configuration. This demonstrates that there is a huge
potential for optimizing the LKH and making it more competitive to other optimizers. Next, our Transformer outperforms or, at least, achieves compatible performance to theother approaches in all categories. Interestingly, all AAC
and PIAC approaches as well as the default configuration
are statistically tied to one another for RUE instances. We
assume that different configurations have little impact on theperformance as the random-uniform nature of these instances
does not provide any structures that can be exploited bydifferent configurations.
On one hand, this is surprising as SMAC achieves stateof-the-art performance in most AAC settings. On the other
hand, it is expected for PIAC approaches to (theoretically)
achieve better performance in comparison to set-based AAC
as PIAC approaches can select from the whole configuration
space while SMAC only outputs a single configuration for
the whole set. However, PIAC training is especially difficult
when the configuration space is large or even infinite.

366
6
Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

101

100

10−1
10−1

100

101

102

103

102

101

100

10−1
10−1

101

100

Default (PQR10)

102

102

101

100

10−1
10−1

103

103

Transformers (PQR10)

102

103

Transformers (PQR10)

103

MLP w/ Costs (PQR10)SMAC (PQR10)

103

a)

101

100

Default (PQR10)

102

103

102

101

100

10−1
10−1

Default (PQR10)b)NetgenMorphedRUE
National
TSPLib
VLSI

100

101

102

103

SMAC (PQR10)c)d)Fig. 6. Runtime comparison between different AAC approaches and the default LKH configuration (a-c). d) Runtime comparison between SMAC andthe transformer approach. The equilibrium line (dotted in orange) symbolizes an equal performance between the two approaches while instances above(below) the equilibrium line indicate a better (worse) performance of the approach plotted on the x-axis the one on the y-axis.
TABLE IIR ESULTS SO FAR . M EAN PQR10 FOR DIFFERENT INSTANCE GROUPS AND RELATIVE TIMEOUT (T/ O ) SCORES . A S T/ O ARE COUNTED PQR10 SCORESTHAT ARE 1 200. T HE ROBUST RANK IS SHOWN IN BRACKETS . I F TWO ALGORITHMS ARE IN THE SAME RANK , THEY ARE STATISTICALLY TIED .
Instance Set#Cities#Instances

Default Config
PQR10
T/o

SMAC
PQR10

T/o

MLP w/ Costs
PQR10
T/o

Transformer
PQR10
T/o

Validation

2 000

25 000342.51 (4)27.1%

257.44 (2)19.9%

287.76 (3)22.1%

228.74 (1)17.5%

NetgenNetgenNetgenNetgen

500
1 000
1 500
2 000

150
150
150
150

77.49 (3)180.25 (2)283.89 (3)464.04 (3)

6.0%
14.0%
22.0%
36.7%

5.32 (2)41.85 (1)140.67 (1)235.85 (1)

0.0%
2.7%
10.0%
17.3%

143.53 (4)139.80 (2)193.49 (2)311.84 (2)

11.3%
10.7%
14.7%
24.0%

3.37 (1)31.40 (1)134.68 (1)215.51 (1)

0.0%
2.0%
10.0%
16.0%

Netgen(All)

600

251.42 (3)19.7%

105.92 (1)7.5%

197.17 (2)15.2%

96.24 (1)7.0%MorphedMorphedMorphedMorphed

500
1 000
1 500
2 000

150
150
150
150

37.20 (3)151.11 (2)347.82 (3)481.36 (2)

2.7%
11.3%
27.3%
38.0%

19.09 (2)139.98 (2)213.47 (2)331.04 (1)

1.3%
10.7%
16.0%
25.3%

205.70 (4)147.25 (2)172.56 (1)290.03 (1)

16.7%
11.3%
12.7%
22.0%

2.55 (1)82.62 (1)
163.58 (1)308.29 (1)

0.0%
6.0%
12.0%
24.0%

Morphed

(All)

600

254.37 (3)19.8%

175.89 (2)13.3%

203.89 (2)15.7%

139.26 (1)

10.5%

RUE
RUE
RUE
RUE

500
1 000
1 500
2 000

150
150
150
150

9.13 (2)86.25 (2)156.48 (1)339.52 (1)

0.7%
6.7%
12.0%
26.7%

0.68 (1)22.55 (1)
141.27 (1)337.18 (1)

0.0%
1.3%
10.7%
26.7%

0.99 (2)48.12 (1)161.56 (1)343.10 (1)

0.0%
3.3%
12.0%
26.7%

0.63 (1)36.98 (1)132.95 (1)345.60 (1)

0.0%
2.7%
10.0%
27.3%

RUE

(All)

600

147.84 (1)11.5%

125.42 (1)9.7%

138.44 (1)10.5%

129.04 (1)10.0%

National 734-1 979
TSPLib 574-1 889
VLSI
662-1 973

521
1713.60 (2)182.59 (3)216.35 (2)

0.0%
14.3%
17.6%

6.17 (1)66.44 (2)144.18 (2)

0.0%
4.8%
11.8%

4.52 (1)120.84 (2)214.27 (2)

0.0%
9.5%
17.6%

8.85 (1)62.80 (1)77.02 (1)

0.0%
4.8%
5.9%

Real World

(All)

43

176.29 (3)14.0%

90.16 (2)7.0%

144.25 (2)11.6%

62.15 (1)

4.7%

Test Set

(All)

1843

216.91 (4)16.9%

134.68 (2)10.1%

179.00 (3)13.7%

120.13 (1)9.1%

Next, the MLP without including feature costs provides
comparable performance in most categories. However, when
including the feature costs in the runtime, the performance ofthe same model becomes noticeably weaker — demonstrating
again the need to investigate the potential of feature-free AAS
and AAC also in other domains.
Last, we found that most of the performance gain is to
the reduced number of timeouts. This is especially true for
SMAC as the instances above and below the equilibriumline in Figure 6 a) are similarly distributed. However, inFigure 6 c-d) it becomes evident, that the PIAC approaches
not only decrease the number of timeouts but also predict
configurations that improve the runtime in comparison to thedefault configuration and also SMAC as many instances are
below the equilibrium line.
VI. C ONCLUSION & O UTLOOK

direction for future work. The same holds for applying ourapproaches to other AI domains where AAC has an impact,
like SAT and MIP solving, in order to – ideally – advance
those fields further and to gain more insights into how RLbased PIAC performance generalizes. One limitation of thecurrent implementation of our PIAC pipeline is that there isa discrepancy between the hardware for the neural networkthat infers the configuration (one GPU) and the LHK solver(one CPU-core). Composing and evaluating a kindred PIAC
pipeline is possible, but requires a thorough analysis of how
the NNs should be efficiently transferred (using compilation,pruning, and distillation), which we consider to be out of
scope for this paper. The value of the cutoff has a large
influence on the measured mean performance of solvers [12].
To overcome this, a multi-objective approach to configuration
can be explored where the expectancy to solve an instanceis set out against the actual running time.

Our RL-based PIAC approaches have shown their ability
to improve the performance of LKH. Applying them toother TSP solvers, such as EAX, would be an interesting

Another contribution is the TSP World-based benchmark
set that we used to fit our policies. Besides making thisbenchmark suite available to the community, we are also

367
7
Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.

planning to provide an instance generator to produce arbitrarily many different TSP instances that are measurably diverse,
but also of varying size. The latter is particularly of interest
when investigating how PIAC approaches are able to respondto the scaling of instances.
To conclude, we created a novel and highly diverse dataset
for training and benchmarking TSP solvers. Further, we propose two novel deep reinforcement-based PIAC approaches,feature- and feature-free, that can clearly outperform current
AAC approaches. The innovation of these approaches lies
especially within the fact that our proposed methods canselect from the full configuration space and are not limited
to a pre-defined set of configurations.
R EFERENCES[1] D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The
Traveling Salesman Problem: A Computational Study, Princeton, NJ,
USA, 2007.
[2] R. Radharamanan and L. Choi, “A branch and bound algorithm
for the travelling salesman and the transportation routing problems,”
Computers & Industrial Engineering, vol. 11, no. 1, 1986.
[3] Y. Nagata and S. Kobayashi, “A Powerful Genetic Algorithm Using
Edge Assembly Crossover for the Traveling Salesman Problem,”
INFORMS Journal on Computing, vol. 25, no. 2, 2013.
[4] K. Helsgaun, “An effective implementation of the Lin–Kernighan traveling salesman heuristic,” European Journal of Operational Research,
vol. 126, no. 1, 2000.
[5] J. Dubois-Lacoste, H. H. Hoos, and T. Stützle, “On the Empirical
Scaling Behaviour of State-of-the-art Local Search Algorithms for the
Euclidean TSP,” in Proc. of the Genetic and Evolutionary Computation
Conference, ser. GECCO’15, 2015.
[6] S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, and H. Trautmann, “Evaluation of a multi-objective ea on benchmark instances for
dynamic routing of a vehicle,” in Proc. of the Genetic and Evolutionary
Computation Conference, ser. GECCO’15, 2015.
[7] P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann,“Leveraging TSP Solver Complementarity through Machine Learning,”
Evolutionary Computation (ECJ), vol. 26, no. 4, 2018.
[8] P. Kerschke, H. H. Hoos, F. Neumann, and H. Trautmann, “AutomatedAlgorithm Selection: Survey and Perspectives,” Evolutionary Computation (ECJ), vol. 27, no. 1, 2019.
[9] O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, and
F. Neumann, “Local Search and the Traveling Salesman Problem: A
Feature-Based Characterization of Problem Hardness,” in Proc. of the
6th International Conference on Learning and Intelligent Optimization(LION), vol. 7219, January 2012.
[10] F. Hutter, L. Xu, H. H. Hoos, and K. Leyton-Brown, “Algorithm
Runtime Prediction: Methods & Evaluation,” Artificial Intelligence
Journal (AIJ), vol. 206, 2014.
[11] J. Pihera and N. Musliu, “Application of machine learning to algorithm
selection for TSP,” in 26th IEEE International Conference on Tools
with Artificial Intelligence, ICTAI 2014, 2014.
[12] J. Bossek, P. Kerschke, and H. Trautmann, “Anytime behavior of
inexact tsp solvers and perspectives for automated algorithm selection,”in Proc. of the IEEE Congress on Evolutionary Computation (CEC),
Glasgow, UK, 2020.
[13] J. Styles and H. H. Hoos, “Using Racing to Automatically Configure
Algorithms for Scaling Performance,” in Learning and Intelligent
Optimization, G. Nicosia and P. Pardalos, Eds. Berlin, Heidelberg:
Springer Berlin Heidelberg, 2013, vol. 7997.
[14] J. Rasku, N. Musliu, and T. Kärkkäinen, “On automatic algorithm
configuration of vehicle routing problem solvers,” Journal on Vehicle
Routing Algorithms, vol. 2, no. 1-4, Dec. 2019.
[15] F. Hutter, H. H. Hoos, and K. Leyton-Brown, “Sequential Model-Based
Optimization for General Algorithm Configuration,” in Proc. of the
5th International Conference on Learning and Intelligent Optimization(LION), 2011, vol. 6683.
[16] S. Adriaensen, A. Biedenkapp, G. Shala, N. Awad, T. Eimer, M. Lindauer, and F. Hutter, “Automated Dynamic Algorithm Configuration,”
Journal of Artificial Intelligence Research, vol. 75, Dec. 2022.

[17] L. Xu, H. Hoos, and K. Leyton-Brown, “Hydra: Automatically Configuring Algorithms for Portfolio-Based Selection,” Proc. of the AAAI
Conference on Artificial Intelligence, vol. 24, Jul. 2010.
[18] Y. Malitsky and M. Sellmann, “Instance-specific algorithm configuration as a method for non-model-based portfolio generation,” in Proc.
of the 9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization
Problems, ser. CPAIOR’12, 2012.
[19] M. V. Seiler, R. P. Prager, P. Kerschke, and H. Trautmann, “A collection of deep learning-based feature-free approaches for characterizing
single-objective continuous fitness landscapes,” in Proc. of the Genetic
and Evolutionary Computation Conference, ser. GECCO’22, 2022.
[20] M. Seiler, J. Pohl, J. Bossek, P. Kerschke, and H. Trautmann, “Deeplearning as a competitive feature-free approach for automated algorithm selection on the traveling salesperson problem,” in International
Conference on Parallel Problem Solving from Nature. Springer, 2020.
[21] J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke,“A study on the effects of normalized tsp features for automatedalgorithm selection,” Theoretical Computer Science, vol. 940, 2023.
[22] J. Bossek and H. Trautmann, “Evolving Instances for Maximizing
Performance Differences of State-of-the-Art Inexact TSP Solvers,” inProc. of the 10th International Conference on Learning and Intelligent
Optimization (LION), vol. 10079 LNCS, Ischia, Italy, 2016.
[23] R. Sinott, “Virtues of the haversine,” Sky and Telescope, vol. 68, 1984.
[24] J. Bossek, salesperson: Computation of Instance Features and R
Interface to the State-of-the-Art Exact and Inexact Solvers for theTraveling Salesperson Problem, 2017, R package version 1.0.0.
[25] J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke,“On the potential of normalized tsp features for automated algorithm
selection,” in Proc. of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI), 2021.
[26] P. Kerschke, J. Bossek, and H. Trautmann, “Parameterization of stateof-the-art performance indicators: A robustness study based on inexact
TSP solvers,” in Proc. of the Genetic and Evolutionary Computation
Conference Companion, Jul. 2018.
[27] J. Bossek and H. Trautmann, “Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected Running Time,” inProc. of the 12th International Conference on Learning and Intelligent
Optimization (LION), vol. 11353, Kalamata, Greece, 2019.
[28] H. H. Hoos, “Automated algorithm configuration and parameter tuning,” in Autonomous Search, 2012.
[29] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov,“Proximal policy optimization algorithms,” arXiv preprint
arXiv:1707.06347, 2017.
[30] A. G. Barto, R. S. Sutton, and C. W. Anderson, “Neuronlike adaptive
elements that can solve difficult learning control problems,” IEEE
transactions on systems, man, and cybernetics, no. 5, 1983.
[31] M. Lindauer, K. Eggensperger, M. Feurer, A. Biedenkapp, and
D. Deng, “SMAC3: A Versatile Bayesian Optimization Package forHyperparameter Optimization,” Journal of Machine Learning Research, vol. 23, 2022.
[32] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image
recognition,” in Proc. of the IEEE conference on computer vision andpattern recognition, 2016.
[33] Y. N. Dauphin, A. Fan, M. Auli, and D. Grangier, “Language modelingwith gated convolutional networks,” in International conference on
machine learning. PMLR, 2017.
[34] I. G. Petrazzini and E. A. Antonelo, “Proximal policy optimization
with continuous bounded action space via the beta distribution,” in2021 IEEE Symposium Series on Computational Intelligence (SSCI).
IEEE, 2021.
[35] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,”in 7th International Conference on Learning Representations, ICLR
2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[36] C. Fawcett, M. Vallati, H. H. Hoos, and A. E. Gerevini, “Competitionsin AI – Robustly Ranking Solvers Using Statistical Resampling,” Aug.
2023.

368
8
Authorized licensed use limited to: UNIVERSITY OF TWENTE.. Downloaded on January 04,2024 at 10:00:33 UTC from IEEE Xplore. Restrictions apply.