Résumé Technique : Conception Automatisée de Solveurs CVRP à Grande Échelle via MCTS Flexible Assisté par LLM

Énoncé du Problème

Le Problème de Routage de Véhicules à Capacité Contrainte (CVRP) est une pierre angulaire de l'optimisation de la chaîne d'approvisionnement, mais la résolution d'instances de CVRP à grande échelle (LSCVRP) impliquant des centaines à des milliers de nœuds demeure un défi majeur. En raison du caractère NP-difficile du problème, l'espace de recherche s'étend de manière exponentielle avec la taille de l'instance, ce qui fait que même les solveurs les plus avancés peinent à performer sur des données à grande échelle.

Bien que la stratégie « diviser pour régner » — décomposant les problèmes globaux en sous-problèmes gérables — soit un paradigme efficace, son application pratique est entravée par deux obstacles majeurs :

1. Dépendance à l'Expertise : Concevoir une logique de décomposition efficace et calibrer les paramètres des sous-solveurs est laborieux et repose fortement sur une expertise de domaine.
2. Limites de la Conception d'Algorithmes Assistée par LLM (LLMaAD) Actuelle : Les approches existantes pilotées par les LLM reposent généralement sur un paradigme monolithique « une pensée unique vers le code ». Ces méthodes peinent à générer les architectures sophistiquées et multi-composantes requises pour le LSCVRP dans des fenêtres de contexte limitées. De plus, le coût computationnel prohibitif de l'évaluation des solveurs candidats sur des instances à grande échelle crée un goulot d'étranglement, restreignant l'exploration au sein de l'espace des hypothèses algorithmiques.

Méthodologie : LaF-MCTS

Pour répondre à ces défis, les auteurs proposent LaF-MCTS (Recherche Arborescente de Monte Carlo Flexible Assistée par LLM), un cadre conçu pour automatiser la conception de solveurs LSCVRP haute performance. La méthodologie opère en deux étapes : Développement (recherche de configurations optimales de solveurs) et Déploiement (application du meilleur solveur découvert).

1. Hiérarchie de Décision à Trois Niveaux

Au lieu de forcer un LLM à générer un solveur entier à partir d'une seule invite, LaF-MCTS emploie une approche hiérarchique inspirée de la Recherche Génétique Hybride Décomposée (HGS). Cette hiérarchie structure l'espace de recherche en trois niveaux :

• Niveau 1 (Conception du Cadre Global) : Le LLM synthétise l'architecture algorithmique globale, définissant le squelette métaheuristique, la granularité de décomposition (taille/quantité des sous-problèmes) et le flux d'exécution (par exemple, cycles évolutifs, mécanismes de réintégration).
• Niveau 2 (Conception de la Stratégie de Décomposition) : Conditionné par le cadre, le LLM génère du code pour partitionner les graphes à grande échelle en sous-problèmes. Pour surmonter le manque de connaissances spécialisées du domaine chez le LLM, ce niveau utilise une stratégie de prompting par quelques exemples avec une bibliothèque spécialisée de 11 codes de décomposition CVRP établis, garantissant que les stratégies générées satisfont des contraintes de domaine strictes (par exemple, homogénéité des sous-problèmes).
• Niveau 3 (Configuration du Sous-solveur) : Le niveau le plus bas se concentre sur l'adaptation locale. Le LLM agit comme un tuneur hyper-heuristique, générant des ensembles de paramètres pour les sous-solveurs (basés sur HGS) adaptés à la topologie et à l'échelle spécifiques de chaque partition.

2. Recherche Arborescente de Monte Carlo Flexible (MCTS)

Le cadre utilise un MCTS flexible topologiquement pour naviguer dans l'espace combinatoire des composants de solveurs. Le processus de recherche implique :

• Sélection : Utilisation de la borne de confiance supérieure appliquée aux arbres (UCT) pour équilibrer exploration et exploitation.
• Expansion : Le LLM génère $K$ composants de code candidats pour le niveau suivant.
• Évaluation : Une stratégie de déploiement assemble un solveur complet à partir du chemin sélectionné et l'évalue sur un ensemble fixe d'instances d'entraînement. La récompense est définie comme l'écart moyen par rapport à la Meilleure Solution Connue (BKS).
• Rétropropagation : Les récompenses sont propagées vers le haut de l'arbre pour mettre à jour les comptes de visites et les estimations de valeur.

3. Élagage Sémantique et Repousse des Branches

Une innovation critique dans LaF-MCTS est le mécanisme pour gérer la redondance du code et maintenir la diversité, abordant le problème où les LLM génèrent du code syntaxiquement différent mais sémantiquement équivalent (ou vice versa).

• Élagage Sémantique : Pour éviter les évaluations redondantes, le système emploie la Distance de Déplacement des Mots et des Phrases (WSMD). Cette métrique combine :
  • Alignement des Embeddings Sémantiques : Utilisation de la Distance de Déplacement des Mots (WMD) sur les embeddings de tokens.
  • Appariement de Topologie Structurelle : Utilisation de la distance de Gromov-Wasserstein sur les Matrices d'Auto-Attention (SAM) pour capturer les dépendances de contrôle et de flux de données.
    Si la distance composite entre deux branches de code est inférieure à un seuil, la variante inférieure est élaguée.
• Repousse des Branches : Pour empêcher l'espace de recherche de devenir trop étroit en raison de l'élagage, le système déclenche une repousse des branches. Lorsqu'un nœud est élagué, le LLM est sollicité avec une contrainte négative pour générer un nouveau candidat logiquement et structurellement distinct du nœud conservé, préservant ainsi la diversité de l'exploration.

Contributions Clés

1. Cadre Novel : Introduction de LaF-MCTS, qui automatise la conception de solveurs améliorés par décomposition pour le LSCVRP en imitant la construction par des experts humains via une hiérarchie à trois niveaux.
2. Espace de Recherche Hiérarchique : La proposition d'un modèle algorithmique plug-and-play (Cadre, Décomposition, Sous-solveur) permettant aux LLM de générer des composants spécialisés au sein d'une structure contrainte mais expressive, surmontant les limites de la génération de code monolithique.
3. Mécanisme de Recherche Efficace : Le développement de mécanismes d'Élagage Sémantique (via WSMD) et de Repousse des Branches. Ces techniques réduisent efficacement le goulot d'étranglement computationnel des évaluations redondantes tout en garantissant que la recherche ne stagne pas dans des optima locaux.
4. Performance de l'État de l'Art : La démonstration que LaF-MCTS peut composer autonomement des solveurs surpassant les métaheuristiques existantes, les méthodes d'Optimisation Combinatoire Neurale (NCO) et d'autres approches LLMaAD.

Résultats Expérimentaux

Les auteurs ont évalué LaF-MCTS sur le benchmark CVRPLib, couvrant 100 instances avec des nombres de nœuds allant de $N=100$ à $N=1000$.

• Performance : LaF-MCTS a obtenu les valeurs objectives moyennes les plus faibles et les écarts d'optimalité les plus bas sur toutes les échelles de problèmes par rapport aux bases de comparaison, incluant OR-Tools, HGS, HGS+BS, divers modèles NCO (par exemple, RF-POMO, CaDA) et d'autres méthodes LLMaAD (par exemple, FunSearch, ReEvo, EoH).
• Comparaison avec HGS+BS : Bien que HGS+BS (une métaheuristique basée sur la décomposition) ait surpassé le HGS standard, LaF-MCTS a généré un solveur basé sur la décomposition qui a dépassé HGS+BS sans intervention humaine, atteignant un écart d'optimalité moyen de 0,05 % sur l'échelle de nœuds $[100, 200)$ et 1,39 % sur l'échelle $[800, 1000]$.
• Études d'Ablation :
  • Hiérarchie : Les variantes intégrant pleinement les trois niveaux ont constamment surpassé les variantes partielles (par exemple, cadre uniquement ou décomposition uniquement), validant la nécessité de la hiérarchie complète.
  • Optimisation Conjoints : L'optimisation conjointe des stratégies de décomposition et des paramètres a donné de meilleurs résultats que la fixation de l'un ou l'autre, la mise au point des paramètres montrant une dépendance critique vis-à-vis de la stratégie de décomposition.
  • Élagage/Repousse : La suppression de l'élagage sémantique ou de la repousse des branches a conduit à une dégradation des performances, confirmant leur rôle dans l'équilibre entre efficacité et diversité.
  • Composantes WSMD : Les composantes sémantiques (embeddings) et structurelles (topologie) de la métrique d'élagage se sont révélées toutes deux nécessaires pour une détection efficace de la redondance.

Importance et Revendications

L'article revendique que LaF-MCTS représente une avancée significative dans la conception automatisée d'algorithmes pour des problèmes complexes d'optimisation combinatoire. En comblant le fossé entre la puissance de raisonnement des LLM et la vitesse d'exécution des algorithmes classiques, le cadre surmonte avec succès les barrières de complexité structurelle et de coût d'évaluation qui avaient précédemment limité le LLMaAD dans les problèmes de routage à grande échelle.

Les auteurs soulignent que leur approche va au-delà des heuristiques constructives simples pour découvrir des architectures complexes et multi-composantes. Les solveurs résultants non seulement égalent mais dépassent les performances des métaheuristiques de l'état de l'art conçues par l'homme (comme HGS+BS) et des approches neuronales. Le travail suggère que la recherche hiérarchique, améliorée par l'élagage, est une voie viable pour automatiser la conception de solveurs sophistiqués dans des domaines où l'optimisation manuelle devient de plus en plus difficile.

Note : Les auteurs reconnaissent les limitations actuelles, spécifiquement la dépendance à un flux de travail HGS défini par un expert qui limite la diversité architecturale, et identifient des travaux futurs visant à permettre une évolution autonome complète du flux de travail et la génération de portefeuilles de décomposition pour une meilleure généralisation.