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 plan de la presentation

La Recherche Tabou Par Joseph Ayas Marc André Viau novembre Recherche Tabou J Ayas M A Viau Plan de la présentation ? Introduction ? Explication détaillée de la Recherche Tabou RT ? Exemples ? Domaines d ? application ? Ressources disponibles ? Conclusion novembre Recherche Tabou J Ayas M A Viau CIntroduction Dé ?nition de base de la RT ? Dé ?nition 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 novembre Recherche Tabou J Ayas M A Viau Introduction Dé ?nition de base de la RT ? 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 diversi ?cation exploration de l ? espace des solutions vers intensi ?cation ? Exception aux interdictions il est possible de violer une interdiction lorsqu ? un mouvement interdit permet d ? obtenir la meilleure solution enregistrée jusqu ? à maintenant novembre Recherche Tabou J Ayas M A Viau CHistorique scienti ?que Introduction Développement des heuristiques ? Tendance dans les années 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 modi ?cations locales mouvements ?? arrêt lorsqu ? un optimum local est trouvé ? une nouvelle heuristique appara? t le Recuit Simulé ?? permet une exploration aléatoire contrôlée de l ? espace des solutions novembre Recherche Tabou J Ayas M A Viau Historique scienti ?que Introduction ? bien que son origine remonte à la RT n ? est proposée qu ? au milieu des années 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 ? novembre Recherche Tabou J Ayas M A Viau CIntroduction Mise en contexte Fable des randonneurs ? 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