La recherche tabou

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.

Introduction à l’optimisation combinatoire et à la recherche tabou

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.

Historique scientifique

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.

Définition et domaine d’application de la recherche tabou

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 :

• Les problèmes de transport
• La planification et l’ordonnancement
• L’optimisation de graphes
• Les télécommunications
• La logique et l’intelligence artificielle

Principe de la recherche tabou

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 :

• Une restriction tabou qui interdit certains mouvements pour éviter de revenir sur des solutions déjà explorées.
• Un critère d’aspiration qui permet de lever ces restrictions si un mouvement conduit à une solution meilleure.
• Des stratégies d’intensification et de diversification :
• L’intensification utilise la mémoire à moyen terme pour renforcer la recherche autour des meilleures solutions récentes.
• La diversification utilise la mémoire à long terme pour explorer de nouvelles régions de l’espace des solutions.

Algorithme général de la recherche tabou

1. Initialisation de la solution et des structures de mémoire.
2. Création d’une liste des mouvements candidats.
3. Choix du meilleur candidat selon les restrictions tabou et le critère d’aspiration. Cette étape permet d’obtenir une nouvelle solution, qui est enregistrée uniquement si elle est meilleure que la précédente.
4. Application du critère d’arrêt :
• Si la recherche continue, on met à jour les candidats admissibles en fonction des restrictions tabou et du critère d’aspiration, puis on retourne à l’étape 2.
• Si la recherche s’arrête, on applique les stratégies d’intensification et de diversification.

Avantages et inconvénients de la recherche tabou

Avantages :

• Réduction du temps de résolution pour des problèmes de grande taille.
• Très bons résultats sur certains types de problèmes.
• Algorithmes relativement faciles à mettre en œuvre.

Inconvénients :

• Paramètres souvent peu intuitifs à régler.
• Demande en ressources importante si la liste des tabous est trop longue.
• Absence de preuve formelle de convergence.

Étude d’un exemple : le problème des n reines

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 :

• X(i) ≠ X(j) pour i ≠ j, afin d’éviter que deux reines soient sur la même colonne.
• Les reines doivent être sur des diagonales différentes.

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.

Déroulement des itérations

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 :

• Itération 1 : collisions réduites à 2, avec la liste tabou contenant le mouvement (R1,R7).
• Itération 2 : collisions réduites à 1, liste tabou mise à jour.
• Itération 3 : collisions toujours à 1, mais la liste tabou s’allonge.
• Itération 4 : collisions remontent à 2, mais la recherche continue.
• Itération 5 : collisions à nouveau à 1.
• Itération 6 : aucune collision, f = 0, solution optimale trouvée.

La liste tabou évolue à chaque étape pour interdire certains mouvements récents, évitant ainsi les cycles et favorisant l’exploration de nouvelles solutions.

Conclusion

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.

Points clés

• La recherche tabou est une métaheuristique qui améliore les solutions en acceptant temporairement des mouvements interdits pour éviter les optima locaux.
• Elle utilise des mémoires à court, moyen et long terme pour guider l’exploration de l’espace des solutions.
• Le critère d’aspiration permet de dépasser les restrictions tabou si cela conduit à une meilleure solution.
• Les stratégies d’intensification et de diversification permettent respectivement d’explorer en profondeur les zones prometteuses et de découvrir de nouvelles régions.
• La méthode est applicable à de nombreux domaines, notamment le transport, la planification, les graphes, les télécommunications et l’intelligence artificielle.
• Un exemple classique est le problème des n reines, où la recherche tabou permet de trouver une disposition sans conflit.
• Les paramètres de la recherche tabou sont souvent difficiles à régler et la méthode peut demander des ressources importantes.
• Il n’existe pas de preuve formelle de convergence, mais la méthode donne de bons résultats pratiques.