Recherche Tabou

Cet article présente une introduction accessible à la recherche tabou, une méthode d’optimisation combinatoire utilisée en informatique et en recherche opérationnelle. Il s’adresse aux étudiants et chercheurs débutants souhaitant comprendre les principes, le fonctionnement et les enjeux de cette métaheuristique, ainsi que ses liens avec d’autres techniques d’optimisation comme les algorithmes génétiques et les approches multi-objectifs.

La question

La recherche tabou vise à résoudre des problèmes d’optimisation complexes où il faut trouver la meilleure solution parmi un grand nombre de configurations possibles. Le défi principal est d’éviter que la recherche locale ne reste bloquée dans un optimum local, c’est-à-dire une solution qui est meilleure que ses voisines immédiates mais pas la meilleure globalement. La recherche tabou propose une méthode pour explorer efficacement l’espace des solutions, en évitant les cycles et en permettant de dépasser ces optima locaux. Ce problème est important car de nombreuses applications industrielles, logistiques ou informatiques nécessitent des solutions optimales ou quasi-optimales dans des espaces de recherche très vastes.

Concepts de base

Pour comprendre la recherche tabou, il faut d’abord saisir quelques notions fondamentales :

• Recherche locale : méthode d’optimisation qui améliore progressivement une solution en explorant ses solutions voisines, c’est-à-dire celles qui diffèrent légèrement de la solution actuelle.
• Optimum local : solution qui est meilleure que toutes ses voisines immédiates, mais pas nécessairement la meilleure solution globale.
• Liste tabou : mémoire à court terme qui enregistre les derniers mouvements ou solutions visités afin d’éviter de revenir immédiatement sur ces configurations, ce qui empêche les cycles.
• Critères d’aspiration : règles permettant de dépasser temporairement les interdictions imposées par la liste tabou si cela conduit à une amélioration significative, par exemple en obtenant la meilleure solution trouvée jusqu’à présent.
• Voisinage V(s) : ensemble des solutions voisines d’une solution s, candidates pour la prochaine étape de la recherche.

La recherche tabou se distingue d’autres méthodes locales comme la descente simple, qui s’arrête dès qu’elle atteint un optimum local, ou le recuit simulé, qui accepte aléatoirement des solutions moins bonnes pour échapper aux minima locaux. Contrairement au recuit simulé, la recherche tabou n’utilise pas de tirages aléatoires mais sélectionne la meilleure solution voisine non interdite.

Approche

La recherche tabou fonctionne selon un algorithme itératif structuré en trois étapes :

1. Initialisation : on choisit une solution initiale s dans l’espace des solutions S, et on initialise la liste tabou T, généralement vide. On conserve aussi la meilleure solution trouvée s*.
2. Choix et terminaison : à chaque itération, on examine le voisinage V(s) de la solution courante s. Parmi les solutions voisines, on choisit la meilleure s' qui n’appartient pas à la liste tabou, ou pour laquelle un critère d’aspiration est applicable, même si cette solution dégrade la fonction objectif f. Cette étape permet de ne pas rester bloqué dans un optimum local. On met à jour s avec s'. Le processus s’arrête si un nombre maximal d’itérations est atteint.
3. Mise à jour : on met à jour la liste tabou T en y ajoutant le mouvement ou la solution récente, et on ajuste les critères d’aspiration. Si la nouvelle solution s est meilleure que la meilleure solution connue s*, on met à jour s*.

La taille de la liste tabou est un paramètre crucial. Une liste trop grande peut rendre la recherche trop restrictive, tandis qu’une liste trop petite peut permettre des cycles. Une taille dynamique, qui diminue au cours de l’exécution, est souvent utilisée pour équilibrer diversification (exploration large) et intensification (exploitation locale).

La recherche tabou autorise parfois la violation des interdictions de la liste tabou si cela permet d’obtenir la meilleure solution enregistrée, ce qui améliore la qualité de la recherche.

Résultats

La recherche tabou présente plusieurs avantages :

• Elle utilise un historique des solutions visitées, ce qui la rend moins « aveugle » que les méthodes locales classiques.
• Elle ne s’arrête pas au premier optimum local rencontré, contrairement à la descente simple, grâce à la possibilité d’accepter des solutions moins bonnes temporairement.
• Elle explore un échantillon complet du voisinage à chaque itération, au lieu de choisir une solution voisine au hasard comme dans le recuit simulé.

En revanche, elle présente aussi des inconvénients :

• La détermination de la taille optimale de la liste tabou et des critères d’aspiration est délicate et dépend du problème.
• Elle peut être plus coûteuse en calcul que des méthodes plus simples.

Globalement, la recherche tabou est une méthode puissante pour les problèmes d’optimisation combinatoire, capable de trouver des solutions de bonne qualité dans des espaces complexes.

Limitations et questions ouvertes

Le travail souligne plusieurs limites de la recherche tabou :

• Le choix des paramètres, notamment la taille de la liste tabou et les critères d’aspiration, reste un défi et peut fortement influencer les performances.
• Le temps d’exécution peut devenir important, surtout pour des problèmes de grande taille ou des voisinages très étendus.
• La méthode ne garantit pas de trouver la solution optimale globale, mais plutôt une bonne approximation.

Ces limites ouvrent la voie à des recherches complémentaires, notamment sur l’adaptation dynamique des paramètres et l’hybridation avec d’autres heuristiques ou métaheuristiques.

Glossaire

• Algorithme génétique : méthode d’optimisation inspirée de la sélection naturelle, utilisant une population d’individus, des opérateurs de croisement et de mutation.
• Critères d’aspiration : règles permettant de dépasser temporairement les interdictions imposées par la liste tabou.
• Liste tabou : mémoire à court terme qui interdit temporairement certains mouvements ou solutions pour éviter les cycles.
• Optimum local : solution meilleure que ses voisines immédiates mais pas nécessairement la meilleure globalement.
• Recherche locale : méthode d’optimisation qui explore l’espace des solutions en améliorant progressivement une solution initiale.
• Voisinage V(s) : ensemble des solutions proches de la solution s, candidates pour la prochaine étape de la recherche.