Embed Size (px)
Citation preview
Université des Sciences Et de la Technologie d’ORAN Mohamed Boudiaf USTO
Faculté des Sciences — Département d’informatique
2er année Master (RFIA)
Module optimisation avancée
ThèmeLa recherche Tabou
Professeur responsable : Mr BENYETTOU MohamedRéalisée par : BOUCHIKHI Nouha
Année Universitaire : 2012/2013
Sommaire
LA RECHERCHE TABOU
Introduction_______________________________________________________________21. Méthodes de résolution des problèmes d’optimisation combinatoire____________22. Historique scientifique____________________________________________________3
2.1. Développement des métaheuristiques_______________________________3
2.2. La recherche Tabou _______________________________________________33. Définition de la recherche Tabou (RT)_______________________________________44. Principe de la recherche Tabou_____________________________________________4
4.1. Stratégie d’exploration agressive____________________________________5
4.2. Liste Tabou ______________________________________________________5
4.3. Critère d’aspiration _______________________________________________6
4.4. Critère d’intensification____________________________________________6
4.5. Critère de diversification___________________________________________6
4.6. Critère d’arrêt ____________________________________________________65. Algorithme générale de la recherche Tabou__________________________________6
5.1. Algorithme ______________________________________________________7
5.2. Définition des variables____________________________________________7
5.3. Procédure________________________________________________________86. Domaines concernés______________________________________________________87. Etude d’un exemple ______________________________________________________9Conclusion générale_______________________________________________________15Bibliographie_____________________________________________________________16
1
LA RECHERCHE TABOU
Introduction
L’optimisation combinatoire occupe une place importante en recherche opérationnelle, en mathématique discrète et en informatique.Son importance se justifie d’une part par la grande difficulté des problèmes d’optimisation et d’autre part par de nombreuses applications pratiques pouvant être formulées sous la forme d’un problème d’optimisation combinatoire.Bien que les problèmes d’optimisation combinatoire soient souvent faciles à définir, ils sont généralement difficiles à résoudre.
Un problème d’optimisation combinatoire consiste à chercher le minimum s d’une fonction f (fonctions économiques), à variable réelle ou entière sur un ensemble fini S, les éléments de S vérifiant certaines contraintes sont appelés solutions réalisables ; parmi lesquels, figure la solution optimale.
Nous décrirons dans cet exposé quelques approches pour la métaheuristique : recherche Tabou (RT).La RT est une méthode métaheuristique efficace et simple, elle peut être appliquée à un grand nombre de problème d’optimisation combinatoire.
C’est pour cela que la RT a trouvée son application dans une grande variété de problèmes puisqu’elle a permis d’obtenir des solutions de meilleure qualité que celle obtenues par des heuristiques classiques. Dans certains types de problème la solution obtenue se rapproche considérablement de la solution optimale.
Le grand succès de la RT a fait croitre rapidement le nombre des utilisateurs de cette méthode et a donné naissance à plusieurs variantes adaptés à différents types de problèmes.
2
LA RECHERCHE TABOU
1. Méthodes de résolution des problèmes d’optimisation combinatoire
Les techniques pour résoudre les problèmes mathématiques dépendent de la nature de la fonction objective et de l'ensemble des contraintes.
Il existe deux grandes classes de méthodes générales pour la résolution des problèmes d’optimisation combinatoire : les méthodes exactes et les méthodes approchées.
Une méthode approchée est un algorithme permettant de trouver une solution réalisable, tenant compte de la fonction économique et éventuellement des contraintes, mais sans garantie d’optimalité.
Une méthode exacte présente un algorithme permettant de fournir une solution optimale si on lui en laisse le temps nécessaire.
2. Historique scientifique
2.1. Développement des métaheuristiques
Une métaheuristique est une stratégie qui guide et modifie d'autres heuristiques afin de produire des solutions qui diffèrent de celles généralement obtenues dans la recherche d'un optimum local.
L’idée de base des métaheuristiques est d’accepter provisoirement une mauvaise solution pour trouver une meilleure solution :
Pour éviter de rester bloqué sur un optimum local.3
LA RECHERCHE TABOU
Eviter de boucler. Pour parcourir le plus d'espace possible.
-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 (mouvements).
Arrêt lorsqu’un optimum local est trouvé.
-1983 : une nouvelle métaheuristique 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 recherche Tabou (RT) n’est proposée qu’au milieu des années 80 par Fred Glover :
Méthode développée pour résoudre des problèmes combinatoires (la plupart NP-durs).
Révolution de cette méthode par rapport aux autres : permet de surmonter le problème des optima locaux par l’utilisation de listes Tabou (principe de mémoire).
Elle est cependant réputée plus efficace et fiable que le recuit simulé.
-Par la suite : algorithmes génétiques, colonies de fourmis, …
2.2. La recherche Tabou
La méthode Tabou a été introduite simultanément par plusieurs (P.Hansen, F.Glover, B.Jaumard) aux environs de 1986.Recherche Tabou parce qu’il y a interdiction de reprendre des solutions récemment visitées.A chaque itération, le moins mauvais voisin est choisit.Pour éviter les cycles, c’est à dire la répétition infinie d’une séquence de mouvements, les L derniers mouvements sont considérés comme interdits, L étant la taille de la liste Tabou.À chaque itération, le mouvement effectué est donc le moins mauvais mouvement non Tabou.
3. Définition de la recherche Tabou (RT)
Le mot Tabou vient du Tonga polynésien. Le Tonga indique une chose qui ne peut pas être touchée parce qu’elle est sacré, la signification du mot Tabou (Tabu en anglais) est interdit.
La recherche Tabou est une métaheuristique originalement développée par Glover et indépendamment par Hansen.
-Définition de base de RT : méthode métaheuristique utilisée pour la résolution des problèmes d’optimisation, destinée principalement à guider
4
LA RECHERCHE TABOU
d’autres méthodes afin de trouver de meilleures solutions à partir d’une solution initiale obtenue par l’une des heuristiques.
La méthode peut être utilisée pour guider n’importe quel processus qui emploie un ensemble de mouvements pour passer d’une solution à une autre et qui fournit une fonction d’évaluation pour mesurer la qualité de ces mouvements.
4. Principe de la recherche Tabou
Le principe de la recherche Tabou repose sur une méthode de déplacement sur l’espace des solutions, tout en cherchant constamment à améliorer la meilleure solution courante et en conservant en mémoire la liste des précédents déplacements et ainsi guider la recherche en dehors de zones précédemment parcourues.
L’idée de base s’inspire des techniques de recherche utilisées en intelligence artificielle. Elle consiste à garder la trace du cheminement passé du processus de recherche dans une ou plusieurs mémoires et à se servir de cette information afin d’en orienté le déroulement futur.
-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).
La RT est basée sur : L’utilisation de structures de mémoires flexibles (court, moyen, long
terme) permettant l’exploration complète du critère d’évaluation et aussi de l’historique de la recherche.
Un mécanisme de contrôle basé sur l’alternance entre les conditions qui restreignent (restriction Tabou) et qui libèrent (critère d’aspiration) le processus de recherche.
L’incorporation des stratégies dites d’intensification et de diversification de la recherche :
o La stratégie d’intensification utilisant la mémoire à moyen terme, sert à renforcer la recherche dans la région des meilleures solutions trouvées récemment.
o La stratégie de diversification utilisant la mémoire à long terme, sert à guider la recherche dans de nouvelles régions.
En générale on ne va pas garder tous les déplacements (trop coûteux en mémoire), mais on va seulement empêcher l’accès à certains solutions pendant un certains nombre d’itérations.
On définit le voisinage V(s(i)) d’une solution par une transformation élémentaire permettant de passer d’une solution s(i) de S à une autre
5
LA RECHERCHE TABOU
solution s(j) proche avec une faible modification de la structure de la solution s(i). Cette opération est appelée mouvement.Une technique pour ne chercher qu’un sous ensemble du voisinage ; consiste alors à garder dans une liste de candidats une collection des mouvements susceptibles d’être meilleurs (de plus forte qualité).
La manière la plus simple de définir les Tabou est de conserver une liste T.Quand on explore un voisinage, on choisit le meilleur voisin à l’exclusion des points de la liste Tabou.
4.1. Stratégie d’exploration agressive
La mémoire à court terme correspond à une stratégie d’exploration agressive, représente la partie principale de la recherche Tabou et a pour but de choisir le meilleur mouvement, ce mouvement pour être accepté doit vérifier certaines contraintes appelées restrictions Tabou. Ces restrictions Tabou sont conçues pour éviter les répétitions et les mouvements n’améliorant pas la solution.
4.2. Liste Tabou
La liste Tabou représente la mémoire à court terme, elle contient les attributs des mouvements les plus réalisés.Cette liste est maintenue dans le but d’orienter la recherche.
4.3. Critère d’aspiration
Ce critère est souvent utilisé pour enlever les restrictions Tabou d’un mouvement de haute qualité.
Il permet de passer outre certains cas interdits. Son utilisation principale consiste à outrepasser l’interdiction d’un mouvement s’il permet d’obtenir un élément meilleur que la solution trouvée jusqu’à présent (consiste à révoquer le statut Tabou d’un mouvement si ce dernier permet d’atteindre une solution de qualité supérieure à celle de la meilleure solution trouvée jusqu’alors).
4.4. Critère d’intensification (exploration plus poussée d’une région prometteuse)
L’intensification consiste à retourner à l’une des meilleures solutions trouvées jusqu'à présent, puis de reprendre la recherche à partir de cette solution.
La stratégie d’intensification est matérialisée dans l’algorithme suivant par renforcement de la recherche dans la liste des meilleurs mouvements.
4.5. Critère de diversification
6
LA RECHERCHE TABOU
Elle consiste à générer une nouvelle solution, différente de celle déjà explorées, dans le but de partir dans une nouvelle direction, pour explorer une autre région.
Remarque : La stratégie d’intensification utilise la mémoire à moyen terme, sert à renforcer la recherche dans la région des meilleures solutions trouvées récemment.La stratégie de diversification utilise la mémoire à long terme, sert à guider la recherche dans des nouvelles régions.
4.6. Critère d’arrêt
En règle générale, pour interrompre l’algorithme, on prend ou à laisser compte deux critères, tout d’abord on vérifie à chaque itération que le compteur d’itérations totales n’a pas dépassé un nombre maximal depuis le début de processus.On se base sur une autre valeur seuil, qui correspond au nombre maximal d’itérations que l’on s’autorise entre deux modifications (améliorations) consécutives de la (meilleure) solution.Mais au lieu de considérer le nombre d’itérations, on pourrait aussi se baser sur le temps total, qui devrait être inférieur à une valeur maximale.
5. Algorithme générale de la recherche Tabou
Nous présentons ci-dessous l’algorithme général de la recherche Tabou, en mettant l’accent sur la mémoire à court terme et l’exploration agressive :
1-Obtenir une solution initiale.2-Créer une liste des mouvements candidats.3-Choisir le meilleur candidat. Ce choix est basé sur les restrictions Tabou et le critère d’aspiration.-On obtient ainsi une autre solution, mais qui ne sera enregistrer que si elle est meilleur que la solution précédente.4-Appliquer le critère d’arrêt.-Continue : changer les candidats d’admissibilité (restriction Tabou et critère d’aspiration). Aller à 2.-Stop : passer aux stratégies d’intensification et de diversification.
5.1. Algorithme
Étape 1: choisir une solution initiale i dans S (l'ensemble des solutions)Appliquer i* = ik = 0T = 0
Étape 2: appliquer k = k+1 et générer un sous-ensemble de solutions en N(i,k) pour que :
7
LA RECHERCHE TABOU
- les mouvements Tabou 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'
Étape 4: si f(i) <= f (i*), alors nous avons trouvé une meilleure solutionAppliquer 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: condition qui régira l'arrêt de l'algorithme.
Ex : arrêt après 22 itérations (k = 22).
5.2. Définition des variables
• i : la solution actuelle• i' : la prochaine solution atteinte (solution voisine)• N(i): l'espace de solutions voisines à i (l'ensemble des i')• m : mouvement de i à i'• i globale : la solution optimale globale qui minimise la fonction objectif f( ).• i* : la solution optimale actuelle f(i*)• T: liste des mouvements Tabou. Il peut exister plusieurs listes simultanément. Les éléments de la liste sont t(i,m).• a(i,m) : critères d'aspiration. Déterminent quand il est avantageux d'entreprendre m, malgré son statut Tabou.
5.3. Procédure
A chaque étape de l'algorithme, on examine la solution du voisinage de la solution courante qui minimise la fonction coût.Si la solution courante n'est pas un minimum local, on va rapidement trouver ce minimum. Si c'est déjà un minimum local, on s'intéresse à la solution qui fait augmenter le coût le moins possible.
On est sûr dans ce cas de tomber sur un cycle. Pour éviter cela, on garde à jour la liste des solutions déjà explorées (liste des solutions Tabou), et on se limite aux solutions qui n'appartiennent pas à cette liste.
Cette liste peut devenir de taille trop grande. Plutôt que de retenir les solutions, on peut donc retenir les modifications locales ayant produit les solutions à partir de la solution initiale. On a donc une liste de modifications qu'on s'interdit de remonter. Pour éviter de bloquer
8
LA RECHERCHE TABOU
complètement l'algorithme, il est bon de ne pas se souvenir de toutes les modifications depuis le début, mais seulement des dernières (de 3 à 15 environ), en les gérants sous forme d'une file.
Ceci dit, aucune garantie n'existe de convergence ni même de non circularité.Il faut donc prévoir un test d'arrêt.Lorsque l'algorithme s'arrête, on garde la meilleure solution rencontrée.
6. Domaines concernés
-Problèmes de transport : Confection de tournées de véhicules (contraintes de capacité,
fenêtres de temps, transport multi-modes, multi-produits,). Ordonnancement de convois. Design de réseaux. Problème du voyageur de commerce.
-Planification et ordonnancement : Flow shop. Job shop. Fabrication en cellule. Planification de la main-d'œuvre requise.
-Optimisation de la production et gestion des inventaires : Production juste-à-temps. Planification d'inventaires multi-produits. Gestion des économies d'échelle.
-Problèmes d'affectation et de localisation.
-Optimisation de graphes : Coloration de graphes (Hertz, Taillard, De Werra). Clique maximale (Gendreau, Soriano).
-Télécommunications : Conception de réseaux (optiques, de service, ). Routage d'appels.
-Logique et intelligence artificielle : Reconnaissance et classification de formes. Réseaux de neurones.
-Application à diverses technologies : Construction de stations spatiales. Distribution de puissance électrique. Inversion sismique.
-Optimisation de structures : Structure des protéines.
9
LA RECHERCHE TABOU
Séquençage d'ADN.
-Résolution en parallèle (parallel computing).
-Optimisation continue et stochastique.
-Analyses financières.
7. Etude d’un exemple :
Pour faciliter la compréhension des divers composants de la recherche Tabou, nous présentons son application sur un problème très connu en intelligence artificielle : le problème des reines.
Ce problème consiste à placer n reines sur un échiquier nxn, de telle manière qu’aucune reine n’en capture une autre. Pour cela, il ne faut pas que deux reines soient placées sur la même ligne, la même colonne ou la même diagonale.Si ce principe n’est pas vérifié, on parle alors de collision.
Le but de l’optimisation du problème est de minimiser le nombre de collisions.
Formulation d’une collision :X = {X(1), X(2),X(3),X(4),……,X(n)} ; X(i) est l’index de la colonne avec :
X(i) ≠ X(j) (pour que deux reines ne soient pas placées dans la même ligne ou la même colonne).
Et pour identifier les diagonales, nous remarquons que :
La somme des index des colonnes et lignes est constant pour chaque diagonale négative.Exemple : si R1 est diagonale négative avec R3 on a : 1+X(1) = 3+X(3)
La différence des index des colonnes et lignes est constant pour chaque diagonale positive.Exemple : si R1 est diagonale positive avec R3 on a : 1-X(1) = 3-X(3)
Pour représenter ce problème, nous utilisons : Liste Tabou : contient les mouvements interdits. Mouvement (permettant d’aller d’une solution à une
autre) : correspond à permuter les positions des deux reines en collision.
Critère d’aspiration : entreprendre le mouvement en respectant les contraintes de collision.
10
LA RECHERCHE TABOU
La fonction f à minimiser : minimiser le nombre de collision.
Pour illustrer la méthode et ses composants, nous utiliserons un échiquier 7x7.Nous supposons au début qu’une solution initiale peut être construite (d’une manière aléatoire ou intelligente), cette solution est représentée comme suit :
Itération 0 :4 5 3 6 7 1 2
Cette solution indique qu’il y’a : une reine (R1) dans la ligne1, colonne4 ; une reine (R2) dans la ligne2, colonne5 ; une reine (R3) dans la ligne3, colonne3 ; ….
Cette configuration a un total de 4 collisions :
(R1,R2) (R4,R5) (R6,R7) (R2,R6)
La fonction f = somme(collisions)=4
Itération 1 :
Initiale
Appliquer le critère d’aspiration : l’échange de position des reines (R1,R7) est le meilleur mouvement.
R1
R2
R3
R4
R5
R6
R7
4 5 3 6 7 1 2
2 5 3 6 7 1 4
R1
R2
R3
R4
R5
R6
R7
11
LA RECHERCHE TABOU
Cette configuration a un total de 2 collisions : (R4,R5) (R2,R6)
La liste Tabou contient : { (R1,R7) }
La fonction f = somme(collisions)=2
Itération 2 :
Appliquer le critère d’aspiration : l’échange de position des reines (R2,R4) est le meilleur mouvement.
Cette configuration a un total de 1 collision :
(R1,R4)
La liste Tabou contient : { (R1,R7), (R2,R4) }
La fonction f = somme(collisions)=1
Itération 3 :
Appliquer le critère d’aspiration : l’échange de position des reines (R1,R3) est le meilleur mouvement.
2 6 3 5 7 1 4
R1
R2
R3
R4
R5
R6
R7
3 6 2 5 7 1 4
12
LA RECHERCHE TABOU
Cette configuration a un total de 1 collision :
(R1,R5)
La liste Tabou contient : { (R1,R7), (R2,R4), (R1,R3) }
La fonction f = somme(collisions)=1
Itération 4 :
Appliquer le critère d’aspiration : l’échange de position des reines (R5,R7) est le meilleur mouvement.
Cette configuration a un total de 2 collisions :
(R3,R5) (R4,R5)
La liste Tabou contient : { (R1,R7), (R2,R4), (R1,R3) (R5,R7) }
La fonction f = somme(collisions)=2
Itération 5 :
Appliquer le critère d’aspiration : l’échange de position des reines (R4,R7) est le meilleur mouvement.
R1
R2
R3
R4
R5
R6
R7
3 6 2 5 4 1 7
R1
R2
R3
R4
R5
R6
R7
3 6 2 7 4 1 5 13
LA RECHERCHE TABOU
Cette configuration a un total de 1 collision :
(R3,R5)
La liste Tabou contient : { (R1,R7), (R2,R4), (R1,R3), (R5,R7), (R4,R7) }
La fonction f = somme(collisions)=1
Itération 6 :Appliquer le critère d’aspiration : l’échange de position des reines (R1,R3) est le meilleur mouvement.
Cette configuration a un total de 0 collision.f = min.
R1
R2
R3
R4
R5
R6
R7
2 6 3 7 4 1 5
R1
R2
R3
R4
R5
R6
R7
14
LA RECHERCHE TABOU
Conclusion générale
Tout un ensemble de méthodes, des plus particulières (la programmation linéaire et les méthodes de gradient) aux plus générales (les métaheuristiques) :
Les méthodes particulières sont plus difficiles à programmer, mais plus efficaces.
Les méthodes générales sont faciles à programmer et d’un champ d’application plus vaste.
Donc choisir toujours la méthode la plus spécialisée compatible avec la définition du problème.
La recherche Tabou peut être considérer comme une généralisation des méthodes d’améliorations locales traditionnelles.
L’application de recherche Tabou sur n’importe quel type de problèmes ne garantie en aucun cas un succès définitif, mais le plus important est de savoir comment adapter la recherche Tabou au problème posé, et ceci en ajustant de façon adéquate ses différents composants (restriction Tabou, critère d’aspiration,…).
15
LA RECHERCHE TABOU
Bibliographie
http://wwwabi.snv.jussieu.fr/jompo/Public/OBI/OBI2/Optimisation_combinatoire.pdf
http://www.cours.polymtl.ca/mth6414/automne2004/presentations/MTH6414_Recherche_Tabou.pdf
http://www.cmi.univ-mrs.fr/~preaux/PDF/Optimisation%20Combinatoire.pdf
http://julien.chauveau.online.fr/m1info/optimisation_combinatoire/assets/OC-Hao-Meta06.ppt
http://www-igm.univ-mlv.fr/~desar/Cours/M1-1_Optimisation_Combinatoire/chap5.pdf
http://www.emse.fr/spip/IMG/ppt/Morineau_26-04-07.ppt
http://deptinfo.unice.fr/twiki/pub/Minfo03/SystemesArtificielsComplexes/Meta-heuristiques.ppt
http://tisic.inrets.fr/Seminaires/seminaire6prog.pdf
http://perso.ens-lyon.fr/paul.feautrier/slides-ch3.pdf
Zach Kahla.Y & Zouaoui.K« Résolution approchée des problèmes de tournées des véhicules avec flotte homogène et fenêtre de temps par la méthode Tabou »Mémoire d’ingénieur, USTO 2007
Sebianne.W & Gadi.FZ« Résolution approchée ‘méthode Tabou’ d’un problème d’ordonnancement de tâches sur une machine »
16
LA RECHERCHE TABOU
Mémoire d’ingénieur, USTO 2003
17
