1

Recherche Tabou
Travail encadré par : Mme Lebbar Mari
2

Introduction
3
Plan:

1. Historique
2. Rappel : Méthode de la recherche locale
3. Définition et principe de la recherche tabou
4. Algorithme de la RT
5. Amélioration de la RT
6. Domaines d’utilisation de la méthode
7. Etude de cas
4 Historique:

Tendance dans les années 70 : techniques d’amélioration des solutions par recherche
locale:
⇒ procédure de recherche itérative qui améliore une solution de
départ en lui appliquant une série de modifications locales
⇒ arrêt lorsqu’un optimum local est trouvé,

1983 : une nouvelle heuristique apparaît, le Recuit Simulé
⇒ permet une exploration aléatoire contrôlée de l’espace des solutions

1986 :bien que son origine remonte à 1977, la RT n’est proposée qu’au milieu des
années 80 par Fred Glover
⇒ Depuis cette date,, la méthode est devenue très populaire, grâce aux
succès qu’elle a remportés pour résoudre de nombreux problèmes.
5 Rappel :Méthode
Méthode de la recherche locale
définition:
la recherche locale est une méthode générale utilisée pour résoudre des
problèmes d'optimisation, c'est-à-dire
c'est des problèmes où l'on cherche la
meilleure solution dans un ensemble de solutions candidates
Principe:
La recherche locale consiste à passer d'une solution à une autre solution
proche dans l'espace des solutions candidates (l'espace
( de recherche)
jusqu'à ce qu'une solution considérée comme optimale soit trouvée

Le voyageur de commerce ,Algorithme “branch

“ and
bound”,Algorithme
”,Algorithme Glouton, Méthode de recherche
locale par Michel Van Caneghem, Décembre 2002
6 Définition et principe de la recherche tabou
Définition:
méthode heuristique de recherche locale utilisée pour résoudre des problèmes complexes
et/ou de très grande taille.
Principe de base:
poursuivre la recherche de solutions même lorsqu’un optimum local est rencontré et ce:
, ⇒ en permettant des déplacements qui n’améliorent pas la solution
⇒ en utilisant le principe de mémoire pour éviter les retours en arrière
(mouvements cycliques)

Principe de mémoire:
⇒ elle est représentée par une liste taboue qui contient les mouvements
qui sont temporairement interdits
⇒ mouvements interdits ou solutions interdites / tabou Liste tabou

La recherche Tabou est une généralisation de la recherche local de type voisinage

Recherche Tabou
J. Ayas & M.A. Viau
7 Exemple d’illustration « Fable des
randonneurs »
Problème:

« Un randonneur malchanceux , Ali, est perdu dans une région montagneuse.

Toutefois, il sait qu’une équipe de secours passe régulièrement par le point
situé à la plus basse altitude dans la région. Ainsi, il doit se rendre à ce point
pour attendre les secours. Comment s’y prendra-t-il ? Il ne connaît pas
l’altitude de ce point et, à cause du brouillard, il ne voit pas autour de lui.
Donc, arrivé à un croisement, il doit s’engager dans une direction pour voir si
le chemin monte ou descend »
8 « Fable des randonneurs »
9 « Fable des randonneurs »
10 « Fable des randonneurs »
11 « Fable des randonneurs »
12 « Fable des randonneurs »
13 Algorithme:
définition des variables
• i : la solution actuelle

• i’ : la prochaine solution atteinte (solution voisine)

14 Algorithme: définition des variables
• • N(i): l’espace de solutions voisines à i (l’ensemble des i’)

• • m : mouvement de i à i’
15 Algorithme: définition des variables
• iglobale : la solution optimale globale qui minimise
la fonction objectif f( ).

• i* : la meilleure solution actuelle

16 Algorithme: définition des variables

Et donc, jusqu’à présent, nous avons:

17 Algorithme:
vocabulaire

Mouvement non améliorateur:
améliorateur un mouvement qui nous sortirait d’un
minimum local i* en nous amenant à une solution voisine i’ pire que
l’actuelle.
18 Algorithme:: Vocabulaire

Mouvement tabou: un mouvement non souhaitable, comme si on redescendait
à un minimum local d’où on vient juste de s’échapper

T : (taille) liste des mouvements tabous.

tabous Il peut exister plusieurs listes
simultanément. Les éléments de la liste sont t(i,m). Pour éviter des problème de
la mémoire (10 à 50 mouvements)

a(i,m) : critères d’aspiration.. Déterminent quand il est avantageux
d’entreprendre m, malgré son statut tabou.
19 Algorithme: étapes

Étape 1:
Choisir une solution initiale i dans S (l’ensemble des solutions)
Appliquer i* = i et k = 0

Étape 2:
Appliquer k = k+1 et générer un sous-ensemble de solutions en N(i,k) pour
que:
– les mouvements tabous ne soient pas choisis
– un des critères d’aspiration a(i,m) soit applicable,

Étape 3:
choisir la meilleure solution i’ parmi l’ensemble de solutions voisines N(i,k)
Appliquer i = meilleur i’
20 Algorithme: étapes

Étape 4:
si f(i) <= f(i*), alors nous avons trouvé une meilleure solution
Appliquer i* = i

Étape 5:
mettre à jour la liste T et les critères d’aspiration

Étape 6: si une condition d’arrêt est atteinte, stop. Sinon, retour à Étape 2.

Condition d’arrêt:
-Si
Si une solution prouvée optimale a été trouvée.
-Si
Si une limite a été atteinte en ce qui concerne
-Le
Le nombre d’itérations ;
-Le
Le temps de calcul.
-Si
Si la recherche semble stagner : nombre d’itérations sans amélioration
de la meilleure configuration trouvée
21 Algorithme: schéma
Initialisation, on choisit une STOP
solution initiale S0
S*=S0
OUI

NON Condition
d’arrêt
Choisir une solution s dans le
atteinte?
voisinage de s* qui ne soit pas
tabou

si f(s) < f(s*) alors s*= s et

f* =f(s). mettre à jour les tabous.
22 Amélioration de la RT

La recherche de la solution optimale peut être améliorée. En utilisant les
options suivants:
1-choix stratégique de la solution initiale i. Ceci donnera une « bonne »
valeur de f(i*)
2-intensification:Intensifier la recherche dans les voisinages de solutions
qui semblent propices à mener à des solutions proches ou égales à
l’optimum

3-diversification :Diversifier
Diversifier la recherche en éloignant celle-ci de
voisinages peu propices à produire de bonne solutions
23 Exemple et domaines d’application

Problèmes de transport: Problème des voyageurs de commerce PVC

Planification et ordonnancement:l’exécution
ordonnancement: de certaines tâches, en leur
allouant les ressources requises, tout en respectant les contraintes
imposées, dans le seul et unique but d’optimiser le calendrier régissant
l’atelier,
optimiser l’efficacité d’un atelier en termes de

Problème de JOB SHOP:optimiser
coûts de production et délais de livraison.

Bin-paking (rangement/placement):
rangement/placement):Il s'agit de ranger des objets avec un
nombre minimum de boîtes ou bien le maximum des objet a mettre dans
une boites
Recherche Tabou
J. Ayas & M.A. Viau
24 Etude de cas: problème de voyageur de commerce
(PVC)

Problématique:

Un voyageur de commerce doit visiter un

certain nombre de villes, et chaque ville
une et une seule fois. Etant donne des
distances entre chaque paire de villes, il
doit minimiser la distance totale parcourue.
25 Etude de cas: problème de voyageur de
commerce (PVC)
Idées:

On peut représenter ce problème par un graphe : chaque ville

correspond a un sommet et chaque arête a une paire de villes
pouvant être visitées l'une a la suite de l'autre.

Le problème correspond a trouver un tour complet dans ce graphe

qui minimise la somme des distances f.

On peut représenter le graphe comme une matrice M n×n dont les

coefficients sont strictement positifs sauf sur la diagonale où ils sont
tous nuls.

M est appelé matrice de coût. Ainsi la distance entre le sommet i et

le sommet j est Mij.
26 Etude de cas: problème de voyageur de
commerce (PVC)
on définit:

l’espace de recherche : Sn l'ensemble des permutations de {1,2, ···,n}.
Un point de l'espace de recherche est une permutation

voisinage N(x) : pour une solution X, N(x) est l’ensemble des permutation
par paire de sommets,

La fonction objectif: (la fonction qu’il faut minimiser)

pour une permutation de x:
 Etude de cas: problème de voyageur de
27 commerce (PVC)

On prend un exemple de 10 villes et une distance entre elles de 0 à 100

On prend:
•Liste tabou de taille 10
•Critère d’arrêt : nombre d’itération (100)
(100
Solution initial : s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], valeur = 391
Solution Tabou : s = [9, 0, 3, 1, 8, 4, 7, 5, 6, 2], valeur = 177
28 Etude de cas: problème de voyageur de
commerce (PVC)
Algorithme:
Initialisation:
1-Trouver une solution initiale x0. x* x0, c* f(x0); x* est la meilleure solution
rencontrée, c* sont coût et f la fonction économique..
2- 0 ← k, Liste Tabou = ∅
Répéter tant qu’un critère de fin n’est pas vérifié
1- Choisir parmi le voisinage de xk, V (xk), le mouvement qui minimise f et qui
n’appartient pas à Liste Tabou,, meilleur(xk).
xk+1 ← meilleur(xk).
2-si (c(xk+1) < c∗∗ ) alors x ∗ ← xk+1, c ∗ ← c(xk+1).
3-Mise à jour de liste tabou
29 Références

La Recherche Tabou Par Joseph Ayas & Marc André Viau- [Link], 2004

Le voyageur de commerce ,Algorithme “branch and bound”,Algorithme Glouton,

Méthode de recherche locale par Michel Van Caneghem, Décembre 2002

Optimisation Combinatoire (Méthodes approchées) par Bilel Derbel, 2014

Livre de Kévin « Les algorithmes métaheuristiques » édition Juin 2006

30

Merci pour votre

attention .