CHAPITRE II. METHODES D'OPTIMISATION
Algorithm: BASIC_LOCAL_SEARCH
1 : générer la solution initiale(s)
2 : repeat
3 : Choisir s' dans V (s)
4 : if f(s') < f(s) then
5 : s ? s'
6 : until (f(s') = f(s))
II.2.2 Le recuit simulé
Le recuit simulé (Simulated Annealing) est une
méthode très ancienne, et peut être la première
à mettre en oeuvre une stratégie d'évitement des minima
locaux (Kirkpatrick, Gelatt, Vecchi ,1983). Elle s'inspire d'une
procédure utilisée depuis longtemps par les
métallurgistes, qui, pour obtenir un alliage sans défaut,
chauffent d'abord à blanc leur morceau de métal, avant de laisser
l'alliage se refroidir très lentement.
Pour simuler ce système physique, on part d'une seule
configuration, et on fait subir au système artificiel une modification
élémentaire. Si cette perturbation a pour effet de diminuer la
fonction objectif, alors elle est acceptée. Sinon, elle est
acceptée avec la probabilité exp(ÄE
T ) (LE :la perturbation et
T :la température).
Algorithm: SIMULATED_ANNEALING
1 : générer une solution initiale(s)
2 : Poser T ? T - 0
3 : repeat :
4 : Choisir aléatoirements' dans V
(s)
5 : Générer r dans [0, 1]
6 : if r <
exp(f(s)-f(s')
T then
7 : s ? s'
8 : Mettre à jour T
9 : until (critère d'arrêt)
II.2.3 La méthode tabou
Les principes de la méthode tabou (Tabou
Search) ont été proposés par Fred Glover en 1986, et
elle est devenue très classique en optimisation combinatoire.
A l'inverse du recuit simulé, TS examine un
échantillonnage de solutions voisines et retient la meilleure même
si elle n'est pas meilleure que la solution globale. Le danger est de tourner
en rond (cycle) autour d'une gamme de solutions. Pour éviter ceci, on
mettre à jour une liste appelée Tabou qui mémorise les
dernières solutions visitées et qui interdit tout
déplacement vers une solution de cette liste. Mais, le statu tabou, peut
crée un autre danger qui consiste à bloquer le processus de
recherche en rendant tout les mouvements tabou. Cependant, le critère
d'aspiration permet certainement de remédier de cet inconvénient
en acceptant un mouvement même si il est Tabou.
11
| 
