La recherche tabou
La recherche tabou
Optimization and Computational Algorithms · notes
Voir tous les documents en programmation
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
Cette conférence porte sur la recherche tabou, une méthode métaheuristique utilisée en optimisation combinatoire. Elle s'inscrit dans le cadre d'un cours d'informatique ou d'optimisation, présentant à la fois les fondements théoriques, le fonctionnement général de l'algorithme, ses applications ainsi qu'un exemple concret d'utilisation.
Un problème d’optimisation combinatoire consiste à chercher le minimum d’une fonction f, souvent appelée fonction économique, sur un ensemble fini S. Les éléments de S qui respectent certaines contraintes sont appelés solutions réalisables. Parmi ces solutions, on cherche la solution optimale.
La recherche tabou est une méthode efficace et simple qui peut être appliquée à un grand nombre de problèmes d’optimisation combinatoire. Elle appartient à la famille des métaheuristiques, qui visent à améliorer les solutions en acceptant temporairement des solutions moins bonnes pour éviter de rester bloqué sur un optimum local.
Dans les années 1970, les techniques d’amélioration des solutions par recherche locale ont connu un essor important. En 1983, le recuit simulé, une nouvelle métaheuristique, a été proposée. La recherche tabou, bien que ses origines remontent à 1977, a été formalisée au milieu des années 1980 par Fred Glover.
Les métaheuristiques partagent l’idée fondamentale d’accepter provisoirement une mauvaise solution afin d’explorer un espace de solutions plus large, évitant ainsi les boucles infinies et les optima locaux.
Le terme « tabou » vient du Tonga polynésien et signifie « interdit » ou « sacré », désignant quelque chose qui ne peut être touché. En optimisation, la recherche tabou est une méthode métaheuristique destinée à guider d’autres méthodes pour trouver de meilleures solutions à partir d’une solution initiale obtenue par heuristique.
Cette méthode est applicable dans plusieurs domaines, notamment :
La recherche tabou repose sur l’utilisation de structures de mémoire flexibles, à court, moyen et long terme, permettant d’explorer à la fois le critère d’évaluation et l’historique de la recherche. Elle combine plusieurs mécanismes :
Avantages :
Inconvénients :
Le problème des n reines consiste à placer n reines sur un échiquier de taille n×n de manière à ce qu’aucune reine ne puisse en capturer une autre. Cela signifie qu’aucune reine ne doit partager la même ligne, colonne ou diagonale qu’une autre.
On représente la solution par un vecteur X = {X(1), X(2), ..., X(n)} où X(i) est l’indice de la colonne où est placée la reine sur la ligne i. Les contraintes sont :
Dans cet exemple, la liste tabou contient les mouvements interdits, chaque mouvement correspondant à la permutation des positions de deux reines en collision. Le critère d’aspiration permet d’entreprendre un mouvement même tabou s’il respecte les contraintes et améliore la solution. La fonction à minimiser est le nombre de collisions entre reines.
Au départ (itération 0), plusieurs collisions sont détectées, par exemple entre R1 et R2, R4 et R5, R6 et R7, et R2 et R6, ce qui donne une fonction f égale à 4.
Au fil des itérations, des mouvements sont effectués pour réduire le nombre de collisions :
La liste tabou évolue à chaque étape pour interdire certains mouvements récents, évitant ainsi les cycles et favorisant l’exploration de nouvelles solutions.
La recherche tabou peut être considérée comme une généralisation des méthodes d’amélioration locale traditionnelles. Elle ne garantit pas un succès définitif sur tous les problèmes, mais son efficacité dépend de la manière dont elle est adaptée au problème posé. L’ajustement adéquat de ses composants, tels que la restriction tabou et le critère d’aspiration, est essentiel pour obtenir de bons résultats.