Remerciez-le!

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

16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 1 La Recherche Tabou Par

16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 1 La Recherche Tabou Par Joseph Ayas Marc André Viau 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 2 • Introduction • Explication détaillée de la Recherche Tabou (RT) • Exemples • Domaines d’application • Ressources disponibles • Conclusion Plan de la présentation 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 3 Introduction • Définition : méthode heuristique de recherche locale utilisée pour résoudre des problèmes complexes et/ou de très grande taille (souvent NP-durs). La RT a plusieurs applications en programmation non linéaire (PNL). • 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) Définition de base de la RT 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 4 Introduction • Mémoire : ⇒elle est représentée par une liste taboue qui contient les mouvements qui sont temporairement interdits ⇒mouvements interdits ou solutions interdites ⇒son rôle évolue au cours de la résolution: diversification (exploration de l’espace des solutions) vers intensification • Exception aux interdictions : il est possible de violer une interdiction lorsqu’un mouvement interdit permet d’obtenir la meilleure solution enregistrée jusqu’à maintenant Définition de base de la RT 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 5 Introduction 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 Historique scientifique 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 6 Introduction • 1986 : bien que son origine remonte à 1977, la 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 taboues (principe de mémoire) • Par la suite : algorithmes génétiques, colonies de fourmis, … Historique scientifique 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 7 Introduction Un randonneur malchanceux , T. A. Bhoulx, 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. Mise en contexte: « Fable des randonneurs » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 8 Introduction Tout d’abord, il commence par descendre tant qu’il peut, en choisissant le chemin de plus grande pente à chaque croisement. Mise en contexte: « Fable des randonneurs » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 9 Introduction Puis, lorsqu’il n’y a plus de sentier menant vers le bas, il décide de suivre le chemin qui remonte avec la plus faible pente car il est conscient qu’il peut se trouver à un minimum local. Mise en contexte: « Fable des randonneurs » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 10 Introduction Toutefois, dès qu’il remonte, il redescend vers le point où il était. Cette stratégie ne fonctionne pas. Par conséquent, il décide de s’interdire de faire marche arrière en mémorisant la direction d’où il vient. Il est à noter que sa mémoire ne lui permet de mémoriser que les deux dernières directions prohibées. Mise en contexte: « Fable des randonneurs » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 11 Introduction Cette nouvelle stratégie lui permet d’explorer des minimum locaux et d’en ressortir. À un moment donné, il arrive à un point où il décèle une forte pente descendante vers le sud. Toutefois, les directions mémorisées lui interdisent d’aller vers le sud car cette direction est prohibée. Il décide d’ignorer cette interdiction et emprunte ce chemin. Mise en contexte: « Fable des randonneurs » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 12 Introduction Cette décision fut bénéfique: il arriva au point de plus basse altitude et attendit les secours qui ne tardèrent à arriver. Mise en contexte: « Fable des randonneurs » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 13 Recherche Tabou: une explication • notion de méta heuristique: souvent utilisée pour décrire la RT (≠méthode exacte) • 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 • ces heuristiques « guidées » peuvent se limiter à de simples descriptions et évaluations de déplacements permis pour passer d’une solution à une autre « Méta heuristique » 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 14 Recherche Tabou: une explication • i : la solution actuelle • i’ : la prochaine solution atteinte (solution voisine) Définition des variables f(i) f( ) f(i’) 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 15 Recherche Tabou: une explication • N(i): l’espace de solutions voisines à i (l’ensemble des i’) • m : mouvement de i à i’ Définition des variables N(i) 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 16 Recherche Tabou: une explication • iglobale : la solution optimale globale qui minimise la fonction objectif f( ). • i* : la solution optimale actuelle Définition des variables f(i*) 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 17 Recherche Tabou: une explication Et donc, jusqu’à présent, nous avons: Résumé des variables f(iglobale) f(i) f(i’) m N(i) 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 18 Recherche Tabou: une explication • 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. La méthode tabou permet un mouvement non améliorateur, comme le permet le recuit simulé. La différence entre les 2 méthodes est que la RT choisira le meilleur i’ dans N(i), l’ensemble des solutions voisines. Définition des termes 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 19 Recherche Tabou: une explication • Mouvement tabou: un mouvement non souhaitable, comme si on redescendait à un minimum local d’où on vient juste de s’échapper. Le mouvement est considéré tabou pour un nombre prédéterminé d’itérations. k représente l’index des itérations (l’itération actuelle). Définition des termes tabou! 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 20 Recherche Tabou: une explication • 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éterminent quand il est avantageux d’entreprendre m, malgré son statut tabou. Définition des termes 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 21 Recherche Tabou: une explication É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’ L’algorithme 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 22 Recherche Tabou: une explication É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: condition qui régira l’arrêt de l’algorithme. ex: arrêt après 22 itérations (k = 22). L’algorithme (suite) 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau 23 Recherche Tabou: une explication • La recherche de la solution optimale peut être améliorée. Voici quelques options: – choix stratégique de la solution initiale i. Ceci donnera une « bonne » valeur de f(i*) – Intensifier la recherche dans les voisinages de solutions qui semblent propices à mener à des solutions proches ou égales à l’optimum – Diversifier la recherche en éloignant celle-ci de voisinages peu propices à produire de bonne solutions – concepts d’intensification et de diversification Améliorations 16 novembre, 2004 Recherche Tabou J. Ayas & M.A. Viau uploads/Science et Technologie/ la-recherche-tabou-plan-de-la-presentation.pdf