Skip to content
Retour aux résultats

Recherche Tabou Multi-objectif (RTMO) — Métaheuristique pour les solutions Pareto-optimales

Introduite par
Hansen, M. P.; building on Glover (1989) Tabu Search
Année
1997
Type
Metaheuristic multi-objective optimization
Famille
Simulation / optimization

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 Multi-objectif (RTMO) est un algorithme métaheuristique qui étend le cadre classique de la Recherche Tabou pour optimiser simultanément deux ou plusieurs fonctions objectives conflictuelles.

Au lieu d'un optimum unique, elle cherche à approximer le front de Pareto — l'ensemble des solutions où aucun objectif ne peut être amélioré sans en dégrader un autre — la rendant ainsi adaptée aux problèmes d'optimisation combinatoire et continue complexes en ingénierie, logistique et recherche opérationnelle.

L’intuition derrière la méthode

Imaginez explorer un paysage accidenté avec de nombreuses collines et vallées, mais vous disposez de plusieurs cartes montrant différents terrains (une par objectif) qui se contredisent. La RTMO navigue dans cet espace en se déplaçant vers des solutions voisines, en conservant une liste de mémoire à court terme (la liste tabou) des endroits récemment visités pour éviter le cyclage, et en maintenant une archive des solutions non dominées trouvées jusqu'à présent. Périodiquement, une diversification stratégique pousse la recherche dans des régions inexplorées du front de Pareto, équilibrant l'exploitation des zones prometteuses avec l'exploration globale.

Histoire

La Recherche Tabou Multi-objectif étend la Recherche Tabou mono-objectif introduite par Fred Glover en 1989. La première formulation systématique de la RTMO — incluant l'archivage de Pareto et les critères d'aspiration multi-objectifs — a été présentée par M. P. Hansen lors de la conférence MCDM de 1997. Des travaux ultérieurs par Gandibleux, Teghem et d'autres ont formalisé des variantes pour les problèmes combinatoires, et la RTMO a depuis été appliquée à l'ordonnancement, la logistique et la conception d'ingénierie comme alternative compétitive aux algorithmes évolutionnistes multi-objectifs.

Quand l’utiliser

Utiliser la RTMO lorsque vous êtes confronté à un problème d'optimisation combinatoire ou mixte-entière avec deux objectifs conflictuels ou plus (par exemple, coût vs qualité, temps vs risque) et que les méthodes exactes sont calculatoirement intraitable. Elle excelle sur les problèmes d'ordonnancement, de tournées de véhicules, de conception de réseaux et de sélection de portefeuille où l'espace de recherche est trop vaste pour une énumération exhaustive. Préférer la RTMO à une recherche purement aléatoire lorsque la structure du voisinage est significative et que les opérateurs de mouvement peuvent être définis clairement. NE PAS utiliser la RTMO lorsque : le problème a un objectif unique (la Recherche Tabou simple suffit) ; lorsque le front de Pareto peut être énuméré exactement ; lorsque des informations de gradient sont disponibles et que le paysage est convexe (utiliser la programmation mathématique à la place) ; ou lorsque les décisions en temps réel nécessitent des sorties déterministes et reproductibles sans variation stochastique.

Limites et points d’attention

  • La performance est très sensible à la longueur de la liste tabou, à la définition du voisinage et à la stratégie de diversification — nécessitant un réglage minutieux des paramètres.
  • Aucune garantie de convergence vers le vrai front de Pareto ; la qualité de la solution dépend de la longueur de l'exécution et de la structure du problème.
  • Coûteuse en calcul par itération lorsque les voisinages sont grands ou les évaluations objectives coûteuses.
  • La maintenance et la mise à jour de l'archive de Pareto peuvent devenir coûteuses à mesure que le nombre d'objectifs et la taille de l'archive augmentent.
  • L'implémentation parallèle n'est pas triviale en raison de la nature séquentielle basée sur la mémoire du mécanisme tabou.

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

Points forts

  • Évite de revisiter des solutions récentes via la liste tabou, réduisant le risque de cyclage dans des paysages complexes.
  • Les critères d'aspiration permettent de outrepasser les restrictions taboues lorsqu'un mouvement conduit à une amélioration exceptionnelle, équilibrant mémoire et flexibilité.
  • Ne nécessite pas d'informations de gradient, la rendant applicable aux fonctions objectives non différentiables, discrètes ou boîte noire.
  • Produit une approximation de l'ensemble du front de Pareto en une seule exécution, soutenant la prise de décision multicritères.
  • La conception flexible du voisinage et des opérateurs de mouvement permet une personnalisation spécifique au problème.
  • Les mécanismes de diversification permettent de s'échapper des optima locaux et d'améliorer la couverture du front de Pareto.

Applications

  • Routage de véhicules et ordonnancement logistique multi-objectifs (minimiser le coût et le temps de livraison simultanément)
  • Ordonnancement de projet bi-objectif : minimiser la durée totale et le coût des ressources sous contraintes de précédence
  • Optimisation de portefeuille : équilibrer le rendement attendu par rapport au risque sur plusieurs classes d'actifs
  • Conception de réseau : minimiser le coût d'installation tout en maximisant la fiabilité ou le débit
  • Planification de processus de fabrication : optimiser conjointement le temps de cycle, la consommation d'énergie et les métriques de qualité
  • Gestion environnementale : équilibrer la production économique par rapport à la pollution ou à l'impact écologique

Comment ça marche

Comment ça marche

1

Initialiser la recherche avec une ou plusieurs solutions de départ (générées aléatoirement ou construites heuristiquement). Définir une liste tabou vide de longueur fixe L et initialiser l'archive de Pareto avec les solutions non dominées de la population de départ.

2

Générer le voisinage N(s) de la solution courante s en appliquant des opérateurs de mouvement (échanges, insertions, perturbations). Évaluer toutes les solutions voisines sur chaque fonction objectif pour identifier les candidats à la progression.

3

Appliquer le filtre tabou : exclure les voisins dont les mouvements définissant apparaissent sur la liste tabou, sauf s'ils satisfont un critère d'aspiration — typiquement, que le voisin domine tous les membres actuels de l'archive ou améliore la meilleure valeur connue sur au moins un objectif. Ceci empêche le cyclage et force l'exploration.

4

Sélectionner le meilleur voisin non tabou (ou le gagnant du critère d'aspiration) comme prochaine solution courante. Mettre à jour l'archive de Pareto en ajoutant la nouvelle solution si elle est non dominée ; supprimer tous les membres de l'archive qui sont dominés par la nouvelle entrée.

5

Appliquer des stratégies de diversification lorsque la recherche stagne : la mémoire de fréquence à long terme identifie les régions rarement visitées ; redémarrer à partir de solutions d'élite de l'archive ou de solutions perturbées aléatoirement pour étendre la couverture du front de Pareto.

6

Répéter les étapes de voisinage, de filtrage et d'archivage jusqu'à ce qu'un critère d'arrêt soit atteint — typiquement un nombre maximum d'itérations, d'évaluations de fonctions ou de temps CPU écoulé. Retourner l'archive de Pareto comme front Pareto-optimal approximé.

Pièges courants

  • Définir la liste tabou trop courte provoque du cyclage ; la définir trop longue restreint excessivement la recherche et manque de bonnes solutions — un calibrage empirique est essentiel.
  • Négliger la diversification conduit à une convergence prématurée sur une région du front de Pareto, produisant une mauvaise approximation.
  • Appliquer la RTMO avec plus de trois objectifs dégrade les performances car la gestion de l'archive et la maintenance de la diversité deviennent calculatoirement lourdes ; envisager des méthodes basées sur la décomposition pour les problèmes à nombreux objectifs.
  • Utiliser des opérateurs de mouvement génériques sans conception spécifique au problème limite sévèrement la qualité de la solution par rapport aux implémentations sur mesure.
  • Rapporter uniquement l'archive finale sans examiner l'historique de convergence peut masquer une stagnation prématurée.

Questions fréquentes

Comment la RTMO gère-t-elle la liste tabou lorsqu'il y a plusieurs objectifs ?

La liste tabou stocke les mouvements (pas les solutions), elle fonctionne donc de la même manière qu'en Recherche Tabou mono-objectif. La différence clé est que la sélection parmi les voisins non tabous utilise la dominance multi-objectif ou une fonction de scalarisation, et le critère d'aspiration est redéfini pour autoriser un mouvement tabou si la solution résultante n'est dominée par aucun des membres actuels de l'archive.

Qu'est-ce que l'archive de Pareto et quelle devrait être sa taille ?

L'archive de Pareto stocke toutes les solutions non dominées trouvées pendant la recherche. Sa taille maximale est généralement bornée (par exemple, 100 à 500 solutions) pour maintenir la mémoire et le coût de mise à jour gérables. Lorsque l'archive est pleine, un élagage par distance de foule (crowding-distance) ou basé sur grille supprime les solutions des régions surpeuplées pour maintenir la diversité.

Comment la RTMO se compare-t-elle à NSGA-II pour les problèmes multi-objectifs ?

NSGA-II utilise une approche évolutionniste basée sur une population avec croisement et mutation, ce qui le rend meilleur pour l'exploration globale en début de recherche. La RTMO repose sur des mouvements de voisinage et la mémoire, ce qui donne souvent une qualité de recherche locale plus fine. En pratique, la RTMO a tendance à surpasser sur les problèmes combinatoires avec une forte structure de voisinage, tandis que NSGA-II est plus largement utilisé pour les problèmes continus.

Combien d'itérations sont typiquement nécessaires ?

Il n'y a pas de règle universelle. La pratique courante consiste à budgétiser les évaluations de fonctions plutôt que les itérations — typiquement 10 000 à 100 000 évaluations selon la taille du problème — et à effectuer plusieurs démarrages indépendants pour évaluer la qualité de la solution et la stabilité du front de Pareto.

La RTMO peut-elle gérer plus de deux objectifs ?

Oui, mais l'efficacité se dégrade à mesure que le nombre d'objectifs dépasse trois (la 'malédiction de la dimensionnalité' dans l'espace des objectifs). Pour quatre objectifs ou plus, la taille de l'archive explose et la maintenance de la diversité devient difficile ; les approches basées sur la décomposition ou les indicateurs sont souvent préférées.

Méthodes associées

Sources

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    Ouvrir la référence de la publication
    Copié.
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Ouvrir la référence DOI
    Copié.