CI

CHAPITRE 5

RI
MÉTHODES DE RECHERCHE LOCALE

Sommaire
1 HE
Principe de la Recherche Locale . . . . . . . . . . . . . . . . . 30
1.1 Transformation élementaire . . . . . . . . . . . . . . . . . . . . 31
aK
2 Recuit Simulé (Simulated Annealing) . . . . . . . . . . . . . . 32
3 Recherche Taboue . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Introduction
Les méthodes de recherche locale sont des métaheuristiques à base de solution unique. La
ad

recherche se fait localement sur un ensemble de voisin de la solution actuelle.

Ce chapitre explique le principe de la recherche locale ainsi que la présentation de deux

méthodes : La méthode de Recuit Simulé (Kirkpatrick et al., 1983), et la méthode de
recherche taboue (Glover, 1989).
.N

1 Principe de la Recherche Locale

Vu l’explosion de l’espace de recherche d’un problème d’optimisation combinatoire, l’énu-
mération peut être contournée par le fait de relier certaines solutions entre elles. Ainsi, à
Dr

partir d’une solution, on peut en trouver une solution voisine.

Le principe des méthodes de recherche locale, appellées aussi méthodes de recherche de

voisinage, se pose sur la construction d’un voisinage de solutions. Autrement dit, à partir
d’une solution de départ S0 on engendre une suite finie de solution Sn déterminées comme

30
 CHAPITRE 5. MÉTHODES DE RECHERCHE LOCALE

plus proches. Généralement, la taille du voisinage est réduite. Ce principe est résumé dans
l’algorithme 3.

CI
Algorithme 3 : Algorithme général d’une méthode de recherche locale
Result : S : Solution
Données :
S0 : Solution initiale;
S : Solution optimale;

RI
S 0 : Solution voisine;
f it : réel;
début
Choisir S0 une solution initiale;
S ← S0 ;
f it ← f (S);

HE
tant que (∃S 0 dans le voisinage de S) et (acceptable(S 0 )) faire
S ← S 0;
f it ← f (S);
fin
fin
aK
1.1 Transformation élementaire
La construction d’un voisinage est définie par des transformations élémentaires. Ces trans-
formations sont des opérations qui permettent de changer une solution S en une autre
solution voisine S 0 . Le voisinage V (S) est l’ensemble de solutions localement proche, que
l’on peut obtenir en appliquant à S une transformation locale élémentaire.
ad

On cite quelques transformations élémentaires :

— Complément : Pour une solution codé en binaire, la transformation élémentaire

est par exemple : remplacer un bit quelconque par son bit complémentaire :
.N

000111 −→ 001111

— Échange (Swap) : Pour une solution codé en caractères (ou en binaires), permuter
2 caractères données :
ABCDE −→ AECDB
Dr

— Insertion Décalage : Pour une chaîne de caractères (ou binaires), choisir 2 posi-
tions i et j, mettre le caractère de la position j en position i et décaler les caractères
à droite :
i=2, j=5 : ABCDEFG −→ AFBCDEG

Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/2021 31

2. RECUIT SIMULÉ (SIMULATED ANNEALING)

2 Recuit Simulé (Simulated Annealing)

Le recuit simulé est une méthode de recherche locale qui simule le procédé de recuit en

CI
métallurgie. Ce processus alterne des cycles de refroidissement lents et de réchauffage
(recuit) qui ont pour effet de minimiser l’énergie du matériau.

La méthode du recuit simulé, introduite par Kirkpatrick et al. (1983), exploite le voisinage

RI
et permet la redirection vers une solution voisine de moindre qualité avec une probabilité
non nulle. Autrement dit, on n’améliore pas toujours la solution. Cette opération permet
d’échapper les optima locaux.

L’algorithme 4 présente le fonctionnement de la méthode Récuit Simulé. Le paramètre

HE
T représente la température qui diminue tout en long de la résolution. Une probabilité
est liée à la température et aux valeurs de la fonction de fitness de la solution actuelle et
celle de la solution voisine. Cette probabilité définit l’acceptation de la nouvelle solution.

Algorithme 4 : Algorithme Recuit Simulé

Result : S : Solution
Données :
aK
S0 , S et S 0 : Solution initiale, optimale et voisine;
V oisin : Liste de solutions;
T0 , T, f it : réels;
début
Initialiser S0 et T0 ;
S ← S0 ;
T ← T0 ;
ad

f it ← f (S);
répéter
Choisir aléatoirement S 0 ∈ V oisin(S);
∆ = f (S 0 ) − f it;
si ∆ ≤ 0 alors
S ← S 0;
.N

f it ← f (S);
sinon
Prendre p nombre aléatoire de [0, 1];
si p < e−∆/T alors
S ← S 0;
f it ← f (S);
fin
Dr

fin
Mise à jour de la température T ;
jusqu’à critère d’arrêt;
fin

Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/2021 32

 CHAPITRE 5. MÉTHODES DE RECHERCHE LOCALE

Discussion
— Si T est très élevée alors p est élevée (−∆/T y 0 , e0 = 1). On a de forte chance
d’accepter la nouvelle solution (une dégradation de qualité).

CI
— Si T est très petite alors p est très petite (−∆/T y −∞ , e−∞ = 0). On a de forte
chance de laisser la solution actuelle.
— Si ∆ est un énorme alors la probabilité est petite.

RI
— Plus la température T est petite plus la probabilité p est petite.
Dans la méthode du recuit simulé, les mécanismes d’intensification et de diversifica-
tion sont contrôlés par la température. Une température élevée permet la diversification.
Comme la température décroît, la recherche tend à s’intensifier vers la fin de l’algorithme.

HE
3 Recherche Taboue
La recherche taboue a été introduite par Glover (1989). L’exploitation du voisinage permet
de se déplacer de la solution courante vers son meilleur voisin. Ce dernier n’est pas
forcément meilleur que la solution courante.
aK
Cette méthode permet un déplacement d’une solution S vers la meilleure solution S 0
appartenant à son voisinage V (S). L’algorithme 5 résume la procédure de la Recherche
Taboue.

Le déplacement interdit, d’où vient le mot tabou, consiste au retour vers une solution
récemment visitée. Pour cela, les solutions visitées sont temporairement interdites et
ad

stockées dans une liste taboue.

Une fois la liste taboue est remplie, la solution la plus ancienne est retirée (selon le
principe d’une file d’attente). La taille de cette liste est un paramètre crucial qui affecte
la résolution du problème. Elle peut être statique ou dynamique.
.N

Discussion
— Si la liste taboue est courte :
— Il y a moins d’interdictions.
— On risque de n’exploiter que peu de distance (intensification).
Dr

— Le risque de tourner en cycle, est plus grand.

— Si la liste taboue est longue :
— Il y a d’avantage d’interdictions.
— On parcourt de plus grandes distances (diversification).

Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/2021 33

3. RECHERCHE TABOUE

Algorithme 5 : Algorithme Recherche taboue

Result : S : Solution
Données :

CI
S0 , S et S 0 : Solution initiale, optimale et voisine;
V oisin, ListeT aboue : Liste de solutions;
T0 , T, f it : réels;
début
Initialiser S0 , V oisin et ListeT aboue;
S ← S0 ;

RI
f it ← f (S);
répéter
Choisir la meilleure S 0 ∈ V oisin(S) tel que S 0 ∈ / ListeT aboue;
si S 0 si elle est meilleure que S alors
S ← S 0;

HE
fin
Enf iler(ListeT aboue, S 0 );
si ListeT aboue est pleine alors
Déf iler(ListeT aboue);
fin
jusqu’à critère d’arrêt;
fin
aK
— Le risque de cycles est réduit.
— Le comportement de l’algorithme dépend de :
— La longueur de la liste taboue.
— La taille du voisinage.
ad

— Plus le voisinage est petit, moins la liste taboue a besoin d’être grande.
Dans la méthode de Recherche Taboue, les mécanismes d’intensification et de diversifi-
cation sont contrôlés par la taille de la liste taboue : On fait de l’intensification, si on
diminue la taille et on favorise la diversification dans le cas contraire.
.N
Dr

Optimisation Combinatoire, M1 GADM, Dr. N. KHERICI, UBMA, 2020/2021 34