Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

La recherche tabou Introduction Nous sommes souvent confronté à des problèmes d

La recherche tabou Introduction Nous sommes souvent confronté à des problèmes d’optimisation dans une multitude de domaine industrielle ou académique tel que la minimisation d’un coût de production, l’optimisation du parcours d’un véhicule, l’amélioration des performances d’un circuit électronique…etc. la plus part de ces problème sont NP-difficiles, l’utilisation des méthodes exacte garantissant la résolution optimale du problème est beaucoup trop couteuse en terme de temps et de calcul et parfois inutile. Dans ce cas l’utilisation des méthodes approchées permet d’obtenir des solutions acceptables, de bonne qualité dans un temps raisonnable dont font partit les méta-heuristiques. Le domaine des Méta-heuristiques est encor jeune, plusieurs chercheurs ont adapté des idées de différent domaines dans le but de développer des procédures plus puissantes ; le Recuit Simulée est fondé sur des processus physique en métallurgie, tandis que les méthodes génétiques essayent d’imiter les phénomènes biologiques d’évolution naturelle. De même la méthode Tabou peut s’apparenter à une technique fondée sur des concepts d’intelligence Artificielle [Rego, Rou]. La recherche tabou a obtenu des solutions optimales et prés optimales pour une grande variété de problèmes classiques et pratiques, dans des applications allant de la planification aux télécommunications et de la reconnaissance de caractères aux réseaux de neurones [Glo, 90].Le travaille que nous proposons dans cet exposé rentre dans ce contexte, on va présenter la méthode tabous. Après avoir donné un petit historique sur le développement des heuristiques, et la définition de la recherche tabou tout en expliquant le mot tabou et l’origine de la méthode, nous donnerons quelques définitions de bases pour pouvoir entamer dans un troisième temps le principe général de la méthode dans lequel nous nous rentrons dans les détailles de la méthode en analysant les différentes stratégies qui existe dans cette méthode. ensuite nous donnerons quelques problèmes d’optimisation combinatoire utilisant la méthode tabou, nous verrons à cette occasion toute la richesse et la variété de l’application de la méthode. Puis nous citons les avantages et les inconvénients de la recherche tabou, en plus nous donnerons une comparaison de la méthode avec d’autres techniques de l’optimisation. Enfin, nous conclurons notre exposé en donnant quelques perspectives concernant la méthode étudiée. Page 1 La recherche tabou 1. Historique Scientifique 1.1. Les méta-heuristiques Les méta-heuristiques [Hao, 99] contiennent souvent une technique ou une astuce permettant d’éviter de se retrouver piégé dans des minima locaux, en explorant tout l’espace des solutions, de façon à augmenter la probabilité de rencontrer le minimum global. Développement des heuristiques • 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 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 Recherche Tabou 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 taboues (Principe de mémoire) • Par la suite : algorithmes génétiques, colonies de fourmis, …, [Via, Aya, 04]. 1.2 Recherche tabou Tabou (en français): un sujet qu’il est préférable de ne pas aborder si l’on veut respecter les codes de la société. La recherche tabou dans le domaine de la recherche opérationnelle La recherche tabou est une méthode d’optimisation mathématique de la famille des techniques de recherche locale présentée pour la première fois par Fred Glover en 1986 [Glo, Tai, Wer, 92], et elle est devenue très classique en optimisation combinatoire. Elle se distingue des méthodes de recherche locale simples par l’introduction de la notion d’historique dans la politique d’exploration des solutions afin de diriger au mieux la recherche dans l’espace. Cette méthode s’est révélée particulièrement efficace et a été appliquée avec succès à de nombreux problèmes difficiles [Glo, Lag, 98]. Page 2 La recherche tabou 2. Définition de base 2.1. Définition des Variables • i : la solution actuelle F(i) • i’ : la prochaine solution atteinte (solution voisine) F (i’) • V(i): l’espace de solutions voisines à i (l’ensemble des i’) Dans le cadre de l’optimisation combinatoire, en pratique, on aura tout intérêt à définir le voisinage en considérant l’ensemble des modifications élémentaires que l’on peut appliquer à une solution i donnée. V(i) Page 3 La recherche tabou • m : mouvement de i à i’ • i globale : la solution optimale globale qui minimise la fonction objectif F ( ). • i* : la solution optimale actuelle F (i*) 2.2. Définition des termes Mouvement non améliorateur : un mouvement qui nous sortirait d’un minimum local i* en nous amenant à une solution voisine i’ pire que l’actuelle. Page 4 La recherche tabou Mouvement tabou: un mouvement non souhaitable, comme si on redescendait à un minimum local d’où on vient juste de s’échapper. Et donc on a jusqu’a présent : m F (i’) F (i) F (i) global V (i) T : liste des mouvements tabous. Il peut exister plusieurs listes simultanément. Les éléments de la liste sont t(i,m). Une liste T avec trop d’éléments peut devenir très restrictive. Il a été observé que trop de contraintes (tabous) forcent le programme à visiter des solutions voisines peu alléchantes à la prochaine itération. Une liste T contenant trop peu d’éléments peu s’avérer inutile et mener à des mouvements cycliques. a (i,m) : critères d’aspiration, détermine quand il est avantageux d’entreprendre m, malgré son statut tabou. Page 5 La recherche tabou 3. Principe de la méthode 3.1. Idée de départ Se déplacer de solution en solution (en visitant éventuellement des solutions moins bonnes) en s’interdisant de revenir à une solution déjà rencontrée [Run, Esc].  A chaque itération, on examine V(i) et on va sur la meilleure solution i’ même si le coup remonte (F (i’) >F(i)). 2 donc La recherche Tabou ne s'arrête pas au premier optimum trouvé.  Le danger serait alors de revenir à i immédiatement, puisque i est meilleure que i’. Pour éviter de tourner ainsi en rond, on crée une liste T qui mémorise les dernières solutions visitées et qui interdit tout déplacement vers une solution de cette liste. Cette liste T est appelée liste Tabou.  On conserve en cours de route la meilleure solution trouvée i*.  On stoppe dés que le critère de fin est vérifié. 3.2 Algorithme tabou (1) Générer une solution initiale S de manière aléatoire (2) S* S ; C* F(S) / S* est la meilleure solution rencontrée, C* est sont cout et F la fonction objectif (3) Ajouter S a la liste tabou ; K 0 (4) Répéter tant qu’un critère de fin n’est pas vérifié (5) Choisir parmi le voisinage de SK ,V(SK), le mouvement qui minimise F et qui n’appartient pas à la liste tabou, meilleur(SK) (6) SK+1  meilleur(SK) (7) Si la liste tabou est pleine alors (8) Remplacer le dernier élément de la liste tabou par SK+1 (9) Si non (10) Ajouter SK+1 a la liste tabou (11) Fin si (12) Si (C (SK+1) < C*) alors (13) S* SK+1, C* C (SK+1) (14) Fin si (15) Fin d’algorithme Page 6 La recherche tabou Lorsque la mémoire est pleine, elle est gérée comme une liste circulaire en FIFO (First In First Out) : on élimine le plus vieux point tabou et on insère la nouvelle solution. La taille de la mémoire permet de ne pas saturer rapidement les ressources disponibles pour la recherche et permet de surcroît d’adapter facilement la méthode à un espace de recherche dynamique. Le critère d’arrêt : Le critère d’arrêt sert à déterminer le moment où l’on considère que la solution trouvée est d’assez bonne qualité pour être recevable. On peut par exemple : - fixer un nombre maximum d’itérations - après un nombre fixe d’étapes n’ayant pas amélioré la solution s*. - fixer un temps limite après lequel la recherche doit s’arrêter. A partir de cet algorithme initial, certaines adaptations ont été élaborées. Ces améliorations ont été introduites afin de pallier à des problèmes constatés dans l’analyse de l’exploration de l’espace de recherche. [Glo, Lag, 98] recense toutes ces techniques. 3.3. Diverses améliorations - la stratégie d’intensification : Il s'agit de repérer les éléments faisant partie des meilleures solutions trouvées, qui seront utilisées pour générer de nouvelles solutions, devant être proches de l'optimum. Par exemple, [Cha, Kap, 93] utilise cette technique en repartant de la meilleure solution avec une liste tabou vide. Cet examen approfondi peut permettre de dégager quelques propriétés communes définissant les régions intéressantes de l’espace de recherche. Il est alors aisé d’orienter la recherche vers ces zones « prometteuses » en rendant tabou tous les points menant à sortir de ces régions, ou bien on peut également ajouter une pénalité dans la fonction objectif pour les solutions appartenant à d’autre région. Elle est dite aussi : mémoire a moyen terme (quand une région semble contenir de bonne uploads/Science et Technologie/ recherche-tabou.pdf