by Alberto Franzin and Thomas Stützle
2018
| Table of Contents |
Simulated Annealing (SA) is one of the oldest metaheuristics and has
been adapted to solve many combinatorial optimization problems.
Over the years, many authors have proposed both general and
problem-specific improvements and variants of SA. We propose to
accumulate this knowledge into automatically configurable,
algorithmic frameworks so that for new applications that wealth of
alternative algorithmic components is directly available for the
algorithm designer without further manual intervention. To do so, we
describe SA as an ensemble of algorithmic components, and describe
SA variants from the literature within these components. We show
the advantages of our proposal by
(i) implementing existing algorithmic components of variants of SA,
(ii) studying SA algorithms proposed in the literature, (iii)
improving SA performance by automatically designing new
state-of-the-art SA implementations and (iv) studying the role and
impact of the algorithmic components based on experimental data. We
experimentally demonstrate the potential of this approach on three
common combinatorial optimization problems, the quadratic assignment
problem and two variants of the permutation flow shop problem.
Keywords: Simulated Annealing; Metaheuristics; Automatic Algorithm Design; Automatic Algorithm Configuration; Empirical Analysis.
PDF.
QAP training set (4.4 MB) and testing set (4.4 MB). In each archive there are 150 random instances and 150 structured instances, equally divided in instances of size 60, 80, 100 taken from IridiaSupp2010-009.
PFSP training set (260 KB) and testing set (404 KB). The test set is the common Taillard benchmark.
The list of parameter definitions, formatted as irace parameter file and including names, type and range for all the components and numerical parameters of this work, is available here.