La recherche tabou
La recherche tabou
Programmation, Mathématiques, Optimisation · notes
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
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 qu'un exemple pratique pour illustrer son fonctionnement. Vous découvrirez également les avantages et inconvénients de cette méthode.
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 sous-optimale pour éviter de rester bloqué dans un optimum local. Le terme "tabou" provient du mot polynésien "Tonga", qui signifie quelque chose de sacré ou d'interdit.
Cette méthode utilise une mémoire à court terme, appelée diversification, et une mémoire à long terme, appelée intensification. La mémoire à court terme permet d'éviter de répéter les solutions déjà explorées, tandis que la mémoire à long terme aide à se concentrer sur les meilleures solutions rencontrées.
L'algorithme de la recherche tabou peut être décrit par les étapes suivantes :
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 l'ensemble des solutions accessibles à partir d'une solution donnée. Un mouvement consiste à passer d'une solution valide à une autre. La liste tabou est une mémoire à court terme qui enregistre les solutions visitées pour éviter de répéter la recherche.
La recherche peut être arrêtée à tout moment, contrairement à d'autres méthodes comme le recuit simulé. Les critères d'arrêt possibles incluent :
La recherche tabou peut être appliquée à divers domaines, tels que :
Un exemple classique de l'application de la recherche tabou est le problème des n reines, où l'on cherche à placer n reines sur un échiquier n x n de manière à ce qu'aucune reine ne puisse en capturer une autre.
La formulation de ce problème peut être décrite par :
X = {X(1), X(2), X(3), ..., X(n)} ; X(i) est l'index de la colonne avec :
X(i) ≠ X(j) (pour éviter que deux reines soient sur la même ligne ou colonne).
Les collisions doivent également être évitées, ce qui signifie que les reines doivent être placées sur des diagonales différentes. La liste tabou contiendra les mouvements interdits, et le critère d'aspiration permettra d'entreprendre des mouvements respectant les contraintes de collision.
Voici un aperçu des itérations dans la recherche tabou pour le problème des n reines :
La recherche tabou présente plusieurs avantages et inconvénients :
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 de rester bloqué sur un optimum local.
La recherche tabou est utilisée dans des domaines tels que les problèmes de transport, la planification, l'optimisation de graphes, et l'intelligence artificielle.
L'algorithme commence par une solution initiale et explore les solutions voisines, en utilisant une liste tabou pour éviter les répétitions et en appliquant des critères d'arrêt.
Les avantages incluent des économies de temps pour des problèmes complexes, de bons résultats sur certains types de problèmes, et une mise en œuvre relativement simple.
Les inconvénients incluent des paramètres peu intuitifs, une demande en ressources si la liste des tabous est trop grande, et l'absence de garantie de convergence.