Skip to content
Retour aux résultats

Recherche Tabou — Métaheuristique de Recherche Locale

Introduite par
Fred Glover
Année
1989
Type
Local-search metaheuristic

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Recherche Tabou est une métaheuristique de recherche locale introduite par Fred Glover en 1989 qui utilise une liste tabou — une mémoire à court terme des solutions récemment visitées — pour prévenir le cyclage et échapper aux optima locaux.

En interdisant explicitement les mouvements qui inversent des décisions récentes, l'algorithme explore plus largement l'espace de recherche et, grâce à des structures de mémoire à long terme telles que les critères d'aspiration, vise à approcher l'optimum global même dans des problèmes combinatoires vastes et complexes.

L’intuition derrière la méthode

Imaginez naviguer dans un paysage montagneux dans l'obscurité, en essayant de trouver le plus haut sommet. Un simple algorithme de recherche locale par ascension monte toujours et se bloque sur la colline la plus proche qu'il atteint. La Recherche Tabou transporte un bloc-notes des endroits récemment visités et refuse d'y retourner, même si revenir en arrière semblerait tentant. Cette amnésie forcée concernant les mouvements récents pousse la recherche hors des impasses et vers un territoire inexploré, lui permettant de découvrir finalement un terrain beaucoup plus élevé qu'une simple recherche locale ne le pourrait jamais.

Histoire

La Recherche Tabou a été introduite par Fred Glover dans un article marquant de 1989 dans l'ORSA Journal on Computing, où elle était présentée comme une stratégie pour guider la recherche locale en exploitant la mémoire des mouvements passés. Les idées fondamentales ont été consolidées et étendues dans la monographie de Springer de Glover et Laguna en 1997, qui a établi la liste tabou canonique à court terme, les critères d'aspiration, et les stratégies de diversification et d'intensification à long terme qui restent centrales à la méthode aujourd'hui. Depuis son introduction, la Recherche Tabou a été appliquée intensivement en recherche opérationnelle, en ordonnancement, en logistique et en conception combinatoire, et elle continue d'être une métaheuristique de référence aux côtés de la recuisson simulée et des algorithmes génétiques.

Quand l’utiliser

La Recherche Tabou est bien adaptée aux problèmes d'optimisation combinatoire et discrète où l'espace de solutions est trop vaste pour les méthodes exactes et où la structure du problème permet de définir un voisinage significatif. Les applications typiques incluent les problèmes d'ordonnancement, de tournées, d'affectation et de séquençage. Elle est particulièrement efficace lorsque le paysage de recherche présente de nombreux optima locaux qui piègent les méthodes plus simples. Elle ne nécessite pas que la fonction objectif soit différentiable ou continue. La définition du voisinage et la durée de vie taboue doivent être adaptées avec soin au problème spécifique ; un voisinage mal choisi ou une durée de vie trop courte ou trop longue peut dégrader significativement les performances. Au moins plusieurs centaines — et idéalement plus d'un millier — d'itérations sont nécessaires pour que la recherche explore adéquatement l'espace.

Limites et points d’attention

  • Les performances sont sensibles à la définition du voisinage et à la durée de vie taboue ; de mauvais choix peuvent piéger la recherche ou la faire cycler malgré le mécanisme tabou.
  • Nécessite un budget d'itération minimum — typiquement plus de 1 000 itérations — pour explorer suffisamment le voisinage ; avec trop peu d'itérations, les résultats ne sont pas meilleurs qu'une simple recherche locale.
  • La liste tabou stocke des attributs de mouvement plutôt que des solutions complètes, donc le critère d'aspiration est nécessaire pour éviter de bloquer involontairement des mouvements véritablement bons.
  • Contrairement aux solveurs exacts, la Recherche Tabou n'offre aucune garantie d'optimalité et la qualité du résultat peut varier d'une exécution à l'autre si la solution initiale ou le voisinage est stochastique.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Échappe aux optima locaux grâce au mécanisme tabou sans nécessiter d'informations de gradient.
  • Applicable aux problèmes combinatoires, mixtes, et même continus — elle ne suppose ni normalité ni aucune propriété distributionnelle.
  • Intègre une mémoire à plusieurs échelles temporelles (liste tabou à court terme, diversification/intensification à long terme) permettant une exploration principielle de l'espace de recherche.
  • Trouve souvent des solutions de haute qualité avec des budgets de calcul relativement modestes par rapport aux méthodes exactes sur de grandes instances.

Applications

  • Ordonnancement de type Job-shop et Flow-shop — optimisation de la séquence des opérations pour minimiser le temps de production ou la ponction.
  • Routage de véhicules — recherche d'itinéraires de livraison efficaces soumis à des contraintes de capacité et de fenêtres temporelles.
  • Affectation et localisation d'installations — affectation de tâches à des ressources ou localisation d'installations pour minimiser les coûts.
  • Coloration de graphes, conception de réseaux et télécommunications — résolution de problèmes d'optimisation structurelle discrets.
  • Sélection de caractéristiques et recherche d'hyperparamètres — exploration d'espaces de configuration discrets dans les pipelines d'apprentissage automatique.

Comment ça marche

Comment ça marche

1

La recherche commence à partir d'une solution candidate initiale, qui peut être construite aléatoirement ou avec une heuristique gloutonne. La liste tabou est configurée comme une file d'attente vide de longueur fixe, et la meilleure solution trouvée jusqu'à présent est enregistrée. La structure de voisinage — la règle qui définit quelles solutions sont à un pas de la solution actuelle — doit être définie de manière significative pour le problème spécifique.

2

À partir de la solution actuelle, tous les mouvements dans le voisinage défini sont générés et évalués par rapport à la fonction objectif. Chaque mouvement correspond à une petite perturbation, telle que l'échange de deux éléments dans une séquence ou le retournement d'une variable binaire. Le voisinage doit être suffisamment riche pour permettre une exploration significative mais suffisamment petit pour être traitable à chaque itération.

3

Chaque mouvement candidat est testé par rapport à la liste tabou. Si le mouvement — ou l'attribut qui le caractérise — apparaît sur la liste, il est classé comme tabou et est interdit, à moins qu'il ne satisfasse un critère d'aspiration : typiquement, si la solution résultante serait meilleure que la meilleure solution trouvée jusqu'à présent, le statut tabou est outrepassé et le mouvement est autorisé. Ce mécanisme d'aspiration donne de la flexibilité à l'algorithme sans abandonner sa discipline anti-cyclage.

4

Parmi tous les mouvements non tabous (et tous les mouvements tabous qui satisfont le critère d'aspiration), le mouvement le plus performant est sélectionné et exécuté, même s'il dégrade la valeur objectif. Cette volonté d'accepter la détérioration est ce qui permet à l'algorithme d'échapper aux optima locaux, ce qui est le trait distinctif de la Recherche Tabou par rapport à la simple montée de colline.

5

Après l'exécution du mouvement, la liste tabou est mise à jour en ajoutant l'inverse du mouvement qui vient d'être effectué (ou son attribut caractéristique), et la plus ancienne entrée est supprimée si la liste est pleine, maintenant sa longueur fixe — la durée de vie taboue. Si la nouvelle solution est meilleure que la meilleure solution enregistrée, la meilleure solution est mise à jour. Des structures de mémoire à long terme optionnelles peuvent suivre la fréquence ou la récence des solutions pour guider la diversification vers des régions moins visitées ou l'intensification autour de régions prometteuses.

6

L'algorithme continue d'itérer jusqu'à ce qu'un critère d'arrêt soit atteint : un nombre maximum d'itérations, une valeur objectif cible, ou un nombre fixe d'itérations sans amélioration. La meilleure solution trouvée tout au long de la recherche est retournée comme résultat. Choisir un budget d'itération adéquat est critique — trop peu d'itérations empêchent une exploration suffisante du voisinage.

Pièges courants

  • Définir la durée de vie taboue trop courte permet au cyclage de réapparaître, rendant le mécanisme tabou inutile ; la durée de vie doit être ajustée à la taille du problème.
  • Définir une durée de vie trop longue restreint excessivement la recherche et empêche l'algorithme de revisiter des régions qui pourraient contenir des améliorations.
  • Exécuter moins d'environ 1 000 itérations signifie que la recherche n'a pas exploré suffisamment le voisinage — si le calcul est limité, revenir à la recuisson simulée qui peut produire des résultats utiles plus rapidement avec moins d'itérations.
  • Utiliser un voisinage trop étroit (par exemple, seulement des échanges simples sur une structure complexe) conduit à une recherche superficielle ; assurez-vous que le voisinage est suffisamment riche pour connecter toutes les régions prometteuses de l'espace de solutions.
  • Ignorer le critère d'aspiration peut bloquer définitivement les mouvements vers l'optimum global si ce mouvement est par hasard tabou ; implémentez toujours au moins le remplacement standard de la meilleure solution.

Questions fréquentes

En quoi la Recherche Tabou diffère-t-elle de la recuisson simulée ?

Les deux méthodes acceptent des mouvements dégradants pour échapper aux optima locaux, mais elles diffèrent par leur mécanisme. La recuisson simulée accepte les mouvements moins bons de manière probabiliste, guidée par un paramètre de température de refroidissement. La Recherche Tabou accepte le meilleur mouvement non tabou disponible de manière déterministe, guidée par une mémoire explicite des mouvements récents. La Recherche Tabou est généralement plus efficace sur les problèmes combinatoires structurés ; la recuisson simulée peut être plus facile à régler sur des problèmes avec des paysages continus ou quasi continus et est préférable lorsque le budget d'itération est faible (inférieur à environ 1 000 itérations).

Quelle doit être la longueur de la liste tabou ?

La durée de vie taboue — le nombre d'itérations pendant lesquelles un mouvement reste interdit — dépend du problème. Un point de départ couramment cité est une durée de vie proportionnelle à la racine carrée de la taille du problème, mais cela doit être ajusté empiriquement. Une durée de vie trop courte permet le cyclage ; une durée de vie trop longue restreint excessivement la recherche. Des stratégies de durée de vie adaptatives ou aléatoires peuvent réduire la sensibilité à ce choix.

La Recherche Tabou garantit-elle de trouver l'optimum global ?

Non. La Recherche Tabou est une métaheuristique et n'offre aucune garantie d'optimalité. Elle vise à trouver des solutions de haute qualité efficacement, mais le résultat dépend de la structure du voisinage, de la durée de vie, du nombre d'itérations et de la solution initiale. Pour une garantie d'optimalité, une méthode exacte telle que la programmation entière est requise, bien que les méthodes exactes puissent être infaisables en termes de calcul pour de grandes instances.

Qu'est-ce qu'un critère d'aspiration et pourquoi est-il nécessaire ?

Un critère d'aspiration est une règle qui outrepasse le statut tabou d'un mouvement dans des conditions spéciales. Le critère le plus courant est : si l'exécution d'un mouvement tabou produisait une solution meilleure que la meilleure solution trouvée jusqu'à présent, la restriction taboue est levée et le mouvement est autorisé. Sans cet outrepas, le mécanisme tabou pourrait bloquer définitivement le chemin vers l'optimum global si ce chemin passe par un mouvement récemment visité.

Méthodes associées

Sources

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Ouvrir la référence de la publication
    Copié.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN : 9780792349907
    Copié.