Heuristic Optimization (HO)
Chapter 4 – Part 1: Introduction to metaheuristics
Prof. Dr. Michael Schneider
Chair of Computational Logistics (CL)
RWTH Aachen University
schneider@[Link]
References
Course outline
1 Fundamentals
2 Greedy algorithms
3 Local search
4 Metaheuristics: introduction, design, and paradigms
5 Performance analysis: comparison and evaluation
Michael Schneider Heuristic Optimization 2
References
Metaheuristics
Learning goals:
know what metaheuristics are and how they are classified
Michael Schneider Heuristic Optimization 3
References
Why (meta)heuristics?
Many planning problems in logistics can be modeled as
combinatorial optimization problems; many of them are NP-hard.
On top:
many constraints, possibly multiple objectives
enormous problem sizes
short response times, e.g., in dynamic planning
⇒ exact methods not applicable
(Meta)heuristics:
no guarantee of optimality
no statement how far from optimum (approximation algorithms)
able to achieve acceptable solution quality within reasonable
runtimes
Michael Schneider Heuristic Optimization 4
References
Metaheuristics as intelligent local search
Some metaheuristics aim to overcome the shortcomings of
greedy local search
local optima
plateaus
f(x)
local optima
global optimum plateau
Michael Schneider Heuristic Optimization 5
References
Countermeasures
f(x)
local optima
global optimum plateau
Countermeasures?
multi-start methods
memory (tabu search)
randomization (simulated annealing)
perturbation (iterated local search, variable neighborhood search)
Michael Schneider Heuristic Optimization 6
References
Definition metaheuristics I
A. Løkketangen/G. Laporte: a metaheuristic contains
mechanisms that allow the search to get out of local optima.
F. Glover, G. Kochenberger: Metaheuristics are „solution
methods that orchestrate an interaction between local
improvement procedures and higher level strategies to create a
process capable of escaping from local optima and performing a
robust search of a solution space.“
Michael Schneider Heuristic Optimization 7
References
Definition metaheuristics II
Some metaheuristics are inspired by biology and nature, e.g.,
genetic algorithms, ant colony algorithms, . . .
E. Talbi: Metaheuristic search methods can be defined as upper
level general methodologies (templates) that can be used as
guiding strategies in designing underlying heuristics to solve
specific optimization problems.
I.H. Osman: A metaheuristic is formally defined as an iterative
generation process which guides a subordinate heuristic by
combining intelligently different concepts for exploring and
exploiting the search space, learning strategies are used to
structure information in order to find efficiently near-optimal
solutions.
Michael Schneider Heuristic Optimization 8
References
Definition metaheuristic III
P. Luke: Metaheuristics is a rather unfortunate1 term often used to
describe a major subfield, indeed the primary subfield, of stochastic
optimization. Stochastic optimization is the general class of algorithms
and techniques which employ some degree of randomness to find optimal
(or as optimal as possible) solutions to hard problems. Metaheuristics are
the most general of these kinds of algorithms, and are applied to a very
wide range of problems.
1: Ordinarily I’d call the subfield stochastic optimization. But that’s too general a
term; it includes important algorithms like Markov Chain Monte Carlo (MCMC) or
Gibbs Sampling, which are not in this category. Metaheuristics has lately been the
term of use, but I think it’s profoundly misleading and weird. When I hear
metadiscussion I think: a discussion about discussions. Likewise when I hear
metaheuristic I think: a heuristic about (or for) heuristics. That’s not at all what
these algorithms are about! Perhaps the lesser-used term black box optimization
would be better, though it too comes with some additional baggage. Weak methods
is also too broad a term: it doesn’t imply stochasticity. Sometimes the term
stochastic search is used: but I usually define search problems as all-or-nothing: either
you find the solution or you don’t. We’re not doing search; we’re doing optimization.
Michael Schneider Heuristic Optimization 9
References
Defintion metaheuristic IV
Metaheuristic (Definition)
T. Grünert, S. Irnich: A metaheuristic is a high-level algorithm which
controls the search of one or multiple dependent algorithms. It is
based on a collection of (meta-) strategies that are independent from
the underlying problem and the dependent algorithms.
Metaheuristics are strategies that control the search process.
They are applicable in many heuristics regardless of the
underlying problem.
Concretization of these strategies leads to heuristics for specific
optimization problems.
There may be a large number of heuristics for a specific problem
which are derived from the same metaheuristic.
Michael Schneider Heuristic Optimization 10
References
Definition metaheuristic V
In this sense, greedy-algorithms with
definition of dependent and independent variables
definition of an auxiliary objective function
and local search with
definition of a neighborhood
definition of a search strategy (first/best/ℓ-first improvement)
can be seen as metaheuristics, even though the literature does not
do so.
Michael Schneider Heuristic Optimization 11
References
Classical heuristics vs. metaheuristics
Classical heuristics:
problem-specific and make use of the problem structure, i.e.,
they are designed for a specific problem and are only applicable
to this problem
design of high-quality heuristics is demanding
Metaheuristics:
applicable to a broad range of optimization problems
adaptation to solve a specific problem usually requires much less
effort than the design of a specialized heuristic (from scratch)
But: good problem-specific heuristics often dominate standard
metaheuristics ⇒ high-quality metaheuristics often incorporate
problem-specific knowledge
Michael Schneider Heuristic Optimization 12
References
History of metaheuristics
The term “metaheuristic” was introduced in Glover (1986),
although already some algorithms existed which would nowadays be
classified as metaheuristics.
Mostly coming from the field of optimization in computer
science or mathematics. Important in many research
communities: AI, especially computational intelligence, soft
computing and operations research . . .
Application fields: logistics and production, bioinformatics,
engineering, data mining, finance, . . .
Michael Schneider Heuristic Optimization 13
References
Classification of metaheuristics I
Classification of heuristics and metaheuristics:
Initial solution and stopping criterion:
construction heuristics: starts without a solution and stops after the
generation of a solution
improvement procedures: starts from a given solution and tries to
improve it. Stops if no local improvement is possible or via artificial
stopping criterion.
combined methods: construction and improvement
number of components: simple vs. hybrid
neighborhood: no neighborhood definition, random sampling, or
explicit search of neighborhoods
Michael Schneider Heuristic Optimization 14
References
Classification of metaheuristics II
randomization: deterministic vs. randomized
memory: with vs. without memory
nature-analogy: nature-inspired vs. artificial
number of solutions: (simultaneous) utilization of only one solution vs.
multiple concurrent solutions (single-solution vs. population-based)
Michael Schneider Heuristic Optimization 15
References
Classes of metaheuristics
Well-known metaheuristics are:
Iterated local search (ILS)
Variable neighborhood descent/search (VND, VNS)
Simulated annealing (SA)
Tabu search (TS)
Ruin-and-recreate/large neighborhood search (LNS)
Lagrange heuristics
Genetic algorithms (GA) and evolutionary strategies (ES): evolutionary
computation (EC)
Ant systems, ant colony optimization
Very large-scale neighborhood search (VLSNS)
Particle swarm optimization (PSO)
...
Michael Schneider Heuristic Optimization 16
References
Important!
Successful metaheuristics alternate between intensification (focus
on promising areas of the search space) and diversification
(exploration of the search space).
There is no metaheuristic that is best suited for all problems.
The intelligent use of efficient data structures and subalgorithms
is crucial to the implementation of state-of-the-art
metaheuristics.
Michael Schneider Heuristic Optimization 17
References
Characteristics of good metaheuristics I
Speed:
depends on the planning level: strategic vs. tactical vs. operational
real-time environments, dynamic planning (new orders, emergencies)
interaction
Michael Schneider Heuristic Optimization 18
References
Characteristics of good metaheuristics II
Accuracy:
deviation of objective value from optimal solution
consistency: a heuristic that does well in all cases is often preferred
to a heuristic that is superior in many cases, but performs badly in
some cases. Serious problem: the obtained solutions can be
improved by visual inspection.
good solutions after a short period and a steady improvement
afterwards is often preferred to a single final solution at the end of
the (potentially long) runtime.
Michael Schneider Heuristic Optimization 19
References
Characteristics of good metaheuristics III
Simplicity:
easy to understand, implement, and fine-tune
robust, even if not all details are implemented
reasonable number of parameters with well-defined meaning.
Number can be reduced using reactive mechanisms or by choosing
fixed values. Low sensitivity to changes in parameter values.
Michael Schneider Heuristic Optimization 20
References
Characteristics of good metaheuristics IV
Flexibility of the metaheuristic after adaptation to a specific
problem:
adaptation to problems with additional constraints without strong
deterioration in solution quality.
example: objective function with penalties enables the utilization of
simple operators which may generate infeasible solutions.
Michael Schneider Heuristic Optimization 21
References
For further reading...
(Glover and Kochenberger 2003)
(Gendreau and Potvin 2010)
(Grünert and Irnich 2005): Section 3.8
Michael Schneider Heuristic Optimization 22
References
M. Gendreau and J.-Y. Potvin, editors. Handbook of Metaheuristics.
Springer US, 2010.
F. Glover. Future paths for integer programming and links to artificial
intelligence. Computers & Operations Research, 5:533–549, 1986.
F. Glover and G. A. Kochenberger, editors. Handbook of Metaheuristics.
Springer US, 2003.
T. Grünert and S. Irnich. Optimierung im Transport Band I: Grundlagen.
Shaker Verlag, 2005.
Michael Schneider Heuristic Optimization 22