Résumé Technique : PathWise

Énoncé du Problème

La Conception Heuristique Automatisée (AHD) vise à générer automatiquement des algorithmes heuristiques pour les Problèmes d'Optimisation Combinatoire (COP), réduisant ainsi la dépendance aux conceptions manuelles élaborées par des experts. Bien que les Grands Modèles de Langage (LLM) aient récemment permis l'AHD en s'intégrant aux processus de recherche évolutionnaire, les cadres existants souffrent de limitations significatives. Les méthodes basées sur les populations reposent souvent sur des règles évolutionnaires fixes et des modèles d'invite statiques, conduisant à une génération heuristique myope, à des évaluations redondantes et à une convergence prématurée. Les méthodes arborescentes, telles que celles utilisant la Recherche Arborescente Monte Carlo (MCTS), imposent des structures hiérarchiques pilotées par des statistiques de performance plutôt que par une compréhension sémantique du paysage de recherche. Crucialement, les approches actuelles manquent d'une représentation étatique et sémantique de la manière dont les heuristiques sont dérivées, de la façon dont les modifications se propagent à travers les générations, ou de la raison pour laquelle certaines modifications réussissent ou échouent. Cela se traduit par une utilisation inefficace des appels aux LLM et par un échec à transmettre efficacement les décisions passées.

Méthodologie

Les auteurs proposent PathWise (Planification via un Modèle du Monde pour la Conception Heuristique Automatisée par des LLMs Auto-Évolutifs), un cadre novateur de raisonnement multi-agents qui formule la génération heuristique comme un processus de décision séquentielle sur un graphe d'inférence. Ce graphe sert de mémoire étatique et compacte de la trajectoire de recherche.

Composants Principaux

1. Graphe d'Inférence ($G = (V, E)$) :

   • Contrairement aux arbres évolutionnaires ou aux populations standards, le graphe d'inférence encode l'historique de dérivation.
   • Nœuds ($v$) : Représentent des tuples contenant le code heuristique ($h$), une justification de dérivation en langage naturel ($\kappa$), une description algorithmique ($d$), des métriques de performance ($P(h; D)$) et des métadonnées parentales ($PM$).
   • Arêtes ($E$) : Relient des ensembles de parents aux nœuds enfants, encodant la justification spécifique utilisée pour dériver l'enfant à partir de ses parents.
   • Cette structure permet au système de conditionner les décisions futures sur l'historique de dérivation plutôt que de traiter les étapes comme des événements d'échantillonnage isolés.

2. Système Multi-Agents :
   Le cadre fonctionne via un cycle coordonné de planification, d'exécution et de réflexion sur deux échelles de temps (mises à jour de population externes et étapes d'inférence internes) :

   • Agent Politique ($\pi_p$) : Agit comme un planificateur de haut niveau. Il observe l'état actuel (le front du graphe d'inférence) et propose des actions définies par un tuple de nœuds parents sélectionnés ($S$) et une justification de dérivation en langage naturel ($\kappa$). Cela permet à la politique d'inventer dynamiquement de nouveaux types d'opérateurs plutôt que de dépendre de modèles fixes.
   • Agent Modèle du Monde ($\pi_{wm}$) : Agit comme un exécuteur de bas niveau. Il traduit les actions de haut niveau de la politique en code heuristique exécutable (déroulements) conditionné par les parents sélectionnés et la directive.
   • Agents Critiques :
     • Critique de Politique ($\pi_{p\_critic}$) : Analyse les résultats des actions de politique (sélection de parents et directives) pour fournir des réflexions routées guidant les stratégies évolutionnaires futures.
     • Critique de Modèle du Monde ($\pi_{wm\_critic}$) : Compare les meilleurs et les pires déroulements heuristiques pour fournir des retours sur la qualité de la synthèse de code, guidant le modèle du monde à affiner la structure et l'efficacité algorithmiques.

3. Processus de Recherche :

   • Boucle Externe : Maintient une population de nœuds racines.
   • Boucle Interne : Construit progressivement un graphe d'inférence ancré à la population actuelle. À chaque étape, le système échantillonne plusieurs actions et déroulements, sélectionne le nœud résultant le meilleur, et met à jour le graphe.
   • Mécanismes de Diversité : Pour prévenir des sorties à faible diversité, PathWise emploie une Diversité au Niveau des Invites (perturbation des invites avec des phrases exploratoires) et un Mélange d'États (randomisation de l'ordre des nœuds pour atténuer les biais positionnels).

Contributions Clés

1. Formulation Hybride Graphe-Population : Les auteurs introduisent une formulation où un graphe d'inférence encode la justification de dérivation et l'historique des performances, servant d'état partagé pour l'interaction entre la politique et le modèle du monde.
2. Cadre Multi-Agents Coordonné : Un système où un agent politique contrôle la stratégie évolutionnaire, un modèle du monde exécute la génération de code, et des agents critiques fournissent des réflexions routées, permettant une génération heuristique auto-évolutive et consciente de l'état sans mise à jour des paramètres du LLM.
3. Diversité au Niveau des Invites : Des mécanismes pour assurer la variété dans la sélection des parents et les déroulements heuristiques, permettant une exploration plus large sur le graphe d'inférence.
4. Validation Empirique : Des expériences extensives démontrant que PathWise découvre des heuristiques plus fortes avec moins d'évaluations, atteint une convergence plus rapide, et s'adapte efficacement à des tailles de problèmes plus grandes sur divers COP.

Résultats Expérimentaux

PathWise a été évalué sur plusieurs COP NP-difficiles, notamment le Problème du Voyageur de Commerce (TSP), le Problème du Sac à Dos (KP), le Problème de Tournées de Véhicules à Capacité Contrainte (CVRP), le Problème du Sac à Dos Multiple (MKP), le Problème d'Orientation (OP) et le Problème de Remplissage de Conteneurs (BPP). Le cadre a été testé sur trois paradigmes de recherche : Construction Étape par Étape, Optimisation par Colonie de Fourmis (ACO) et Recherche Locale Guidée (GLS).

• Performance : PathWise a constamment surpassé les références AHD basées sur les LLM les plus avancées (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) et les heuristiques conçues manuellement. Il a atteint des écarts d'optimalité inférieurs sur les ensembles de tests à la fois en domaine et hors domaine.
• Efficacité : PathWise a convergé plus rapidement vers de meilleures heuristiques. Dans plusieurs expériences, PathWise a atteint une performance supérieure avec seulement 500 évaluations, alors que les références avaient droit à 1000 évaluations.
• Évolutivité : La méthode a démontré une forte généralisation à des tailles de problèmes plus grandes (par exemple, TSP avec $N=200$, KP avec $N=500$) et à différents modèles de base LLM (GPT-4o-mini, GPT-5-nano avec des niveaux de raisonnement variables).
• Études d'Ablation : La suppression des agents critiques ou des mécanismes de diversité a considérablement dégradé les performances, confirmant la nécessité d'un retour d'information conscient de l'état et de l'exploration.

Importance et Revendications

L'article revendique que PathWise représente un passage de l'"évolution par essais et erreurs" vers la "planification consciente de l'état par le raisonnement". En traitant la découverte heuristique comme un processus de décision séquentielle sur un graphe d'inférence, le système peut transmettre les décisions passées et réutiliser ou éviter les informations de dérivation à travers les générations.

Les auteurs soulignent que PathWise est sans entraînement dans le sens où il ne met pas à jour les paramètres du LLM ; au lieu de cela, il exploite les connaissances pré-entraînées des LLM renforcées par des réflexions en langage naturel. L'importance réside dans sa capacité à surmonter la myopie des méthodes AHD existantes en fournissant une mémoire structurée du processus de recherche, réduisant ainsi les évaluations redondantes et permettant une découverte plus efficace d'heuristiques de haute qualité pour des problèmes combinatoires complexes. Ce travail suggère que le raisonnement structuré sur l'historique de dérivation est un composant critique pour l'extension de la conception automatisée d'algorithmes basée sur les LLM.