Tutorial

Enna

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

27 pages

English

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Informations

Publié par	Enna
Nombre de lectures	12
Langue	English

Extrait

Meta-heuristics for Combinatorial Optimization
Jin-Kao Hao
LERIA
University of Angers
2, Boulevard Lavoisier
F- 49045 Angers Cedex 01
phone: (+33) 2 41 73 50 76
email: hao@info.univ-angers.fr
web: www.info.univ-angers.fr/pub/hao
J.K. Hao, Université d'Angers, France
PLAN
1. Combinatorial optimization
2. Review of resolution methods
3. Local search methods
4. Evolutionary methods
5. Hybrid methods
6. Application examples
7. Conclusions
J.K. Hao, Université d'Angers, France
1£
‡
˛
˛
£
ﬁ
˝
Part One
Review of Resolution Methods
for Combinatorial Optimization
J.K. Hao, Université d'Angers, France
Combinartorial Optimization
Minimization
Given a couple (S,f) where
• S a finite set of solutions or configurations (search space)
• f: S R a cost function (or objective)
find s* X S such that f(s*) f(s) for each element s X (feasible space)

X
• • Example: Traveling Salesman Problem TSP• • • • • •
• S • • • • s*
• • • •
Remarks :
• For maximization, one replaces "f(s*) f(s)" by "f(s*) f(s)"
• In practical situations, neither S or f is necessarily given (modeling)
• Most of important optimization problems are NP-hard.
J.K. Hao, Université d'Angers, France
2Resolution Methods
(AI) (OR)
construction recombination local search construction Evolut. Algo. repair
B&BGreedy scatter search Desc tabu SA CSP A* MC GSATEP ES GA
(<56) (<66) path relinking (90) (92)(<72) (86) (83) (74) (68) (75) (66) (73)
(77)
Four main approaches :
1. Construction: step-by-step instantiation of variables according to a static or
dynamic order (branch & bound, CSP, greedy methods...)
2. Local search: iterative transition of complete configurations by local changes
(descent, simulated annealing, tabu search, min-conflicts...)
3. Evolution: evolution of a population of solutions by « genetic » operators (selection,
crossover, mutation), ex: genetic algorithms, scatter search...
4. Hybrid: combination of different approaches (evolution + LR, evolution +
construction...)
J.K. Hao, Université d'Angers, France
Resolution Methods
Construction approach
- step-by-step instantiation of variables according to a static or dynamic order.
- if complete (or exact), then exponential complexity
- examples: branch & bound, CSP, greedy algorithms...
Local search or neighborhood search
- iterative repairs of complete configurations by local changes
- only sub-optimal solutions
- examples: descent, simulated annealing, tabu search, min-conflicts...
Remark : It’s possible to integrate local search within an exhaustive search
Evolution approach
- evolution of a population of solutions by « genetic » operators (selection, crossover,
mutation)
- only sub-optimal solutions
- examples: genetic algorithms, scatter search...
J.K. Hao, Université d'Angers, France
3˛
˛
˛
˛
‹
"
Ì
‹
‹
˛
‹
˛
£
˛
ﬁ
Local Search
Basic Notions
S- Neighborhood function N: S 2 , for each s S, N(s) S
- s S is a local optimum w.r.t. N if s' N(s), f(s) f(s') (minimization)
General procedure
Step 1 (initialization)
a) choose an initial solution s S
b) s* s (i.e. record the best solution found so far)
step 2 (choice & termination)
a) choose s' N(s)
b) s s' (i.e. replace s by s')
c) terminate et return the best solution found if the stop test is verified
step 3 (update)
a) s* s if f(s) < f(s*)
b) go to 2
Remark: Meta-heuristics are different according to the strategy used at step 2
J.K. Hao, Université d'Angers, France
Resolution Methods
Pure descent
step 2 (choice & termination)
a) choose s’ N(s) such that f(s’) < f(s)
b) s s’ (i.e. replace s by s’)
c) terminate if s’ N(s), f(s’) > f(s)
Remark:
Decisions to be taken
o First improvement or best improvement
o how are neighbors evaluated rapidly at each iteration
(special data structures)
Local optimum & remedy
o stop once a local optimum is found
o random re-run
o acceptation of non-improvement neighbors
J.K. Hao, Université d'Angers, France
4
£
D

˛
‹

£
˛
˛
"
D
Local Search
Simulated annealing
Step 2 (choice & termination)
1. choose randomly s' N(s)
2. if f(s') f(s), then accept s, otherwise accept s with probability p( f,T)
3. terminate if stop condition is verified (max nb of iterations…)
Remark:
Decision to be taken
1. how to determine the probability p( f,T)
2. how to evaluate rapidly the neighbors (move values) at each iteration
a search method based (partially) on randomness (exploration > exploitation)
J.K. Hao, Université d'Angers, France
Local Search
Tabu search (TS)
step 2 (choice & termination)
1. choose the best neighbor s’ N(s) i.e. s” N(s), f(s’) f(s”) (tabu list
to prevent the search from cycling)
2. s s’, even if f(s’) > f(s)
3. terminate if stop condition is verified
Remark:
decision to be taken
• what to record in tabu list
• how to determine the length (tabu tenure) of tabu list (dynamic or static)
• how to evaluate rapidly the neighbors (move values) at each iteration
randomness is not essential: exploitation > exploration
J.K. Hao, Université d'Angers, France
5£
D

˛
˛
˛
Local Search
Other local search methods
Variable Neighborhood Search (VNS): a set of (nested) neighborhood
relations are alternatively used during the search process
GRASP: a hybrid method combining greedy construction and local search
J.K. Hao, Université d'Angers, France
Local Search (summary)
Descent:
choose an improving neighbor s' N(s) i.e. f(s') < f(s)
fast but stops at the first local optimum found
Simulated annealing:
choose randomly s' N(s); if f(s') f(s) then accept s'
otherwise accept s' probability p( f,T)
Tabu search:
choose the best neighbor s' N(s), accept s' even if f(s') > f(s) (tabu list to
prevent the search from cycling)
Simualted annealing and tabu search don’t stop at the first local optimum
encountered
J.K. Hao, Université d'Angers, France
6

Local Search: performance
Theory
convergence proof in certain cases (SA, probabilistic TS…) under strong
conditions
Practice
strong experimental results for numerous hard problems
adaptation is necessary:
• problem encoding (configuration and search space)
• neighborhood relations
• constraint handling
• data structures
Improvement
hybrid with genetic algorithms
hybrid with construction approaches
J.K. Hao, Université d'Angers, France
Evolutionary Approach
Basic concepts
evolution of a set of configurations (notion of population)
evolution operators (selection, recombination and mutation)
General procedure
step 1 : (initialization)
choose a set of initial configurations (population)
step 2 : (evolution)
application of recombination and mutation operators
step 3 : (update)
re-organization of the population (e.g. elimination of bad
configurations from the population)
Remarks:
different schools: genetic algorithms, evolutionary strategies,
evolutionary programming
a general and powerful framework for algorithm design
J.K. Hao, Université d'Angers, France
7

Simple Genetic Algorithms (Holland 75)
Main features:
universal problem representation based on binary encoding (binary strings)
random genetic operators (mutaion and crossover)
Crossover: exchange of sub-strings between two indivuduals (monopoint, bi-points,
uniforme...)
1 1 11 0 1 0 1 1 0 1 0
X childrenparents
0 0 0 0 0 0 10 1 1 0 1
Mutation: random modification of bit values of a new configuration

1 1 1 0 1 1 0 1 0 1 0 0
Remarks:
Therory of schemata (building blocks):
the number of short and good schemas (building blocks) increases with the
search,
the performance of a configuration is an indicator of the performance of all the
schemas represented by this particular schema (implicit //)
Decision to be taken:
how to define the fitness function
how to find a compromis between exploitation and exploration
J.K. Hao, Université d'Angers, France
Evolutionary Approach
In practice
Specialization:
specialized encoding adapted to each problem (e.g. permutation for TSP)
specialized evolution operators based on the specialized encoding
Hybrid:
with construction approaches
with local search
•••••• ••••••
•••••• •••••••••••• X X X
•••••• ••••••
J.K. Hao, Université d'Angers, France
8

Evolutionary Approach: Performance
Theory
convergence proof for some cases under strong conditions
Practice
weak results for combinatoria