Automated Design of Algorithms

Thomas Stützle

Manuel López-Ibáñez

stuetzle@ulb.ac.be
http://iridia.ulb.ac.be/∼stuetzle

manuel.lopez-ibanez@manchester.ac.uk
http://lopez-ibanez.eu

IRIDIA, CoDE, ULB,Brussels, Belgium

University of Manchester, UK

Part I
Automatic Algorithm Configuration(Overview)

Manuel López-Ibáñez and Thomas Stützle

Solving complex optimization problems
The algorithmic solution of hard optimization problems
is one of the CS/OR success stories!
Exact (systematic search) algorithms
branch&bound, branch&cut, constraint programming, . . .
guarantees of optimality but often time/memory consuming
powerful general-purpose software available

Approximation algorithms
heuristics, local search, metaheuristics, hyperheuristics . . .
rarely provable guarantees but often fast and accurate
typically special-purpose software

Automated Offline Design of Algorithms

Design choices and parameters everywhere
Modern high-performance optimizers involve a large
number of design choices and parameter settings

Exact solvers
Design choices: alternative models, pre-processing, variableselection, value selection, branching rules . . .
+ numerical parameters
SCIP solver: more than 200 parameters that influence search(Meta)-heuristic solvers
Design choices: solution representation, operators, neighborhoods,
pre-processing, strategies, . . . + numerical parameters
Multi-objective ACO algorithms with 22 parameters (see part 2)

Very active research on hybrids of exact/approximate algorithms!
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

ACO, Probabilistic solution construction

Applying Ant Colony Optimization

g

j

?

! ij , " ijikManuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

ACO design choices and numerical parameters

Automated Offline Design of Algorithms

Parameter types
categorical parameterssolution construction
choice of constructive procedure
choice of pheromone model
choice of heuristic information
numerical parametersα, β influence the weight of pheromone and heuristic
information, respectively
q0 determines greediness of construction procedurem, the number of ants

pheromone update
which ants deposit pheromone and how much?
numerical parameters
ρ: evaporation rate
τ0 : initial pheromone level

local search

designchoice of constructive procedure, choice of recombination
operator, choice of branching strategy,. . .

ordinal parameters

designneighborhoods, lower bounds, . . .

numerical parameters

tuning, calibration

integer or real-valued parameters
weighting factors, population sizes, temperature, hidden
constants, . . .

Parameters may be conditional to specific values of otherparameters
Configuring algorithms involves setting
categorical, ordinal and numerical parameters. . . many more . . .
Manuel López-Ibáñez and Thomas Stützle

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Towards more systematic approaches

Towards automatic algorithm configuration

Traditional approaches
Trial–and–error design guided by expertise/intuition
8 prone to over-generalizations, limited exploration of design
alternatives, human biases

Guided by theoretical studies
8 often based on over-simplifications, specific assumptions,few parameters

Automatic algorithm configuration
apply powerful search techniques to design algorithms
use computation power to explore algorithm design spaces
free human creativity for higher level tasks

Can we make this approach more principled and automatic?

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Offline configuration

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

AC is a stochastic optimization problem
Decision variables
discrete (categorical, ordinal, integer) and continuous
Stochasticityof the target algorithmof the problem instances
Typical tuning goals
maximize solution quality within given timeminimize run-time to decision / optimal solution
AC requires specialized methods

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Methods for Automatic Algorithm Configuration
experimental design, ANOVACALIBRA [Adenso-Dı́az & Laguna, 2006]
others [Coy et al., 2001; Ridge & Kudenko, 2007; Ruiz & Maroto, 2005]

ParamILS Framework[Hutter et al., 2007b, 2009]

ParamILS is an iterated local search method that works
in the parameter space
perturbation

numerical optimization
MADS [Audet & Orban, 2006], CMA-ES, BOBYQA [Yuan et al., 2012]

model-based
SPO [Bartz-Beielstein et al., 2005, 2010b], SMAC [Hutter et al., 2011]
sequential statistical testing
F-race, iterated F-race [Balaprakash et al., 2007; Birattari et al., 2002]
irace [López-Ibáñez et al., 2011]
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Main design choices for ParamILSParameter encoding: only categorical parameters,
numerical parameters need to be discretized
Initialization: select best configuration among default and several
random configurations
Local search:

1-exchange neighborhood, where exactly one
parameter changes a value at a timeneighborhood is searched in random order

Perturbation: change several randomly chosen parameters
Acceptance criterion: always select the better configuration

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

s’
cost

heuristic optimization
meta-GA [Grefenstette, 1986], ParamILS [Hutter et al., 2007b, 2009],
gender-based GA [Ansótegui et al., 2009], linear GP [Oltean, 2005],
REVAC(++) [Nannen & Eiben, 2006; Smit & Eiben, 2009, 2010] . . .

s*

s*’

solution space S
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Main design choices for ParamILS

Evaluation of incumbent
BasicILS: each configuration is evaluated on thesame number of N instances
FocusedILS: the number of instances on which thebest configuration is evaluated increases at run time(intensification)
Adaptive Capping
mechanism for early pruning the evaluation ofpoor candidate configurations
particularly effective when configuring algorithms forminimization of computation time

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The danger of over-tuning

Applications of ParamILS

4

x 10
6

BasicILS(1)Runlength (median)

5.5

SAT-based verification [Hutter et al., 2007a]

5

SPEAR solver with 26 parameters⇒ speed-ups of up to 500 over default configuration

4.5
4Configuration of commercial MIP solvers [Hutter et al., 2010]

BasicILS(10)3.5

CPLEX (63 parameters), Gurobi (25 parameters) and lpsolve(47 parameters) for various instance distributions of MIP
encoded optimization problems

BasicILS(100)3

FocusedILS

2.5
2 −2
10

speed-ups ranged between a factor of 1 (none) to 153
0

10

2

10
CPU time [s]

4

10

6

10

example: comparison of BasicILS and FocusedILS for configuring
the SAPS solver for SAT-encoded quasi-group with holes, takenfrom [Hutter et al., 2007b]
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Numerical optimization techniques
MADS / OPAL
Mesh-adaptive direct search applied to parameter tuning ofother direct-search methods [Audet & Orban, 2006]
later extension to OPAL (OPtimization of ALgorithms)
framework [Audet et al., 2010]
Limited experiments
Other continuous optimizers [Yuan et al., 2012, 2013]
study of CMAES, BOBYQA, MADS, and irace for tuning
continuous and quasi-continuous parameters
BOBYQA best for few parameters; CMAES best for many

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Model-based Approaches (SPOT, SMAC)
Idea: Use surrogate models to predict performance
Algorithmic scheme
1: generate and evaluate initial set of configurations Θ0
2: choose best-so-far configuration θ ∗ ∈ Θ0
3: while tuning budget available do4:learn surrogate model M : Θ 7→ R
5:generate set of possible candidate configurations Θ
6:
use model M to filter promising configurations Θp ⊆ Θ
7:evaluate configurations in Θp8:
Θ0 : = Θ0 ∪ Θp
9:
update θ ∗ ∈ Θ0
10: output: θ ∗post-selection mechanism appears promising
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Sequential parameter optimization (SPO) toolbox

Sequential model-based algorithm configuration (SMAC)[Bartz-Beielstein et al., 2005, 2010b][Hutter et al., 2011]

Main design decisions
Gaussian stochastic processes for M (in most variants)
Expected improv. criterion (EIC) ⇒ promising configurations
Intensification mechanism ⇒ increase num. of evals. of θ ∗SMAC extends surrogate model-based configuration to complex
algorithm configuration tasks and across multiple instances
Main design decisions
Random forests for M ⇒ categorical & numerical parameters
Aggregate predictions from Mi for each instance i

Practicalities
SPO is implemented in the comprehensive SPOT R package

Local search on the surrogate model surface (EIC)⇒ promising configurations

Most applications to numerical parameters on one instance

Instance features ⇒ improve performance predictions

SPOT includes various analysis and visualization tools

Intensification mechanism (inspired by FocusedILS)
Further extensions ⇒ capping

Manuel López-Ibáñez and Thomas Stützle

The racing approach

Automated Offline Design of Algorithms[Birattari et al., 2002]

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The racing approach[Birattari et al., 2002]

Θ0
How to discard?
start with a set of initial candidates
consider a stream of instances

Statistical testing!

sequentially evaluate candidates
discard inferior candidates
as sufficient evidence is gathered against them

. . . repeat until a winner is selected

F-Race: Friedman two-way analysis of variance by ranks+ Friedman post-hoc test [Conover, 1999]

or until computation time expires

Instances

Alternative: paired t-test with/without p-value correction(against the best)

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Sampling configuration

What is Iterated Racing and irace?

Iterated Racing (irace)

F-race is a method for the selection of the best
among a given set of algorithm configurations Θ0 ⊂ Θ
1A variant of I/F-Race with several extensions
I/F-Race proposed by Balaprakash, Birattari, and Stützle [2007]

How to sample algorithm configurations?

Refined by Birattari, Yuan, Balaprakash, and Stützle [2010]

Full factorial

Further refined and extended by López-Ibáñez, Dubois-Lacoste,Stützle, and Birattari [2011]

Random sampling
Iterative refinement of a sampling model⇒ Iterated F-Race (I/F-Race) [Balaprakash et al., 2007]

Elitist variant proposed by López-Ibáñez, Dubois-Lacoste, PérezCáceres, Stützle, and Birattari [2016]
2

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Iterated Racing

A software package implementing the latest variants.

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Iterated Racing

Iterated Racing ⊇ I/F-Race2

Selecting the best configurations from the newly sampled
ones by means of racing

3

Updating the probability distribution in order to bias the
sampling towards the best configurations{

0.4

Sampling new configurations according to a probability
distribution

0.0

0.2

1

x2

x3

{

0.0

0.2

0.4

x1

x1

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithmsx2x3

Iterated Racing: Sampling distributions

Iterated Racing: Elitist Iterated Racing [López-Ibáñez et al., 2016]

Numerical parameter
Xd ∈ [ x d , x d ]⇒ Truncated normal distribution

8 irace may “lose” the best-so-far configuration⇒ Each new iteration (race) forgets the results of theprevious one

N (µzd , σdi ) ∈ [x d , x d ]4 Protect the best configurations (elites) from being discarded
unless all their results are consideredµzd = value of parameter d in elite configuration z

Categorical parameter
Xd ∈ {x1 , x2 , . . . , xnd }⇒ Discrete probability distribution
Prz {Xd = xj } =

x1
0.1

x2
0.3

...
...

1

after race i, elites were evaluated in Ie instances

2

race i + 1 will start with Inew ∪ Ie instances3

irace remembers the values of the elites on Ie

4elites can only be discarded after alive configurations areevaluated on at least all Inew ∪ Ie

0.0

0.2

0.4

σdi = decreases with the number of iterations

x1

x2

xnd
0.4

x3

(similar to ParamILS’s domination concept, but more strict)Updated by increasing probability of parameter value in elite configuration
Other probabilities are reduced
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

0.4
0.2
0.0

x2

x3

Automated Offline Design of Algorithms

Iterated Racing: Elitist Iterated Racing [López-Ibáñez et al., 2016]

{

0.0

0.2

0.4

x1

non-elites are discarded as usual
Manuel López-Ibáñez and Thomas Stützle

Iterated Racing: Elitist Iterated Racing [López-Ibáñez et al., 2016]

{

5

x1

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

x2

x3

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The irace Package

The irace Package: version 2.3

Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres,Thomas Stützle, and Mauro Birattari.
The irace package: Iterated Racing for Automatic Algorithm Configuration.
Operations Research Perspectives, 3:43–58, 2016. doi:10.1016/j.orp.2016.09.002
http://iridia.ulb.ac.be/irace

Elitist irace by default
New interfaces with more intuitive names
A detailed user-guide / tutorial:

Implementation of Iterated Racing in R
Goal 1: Flexible

https://cran.r-project.org/web/packages/irace/vignettes/
irace-package.pdf

Goal 2: Easy to use
Available from CRAN (GNU/Linux, Windows, OSX)

R package available at CRAN

https://cran.r-project.org/package=irace
Use it through the command-line: (see irace --help)
irace --max-experiments 1000 --param-file parameters.txt

4 No knowledge of R needed

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The irace Package

Training
instances

calls with θ,iManuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The irace Package: Instances

Parameter
space

Configuration
scenario

TSP instances$ dir Instances/
3000-01.tsp 3000-02.tsp 3000-03.tsp ...

Continuous functions

irace
irace

returns c(θ,i)

targetRunner

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms$ cat instances.txt
function=1 dimension=100
function=2 dimension=100...

Parameters for an instance generator$ cat instances.txt
I1 --size 100 --num-clusters 10 --sym yes --seed 1
I2 --size 100 --num-clusters 5 --sym no --seed 1...

Script / R function that generates instances+ if you need this, tell us!
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The irace Package: Parameter space

The irace Package: Options

Categorical (c), ordinal (o), integer (i) and real (r)maxExperiments: maximum number of runs of the target
algorithm (tuning budget)

Subordinate parameters (| condition)

digits: number of decimal places to be considered for the realparameters (default: 4)$ cat parameters.txt# NameLS
rate
population
temp

Label/switch"--localsearch ""--rate=""--pop ""--temp "

Type
c
o
i
r

DomainCondition{SA, TS, II}{low, med, high}(1, 100)(0.5, 1)| LS == "SA"testType: either F-test or t-test
firstTest: specifies how many instances are seen before thefirst test is performed (default: 5)
eachTest: specifies how many instances are seen between
tests (default: 1)

For real parameters, number of decimal places is controlled by
option digits (--digits)

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

The irace Package: target-runner

Manuel López-Ibáñez and Thomas Stützle

The irace Package: Other features1e.g. :./target-runner 2 1 1234567 3000-01.tsp --localsearch SA ...

Initial configurations
4 “seed” irace with the default configuration

A script/program that calls the software to be tuned:./target-runner configID instanceID seed instance configuration

Automated Offline Design of Algorithms

2

Parallel evaluation: MPI, multiple cores, Grid Engine / qsub3

Forbidden configurations:
popsize < 5 & LS == "SA"An R function
Flexibility: If there is something you cannot tune, let us know!

4

Recovery file: allows resuming an interrupted irace run

5

Test instances
4 Specify not only the training instances but also test instances
for comparing results

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

An overview of applications of irace

An overview of applications of irace

Parameter tuning
Exact MIP solvers (CPLEX, SCIP with > 200 parameters)
single-objective optimization metaheuristics

irace (and others) works great for

multi-objective optimization metaheuristics

Complex parameter spaces:
numerical, categorical, ordinal, subordinate (conditional)

anytime algorithms (improve time-quality trade-offs)

Automatic algorithm design

Large parameter spaces (few hundred parameters)

From a flexible framework of algorithm components

Heterogeneous instances

From a grammar description

Medium to large tuning budgets (thousands of target runs)

Machine learning
Automatic model selection for high-dimensional survival
analysis [Lang et al., 2014]

Target runs require from seconds to hours
Multi-core CPUs, MPI, Grid-Engine clusters

Hyperparameter tuning [Miranda et al., 2014] (mlr R package,
Bischl et al.)Automatic design of control software for robots[Francesca et al., 2015]
Manuel López-Ibáñez and Thomas Stützle

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

An overview of applications of irace

What we haven’t deal with yet
Extremely large parameter spaces (thousands of parameters)

Conclusions“

Extremely heterogeneous instances

Target runs require days

We are looking for interesting benchmarks / applications!
Talk to us!

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

For procedures that require parameter tuning, theavailable data must be partitioned into a training anda test set. Tuning should be performed in the training
set only.
[Journal of Heuristics: Policies on Heuristic Search Research]

Small tuning budgets (500 or less target runs)
Very large tuning budgets (millions of target runs)

Automated Offline Design of Algorithms“

The performance of swarm intelligence algorithms [. . .] isoften strongly dependent on the value of the algorithm
parameters. Such values should be set using either
sound statistical procedures [. . .] or automatic parametertuning procedures.

”[Swarm Intelligence Journal (Springer)]”
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example #1

Part II
Automated Algorithm Design

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example: ACOTSP

Example: Tuning ACOTSP

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example: ACOTSP$ cat parameters-acotsp.txt

Thomas Stützle. ACOTSP: A software package of various ant colony
optimization algorithms applied to the symmetric traveling salesman
problem, 2002.

Command-line program:$ ./acotsp -i instance -t 20 --mmas --ants 10 --rho 0.95 ...

Goal: find best parameter settings of ACOTSP for solving
random Euclidean TSP instances with n ∈ [500, 5000]
within 20 CPU-seconds

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms# NameLabel/switch
Type Domain
Condition
algorithm"--"c (as,mmas,eas,ras,acs)
localsearch "--localsearch " c (0, 1, 2, 3)
alpha"--alpha "r (0.00, 5.00)
beta"--beta "r (0.00, 10.00)
rho"--rho "r (0.01, 1.00)
ants"--ants "i (5, 100)q0"--q0 "
r (0.0, 1.0) | algorithm == "acs"rasrank"--rasranks "i (1, 100)
| algorithm == "ras"elitistants "--elitistants " i (1, 750)
| algorithm == "eas"nnls"--nnls "i (5, 50)
| localsearch %in% c(1,2,3)
dlb"--dlb "c (0, 1)| localsearch %in% c(1,2,3)

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example: ACOTSP

Example: ACOTSP$ cat target-runner$ dir Instances/
3000-01.tsp 3000-02.tsp 3000-03.tsp ...

#!/bin/bash
CONFIG ID=$1
INSTANCE ID=$2
SEED=$3
INSTANCE=$4
CONFIG PARAMS=$*
FIXED PARAMS=" --time 1 --tries 1 --quiet "STDOUT="c$CONFIG ID-$INSTANCE ID.stdout"acotsp $FIXED PARAMS -i $INSTANCE --seed $SEED \$CONFIG PARAMS > $STDOUTCOST=$(grep -oE ’Best [-+0-9.e]+’ $STDOUT | cut -d’ ’ -f2)
echo "$COST"
exit 0
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example: ACOTSP: and more

$ cat scenario.txt
trainInstancesDir = "./Instances"
maxExperiments = 1000
digits = 2
4 Good to go:$ irace --parallel 2 --debug-level 1--parallel to execute in parallel--debug-level to see what irace is executing

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example #1

Initial configurations:$ cat default.txt
algorithm localsearch alpha beta rho ants nnls dlb q0
as0
1.0
1.0 0.95 10
NA
NA NA

Configuring known algorithms

Logical expressions that forbid configurations:$ cat forbidden.txt(alpha == 0.0) & (beta == 0.0)

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Mixed integer programming (MIP) solvers

Example application: configuring IPOP-CMAES[Hutter, Hoos, Leyton-Brown, and Stützle, 2009; Hutter, Hoos, and Leyton-Brown, 2010][Liao et al., 2013]

IPOP-CMAES is state-of-the-art continuous optimizer
configuration done on benchmark problems (instances)distinct from test set (CEC’05 benchmark function set)using seven numerical parameters

MIP solvers widely used for tackling optimization problems
powerful commercial (e.g. CPLEX) and non-commercial (e.g.
SCIP) solvers
large number of parameters (tens to hundreds)

FocusedILS, 10 runs, 2 CPU days, 63 parameters

1e−08

1e−05

250
1e−02

600
1e+01

1000
1e+04

900

18,19,20

600

22
23
21

20
1e−05

14
8

16
9 13
10
2

5

600
220

1e+04
1e−02

1e+01

f_id_opt
1e−08

iCMAES−tsc (opt 7 )

14
168
913
10

800

20

1e−02

1100
25

17
15,24

160

15,24
150

23
21

20
19
18
22
23
21
25
24
1715

11

5

2 5

25

12

−Win 13 +−Lose 4
−Draw 8

4

1e−05

900

f_id_opt

700

17

500

20

180

10

18,19,2022

iCMAES−dp (opt 5 )

11

1e−08

8
16
14
913
10

240

1e+04

20
19
18
22
23
21
17
25
15
24

13

1 2 4
8
16
14

Average Errors−50D−100runs

12

4

1e+01

2

9
10

1

1e−02

6.8
2.51
30.43
54.54
1.85

4

20

10.5 (11.4 ± 0.9)
2.14 (2.4 ± 0.29)
23.4 (327 ± 860)
1.19 (301 ± 948)525 (827 ± 306)

Speedup−Win 8−Lose 4
−Draw 13

10

72
5.37
712
64.8
969

Configured

1e−05

Regions200
Conic.SCH
CLS
MIK
QP

Default

1e−08

Benchmark set

iCMAES−dp (opt 6 )Average Errors−30D−100runs

50 100
1e+01

250
1e+04

iCMAES−tsc (opt 7 )Smit & Eiben [2010] configured another variant of IPOP-CMAES for threedifferent objectives

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example #2

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Automatically Improving the Anytime Behavior

Anytime Algorithm[Dean & Boddy, 1988]
May be interrupted at any moment and returns a solution
Keeps improving its solution until interrupted
Automatically Improving the Anytime Behaviorof Optimization Algorithms with irace

Eventually finds the optimal solution

Good Anytime Behavior[Zilberstein, 1996]
Algorithms with good “anytime” behavior produce as highquality result as possible at any moment of their execution.

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

solution cost

Automatically Improving the Anytime Behavior

Automatically Improving the Anytime Behavior

A
B
C

8
7
6
5
4
3
2
1
1 2 3 45 6

7 8

Hypervolume measure ≈ Anytime behaviour

time
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Offline configuration and online parameter control
Offline tuning / Algorithm configuration
Learn best parameters before solving an instanceConfiguration done on training instances
Performance measured over test (6= training) instances

Online tuning / Parameter control / Reactive search

Manuel López-Ibáñez and Thomas Stützle.
Automatically improving the anytime behaviour of optimisation algorithms.
European Journal of Operational Research, 2014.
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Automatically Improving the Anytime Behavior
Scenario #1
Online parameter adaptation to make an algorithm more robust todifferent termination criteria
8 Which parameters to adapt? How? ⇒ More parameters!
4 Use irace (offline) to select the best parameter adaptation
strategies

Learn parameters while solving an instance
No training phase

Scenario #2

Limited to very few crucial parameters

General purpose black-box solvers (CPLEX, SCIP, . . . )Hundred of parameters

Offline configuration techniques can be helpful
to configure online parameter control strategies

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Tuned by default for solving fast to optimality

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Visually compare SQT plots

After about one year:+ Strategies for varying ants, β, or q0 that significantly improve
the anytime behaviour of MMAS on the TSP.
- Extremely time consuming

0.8

3

0.6

Run lots of experiments

0.4

2

default ( 1.1599 )
auto var ants ( 1.1865 )
auto var beta ( 1.182 )
auto var rho ( 1.1813 )
auto var q0 ( 1.1935 )
auto var ALL ( 1.2012 )0.2

Choose many parameter settings

0.0

1

Scenario #2: Experimental comparison
relative deviation from best−known

Scenario #1: Brute-Force Approach1- Subjective / Bias

2

5

10

20

50

100

200

time in seconds

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Automated Offline Design of Algorithms

Scenario #2: SCIP

Benchmark set: Winner determination problem for
combinatorial auctions [Leyton-Brown et al., 2000]
1 000 training + 1 000 testing instances
Single run timeout: 300 seconds
irace budget (maxExperiments): 5 000 runs

8
6
4

200 parameters controlling search, heuristics, thresholds, . . .

2[Achterberg, 2009]

default (0.9834)
auto quality (0.9826)
auto time (0.9767)
auto anytime (0.9932)

0

SCIP: an open-source mixed integer programming (MIP) solver

RPD from best−known

10

Scenario #2: SCIP

Manuel López-Ibáñez and Thomas Stützle

1

2

5

10

20

50

100

time in seconds

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

200

Example #3

Tuning in-the-loop: (re)design of continuous optimizers[Montes de Oca et al., 2011]

re-design of an incremental PSO algorithm for large-scalecontinuous optimization

Integration in algorithm (re-)engineering process

steps: (1) local search, (2) call and control strategy of LS,(3) PSO rules, (4) bound constraint handling,(5) stagnation handling, (6) restarts
iterated F-race used at each step to configure up to
10 parameters
configuration done on 19 functions of dimension 10
scaling examined until dimension 1000
configuration results may help the designer gain
insight useful for further development

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Tuning in-the-loop: (re)design of continuous optimizers[Montes de Oca et al., 2011]

Stage−I
Stage−VI

Objective Function Value

1e+02

Automated design from (flexible) algorithm frameworks
1e−02

1e−06

1e−10

1e−14
DEFAULTDEFAULT

TUNED

TUNED

Manueland ThomasStützleacrossAutomated
Offline Design of Algorithms
comparison
onLópez-Ibáñez
100D, medianvalues19 functions

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

General approach

Main approaches
Top-down approaches
develop flexible framework following a fixed algorithm
template with alternatives
apply high-performing configurators
Examples: Satenstein, MOACO, AutoMOEA, MIP Solvers(?!)
Bottom-up approaches
flexible framework implementing algorithm components
define rules for composing algorithms from components e.g.
through grammars
frequently usage of genetic programming, grammaticalevolution etc.

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example #4

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

A more complex example: MOACO framework
Manuel López-Ibáñez and Thomas Stützle.
The automatic design of multi-objective ant colony optimization
algorithms.
IEEE Transactions on Evolutionary Computation, 2012.

Top-down design approach: MOACO framework
A flexible framework of multi-objective ACO algorithms
Parameters controlling multi-objective algorithmic design
Parameters controlling underlying ACO settings
Instantiates 9 MOACO algorithms from the literature
Hundreds of potential papers algorithm designs

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

A more complex example: MOACO framework

Results: Multi-objective components

8 Multi-objective! Output is an approximation to the Pareto
front!

8
7
6
5
4
3
2
1
1 2 3 45 6

7 8

irace + hypervolume = automatic configurationof multi-objective solvers!
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Summary

0.5 0.6 0.7 0.8 0.9 1.0
euclidAB100.tsp

euclidAB300.tsp

●●

MOAQ
BicriterionAnt (1 col)BicriterionAnt (3 col)MACS
COMPETants
PACO
mACO−1mACO−2mACO−3mACO−4
MOACO (1)
MOACO (2)MOACO (3)
MOACO (4)MOACO (5)euclidAB500.tsp

●
●
●

●

●

●
●

●

●
●

●

●

●
●

●

●

●

●

●

●

●

●

●●

●

●

●

●

●

●●
●

●

●●

●

●●
●

●

●

●

●

●
●

●●

●

●

●

●

●

●

●
●

●

●

0.5 0.6 0.7 0.8 0.9 1.0

Manuel López-Ibáñez and Thomas Stützle

0.5 0.6 0.7 0.8 0.9 1.0

Automated Offline Design of Algorithms

Example #5

We propose a new MOACO algorithm that. . .
We propose an approach to automatically design MOACO algorithms:
1

Synthesize state-of-the-art knowledge into a flexible MOACO framework

2

Explore the space of potential designs automatically using irace

Top-down design approach: MOEA framework

Other examples:Single-objective top-down frameworks for MIP: CPLEX, SCIP
Single-objective top-down framework for SAT: SATenstein[KhudaBukhsh, Xu, Hoos, and Leyton-Brown, 2009]
Multi-objective automatic configuration with SPO[Wessing, Beume, Rudolph, and Naujoks, 2010]
Multi-objective framework for PFSP, TP+PLS[Dubois-Lacoste, López-Ibáñez, and Stützle, 2011]
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

An even more complex example: MOEA framework

AutoMOEA: A MOEA template
1: pop : = Initialization ()2: if type (popext ) != none thenpopext := pop
4: repeat5:pool := BuildMatingPool (pop)6:popnew := Variation (pool)7:
popnew := Evaluation (popnew )8:
pop:= Replacement (pop, popnew )9:
if type (popext ) == bounded then10:
popext := Archiving (popext , popnew )11:else if type (popext ) == unbounded then12:
popext := popext ∪ pop
13: until termination criteria met
14: if type (popext ) == none then15:
return pop
16: else
17:
return popext
3:

4 Replicate as many well-known MOEAs as possible from thesame template
4 The template has a number of configurable algorithmic
components
4 Each component can be configured by choosing one option
from various alternatives
4 Aim to maximise the number of different configurations thatare valid MOEAs

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

AutoMOEA: Main components
Component“On Set-Based Multiobjective Optimization”[Zitzler, Thiele, and Bader, 2010]

Parametersh PreferenceMat , Selection i
h PreferenceRep , Removal i
h PreferenceExt , RemovalExt i
h Fitness, Diversity i

Algorithm

Fitness

Diversity

dominance depth crowding distancedom. strengthkNN
binary indicator
IHhdom. depth-rank
IH1

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

AutoMOEA: Main components

BuildMatingPool
Replacement
Archiving
Preference

NSGA-II
SPEA2
IBEA
HypE
SMS-EMOA

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Set-partitioning

Pareto-compliant
quality measures

Diversity measures(not Pareto-compliant)
dominance count





dominance rank
dominance strength
dominance depth
dominance depth-rank−binary indicator (Ie or IH )exclusive hypervolume contribution (IH1 )shared hypervolume contribution (IHh )niche sharing
k-th nearest neighbor (kNN)
crowding distance

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

AutoMOEA: Main components
Component
BuildMatingPool
Replacement
Archiving
Preference

AutoMOEA: Automatic Design

Parameters

BuildMatingPool

MOGA
NSGA-II
SPEA2
IBEA
HypE
SMS-EMOA

Automatic configuration (irace)+ Flexible algorithmic framework (AutoMOEA)= Automatic design of state-of-the-art MOEAsh PreferenceMat , Selection i
h PreferenceRep , Removal i
h PreferenceExt , RemovalExt i
h Fitness, Diversity ih Set-partitioning, Quality, Diversity i

Replacement

SetPart

Quality

Diversity

SetPart

Quality

Diversitydom. rank
dom. depth
dom. strength
—
—
—

—
—
—
binary indicator
IHh—niche-sharing
crowding dist.
kNN
—
—
—

—
dom. depth
dom. strength—
dom. depth
dom. depth-rank———binary ind.
IHh
IH1

—
crowding dist.
kNN
—
—
—

Manuel López-Ibáñez and Thomas Stützle

BuildMatingPool
Quality

Diversity

SetPart

Quality

Diversity

MOGA
NSGA-II
SPEA2
IBEA
HypE
SMS-EMOA

rank
depth
strength
—
—
—

—
—
—
binary indicator
IHh—niche-sharing
crowding dist.
kNN
—
—
—

—
depth
strength—
depth
depth-rank———binary ind.
IHh
IH1

—
crowding dist.
kNN
—
—
—

DTLZ 2-obj
DTLZ 3-obj
DTLZ 5-obj—
depth-rank
rank

—
Ie
IH1

crowdingkNN
crowding

depth-rank
rank
depth

Ie
IH1
IH1

sharing
sharing—

WFG 2-obj
WFG 3-obj
WFG 5-obj

rank
count
count

—
IH1
IHh

crowding
crowding
crowding

depth-rankstrength
—

IH1
IH1
IH1

—
sharing—

Automated Offline Design of Algorithms

AutoMOEA: Automatic Design
Automatic configuration (irace)+ Flexible algorithmic framework (AutoMOEA)= Automatic design of state-of-the-art MOEAs

Replacement

SetPartManuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Automatic Design: The End of the Game“

True innovation in metaheuristics research therefore does
not come from yet another method that performs better
than its competitors, certainly if it is not well understood
why exactly this method performs well. [Sörensen, 2015]

Fair to compare with untuned traditional MOEAs?

”

Why is our setup representative?
Finding a state-of-the-art algorithm is “easy”:
Different AutoMOEAs for termination criterion in FEs orseconds

problem modeling + algorithmic components + computing power

How do you define “state-of-the-art”?
What novel components? Why they work? When they work?
What is a “novel” MOEA?

Exactly!
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Automatic Design of Algorithms: Top-down vs. Bottom-up

Example #6

Top-down approaches
Flexible frameworks:
SATenstein [KhudaBukhsh et al., 2009]
MOACO framework [López-Ibáñez andFrom Grammars to Parameters:
How to use irace to design algorithms
from a grammar description?

Stützle, 2012]

MIP solvers: CPLEX, SCIP
Automatic configuration tools:

Bottom-up approaches
Based on GP and trees[Vázquez-Rodrı́guez & Ochoa, 2010]

Based on GP and Lisp-like
S-expressions [Fukunaga, 2008]
Based on GE and a grammar
description [Burke et al., 2012]

ParamILS [Hutter et al., 2009]
irace [Birattari et al., 2010; López-Ibáñez
et al., 2011]

Bottom-up approach using grammars + irace[Mascia, López-Ibáñez, Dubois-Lacoste, and Stützle, 2014]

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Automatic design of hybrid SLS algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

General Local Search Structure: ILS[Marmion, Mascia, López-Ibáñez, Stützle, 2013]

Approachdecompose single-point SLS methods into components
derive generalized metaheuristic structurecomponent-wise implementation of metaheuristic part
Implementation
present possible algorithm compositions by a grammar
instantiate grammar using a parametric representation
allows use of standard automatic configuration tools
shows good performance when compared to, e.g., grammaticalevolution [Mascia, López-Ibáñez, Dubois-Lacoste, and Stützle,

s0 :=initSolutions ∗ := ls(s0 )repeats 0 :=perturb(s ∗ ,history )s ∗0 :=ls(s 0 )s ∗ :=accept(s ∗ ,s ∗0 ,history )until termination criterion met
many SLS methods instantiable from this structureabilities
hybridization through recursion
problem specific implementation at low-levelseparation of generic and problem-specific components

2014]

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Example instantiations of some metaheuristics

Grammar<algorithm> ::= <initialization> <ils><initialization> ::= random | <pbs_initialization><ils> ::= ILS(<perturb>, <ls>, <accept>, <stop>)

perturbls

acceptSA

random move∅

Metropolis

PII

random move∅

Metropolis, fixed T

TS

∅

TS

∅

ILS

any

any

any

IG

destruct/construct

any

any

GRASP

rand. greedy sol.

Manuel López-Ibáñez and Thomas Stützle

any∅

Automated Offline Design of Algorithms

Grammar<perturb> ::= none | <initialization> | <pbs_perturb><ls> ::= <ils> | <descent> | <sa> | <rii> | <pii> | <vns> | <ig> | <pbs_ls><accept> ::= alwaysAccept | improvingAccept <comparator>| prob(<value_prob_accept>) | probRandom | <metropolis>| threshold(<value_threshold_accept>) | <pbs_accept><descent> ::= bestDescent(<comparator>, <stop>)| firstImprDescent(<comparator>, <stop>)<sa> ::= ILS(<pbs_move>, no_ls, <metropolis>, <stop>)<rii> ::= ILS(<pbs_move>, no_ls, probRandom, <stop>)<pii> ::= ILS(<pbs_move>, no_ls, prob(<value_prob_accept>), <stop>)<vns> ::= ILS(<pbs_variable_move>, firstImprDescent(improvingStrictly),
improvingAccept(improvingStrictly), <stop>)<ig> ::= ILS(<deconst-construct_perturb>, <ls>, <accept>, <stop>)<comparator> ::= improvingStrictly | improving<value_prob_accept> ::= [0, 1]<value_threshold_accept> ::= [0, 1]<metropolis> ::= metropolisAccept(<init_temperature>, <final_temperature>,<decreasing_temperature_ratio>, <span>)<init_temperature> ::= {1, 2,..., 10000}<final_temperature> ::= {1, 2,..., 100}<decreasing_temperature_ratio> ::= [0, 1]<span> ::= {1, 2,..., 10000}

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

System overview [Mascia, López-Ibáñez, Dubois-Lacoste, and Stützle, 2014]<algorithm> ::= <initialization> <ils><initialization> ::= random | <pbs_initialization><ils> ::= ILS(<perturb>, <ls>, <accept>, <stop>)<perturb> ::= none | <initialization> | <pbs_perturb><ls> ::= <ils> | <descent> | <sa> | <rii> | <pii> | <vns> | <ig> | <pbs_ls><accept> ::= alwaysAccept | improvingAccept <comparator>| prob(<value_prob_accept>) | probRandom | <metropolis>| threshold(<value_threshold_accept>) | <pbs_accept><descent> ::= bestDescent(<comparator>, <stop>)| firstImprDescent(<comparator>, <stop>)<sa> ::= ILS(<pbs_move>, no_ls, <metropolis>, <stop>)<rii> ::= ILS(<pbs_move>, no_ls, probRandom, <stop>)<pii> ::= ILS(<pbs_move>, no_ls, prob(<value_prob_accept>), <stop>)<vns> ::= ILS(<pbs_variable_move>, firstImprDescent(improvingStrictly),
improvingAccept(improvingStrictly), <stop>)<ig> ::= ILS(<deconst-construct_perturb>, <ls>, <accept>, <stop>)<comparator> ::= improvingStrictly | improving<value_prob_accept> ::= [0, 1]<value_threshold_accept> ::= [0, 1]<metropolis> ::= metropolisAccept(<init_temperature>, <final_temperature>,<decreasing_temperature_ratio>, <span>)<init_temperature> ::= {1, 2,..., 10000}<final_temperature> ::= {1, 2,..., 100}<decreasing_temperature_ratio> ::= [0, 1]<span> ::= {1, 2,..., 10000}

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Flow-shop problem with makespan objective

Flow-shop problem with total completion time objective[Pagnozzi, Stützle, 2017][Pagnozzi, Stützle, 2017]

Automatic configuration:

Automatic configuration:
max. three levels of recursion
budget: 100 000 trials of n · m · 0.03 seconds
0.75

max. three levels of recursion
biased / unbiased grammar resulting in 262 and 502
parameters, respectively
budget: 200 000 trials of n · m · 0.03 seconds

●

0.70
0.60

0.65

●

0.55

0.26
0.24

ARPD

0.28

0.30

Relative Percentage Deviation

95% confidence limits

0.22

0.50

●

ALGirtct

IGrs

IGtb

irace1

irace2

irace3

IGA

IGAb

irace4

Algorithms

Results are clearly superior to state-of-the-art

Results are clearly superior to state-of-the-art
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Flow-shop problem with total tardiness objective

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Summary[Pagnozzi, Stützle, 2017]

Automatic configuration:
max. three levels of recursion
budget: 100 000 trials of n · m · 0.03 seconds

Contributions
approach to automate design and analysis of (hybrid)
metaheuristics

●

4

5

better or equal performance to state-of-the-art for UBQP,
TSP-TW, many (flow-shop) scheduling problems
directly extendible for automated comparison ofmetaheuristics

3

●

2

Relative Deviation Index

6

not a silver bullet, but needs right components, especiallyproblem-specific onesCurrent/future work

1

●

TSM63

TSMe63

irace4

Results are clearly superior to state-of-the-art

extensions to other methods and templates
dealing with complexity of hybrid algorithms
increase generality, tackling wide problem classes

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Why automatic algorithm configuration?

Towards a paradigm shift in algorithm design

improvement over manual, ad-hoc methods for tuning
reduction of development time and human intervention

      

increased number of potential designs

empirical studies, comparisons of algorithms
support for end-users of algorithms



 

    

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Conclusions

Automated Offline Design of Algorithms

Configurable, flexible (SLS) frameworks XXL

Automatic Configuration
leverages computing power for software design
is rewarding w.r.t. development time and algorithm
performance
Future work
more powerful configurators
more and more complex applications
paradigm shift in optimization software development

Manuel López-Ibáñez and Thomas Stützle

Manuel López-Ibáñez and Thomas Stützle

     

Automated Offline Design of Algorithms

paradigm shift in SLS algorithm development
configurable frameworks XXL
solve = model + configure + search
Many challenges remain on (i) problem representations, (ii)algorithmic structure, (iii) algorithmic components and generation
thereof, (iv) automatic configuration techniques, and (v)extensions to other techniques and challenging problems, . . .

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Acknowledgments

References I

The tutorial has benefited from collaborations and discussions with our colleagues:
Prasanna Balaprakash, Mauro Birattari, Jérémie Dubois-Lacoste, Alberto Franzin,
Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown, Tianjun Liao, Marie-Eléonore Marmion,
Franco Mascia, Marco Montes de Oca, Federico Pagnozzi, Leslie Pérez, Zhi Yuan.

T. Achterberg. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1–41, July 2009.
B. Adenso-Dı́az and M. Laguna. Fine-tuning of algorithms using fractional experimental design and local search. Operations
Research, 54(1):99–114, 2006.
C. Ansótegui, M. Sellmann, and K. Tierney. A gender-based genetic algorithm for the automatic configuration of algorithms. In
I. P. Gent, editor, Principles and Practice of Constraint Programming, CP 2009, volume 5732 of Lecture Notes in Computer
Science, pages 142–157. Springer, Heidelberg, Germany, 2009. doi: 10.1007/978-3-642-04244-7\ 14.
C. Audet and D. Orban. Finding optimal algorithmic parameters using derivative-free optimization. SIAM Journal on Optimization,
17(3):642–664, 2006.
C. Audet, C.-K. Dang, and D. Orban. Algorithmic parameter optimization of the DFO method with the OPAL framework. In
K. Naono, K. Teranishi, J. Cavazos, and R. Suda, editors, Software Automatic Tuning: From Concepts to State-of-the-Art
Results, pages 255–274. Springer, 2010.
P. Balaprakash, M. Birattari, and T. Stützle. Improvement strategies for the F-race algorithm: Sampling design and iterativerefinement. In T. Bartz-Beielstein, M. J. Blesa, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels, editors, Hybrid
Metaheuristics, volume 4771 of Lecture Notes in Computer Science, pages 108–122. Springer, Heidelberg, Germany, 2007.

The research leading to the results presented here has received funding from diverse projects:
European Research Council under the European Union’s Seventh Framework Programme(FP7/2007-2013) / ERC grant agreement no 246939
PAI project COMEX funded by the Interuniversity Attraction Poles Programme of the Belgian
Science Policy Officeand the EU FP7 ICT Project COLOMBO, Cooperative Self-Organizing System for Low Carbon
Mobility at Low Penetration Rates (agreement no. 318622)

T. Bartz-Beielstein, C. Lasarczyk, and M. Preuss. Sequential parameter optimization. In Proceedings of the 2005 Congress on
Evolutionary Computation (CEC 2005), pages 773–780, Piscataway, NJ, Sept. 2005. IEEE Press.
T. Bartz-Beielstein, M. Chiarandini, L. Paquete, and M. Preuss, editors. Experimental Methods for the Analysis of Optimization
Algorithms. Springer, Berlin, Germany, 2010a.
T. Bartz-Beielstein, C. Lasarczyk, and M. Preuss. The sequential parameter optimization toolbox. In Bartz-Beielstein et al.
[2010a], pages 337–360.
M. Birattari, T. Stützle, L. Paquete, and K. Varrentrapp. A racing algorithm for configuring metaheuristics. In W. B. Langdon
et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2002, pages 11–18. Morgan
Kaufmann Publishers, San Francisco, CA, 2002.
M. Birattari, Z. Yuan, P. Balaprakash, and T. Stützle. F-race and iterated F-race: An overview. In Bartz-Beielstein et al. [2010a],pages 311–336.

Thomas Stützle acknowledges support of the F.R.S.-FNRS
of which he is a senior research associate.
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

References II

Automated Offline Design of Algorithms

References III

E. K. Burke, M. R. Hyde, and G. Kendall. Grammatical evolution of local search heuristics. IEEE Transactions on Evolutionary
Computation, 16(7):406–417, 2012. doi: 10.1109/TEVC.2011.2160401.
W. J. Conover. Practical Nonparametric Statistics. John Wiley & Sons, New York, NY, third edition, 1999.
S. P. Coy, B. L. Golden, G. C. Runger, and E. A. Wasil. Using experimental design to find effective parameter settings forheuristics. Journal of Heuristics, 7(1):77–97, 2001.
T. Dean and M. S. Boddy. An analysis of time-dependent planning. In H. E. Shrobe, T. M. Mitchell, and R. G. Smith, editors,
Proceedings of the 7th National Conference on Artificial Intelligence, AAAI-88, pages 49–54. AAAI Press/MIT Press, Menlo
Park, CA, 1988. URL http://www.aaai.org/Conferences/AAAI/aaai88.php.
J. Dubois-Lacoste, M. López-Ibáñez, and T. Stützle. Automatic configuration of state-of-the-art multi-objective optimizers using
the TP+PLS framework. In N. Krasnogor and P. L. Lanzi, editors, Proceedings of the Genetic and Evolutionary Computation
Conference, GECCO 2011, pages 2019–2026. ACM Press, New York, NY, 2011. ISBN 978-1-4503-0557-0. doi:
10.1145/2001576.2001847.
G. Francesca, M. Brambilla, A. Brutschy, L. Garattoni, R. Miletitch, G. Podevijn, A. Reina, T. Soleymani, M. Salvaro, C. Pinciroli,
F. Mascia, V. Trianni, and M. Birattari. AutoMoDe-Chocolate: Automatic design of control software for robot swarms. SwarmIntelligence, 2015. doi: 10.1007/s11721-015-0107-9.
A. S. Fukunaga. Automated discovery of local search heuristics for satisfiability testing. Evolutionary Computation, 16(1):31–61,
Mar. 2008. doi: 10.1162/evco.2008.16.1.31.
J. J. Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, andCybernetics, 16(1):122–128, 1986.
F. Hutter, D. Babić, H. H. Hoos, and A. J. Hu. Boosting verification by automatic tuning of decision procedures. In FMCAD’07:
Proceedings of the 7th International Conference Formal Methods in Computer Aided Design, pages 27–34, Austin, Texas,
USA, 2007a. IEEE Computer Society, Washington, DC, USA.
F. Hutter, H. H. Hoos, and T. Stützle. Automatic algorithm configuration based on local search. In R. C. Holte and A. Howe,editors, Proc. of the Twenty-Second Conference on Artifical Intelligence (AAAI ’07), pages 1152–1157. AAAI Press/MIT
Press, Menlo Park, CA, 2007b.
F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle. ParamILS: an automatic algorithm configuration framework. Journal of
Artificial Intelligence Research, 36:267–306, Oct. 2009.

Manuel López-Ibáñez and Thomas Stützle

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

F. Hutter, H. H. Hoos, and K. Leyton-Brown. Automated configuration of mixed integer programming solvers. In A. Lodi,
M. Milano, and P. Toth, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial
Optimization Problems, 7th International Conference, CPAIOR 2010, volume 6140 of Lecture Notes in Computer Science,
pages 186–202. Springer, Heidelberg, Germany, 2010.
F. Hutter, H. H. Hoos, and K. Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In C. A.
Coello Coello, editor, Learning and Intelligent Optimization, 5th International Conference, LION 5, volume 6683 of Lecture
Notes in Computer Science, pages 507–523. Springer, Heidelberg, Germany, 2011.
A. R. KhudaBukhsh, L. Xu, H. H. Hoos, and K. Leyton-Brown. SATenstein: Automatically building local search SAT solvers fromcomponents. In C. Boutilier, editor, Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence(IJCAI-09), pages 517–524. AAAI Press, Menlo Park, CA, 2009.
M. Lang, H. Kotthaus, P. Marwedel, C. Weihs, J. Rahnenführer, and B. Bischl. Automatic model selection for high-dimensional
survival analysis. Journal of Statistical Computation and Simulation, 85(1):62–76, 2014. doi: 10.1080/00949655.2014.929131.
K. Leyton-Brown, M. Pearson, and Y. Shoham. Towards a universal test suite for combinatorial auction algorithms. In A. Jhingran
et al., editors, ACM Conference on Electronic Commerce (EC-00), pages 66–76. ACM Press, New York, NY, 2000. doi:
10.1145/352871.352879.
T. Liao, M. A. Montes de Oca, and T. Stützle. Computational results for an automatically tuned CMA-ES with increasing
population size on the CEC’05 benchmark set. Soft Computing, 17(6):1031–1046, 2013. doi: 0.1007/s00500-012-0946-x.
M. López-Ibáñez and T. Stützle. The automatic design of multi-objective ant colony optimization algorithms. IEEE Transactions
on Evolutionary Computation, 16(6):861–875, 2012. doi: 10.1109/TEVC.2011.2182651.
M. López-Ibáñez, J. Dubois-Lacoste, T. Stützle, and M. Birattari. The irace package, iterated race for automatic algorithm
configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium, 2011. URL
http://iridia.ulb.ac.be/IridiaTrSeries/IridiaTr2011-004.pdf.
M. López-Ibáñez, J. Dubois-Lacoste, L. Pérez Cáceres, T. Stützle, and M. Birattari. The irace package: Iterated racing forautomatic algorithm configuration. Operations Research Perspectives, 3:43–58, 2016. doi: 10.1016/j.orp.2016.09.002.
F. Mascia, M. López-Ibáñez, J. Dubois-Lacoste, and T. Stützle. Grammar-based generation of stochastic local search heuristics
through automatic algorithm configuration tools. Computers & Operations Research, 51:190–199, 2014. doi:
10.1016/j.cor.2014.05.020.

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

References IV

References V

P. Miranda, R. M. Silva, and R. B. Prudêncio. Fine-tuning of support vector machine parameters using racing algorithms. In 22stEuropean Symposium on Artificial Neural Networks, Computational Intelligence And Machine Learning, Bruges, April
23-24-25, 2014, pages 325–330. ESANN, 2014.
M. A. Montes de Oca, D. Aydın, and T. Stützle. An incremental particle swarm for large-scale continuous optimization problems:
An example of tuning-in-the-loop (re)design of optimization algorithms. Soft Computing, 15(11):2233–2255, 2011. doi:
10.1007/s00500-010-0649-0.
V. Nannen and A. E. Eiben. A method for parameter calibration and relevance estimation in evolutionary algorithms. In
M. Cattolico et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2006, pages
183–190. ACM Press, New York, NY, 2006. doi: 10.1145/1143997.1144029.

Z. Yuan, M. A. Montes de Oca, T. Stützle, and M. Birattari. Continuous optimization algorithms for tuning real and integer
algorithm parameters of swarm intelligence algorithms. Swarm Intelligence, 6(1):49–75, 2012.
Z. Yuan, M. A. Montes de Oca, T. Stützle, H. C. Lau, and M. Birattari. An analysis of post-selection in automatic configuration.
In C. Blum and E. Alba, editors, Proceedings of GECCO 2013, pages 1557–1564. ACM Press, New York, NY, 2013.
S. Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine, 17(3):73–83, 1996.
E. Zitzler, L. Thiele, and J. Bader. On set-based multiobjective optimization. IEEE Transactions on Evolutionary Computation, 14(1):58–79, 2010. doi: 10.1109/TEVC.2009.2016569.

M. Oltean. Evolving evoluionary algorithms using linear genetic programming. Evolutionary Computation, 13(3):387–410, 2005.
E. Ridge and D. Kudenko. Tuning the performance of the MMAS heuristic. In T. Stützle, M. Birattari, and H. H. Hoos, editors,
Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics. SLS 2007,
volume 4638 of Lecture Notes in Computer Science, pages 46–60. Springer, Heidelberg, Germany, 2007.
R. Ruiz and C. Maroto. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal ofOperational Research, 165(2):479–494, 2005.
S. K. Smit and A. E. Eiben. Comparing parameter tuning methods for evolutionary algorithms. In Proceedings of the 2009
Congress on Evolutionary Computation (CEC 2009), pages 399–406. IEEE Press, Piscataway, NJ, 2009.
S. K. Smit and A. E. Eiben. Beating the ’world champion’ evolutionary algorithm via REVAC tuning. In H. Ishibuchi et al., editors,
Proceedings of the 2010 Congress on Evolutionary Computation (CEC 2010), pages 1–8. IEEE Press, Piscataway, NJ, 2010.
doi: 10.1109/CEC.2010.5586026.
K. Sörensen. Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1):3–18, 2015. doi:
10.1111/itor.12001.
J. A. Vázquez-Rodrı́guez and G. Ochoa. On the automatic discovery of variants of the NEH procedure for flow shop schedulingusing genetic programming. Journal of the Operational Research Society, 62(2):381–396, 2010.
S. Wessing, N. Beume, G. Rudolph, and B. Naujoks. Parameter tuning boosts performance of variation operators in multiobjective
optimization. In R. Schaefer, C. Cotta, J. Kolodziej, and G. Rudolph, editors, Parallel Problem Solving from Nature, PPSN XI,
volume 6238 of Lecture Notes in Computer Science, pages 728–737. Springer, Heidelberg, Germany, 2010. doi:
10.1007/978-3-642-15844-5 73.

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

AClib: A Benchmark Library for Algorithm Configuration
F. Hutter, M. López-Ibáñez, C. Fawcett, M. Lindauer, H. H. Hoos, K. Leyton-Brown
and T. Stützle. AClib: a Benchmark Library for Algorithm Configuration, Learning

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Scaling to expensive instances
What if my problem instances are too difficult/large?

and Intelligent Optimization Conference (LION 8), 2014.

Cloud computing / Large computing clusters

http://www.aclib.net/

J. Styles and H. H. Hoos. Ordered racing protocols for automaticallyconfiguring algorithms for scaling performance. GECCO, 2013

Standard benchmark for experimenting with configurators

Tune on easy instances,then ordered F-race on increasingly difficult ones

326 heterogeneous scenarios
SAT, MIP, ASP, time-tabling, TSP, multi-objective, machinelearning
Extensible ⇒ new scenarios welcome !

Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

F. Mascia, M. Birattari, and T. Stützle. Tuning algorithms for tacklinglarge instances: An experimental protocol. Learning and Intelligent
Optimization, LION 7, 2013.

Tune on easy instances,then scale parameter values to difficult ones
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms

Configuring configurators
What about configuring automatically the configurator?
. . . and configuring the configurator of the configurator?

4 it can be done [Hutter et al., 2009] but . . .
8 it is costly and iterating further leads to diminishing returns
Manuel López-Ibáñez and Thomas Stützle

Automated Offline Design of Algorithms