Aller au contenu

La recherche tabou

Recherche tabou définition et exemple La recherche tabou est une méthode heuristique utilisée pour résoudre des problèmes d'optimisation combinatoire. Cet article présente sa définition, son algorithme, ses domaines d'application, ainsi que ses avantages et inconvénients. Un exemple illustratif est également fourni pour aider à comprendre son fonctionnement.

D'après le document La recherche tabou

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

La recherche tabou

Programmation, Mathématiques, Optimisation combinatoire · PPTX · 25 pages · 1977

Consulter le document original →

Recherche tabou définition et exemple

La recherche tabou est une méthode heuristique utilisée pour résoudre des problèmes d'optimisation combinatoire. Cet article présente sa définition, son algorithme, ses domaines d'application, ainsi que ses avantages et inconvénients. Un exemple illustratif est également fourni pour aider à comprendre son fonctionnement.

Définition de la recherche tabou

La recherche tabou est une méthode heuristique de recherche locale qui permet de résoudre des problèmes complexes et de grande taille. Elle repose sur l'idée d'accepter temporairement une solution moins optimale pour explorer d'autres possibilités et éviter de rester bloqué sur un optimum local. Le terme "tabou" provient du mot polynésien "Tonga", signifiant quelque chose de sacré ou d'interdit.

Les métaheuristiques, dont fait partie la recherche tabou, sont conçues pour éviter les cycles de recherche en mémorisant certaines solutions. Cela se fait à travers deux types de mémoire :

  • Mémoire à court terme : utilisée pour diversifier la recherche.
  • Mémoire à long terme : utilisée pour intensifier la recherche.

Algorithme général de la recherche tabou

L'algorithme de la recherche tabou se déroule en plusieurs étapes :


s0 : solution initiale
s* : meilleure solution jusqu'à présent
s : nouvelle solution du voisinage de s*
f(s) : fonction objectif à minimiser
f(s*) : valeur de la meilleure solution.

Le voisinage est défini comme l'ensemble des solutions accessibles à partir d'une solution donnée. Un mouvement permet de passer d'une solution valide à une autre, et la liste tabou enregistre les solutions déjà visitées pour éviter les répétitions.

Critères d'arrêt

La recherche peut être arrêtée à tout moment, contrairement à d'autres méthodes comme le recuit simulé. Les critères d'arrêt peuvent inclure :

  • Toutes les solutions voisines sont tabou.
  • Une solution optimale a été trouvée.
  • Un nombre maximal d'itérations a été dépassé.
  • Un nombre d'itérations sans amélioration de la meilleure configuration trouvée.

Domaine d'application de la recherche tabou

La recherche tabou est applicable dans divers domaines, notamment :

  • Problèmes de transport.
  • Planification et ordonnancement.
  • Optimisation de graphes.
  • Télécommunications.
  • Logique et intelligence artificielle.

Exemple d'application de la recherche tabou

Un exemple classique de l'application de la recherche tabou est le problème des n reines, où l'objectif est de placer n reines sur un échiquier de manière à ce qu'aucune reine ne puisse capturer une autre. Voici comment cela se déroule :

On définit les collisions comme suit :


X = {X(1), X(2), X(3), ..., 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 colonne).

Les itérations se déroulent en évaluant les mouvements possibles, en mettant à jour la liste tabou et en appliquant le critère d'aspiration pour choisir les mouvements qui améliorent la solution actuelle.

Itérations du processus

Voici un aperçu des itérations du processus :

  • Itération 0 : Collisions initiales détectées.
  • Itération 1 : Mouvements effectués pour réduire les collisions.
  • Itération 2 : Poursuite de l'optimisation avec mise à jour de la liste tabou.
  • Itération 3 : Analyse des nouvelles collisions et ajustement des mouvements.
  • Itération 4 : Réduction des collisions à un minimum.
  • Itération 5 : Optimisation continue jusqu'à atteindre une solution sans collisions.

Avantages et inconvénients de la recherche tabou

La recherche tabou présente plusieurs avantages et inconvénients :

Avantages

  • Économie de temps de résolution pour des problèmes de grande taille.
  • Résultats efficaces sur certains types de problèmes.
  • Algorithmes relativement simples à mettre en œuvre.

Inconvénients

  • Paramètres parfois peu intuitifs.
  • Exigences en ressources importantes si la liste des tabous est trop grande.
  • Aucune garantie de convergence vers une solution optimale.

Questions fréquentes

Qu'est-ce que la recherche tabou ?

La recherche tabou est une méthode heuristique de recherche locale utilisée pour résoudre des problèmes d'optimisation combinatoire, permettant d'éviter les optimums locaux.

Quels sont les avantages de la recherche tabou ?

Les avantages incluent des économies de temps de résolution, des résultats efficaces sur certains problèmes et une mise en œuvre relativement simple.

Quels sont les inconvénients de la recherche tabou ?

Les inconvénients comprennent des paramètres peu intuitifs, une demande en ressources importantes et l'absence de garantie de convergence.

Comment fonctionne l'algorithme de la recherche tabou ?

L'algorithme commence par une solution initiale et explore le voisinage pour trouver de meilleures solutions tout en évitant les répétitions grâce à une liste tabou.

Dans quels domaines la recherche tabou est-elle appliquée ?

Elle est utilisée dans des domaines tels que les problèmes de transport, la planification, l'optimisation de graphes, et l'intelligence artificielle.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions