Recherche Tabou Stochastique — Métaheuristique Randomisée avec Mémoire
- Introduite par
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- Année
- 1990s
- Type
- Stochastic metaheuristic optimizer
- Famille
- Simulation / optimization
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La recherche tabou stochastique (STS) est une extension de la recherche tabou classique qui introduit de l'aléatoire dans les phases d'exploration du voisinage et de sélection des mouvements.
En combinant la mémoire tabou — qui interdit les solutions récemment visitées — avec une acceptation probabiliste ou un échantillonnage aléatoire de candidats, la STS échappe plus efficacement aux optima locaux et explore des paysages de solutions complexes que la recherche tabou déterministe pourrait ne pas réussir à traverser.
L’intuition derrière la méthode
La recherche tabou classique navigue dans un espace de solutions en se déplaçant toujours vers le meilleur voisin autorisé, en utilisant une mémoire à court terme (la liste tabou) pour éviter les cycles. En pratique, cependant, le meilleur mouvement autorisé peut toujours piéger l'algorithme dans une région du paysage. La recherche tabou stochastique injecte un aléa contrôlé : le mouvement suivant est choisi de manière probabiliste parmi un ensemble de voisins candidats plutôt que de manière gloutonne, et des perturbations aléatoires sont occasionnellement introduites pour diversifier la recherche. Cela préserve la discipline guidée par la mémoire de la recherche tabou tout en ajoutant le pouvoir exploratoire qui manque à la descente déterministe pure.
Histoire
La recherche tabou a été formellement introduite par Fred Glover en 1986 et élaborée dans des articles marquants entre 1989 et 1990. Les extensions stochastiques sont apparues dans les années 1990, lorsque les chercheurs ont reconnu que l'évaluation déterministe du voisinage constituait un goulot d'étranglement dans les problèmes à grande échelle. L'échantillonnage aléatoire de candidats, l'acceptation probabiliste des mouvements et l'injection de bruit ont été incorporés pour améliorer la diversification, donnant naissance à ce que l'on appelle globalement la recherche tabou stochastique. La technique est largement appliquée en recherche opérationnelle, en conception d'ingénierie et en optimisation des hyperparamètres d'apprentissage automatique.
Quand l’utiliser
Utilisez la recherche tabou stochastique lors de la résolution de problèmes d'optimisation combinatoire ou continue en boîte noire avec des paysages complexes et multimodaux où la recherche locale déterministe est constamment piégée (par exemple, l'ordonnancement, le routage, la sélection de caractéristiques). Elle est particulièrement précieuse lorsque l'évaluation complète du voisinage est coûteuse en calcul, rendant l'échantillonnage aléatoire nécessaire. N'utilisez PAS la STS lorsque le problème est convexe ou unimodal — les méthodes basées sur le gradient ou exactes sont plus rapides et optimales. Évitez-la lorsque vous avez besoin d'une garantie d'optimalité globale, car la STS n'offre aucune garantie de convergence au-delà des meilleures solutions heuristiques trouvées. Évitez également lorsque la fonction objectif est peu coûteuse à évaluer complètement et qu'une recherche tabou déterministe avec une recherche exhaustive des voisins est réalisable.
Limites et points d’attention
- Aucune garantie théorique de trouver l'optimum global ; la qualité de la solution dépend fortement des réglages des paramètres.
- La durée tabou et la taille de la liste de candidats nécessitent un réglage spécifique au problème ; de mauvais choix conduisent à une convergence prématurée ou à une progression lente.
- Les exécutions stochastiques ne sont pas reproductibles sans une graine aléatoire fixe, ce qui complique l'évaluation comparative et l'audit.
- La surcharge de mémoire augmente avec la taille de la liste tabou ; des représentations tabou basées sur les attributs sont nécessaires pour les grands espaces de solutions.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Échappe plus efficacement aux optima locaux que la recherche tabou déterministe en combinant la mémoire avec l'exploration probabiliste.
- S'adapte aux grandes structures de voisinage en sous-échantillonnant les candidats, réduisant ainsi le coût de calcul par itération.
- La mémoire tabou empêche le cyclage, un mode de défaillance courant des méthodes stochastiques pures comme l'escalade aléatoire avec redémarrage.
- Cadre flexible : la probabilité de perturbation et la durée tabou peuvent être ajustées pour équilibrer l'intensification et la diversification.
- Applicable aux problèmes combinatoires (TSP, ordonnancement) et à l'optimisation continue avec des adaptations mineures.
Applications
- Optimisation du routage des véhicules et de la logistique sous demande incertaine
- Ordonnancement d'atelier (job-shop et open-shop) avec des temps de traitement stochastiques
- Sélection de caractéristiques dans les ensembles de données d'apprentissage automatique de grande dimension
- Conception de réseaux et optimisation de la topologie
- Optimisation de portefeuille avec des contraintes combinatoires de sélection d'actifs
- Réglage des hyperparamètres pour des modèles de simulation complexes
Comment ça marche
Comment ça marche
Générer une solution initiale x0 (aléatoirement ou heuristiquement). Initialiser la liste tabou T comme vide, définir la durée tabou tau, la limite d'itérations I_max, et les paramètres stochastiques (par exemple, la taille de la liste de candidats k, la probabilité de perturbation p_perturb).
À chaque itération, échantillonner aléatoirement un sous-ensemble N_s du voisinage complet N(x_current) plutôt que d'évaluer tous les voisins. Cela réduit le coût par itération et introduit de la stochasticité dans les régions de l'espace explorées.
Sélectionner la solution suivante x_next de N_s : soit (a) choisir le meilleur candidat non tabou avec une probabilité de 1-p_perturb, soit (b) avec une probabilité p_perturb choisir un candidat non tabou aléatoire pour diversifier. Les critères d'aspiration peuvent outrepasser le statut tabou si x_next améliore la meilleure solution connue.
Ajouter x_current (ou l'attribut du mouvement) à la liste tabou T. Supprimer l'entrée la plus ancienne si |T| > tau. Mettre à jour la meilleure solution courante x_best si f(x_next) < f(x_best).
Répéter l'échantillonnage du voisinage jusqu'à la mise à jour tabou jusqu'à ce que I_max itérations soient atteintes, qu'une valeur d'objectif cible soit atteinte, ou qu'aucune amélioration n'ait eu lieu pendant une fenêtre de patience. Retourner x_best comme solution finale.
Pièges courants
- Définir une durée tabou trop courte permet le cyclage malgré la liste tabou ; trop longue bloque inutilement des régions prometteuses.
- L'utilisation d'une liste de candidats trop petite (sous-échantillonnage agressif) peut faire en sorte que la recherche manque constamment de bons voisins.
- Négliger les critères d'aspiration amène l'algorithme à rejeter des mouvements globalement améliorants qui se trouvent être tabous.
- Ne rapporter qu'une seule exécution sans plusieurs redémarrages ou graines donne une image trompeuse de la qualité typique de la solution.
- Confondre la recherche tabou stochastique avec le recuit simulé : les deux sont stochastiques mais diffèrent fondamentalement — la STS utilise une mémoire explicite tandis que le recuit simulé utilise une acceptation probabiliste basée sur la température sans mémoire.
Questions fréquentes
En quoi la recherche tabou stochastique diffère-t-elle du recuit simulé ?
Les deux sont des métaheuristiques stochastiques, mais la STS utilise une mémoire tabou explicite pour interdire les mouvements récemment visités, empêchant ainsi le cyclage. Le recuit simulé n'a pas de mémoire — il accepte des solutions moins bonnes avec une probabilité qui diminue avec le temps (calendrier de température). La STS est généralement plus performante sur les problèmes combinatoires où la revisite des mouvements est un danger clair.
Combien d'itérations (I_max) dois-je exécuter ?
Il n'y a pas de règle universelle. Une pratique courante consiste à exécuter plusieurs essais indépendants (par exemple, 10 à 30 redémarrages) avec un budget proportionnel à la taille du problème, puis à rapporter les meilleurs résultats et les résultats moyens. Pour l'évaluation comparative, faites correspondre le budget total d'évaluation de fonction utilisé par les méthodes concurrentes.
La recherche tabou stochastique peut-elle gérer des variables continues ?
Oui, mais cela nécessite de définir un voisinage continu (par exemple, une perturbation gaussienne autour de la solution actuelle) et un attribut approprié pour la liste tabou (par exemple, une région ou une direction). La plupart de la littérature sur la STS cible les problèmes combinatoires ; pour les espaces continus, l'évolution différentielle ou le CMA-ES sont souvent des alternatives plus naturelles.
Quel est le rôle des critères d'aspiration ?
Les critères d'aspiration outrepassent le statut tabou d'un mouvement si son acceptation conduit à une solution meilleure que la meilleure trouvée jusqu'à présent. Sans aspiration, l'algorithme pourrait rejeter de manière permanente des mouvements globalement améliorants qui se trouvent être tabous, limitant sévèrement la qualité de la solution.
Dois-je fixer la graine aléatoire pour la reproductibilité ?
Oui, fixez la graine lorsque vous rapportez des résultats de recherche pour assurer la reproductibilité. En pratique, exécutez avec plusieurs graines et rapportez des statistiques (moyenne, meilleure, écart-type) pour donner une image fiable des performances de l'algorithme sur le paysage stochastique.
Méthodes associées
Sources
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Ouvrir la référence DOICopié.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
Ouvrir la référence DOICopié.