Riepilogo Tecnico: PathWise

Enunciato del Problema

La Progettazione Euristica Automatizzata (AHD) mira a generare automaticamente algoritmi euristici per Problemi di Ottimizzazione Combinatoria (COP), riducendo la dipendenza da progettazioni manuali realizzate da esperti. Sebbene i Modelli Linguistici di Grande Dimensione (LLM) abbiano recentemente abilitato l'AHD integrandosi nei processi di ricerca evolutiva, i framework esistenti soffrono di limitazioni significative. I metodi basati su popolazione spesso fanno affidamento su regole evolutive fisse e modelli di prompt statici, portando a una generazione euristica miope, a valutazioni ridondanti e a una convergenza prematura. I metodi basati su alberi, come quelli che utilizzano la Ricerca ad Albero Monte Carlo (MCTS), impongono strutture gerarchiche guidate dalle statistiche delle prestazioni piuttosto che dalla comprensione semantica del paesaggio di ricerca. Fondamentalmente, gli approcci attuali mancano di una rappresentazione semantica e con stato di come vengono derivate le euristiche, di come le modifiche si propagano attraverso le generazioni o di perché le modifiche abbiano successo o fallimento. Ciò si traduce in un uso inefficiente delle chiamate agli LLM e nel fallimento nel portare avanti efficacemente le decisioni passate.

Metodologia

Gli autori propongono PathWise (Pianificazione attraverso un Modello del Mondo per la Progettazione Euristica Automatizzata tramite LLM Auto-Evolventi), un nuovo framework di ragionamento multi-agente che formula la generazione euristica come un processo decisionale sequenziale su un grafo di implicazione. Questo grafo funge da memoria compatta e con stato della traiettoria di ricerca.

Componenti Principali

1. Grafo di Implicazione ($G = (V, E)$):

   • A differenza degli alberi evolutivi standard o delle popolazioni, il grafo di implicazione codifica la storia della derivazione.
   • Nodi ($v$): Rappresentano tuple contenenti il codice euristico ($h$), una motivazione di derivazione in linguaggio naturale ($\kappa$), una descrizione algoritmica ($d$), metriche di prestazione ($P(h; D)$) e metadati dei genitori ($PM$).
   • Archi ($E$): Collegano insiemi di genitori ai nodi figli, codificando la motivazione specifica utilizzata per derivare il figlio dai suoi genitori.
   • Questa struttura permette al sistema di condizionare le decisioni future sulla storia della derivazione, anziché trattare i passaggi come eventi di campionamento isolati.

2. Sistema Multi-Agente:
   Il framework opera attraverso un ciclo coordinato di pianificazione, esecuzione e riflessione su due scale temporali (aggiornamenti della popolazione esterna e passaggi di implicazione interni):

   • Agente di Politica ($\pi_p$): Agisce come pianificatore di alto livello. Osserva lo stato corrente (il fronte del grafo di implicazione) e propone azioni definite da una tupla di nodi genitori selezionati ($S$) e una motivazione di derivazione in linguaggio naturale ($\kappa$). Ciò permette alla politica di inventare dinamicamente nuovi tipi di operatori anziché affidarsi a modelli fissi.
   • Agente del Modello del Mondo ($\pi_{wm}$): Agisce come esecutore di basso livello. Traduce le azioni di alto livello della politica in codice euristico eseguibile (rollout) condizionato sui genitori selezionati e sulla direttiva.
   • Agenti Critici:
     • Critico della Politica ($\pi_{p\_critic}$): Analizza gli esiti delle azioni della politica (selezioni dei genitori e direttive) per fornire riflessioni instradate che guidano le future strategie evolutive.
     • Critico del Modello del Mondo ($\pi_{wm\_critic}$): Confronta i rollout euristici con le prestazioni migliori e peggiori per fornire feedback sulla qualità della sintesi del codice, guidando il modello del mondo a rifinire la struttura algoritmica e l'efficienza.

3. Processo di Ricerca:

   • Ciclo Esterno: Mantiene una popolazione di nodi radice.
   • Ciclo Interno: Costruisce incrementally un grafo di implicazione radicato nella popolazione corrente. Ad ogni passaggio, il sistema campiona molteplici azioni e rollout, seleziona il nodo risultante migliore e aggiorna il grafo.
   • Meccanismi di Diversità: Per prevenire output a bassa diversità, PathWise impiega Diversità a Livello di Prompt (perturbando i prompt con frasi esplorative) e Mescolamento dello Stato (randomizzando l'ordine dei nodi per mitigare il bias posizionale).

Contributi Chiave

1. Formulazione Ibrida Grafo-Popolazione: Gli autori introducono una formulazione in cui un grafo di implicazione codifica la motivazione della derivazione e la storia delle prestazioni, fungendo da stato condiviso per l'interazione tra politica e modello del mondo.
2. Framework Multi-Agente Coordinato: Un sistema in cui un agente di politica controlla la strategia evolutiva, un modello del mondo esegue la generazione di codice e agenti critici forniscono riflessioni instradate, abilitando una generazione euristica auto-evolutiva e consapevole dello stato senza aggiornare i parametri degli LLM.
3. Diversità a Livello di Prompt: Meccanismi per garantire varietà nella selezione dei genitori e nei rollout euristici, consentendo un'esplorazione più ampia sul grafo di implicazione.
4. Validazione Empirica: Esperimenti estesi che dimostrano come PathWise scopra euristiche più forti con meno valutazioni, raggiunga una convergenza più rapida e si scalini efficacemente a dimensioni di problema più grandi su COP diversi.

Risultati Sperimentali

PathWise è stato valutato su molteplici COP NP-difficili, tra cui il Problema del Commesso Viaggiatore (TSP), il Problema dello Zaino (KP), il Problema di Instradamento Veicolare a Capacità (CVRP), il Problema dello Zaino Multiplo (MKP), il Problema di Orientamento (OP) e il Problema di Imballaggio in Bin (BPP). Il framework è stato testato su tre paradigmi di ricerca: Costruzione Passo-Passo, Ottimizzazione della Colonia di Formiche (ACO) e Ricerca Locale Guidata (GLS).

• Prestazioni: PathWise ha costantemente superato le linee di base AHD basate su LLM all'avanguardia (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) e le euristiche progettate manualmente. Ha raggiunto gap di ottimalità inferiori sia su set di test intra-dominio che extra-dominio.
• Efficienza: PathWise ha converguto più rapidamente verso euristiche migliori. In diversi esperimenti, PathWise ha raggiunto prestazioni superiori con sole 500 valutazioni, mentre alle linee di base erano consentite 1000 valutazioni.
• Scalabilità: Il metodo ha dimostrato una forte generalizzazione a dimensioni di problema più grandi (ad esempio, TSP con $N=200$, KP con $N=500$) e diversi back-end LLM (GPT-4o-mini, GPT-5-nano con livelli di ragionamento variabili).
• Studi di Ablazione: La rimozione degli agenti critici o dei meccanismi di diversità ha degradato significativamente le prestazioni, confermando la necessità di feedback consapevoli dello stato e di esplorazione.

Significato e Affermazioni

Il documento afferma che PathWise rappresenta un passaggio dall'"evoluzione per tentativi ed errori" verso la "pianificazione consapevole dello stato attraverso il ragionamento". Trattando la scoperta euristica come un processo decisionale sequenziale su un grafo di implicazione, il sistema può portare avanti le decisioni passate e riutilizzare o evitare informazioni di derivazione attraverso le generazioni.

Gli autori sottolineano che PathWise è senza addestramento nel senso che non aggiorna i parametri degli LLM; invece, sfrutta la conoscenza pre-addestrata degli LLM rafforzata attraverso riflessioni in linguaggio naturale. Il significato risiede nella sua capacità di superare la miopia dei metodi AHD esistenti fornendo una memoria strutturata del processo di ricerca, riducendo così le valutazioni ridondanti e abilitando una scoperta più efficace di euristiche di alta qualità per problemi combinatori complessi. Il lavoro suggerisce che il ragionamento strutturato sulla storia della derivazione è un componente critico per la scalabilità della progettazione algoritmica automatizzata basata su LLM.