La recherche Tabou

La recherche tabou est une méthode d’optimisation combinatoire utilisée pour résoudre des problèmes complexes où il s’agit de trouver la meilleure solution parmi un ensemble fini de possibilités. Cette technique intéressera particulièrement les étudiants et chercheurs en informatique, mathématiques appliquées, optimisation, intelligence artificielle, ainsi que les professionnels confrontés à des problèmes de planification, de transport ou d’ordonnancement.

La question

Le travail s’intéresse à la résolution efficace de problèmes d’optimisation combinatoire, c’est-à-dire la recherche du minimum d’une fonction objectif sur un ensemble fini de solutions réalisables. Ces problèmes sont souvent difficiles car ils comportent de nombreuses contraintes et un grand espace de recherche, ce qui rend complexe la découverte de la solution optimale. La recherche tabou vise à dépasser les limites des méthodes classiques qui peuvent rester bloquées dans des optima locaux, en proposant une approche heuristique capable d’explorer plus largement l’espace des solutions.

Concepts de base

Avant de comprendre la recherche tabou, il est essentiel de saisir quelques notions fondamentales :

• Problème d’optimisation combinatoire : Il s’agit de minimiser (ou maximiser) une fonction f sur un ensemble fini S de solutions, chaque solution respectant certaines contraintes. La solution optimale est celle qui minimise la fonction objectif.
• Métaheuristique : C’est une méthode générale d’optimisation qui guide une recherche locale en acceptant temporairement des solutions moins bonnes pour éviter de rester bloqué dans un optimum local et pour explorer un espace plus vaste.
• Recherche locale : Technique qui améliore progressivement une solution en explorant ses voisins, c’est-à-dire des solutions proches obtenues par de petits changements.
• Recherche tabou : Méthode heuristique de recherche locale enrichie d’une mémoire qui empêche de revisiter certaines solutions ou mouvements récemment explorés, afin d’éviter les cycles et d’encourager la diversification.
• Mémoire à court terme : Liste tabou qui enregistre les mouvements interdits temporairement pour éviter de revenir en arrière.
• Mémoire à long terme : Stratégies d’intensification et de diversification qui permettent respectivement de focaliser la recherche sur des régions prometteuses ou d’explorer de nouvelles zones de l’espace de solutions.
• Critère d’aspiration : Mécanisme qui permet de dépasser une interdiction tabou si la solution obtenue est meilleure que la meilleure connue jusqu’alors.

Approche

La recherche tabou commence par une solution initiale s0. Elle explore ensuite l’ensemble des solutions voisines de la meilleure solution actuelle s*, en évaluant leur qualité via la fonction objectif f. Pour éviter de rester bloqué sur un optimum local, elle autorise des mouvements qui peuvent temporairement dégrader la solution. Cependant, pour ne pas revenir constamment sur les mêmes solutions, une liste tabou mémorise les mouvements interdits, ce qui empêche les cycles.

Le processus se déroule ainsi :

• Choisir une solution initiale s0.
• Explorer le voisinage de la solution courante s* pour générer de nouvelles solutions.
• Évaluer ces solutions avec la fonction objectif f.
• Choisir la meilleure solution voisine non interdite par la liste tabou, ou qui satisfait le critère d’aspiration.
• Mettre à jour la liste tabou avec le mouvement effectué.
• Répéter jusqu’à ce qu’un critère d’arrêt soit atteint (nombre d’itérations, absence d’amélioration, solution optimale trouvée, etc.).

Deux stratégies complémentaires sont utilisées pour améliorer la recherche :

• Intensification : Concentrer la recherche sur les meilleures solutions rencontrées pour approfondir leur exploration.
• Diversification : Encourager l’exploration de régions peu visitées de l’espace des solutions en favorisant des mouvements nouveaux.

Résultats

Le travail illustre la recherche tabou à travers l’exemple classique du problème des n reines, qui consiste à placer n reines sur un échiquier n×n de manière à ce qu’aucune ne puisse en capturer une autre. La fonction objectif à minimiser est le nombre de collisions entre reines. La liste tabou contient les mouvements interdits, c’est-à-dire les permutations de positions des reines en collision déjà effectuées récemment.

Au fil des itérations, la recherche tabou réduit progressivement le nombre de collisions :

• Itération 0 : 4 collisions.
• Itération 1 : 2 collisions.
• Itération 2 : 1 collision.
• Itération 3 : 1 collision.
• Itération 4 : 2 collisions (l’algorithme explore d’autres configurations).
• Itération 5 : 1 collision.
• Itération 6 : 0 collision, solution optimale trouvée.

Cette progression montre comment la recherche tabou, grâce à sa mémoire et à ses critères d’aspiration, parvient à échapper aux minima locaux et à converger vers une solution satisfaisante.

Limites et questions ouvertes

La recherche tabou présente plusieurs limites :

• Les paramètres de la méthode (taille de la liste tabou, critères d’aspiration, stratégies d’intensification et diversification) sont peu intuitifs et nécessitent un ajustement adapté au problème.
• La taille de la liste tabou peut engendrer une forte demande en ressources, ce qui peut ralentir la recherche.
• Il n’existe aucune preuve formelle de convergence vers la solution optimale, ce qui signifie que le succès n’est jamais garanti.
• La méthode doit être adaptée spécifiquement à chaque problème pour être efficace, ce qui demande une bonne compréhension des composants et contraintes du problème.

Glossaire

• Algorithme : Ensemble d’instructions permettant de résoudre un problème.
• Critère d’aspiration : Règle permettant de dépasser une interdiction tabou si la solution est meilleure que la meilleure connue.
• Fonction objectif : Fonction à minimiser ou maximiser dans un problème d’optimisation.
• Intensification : Stratégie visant à approfondir la recherche autour des meilleures solutions rencontrées.
• Liste tabou : Mémoire à court terme qui interdit temporairement certains mouvements pour éviter les cycles.
• Métaheuristique : Méthode générale d’optimisation combinatoire guidant la recherche locale.
• Mouvement : Passage d’une solution à une solution voisine dans l’espace de recherche.
• Optimisation combinatoire : Recherche de la meilleure solution dans un ensemble fini soumis à des contraintes.
• Recherche locale : Technique d’amélioration progressive d’une solution en explorant ses voisins.
• Diversification : Stratégie visant à explorer de nouvelles régions de l’espace de solutions pour éviter la stagnation.
• Voisinage : Ensemble des solutions accessibles à partir d’une solution donnée par un mouvement simple.