La recherche Tabou
La recherche Tabou
Optimization Techniques · textbook
Fiche de révisionExplication
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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.
Avant de comprendre la recherche tabou, il est essentiel de saisir quelques notions fondamentales :
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 :
Deux stratégies complémentaires sont utilisées pour améliorer la recherche :
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 :
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.
La recherche tabou présente plusieurs limites :