University of Zagreb, Croatia
Lecture 6
Heuristic Optimization Methods:
Improving Local Search
Slides prepared by Lea Skorin-Kapov
Academic year 2020/2021
Graduate Studies Programme
Local Search improvements
University of Zagreb, Croatia
Source: Talbi, “Metaheuristics: From Design to Implementation”, 2009
Zavod za telekomunikacije 2
Outline
University of Zagreb, Croatia
Iterating with different solutions
Multistart local search
Iterative local search
Variable Neighborhood Search
Guided local search
Zavod za telekomunikacije 3
Outline
University of Zagreb, Croatia
Iterating with different solutions
Multistart local search
Iterative local search
Variable Neighborhood Search
Guided local search
Zavod za telekomunikacije 4
Multistart local search
University of Zagreb, Croatia
Example: minimization, 3 initializations
2nd initial solution 1st initial solution
3rd initial solution
END
Already
found!
Still not
1st found local
2ndfound local The best seen necessarily
optimum solution is the optimum globally
final one optimal…
Zavod za telekomunikacije 5
Multistart local search
University of Zagreb, Croatia
knowledge obtained during the previous local
search phases is not used.
an initial solution is generated randomly and is
unrelated to previously generated local optima.
Random restart becomes less effective as the
instance size grows → biased sampling is
neccessary
Zavod za telekomunikacije 6
Iterated local search (ILS)
University of Zagreb, Croatia
How to improve classical multi-start local
search?
➢ At each iteration, perturb the obtained local optima
➢ Apply local search on the perturbed solution
➢ Accept generated solution as new current solution
under certain conditions
➢ Iterate until a given stopping criterion
Zavod za telekomunikacije 7
Iterated local search (ILS)
University of Zagreb, Croatia
objective
initial solution
LS
𝑠0 perturbed solution
𝑠∗
𝑠′
first local optimum
𝑠∗′
second local optimum
search space
If S* is the set of all locally optimal solutions, we want to explore S* using a walk from
one local optimum to another. If 𝑠∗′ passes an acceptance test, it becomes the next
element in the walk. Otherwise go back to 𝑠∗
Zavod za telekomunikacije 8
Iterated local search (ILS)
University of Zagreb, Croatia
Basic algorithm template:
Source: Talbi, “Metaheuristics: From Design to Implementation”, 2009
Perturbation Search algorithm Acceptance
method initial solution (e.g., LS, TS, SA…) local optima criteria
Zavod za telekomunikacije 9
Iterated local search (ILS)
University of Zagreb, Croatia
Design choices:
1. Local search: any single-solution metaheuristic
can be used (e.g., simple descent, tabu search,
SA…)
2. Perturbation method: the perturbation operator
may be seen as a large random move of the
current solution.
Goal: keep some part of the solution and perturb strongly
another part of the solution
3. Acceptance criteria: defines the conditions the
new local optima must satisfy to replace the current
solution.
Zavod za telekomunikacije 10
ILS: perturbation method
University of Zagreb, Croatia
Perturbation length: related to the neighborhood associated
with the encoding or the number of modified components;
can be fixed or variable length
Too small perturbation: may generate cycles in the search and no
gain is obtained
Too large perturbation: will erase the information about the search
memory; good properties of the local optima are skipped
Perturbation can be random or semideterministic
When designing an ILS algorithm, a good idea is to compare the
performance of random restart and the implemented perturbation.
Speed: in general, k local searches embedded in an iterated local search
will be much faster than running k local searches with random restart!
Zavod za telekomunikacije 11
ILS: acceptance criteria
University of Zagreb, Croatia
Control the tradeoff between intensification and diversification
weak strong
selection selection
Diversification Intensification
Accept any solution Accept only improving
regardless of its quality solutions in terms of
objective function
Balancing the two extremes: probabalistic acceptance (e.g.,
Boltzmann distribution in SA), deterministic acceptance criteria
(e.g., based on predefined threshold…)
Zavod za telekomunikacije 12
ILS application domains
University of Zagreb, Croatia
ILS algorithms have been successfully applied to a variety of
combinatorial opt. problems.
Example application domains
TSP (e.g., iterated Lin-Kernighan heuristic - ILK)
VRP (e.g., prize collecting VRP, VRPs with time penalty
functions…)
Scheduling problems
Graph partitioning
Quadratic assignment problem
…
Zavod za telekomunikacije 13
Outline
University of Zagreb, Croatia
Iterating with different solutions
Multistart local search
Iterative local search
Variable Neighborhood Search
Guided local search
Zavod za telekomunikacije 14
Variable Neigborhood Search (VNS)
University of Zagreb, Croatia
Key concepts:
Fact 1: a local minimum w.r.t. one neighborhood
structure is not necessarily so for another
Fact 2: A global minimum is a local minimum w.r.t. all
possible neighborhood structures
Fact 3: For many problems, local minima w.r.t. one or
several Nk (neighborhood structures) are relatively
close to one another.
Zavod za telekomunikacije 15
Variable Neigborhood Search (VNS)
University of Zagreb, Croatia
Basic idea:
successively explore a set of predefined neighborhoods to provide
a better solution
Systematically change neighborhood both in a descent phase to
find a local optimum and in a perturbation phase to get out of a
correspoding valley
Difference between ILS and VNS:
ILS has the explicit goal of building a walk in the set of locally optimal
solutions, while VNS algorithms are based on the idea of systematically
changing neighborhoods during the search.
Zavod za telekomunikacije 16
Variable Neigborhood Descent (VND)
University of Zagreb, Croatia
First consider Variable Neigborhood Descent and then build towards
Basic VNS and General VNS…
VND: performs a change of neighborhoods in a deterministic way.
Neighborhoods denoted as 𝑁𝑙 , 𝑙 = 1, … , 𝑙𝑚𝑎𝑥
Neighborhood Neighborhood Neighborhood
N2 N3 Nmax
….
Neighborhood
N1
Improving neighbor
Non-improving neighbor
Zavod za telekomunikacije 17
Variable Neigborhood Descent (VND)
University of Zagreb, Croatia
Basic algorithm template:
Source: Talbi, “Metaheuristics: From Design to Implementation”, 2009
w.r.t. the order in which neighborhoods are applied: the most popular
strategy is to rank the neighborhoods following the increasing order of their
complexity (e.g., the size of the neighborhoods)
Zavod za telekomunikacije 18
Basic VNS
University of Zagreb, Croatia
Define a set of neighborhood structures Nk, k=1,…,n
At each iteration, an initial solution is shaken from the SHAKING
current neighborhood Nk
For example, solution x’ is generated randomly from Nk(x)
A local search procedure is applied to x’ to generate x’’. LOCAL SEARCH
If f(x’’)<f(x), then x’’ becomes the new current solution
and the search restarts from the current solution using
N 1.
If x’’ is not better than x (i.e. f(x’’)>=f(x)), then move to
Nk+1, randomly generate a new solution and try to
MOVE
improve it.
Repeat until termination criteria satisfied.
Zavod za telekomunikacije 19
Basic VNS
University of Zagreb, Croatia
Basic algorithm template:
Source: Talbi, “Metaheuristics: From Design to Implementation”, 2009
Often nested neighborhoods are used: 𝑁1 (x)⊂ 𝑁2 (𝑥) ⊂… ⊂ 𝑁𝑘 (𝑥), ∀𝑥 ∈ 𝑆
Zavod za telekomunikacije 20
General VNS
University of Zagreb, Croatia
General VNS: replace simple LS procedure
Basic algorithm template: with the VND algorithm.
Note: in that case, neighborhoods N1,…,Nlmax
are used in VND, while a different series of
neighborhoods N1,…,Nkmax apply to the shake
step!
Source: Talbi, “Metaheuristics: From Design to Implementation”, 2009
Often nested neighborhoods are used: 𝑁1 (x)⊂ 𝑁2 (𝑥) ⊂… ⊂ 𝑁𝑘 (𝑥), ∀𝑥 ∈ 𝑆
Zavod za telekomunikacije 21
Outline
University of Zagreb, Croatia
Iterating with different solutions
Multistart local search
Iterative local search
Variable Neighborhood Search
Guided local search
Zavod za telekomunikacije 22
Guided Local Search (GLS)
University of Zagreb, Croatia
Basic idea:
dynamically change objective function according to the
already generated local optima
features of the obtained local optima are used to
transform the objective function
allows modification of the landscape structure to escape
from the obtained local optima
Zavod za telekomunikacije 23
GLS
University of Zagreb, Croatia
objective
objective penalization
𝑠0
first local optimum
second local optimum
search space
Zavod za telekomunikacije 24
GLS
University of Zagreb, Croatia
A set of m features of a solution are defined:
𝑓𝑡𝑖 (𝑖 = 1, … , 𝑚)
A cost ci is associated with each feature. When trapped
in local optima, the algorithm will penalize solutions
according to selected features.
To each feature i is associated a penalty pi that
represents the importance of the feature.
Indicator function: indicates whether the feature is
present in the current solution or not:
1 𝑖𝑓 𝑓𝑒𝑎𝑡𝑢𝑟𝑒 𝑓𝑡𝑖 ∈ 𝑠
𝐼𝑖 𝑠 = ቊ
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Zavod za telekomunikacije 25
GLS
University of Zagreb, Croatia
• Specifies an augmented objective (cost) function to guide
the Local Search algorithm out of the local minimum, by
penalising features present in that local minimum:
𝑚
𝑓′ 𝑠 = 𝑓 𝑠 + 𝜆 𝑝𝑖 𝐼𝑖 (𝑠)
𝑖=1
𝜆 represents the weights associated with different penalties
• Given a local optima s*, a utility ui is associated with each
feature.
→ Idea: penalise features that have high costs, although the
utility of doing so decreases as the feature is penalised more
and more often ∗ ∗
𝑐𝑖
𝑢𝑖 𝑠 = 𝐼𝑖 (𝑠 )
1 + 𝑝𝑖
Zavod za telekomunikacije 26
GLS
University of Zagreb, Croatia
Basic algorithm template:
Source: Talbi, “Metaheuristics: From Design to Implementation”, 2009
intensify the search of promising regions defined by lower cost features;
diversify the search by penalizing features of local optima to avoid them
Zavod za telekomunikacije 27
GLS
University of Zagreb, Croatia
Prior information Search information
GLS local minima
feature costs
problem operator (i.e. move) Local
information Search
penalties
cost (objective)
function augmented cost
function
source: Voudouris, Christos & Tsang, Edward & Alsheddy, Abdullah. (2010). Guided Local Search. 10.1007/978-1-4419-1665-5_11.
Zavod za telekomunikacije 28
