Riepilogo Tecnico: ImprovEvolve: Basin-Hopping incontra la Ricerca Evolutiva Guidata da LLM

Definizione del Problema

Il documento affronta la sfida di utilizzare i Large Language Models (LLM) per risolvere problemi complessi di ottimizzazione matematica, in particolare quelli con paesaggi rugosi, non convessi e non regolari (ad esempio, problemi di impacchettamento, disuguaglianze funzionali e codici sferici). Il lavoro precedente come AlphaEvolve ha tentato di evolvere programmi monolitici per produrre direttamente soluzioni candidate, ma gli autori sostengono che questo approccio imponga un carico cognitivo eccessivo all'LLM. Il modello deve progettare simultaneamente uno schema di inizializzazione, una strategia di ricerca e criteri di terminazione, portando spesso alla generazione di programmi che si affidano a routine standard (come L-BFGS-B) che non riescono a gestire efficacemente i vincoli specifici e la non convessità del problema. Di conseguenza, le soluzioni generate dagli LLM mescolano l'intuizione matematica con l'euristica piuttosto che risolvere rigorosamente il compito di ottimizzazione, e faticano a generalizzare a dimensioni di problemi non viste o a migliorare le soluzioni costruite da esperti.

Metodologia: ImprovEvolve

Gli autori propongono ImprovEvolve, un'alternativa algoritmica che decompone il compito di ottimizzazione in sottoprogrammi specializzati, integrando efficacemente le tecniche di ottimizzazione globale Basin-Hopping con la ricerca evolutiva guidata da LLM.

Decomposizione Core

Invece di evolvere una singola funzione che restituisce una soluzione, ImprovEvolve evolve una classe Python che implementa tre operatori distinti:

1. generate_config(seed): Inizializza una soluzione fattibile da un seme casuale.
2. improve(x): Esegue un'ottimizzazione locale per raffinare una configurazione $x$, restituendo una soluzione $x'$ con un fitness almeno pari a $x$.
3. perturb(x, \sigma): Esplora casualmente lo spazio di ricerca a un'intensità specifica $\sigma$.

Schema di Validazione (Basin-Hopping)

La classe evoluta viene utilizzata all'interno di uno schema di validazione a due stadi (Algoritmo 1) che imita il Monotonic Basin-Hopping ($T=0$):

• Stadio A (Inizializzazione): Vengono generate molteplici configurazioni iniziali e raffinate tramite improve. Viene selezionato il miglior risultato come punto di partenza $x^*$.
• Stadio B (Ricerca Iterativa): L'algoritmo esegue $R$ round di perturbazione e miglioramento. In ogni round, l'intensità della perturbazione $\sigma$ decade geometricamente da $\sigma_{max}$ a $\sigma_{min}$. Il processo prevede:
  1. Perturbare l'attuale migliore soluzione: $x' = \text{perturb}(x^*, \sigma)$.
  2. Raffinare la soluzione perturbata: $x'' = \text{improve}(x')$.
  3. Accettazione Monotona: $x^*$ viene aggiornato a $x''$ solo se il fitness migliora rigorosamente.

Questa decomposizione sposta il compito dell'LLM dal progettare un ottimizzatore end-to-end all'codificare euristiche specifiche del dominio per l'inizializzazione, la ricerca locale e l'esplorazione, che vengono poi orchestrate dal framework classico di Basin-Hopping.

Framework Evolutivo

Il sistema utilizza il framework GigaEvo con un ciclo MAP-Elites. Il fitness di un programma candidato è determinato eseguendo l'intero schema di validazione a due stadi su di esso. L'LLM (Gemini 3 Pro per l'inizializzazione, Gemini 3 Flash per l'evoluzione) muta il codice della classe Improv, guidato dal feedback sul fitness e dalle intuizioni sulla linea di discendenza.

Contributi Chiave e Risultati

1. Impacchettamento Esagonale (HEX $n$)

• Task: Impacchettare $n$ esagoni regolari unitari nel più piccolo esagono regolare contenitore.
• Risultati:
  • Per $n=11$, ImprovEvolve ha scoperto un nuovo stato dell'arte (SOTA) di impacchettamento con lato $L=3.9245$, superando il $3.9301$ di AlphaEvolve e il precedente record umano di $3.9434$.
  • Il programma evoluto si è generalizzato a dimensioni di problemi non viste ($11 \le n \le 24$) senza nuova evoluzione, trovando nuovi impacchettamenti SOTA per $n=12, 15, 16$.
  • ImprovEvolve+E: Con lievi modifiche umane (cambio di ottimizzatori, regolazione dei pesi delle penalità), il sistema ha trovato nuovi impacchettamenti SOTA per $n=14, 17, 23$ e ha fornito impacchettamenti strutturati per $n=25-30$ dove non esistevano risultati precedenti.
• Confronto: ImprovEvolve ha superato significativamente il baseline GigaEvo (approccio monolitico), che non è riuscito a generalizzare a $n > 11$ a causa di errori di sovrapposizione.

2. Seconda Disuguaglianza di Autocorrelazione (ACI 2)

• Task: Trovare una funzione non negativa $f$ che massimizzi la costante $C_2$ nella disuguaglianza $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$.
• Risultati:
  • Il programma base ImprovEvolve ha raggiunto $C(f) = 0.9512$, superando i baseline open-source ma restando al di sotto dello $0.96102$ di AlphaEvolve.
  • ImprovEvolve+E: Riprendendo l'ottimizzazione dalla soluzione di AlphaEvolve e applicando modifiche guidate dall'uomo (scaling progressivo della risoluzione fino a 1.6M step, rimozione del clipping inferiore), il sistema ha raggiunto un nuovo limite inferiore SOTA di $C(f) = 0.96258$.
• Significato: Ciò dimostra la capacità del framework di raffinare le soluzioni di alta qualità esistenti fornite da esperti o altri modelli, una capacità che gli approcci monolitici degli LLM faticano a gestire.

3. Codici Sferici

• Task: Disporre $N$ punti su una sfera unitaria $S^{d-1}$ per minimizzare il prodotto scalare massimo (coerenza).
• Risultati:
  • Valutato su 90 diverse configurazioni del catalogo Cohn ($d \in [8, 16]$).
  • ImprovEvolve++ (un miglioratore generale calibrato evoluto attraverso molteplici dimensioni) ha ridotto rigorosamente il coseno massimo per 53 dei 90 configurazioni, ottenendo un miglioramento relativo medio dello 0.1765%.
  • Ciò rappresenta un miglioramento di 2.35$\times$ rispetto al miglior programma precedente (ImprovEvolve).
  • Le diagnosi (UMAP e distribuzioni dei prodotti scalari) hanno mostrato che ImimprovEvolve++ ha eseguito riarrangiamenti strutturali globali, spostando i punti in regioni distinte dello spazio di ricerca, mentre altre varianti hanno effettuato solo aggiustamenti locali.

Robustezza Statistica

Gli studi multi-run hanno confermato che i miglioramenti di ImprovEvolve sono statisticamente significativi ($p < 0.05$) rispetto al baseline GigaEvo, validando il fatto che la decomposizione modulare offre un vantaggio riproducibile rispetto all'apprendimento di un ottimizzatore monolitico.

Significato e Claim

Il documento sostiene che decomporre i compiti di ottimizzazione in sottoproblemi modulari è un principio critico per la scoperta guidata da LLM.

• Riduzione del Carico Cognitivo: Separando l'inizializzazione, il miglioramento locale e la perturbazione, l'LLM si concentra sull'codificare la struttura matematica e le euristiche piuttosto che sull'orchestrare l'intero processo di ricerca.
• Collaborazione Uomo-LLM: L'interfaccia modulare consente agli esperti di dominio di applicare modifiche mirate e minime (ad esempio, cambiare ottimizzatori, regolare gli schedule di risoluzione) per aumentare significativamente le prestazioni, colmando il divario tra il codice generato dall'LLM e il tuning di livello esperto.
• Generalizzazione: L'interfaccia improve/perturb consente ai programmi evoluti di generalizzare a dimensioni di problemi non viste e di riprendere l'ottimizzazione da soluzioni fornite da esperti, superando la fragilità dei programmi end-to-end monolitici.

Gli autori posizionano questo lavoro come un passo verso la scalabilità della scoperta matematica potenziata dagli LLM, suggerendo che i sistemi futuri dovrebbero combinare tali decomposizioni personalizzate con workflow agentici in grado di decidere autonomamente quali moduli raffinare. Il documento rimane modesto riguardo alla generalizzabilità più ampia, notando che la valutazione quantitativa è attualmente limitata a questi tre specifici domini di ottimizzazione.