Recherche Tabou en Algorithmes

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Que sont les algorithmes de recherche locale?

Les algorithmes de recherche locale sont des algorithmes d'optimisation qui cherchent à trouver la meilleure solution parmi un espace de solutions possibles en explorant uniquement les solutions voisines de la solution courante.

Quelles sont les deux principales lacunes de la méthode de descente?

  • La complexité temporelle et la complexité spatiale
  • La taille du voisinage et le blocage en optima locaux (correct)
  • Le manque de robustesse et la sensibilité aux paramètres d'entrée
  • La difficulté de trouver un point de départ adéquat et la convergence lente

La recherche Tabou est une méthode heuristique qui permet d'éviter le risque de cycler autour d'un optimum local.

True (A)

Quand la recherche Tabou a-t-elle été développée?

<p>La recherche Tabou a été développée dans un cadre particulier par Glover en 1986 et indépendamment par Hansen en 1986. Elle a ensuite été généralisée en 1989-90.</p> Signup and view all the answers

Quel est le principe de base de la recherche Tabou?

<p>Le principe de base de la recherche Tabou est de poursuivre la recherche de solutions même lorsqu'un optimum local est rencontré. Elle permet des déplacements qui n'améliorent pas la solution actuelle et utilise le principe de mémoire pour éviter les retours en arrière (mouvements cycliques).</p> Signup and view all the answers

Que représente la liste tabou dans la recherche Tabou?

<p>La liste tabou représente un ensemble de mouvements ou de solutions qui sont temporairement interdits. Son rôle évolue au cours de la résolution: diversification (exploration de l'espace des solutions) vers intensification.</p> Signup and view all the answers

Il est impossible de violer une interdiction dans la recherche Tabou.

<p>False (B)</p> Signup and view all the answers

Expliquez le concept de fonction d'aspiration dans la recherche Tabou.

<p>La fonction d'aspiration est un critère qui permet de lever l'interdiction pour une solution si elle est considérée comme prometteuse. Elle permet d'explorer une nouvelle région voisine de s si elle est plus prometteuse que les solutions actuelles. La solution s' doit être voisine de s et avoir une valeur inférieure à la solution actuelle s.</p> Signup and view all the answers

Définissez un mouvement non améliorateur.

<p>Un mouvement non améliorateur est un mouvement qui nous sortirait d'un minimum local en nous amenant à une solution voisine pire que l'actuelle.</p> Signup and view all the answers

Comment la recherche Tabou s'applique-t-elle au problème du job shop ?

<p>Le problème du <em>job shop</em> est un problème d'ordonnancement sur plusieurs machines. Il est souvent résolu en utilisant la recherche Tabou pour trouver une bonne solution car il est impossible de tester toutes les combinaisons possibles.</p> Signup and view all the answers

Quelles sont les étapes principales de l'algorithme de recherche Tabou ?

<p>L'algorithme de recherche Tabou comprend plusieurs étapes : 1) choisir une solution initiale, 2) appliquer la liste tabou et les critères d'aspiration, 3) choisir la meilleure solution voisine, 4) mettre à jour la liste tabou et les critères d'aspiration, et 5) vérifier la condition d'arrêt.</p> Signup and view all the answers

Quelle est l'une des conditions d'arrêt possible pour l'algorithme de recherche Tabou?

<p>Le nombre d'itérations successives sans amélioration de la solution dépasse un seuil. (C)</p> Signup and view all the answers

Expliquez la différence entre l'intensification et la diversification dans la recherche Tabou.

<p>L'intensification vise à explorer plus attentivement les régions prometteuses de l'espace de recherche, tandis que la diversification vise à explorer de nouvelles régions qui n'ont pas été explorées auparavant.</p> Signup and view all the answers

Donnez quelques exemples de techniques d'intensification dans la recherche Tabou.

<p>Les techniques d'intensification incluent : geler les éléments bons de la solution courante, augmenter la taille de l'échantillon quand on utilise une méthode de recherche probabiliste, ou modifier l'algorithme interne ou ses paramètres.</p> Signup and view all the answers

Donnez quelques exemples de techniques de diversification dans la recherche Tabou.

<p>Les techniques de diversification incluent : la diversification radicale, qui consiste à forcer l'inclusion d'éléments peu fréquents dans la solution courante, et la diversification continue, qui consiste à biaiser l'évaluation des mouvements en fonction de la fréquence des éléments.</p> Signup and view all the answers

Signup and view all the answers

Flashcards

Recherche Tabou

Une approche de recherche locale qui vise à éviter de se répéter en interdisant temporairement l'exploration de certaines solutions.

Liste Tabou

Un ensemble de solutions interdites pendant un nombre d'itérations défini. La liste tabou empêche la recherche de revenir vers des solutions déjà visitées.

Solution Tabou

Une solution qui est temporairement interdite en raison de sa présence dans la liste tabou.

Voisinage

Un ensemble de solutions voisines à la solution courante. Les solutions voisines diffèrent de la solution courante par un changement minimal.

Signup and view all the flashcards

Critère d'aspiration

Un critère qui permet de lever temporairement l'interdiction d'une solution tabou si elle semble prometteuse. Le critère d'aspiration permet d'explorer de nouvelles régions de l'espace de recherche.

Signup and view all the flashcards

Meilleur Voisin

La meilleure solution parmi toutes les solutions voisines de la solution courante.

Signup and view all the flashcards

Descente

Une technique de recherche locale qui cherche à améliorer progressivement la solution courante en explorant ses voisins, en sélectionnant toujours la meilleure solution parmi les voisins.

Signup and view all the flashcards

Optimum Local

Un état où l'algorithme de descente ne trouve aucune solution voisine meilleure que la solution courante. L'algorithme peut se retrouver bloqué dans un optimum local.

Signup and view all the flashcards

Optimum Global

Une solution qui correspond à la meilleure valeur de la fonction objectif dans tout l'espace de recherche.

Signup and view all the flashcards

Cyclage

Le risque de cycler entre les solutions voisines autour d'un optimum local, empêchant la recherche de trouver de meilleures solutions.

Signup and view all the flashcards

Study Notes

Algorithmes de recherche locale : Recherche Tabou

  • La recherche tabou est une heuristique pour résoudre des problèmes complexes.
  • Elle est apparue dans les années 1970 et a été généralisée en 1989-90.
  • Inspirée du recuit simulé et de la descente.
  • Elle autorise des mouvements de dégradation pour explorer plus largement l'espace de recherche.
  • Risque de cyclage (problème de la méthode de descente).
  • Pour éviter le cyclage, des solutions (ou des mouvements) sont interdites pour un nombre d'itérations spécifiques.
  • Des critères d'aspiration sont mis en place pour permettre de lever l'interdiction d'une solution jugée prometteuse lors de l'exploration.

La méthode de recherche Tabou (RT) : idées de base

  • Considère des solutions voisines.
  • Si l'optimum local est trouvé -> déplacer vers une solution légèrement moins bonne (dégradation de la fonction objectif).
  • L'opération inverse de la dernière opération est interdite (pour une durée donnée).
  • Cette mémoire des itérations précédentes permet d'éviter les optimum locaux.

La méthode de recherche Tabou : mise en œuvre

  • Sauvegarde des solutions (ou des mouvements) interdites.
  • Deux stratégies possibles : liste de solutions interdites ou liste de mouvements interdits.
  • Les listes tabous sont en général de type FIFO (First-In, First-Out).
  • La méthode recherche un optimum global.

La méthode de recherche Tabou : schéma général

  • Commence par une configuration initiale.
  • Génération de configurations voisines.
  • Sélection du meilleur voisin non tabou.
  • Si l'amélioration est observée, le nouveau voisin devient la solution courante et on recommence.
  • Sinon, on arrête.
  • L'algorithme fonctionne à l'aide d'une boucle itérative jusqu'à la condition d'arrêt.

La méthode de recherche Tabou : aspiration

  • L'évaluation des permutations doit pouvoir changer.
  • Possibilité delever l'interdiction pour une solution qui apparait comme prometteuse.
  • La prise en compte de la notion d'aspiration permet de sortir d'un minimum local.

La méthode de recherche Tabou : modifications à la fonction objectif

  • L'intensification et la diversification modifient la fonction objectif pour guider l'exploration vers différentes zones de l'espace de solution.
  • Intensification : privilégier l'exploration de zones proches de la solution courante.
  • Diversification : privilégier l'exploration de nouvelles zones.
  • Les modifications à la fonction objectif sont souvent appliquées pendant des intervalles de temps.

Conditions d'arrêt

  • Arrêt lorsque une solution optimale est trouvée.
  • Arrêt si une limite est atteinte.
  • Arrêt si le temps de calcul est dépassé.
  • Arrêt si la recherche stagne.

Exemple : Problème du job shop

  • Problème d'ordonnancement sur plusieurs machines.
  • Problème NP complet.
  • Différentes problématiques selon le contexte pour la modélisation en graphe des solutions.
  • Détermination du voisinage (exemple: permutation de deux tâches).

Codage de l'algorithme de RT

  • Initialiser une solution courante (une solution initiale).
  • Génération d'un voisinage de solutions possibles.
  • Calcul des temps de production.
  • Mise à jour de la liste des éléments tabous.
  • Conditions d'arrêt.

Conclusion

  • La recherche tabou est efficace pour des problèmes complexes.
  • Elle est compétitive, mais il est important de connaître le problème à traiter.
  • Il faut aussi connaître et comprendre le problème afin de mettre au point une approche de résolution efficace.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Cours4 - Algorithmes de Recherche Locale (PDF)
Use Quizgecko on...
Browser
Open
Browser
Browser