Hybrid Metaheuristics

Prof. E-G. TALBI

OPAC (Parallel Cooperative Optimization)

INRIA DOLPHIN Project

University of Lille, France
http://www.lifl.fr/~talbi
 Motivations
„ Large scale multi-objective optimization problems in
different industrial domains (Telecommunications,
Genomics, Transportation and Logistics, Engineering
design, ...).
„ Problem size more and more important (combinatorial
explosion) et/ou Delays more and more reduced.
(POC) min f ( x ) x∈S

(f (x), f (x),..., f (x))

min f ( x) = n≥2
1 2 n
(PMO)
s.c. x∈S
„ Objective : Efficient Modelling and Solving of Large
(Multi-objective) Combinatorial Optimization Problems
 Optimization Algorithms

Exact algorithms Heuristics

Branch Dynamic Specific

CP Metaheuristics
and X programming (ε-approximation)

Problems of small size

Unique
Population
solution

Simulated Tabu Evolutionary Ants,

Hill-climbing
annealing search algorithms SS, PSO

Tendance in exploitation Tendance in exploration

(neighborhood)

• Exact methods are useless for large problems

• Metaheuristics are efficient (lower bound, best known results, …).
• Lack of theoretical results (applicable in a real context).
 Solution-based metaheuristics

ƒ “Improvement” of a solution
ƒ Exploitation oriented
ƒ Based on the descent
ƒ Exploration of the neighborhood (intensification)
Neighborhood

Replacement
Local
optima
ƒ Local search
ƒ Escape from local optima: Simulated Annealing, Tabu
Search, ILS, VNS, GLS, …
 Population-based metaheuristics
ƒ “Improvement” of a population
ƒ Exploration oriented
ƒ Solutions distributed in the search space
ƒ Recombination is explorative

Recombination Replacement
Parents

Replacement

Offsprings
 Direct recombination
Evolutionary Algorithms: GA, GP, ES, EA
Scatter Search

Selection
Parents

Crossover

Population Mutation

Replacement Offspring
 Indirect recombination: Ant colonies

ƒ Artificial ants: Dorigo (1992)

ƒ Imitate the cooperative behavior of ant colonies
to solve optimization problems
ƒ Use very simple communication mechanism :
pheromone
ƒ Olfactive and volatile substance
ƒ Evolution : evaporation, reinforcement

M. Dorigo, & G. Di Caro. “The Ant Colony Optimization Meta-heuristic”.

New Ideas in Optimization, 1999
 A nature-inspired process
Nest Nest Nest Nest

Obstacle

Equal
Higher level
probability
of pheromone
(left, right)
on the left
Food Food Food Food

ƒ During the trip, a pheromone is left on the ground.

ƒ The quantity left depends on the amount of food found.
ƒ The path is chosen accordingly to the quantity of pheromones.
ƒ The pheromone has a decreasing action over time.

Ant : Solution construction, Pheromone update

 Particle Swarm

ƒ Population based stochastic

metaheuristic
ƒ Dr. Eberhart and Dr. Kennedy (1995)
ƒ Inspired by social behavior of bird
flocking or fish schooling

Kennedy, J. and Eberhart, R. C., "The particle swarm: social adaptation in

information processing systems.," in Corne, D., Dorigo, M., and Glover, F.
(eds.) New Ideas in Optimization London, UK: McGraw-Hill, 1999
 A nature-inspired process

ƒ Particles fly through the problem space

ƒ Flight = add a velocity to the current position
ƒ Social adaptation of knowledge
ƒ Particles follow the current optimum particles («follow the bird which is
nearest to the food »)

Particle: Evaluate the velocities, Flight, Update the

bests
 Estimation of Distribution Algorithm

ƒ Based on the use of (unsupervised) density

estimators/generative statistical models
ƒ Idea is to convert the optimization problem into
a search over probability distributions
ƒ The probabilistic model is in some sense an
explicit model of (currently) promising regions of
the search space
• Initialize a probability model Q(x)
• Do
• Create a population of points by sampling from Q(x)
• Evaluate the objective function for each point
• Update Q(x) using selected population and f() values
• While termination criterion not reached
 EDA simplest probability model

ƒ Population-based incremental Learning (PBIL)

ƒ Initial distribution D=(0.5, …, 0.5)
ƒ Iteration :
ƒ Generation of the population
ƒ Xi = 1 if r<Di (r uniform in [0,1]
ƒ Xi = 0 else
ƒ Evaluate and sort the population
ƒ Update the distribution

D = (1 − α )D + α ⋅ X best
S. Baluja, R. Caruana. Removing the Genetics from the Standard Genetic Algorithm. ICML’95
 Other probability models

ƒ Mutual Information Maximization for Input

Clustering (MIMIC) regards pairwise dependances

J. De Bonet, C. Isbell and P. Viola. MIMIC: Finding optima by estimating

probability densities.
Advances in Neural Information Processing Systems, vol.9, 1997

ƒ Bayesian Optimization Algorithm (BOA) for

multivariate dependances
M. Pelikan, D. Goldberg and E. Cantu-Paz. BOA: The Bayesian optimization
algorithm. In Proc. GECCO’99
Main search components

Representation (Encoding)

Objective function

Variation Operators, Neighborhood

Diversification, Exploration

Intensification, Exploitation

Hybridization

Parallellism and Distribution

 Hybrid Metaheuristics
 Why Hybridation ?
• Equilibrate exploration / exploitation : Gain in performance, Robustness
• Taxonomy : Grammar – Large variety of classified methods
Hybrid Metaheuristics

Low-level High-level Hierarchical

Relay TeamWork Relay TeamWork

Exact Approximate Global Partial General Specialist Flat

Resolution Search space Problems

Application uniformity

• E-G. Talbi, « A taxonomy of hybrid metaheuristics », Journal of heuristics, 8(5), 2002.

 Design issues (Hierarchical)

Hybrid Metaheuristics

Low-level High-level

Relay TeamWork Relay TeamWork

4 Classes : 1. LRH 2. LTH 3. HRH 4. HTH

ƒ Low-level / High-level
ƒ Low-level : Functional composition of a single method.
ƒ High-level : Different methods are self-contained.

ƒ Relay / Teamwork
ƒ Relay : Pipeline fashion.
ƒ Teamwork : Parallel cooperating agents.
 Low-Level Relay Hybrid

ƒ LRH : Hybrids in which a given metaheuristic is

embedded into a single-solution metaheuristic

ƒ Example : Local search embedded in Simulated annealing

(Markov chain explores only local optima) [Martin et Otto 92]

Cost « Kick »
Intermediate

Local search

Start
Trial
Simulated annealing
Configuration
 Low-Level Teamwork Hybrid
ƒ LTH : A optimization method is embedded into a
population-based method.

ƒ Examples :
ƒ Greedy crossover [Grefenstette 85], local search for mutation [Fleurant
94, Chu 97] (lamarckian, baldwin, …) in GAs.
ƒ Local search in Ant colonies [Taillard 97, Talbi et al. 99], Scatter search
[Van Dat 97], and Genetic programming [O’Reilly 95].

[Davis 85]
GA [Talbi 94]
Greedy Indiviuals Individual Tabou
heuristic

Crossover Mutation

Good exploration Good exploitation

 High-Level Relay Hybrid

ƒ HRH : Self-contained optimization methods are executed

in a sequence.

ƒ Example :
ƒ GA + Simulated annealing [Mahfoud 95]. GA + Tabu search [Talbi 94].
ƒ ES + Local search [Nissen 94]. Simulated annealing + GA [Lin 91]

GA Greedy heuristic Greedy heuristic

Initial
population Initial population

Tabu GA GA

Population to exploit

Tabu
 High-Level Teamwork Hybrid
ƒ HTH : Parallel cooperating self-contained algorithms.
ƒ Example :
ƒ Island model for GAs [Tanese 87], Genetic programmig [Koza 95],
Evolution strategies [Voigt 90].
ƒ Tabu search [Rego 96], Simulated annealing [De Falco 95], Ant
colonies [Mariano 98], Scatter search [Van Dat et al. 99].
GA GA
Simulated Annealing
GA GA Genetic Programming
Evolution Strategy
Tabu search
GA GA
Ant Colonies
Scatter search
GA GA

Topology, Frequency of migration, which individuals to migrate ?,

Which individuals to replace ?, ...
 High-Level Teamwork Hybrid

ƒ Example (meta exact): Cooperation between multi-objective

genetic algorithm and a single objective Branch & Cut algorithm (sub-
problem for Vehicle Routing Problem) [Jozefowiez, Talbi 04].

Multi-objective
GA

Single-objective
Branch & cut
(sub-problems)
 Global versus Partial

ƒ Partial : Problem is decomposed in sub-problems. Each

algorithm is dedicated to solve one sub-problem.

ƒ Examples :
ƒ HTH : Tabu search (Vehicle routing) [Taillard 93], Simulated
annealing (placement of macro-cells) [Casoto et al. 86].
ƒ HTH : GA (Job-shop scheduling) [Husbands et al. 90].
Problem

Sub-problem Sub-problem Sub-problem Problem Specific

Genetic Genetic Genetic Tabu search

algorithm algorithm algorithm Simulated annealing

Synchronisation : Build a global viable solution

 Specialist versus General

ƒ Specialist : Algorithms which solve different problems.

ƒ Examples :
ƒ HTH : GA + Tabu (QAP) [Talbi et al. 98]
ƒ HRH : GA + (SA | NM | GA | AC) [Krueger 93][Shahookar et al.
90][Abbattista et al. 95]

Parallel tabu search to solve the QAP Genetic

tabu tabu tabu algorithm

HRH Optimizing the parameters

of another heuristic
Frequency Communication Initial
HTH memory medium solutions Noisy method
Simulated
Genetic algorithm
annealing
Ant colonies

Genetic algorithm to solve a different optimization problem

(diversification task)
 Robot path planning
[E-G. Talbi, P. Bessière, E. Mazer, J-M. Ahuactzin, 1994]
(European project PAPAGENA)

Search Agent SEARCH (local optima)

⎧⎪ 0 If a direct movement exist from mi to τ (i<a)

Min ( M ,τ ) = ⎨
M∈ SS F S
⎪⎩ Min τ − mi Else
i = , a −1
 Robot path planning
Diversification agent EXPLORE

Min (M ) = Max − λ Λ = {λ , λ ,..., λ}

SeF S e Min λ k ∈ Λ m 1 2 n
M∈ e M∈ a k
Set of landmarks

SEARCH EXPLORE
(Parallel GA) (Parallel GA)

Fil d’Ariane (Real robots with Aleph Technologies)

 Hybrid Metaheuristics
 COSEARCH : 3 complementary agents cooperate
via an adaptive memory

Diversifying Agent Intensifying Agent

Solutions
Refers to

Refers to
Promising
in solutions
unexplored regions

Adaptative Memory
Explored regions Promising regions

explored Initial solutions

Good
space
solutions

Search Agent

E-G. Talbi et al. COSEARCH: A parallel cooperativ metaheuristic. Journal of Mathematical Modeling
and algorithms JMMA, Vol.5(2), 2006.
 COSEARCH for QAP

Diversifying Genetic Algo Path relinking Intensifier

The fitness function Solutions being Solutions being Pick

refers to the in unexplored in promising elite
adaptive memory regions regions solutions
Adaptive memory

... ...
Global Frequencies Initial Solutions Elite Solutions
Local Best
Initial
frequency solution
solution
matrix found
Multiple Tabu Search
Tabu search Tabu search ... Tabu search
 Cooperation Meta-Exact
„ Heuristic approach :
„ VLNS : Very Large Neighborhood Search (use of an exact method)

„ Generation of different Sub-Problems solved by an exact method

„ Exact approach :
„ Good solutions found by metaheuristics to reduce the visited search space
for exact methods
Upper bound, Branch and
Partial solutions Bound, Cut
Cooperative
Metaheuristic

Lower bound, Constraint

Optimal Solution sous-pb, programming
Best neighbor

• M. Basseur, J. Lemesre, C. Dhaenens, E-G. Talbi, «Cooperation between branch and bound and evolutionary
algorithms to solve a bi-objective flow-shop problem», WEA’2004, LNCS, Springer, 2004.

• M. Basseur, L. Jourdan E-G. Talbi, «Cooperation between exact methods and metaheuristics : A survey»,
EJOR Journal.2007
 Grammar for extended schemes

< hybrid method > < design-issues > < implementation-issue >
< design-issues > < hierarchical > < flat >
< hierarchical > < LRH >|< LCH >|< HRH >|< HCH >
< LRH > LRH (< method >( < method >))
< LCH > LCH (< method >( < method >))
< HRH > (< method >+ < method >)
< HCH > HCH (< method>)
< HCH > HCH (< method >,< method >)
< flat > (< resolution >,< optimization >,< function >)
< resolution > exact | approached
< optimization > global | partial
< function > general | specialist
< implementation-issue > sequential | parallel < scheduling >
< scheduling > static | dynamic | adaptive
< method > < exact > | < heuristic >
< heuristic > LS | TS | SA | GA | ES | GP | GH | AC | SS | NM | ... < hybrid method
< exact > B&B | B&C | B&P | PL | PD | MS | ... < hybrid method >
 Example of extended hybrid
HTH (HRH (GH + LTH(GA(LS))))
GA GA
Greedy
heuristic
GA GA

GA GA Genetic
algorithm
GA GA

Local search

[Levine 94] [Braun 90]

Set Partitioning Problem Traveling salesman
Airline crew scheduling problem

Parallel static Sequential implementation

implementation