Technische Samenvatting: ImprovEvolve: Basin-Hopping ontmoet LLM-gestuurde evolutionaire zoektocht

Probleemstelling

Het artikel behandelt de uitdaging van het gebruik van Large Language Models (LLM's) om complexe wiskundige optimalisatieproblemen op te lossen, met name die met grillige, niet-convexe en niet-gladde landschappen (bijv. pakproblemen, functionele ongelijkheden en sferische codes). Eerdere werken zoals AlphaEvolve slaagden er succesvol in om monolithische programma's te evolueren die kandidaat-oplossingen direct outputten, maar de auteurs stellen dat deze aanpak een excessieve cognitieve belasting legt op het LLM. Het model moet simultaan een initialisatieschema, een zoekstrategie en terminatiecriteria ontwerpen, wat vaak leidt tot gegenereerde programma's die vertrouwen op standaardroutines (zoals L-BFGS-B), die er echter niet in slagen de specifieke beperkingen en niet-convexiteit van het probleem effectief te behandelen. Bijgevolg zijn door LLM-gegenereerde oplossingen vaak een mengeling van wiskundig inzicht en heuristieken, in plaats van het optimalisatietaak rigoureus op te lossen, en hebben ze moeite met het generaliseren naar ongeziene probleemgroottes of het verbeteren van door experts geconstrueerde oplossingen.

Methodologie: ImprovEvolve

De auteurs stellen ImprovEvolve voor, een algoritmisch alternatief dat de optimalisatietaak deelt in gespecialiseerde subroutines, waarbij effectief Basin-Hopping globale optimalisatietechnieken wordt geïntegreerd met LLM-gestuurde evolutionaire zoektocht.

Kerndecompositie

In plaats van een enkele functie te evolueren die een oplossing output, evolueert ImprovEvolve een Python-klasse die drie afzonderlijke operatoren implementeert:

1. generate_config(seed): Initialiseert een haalbare oplossing vanuit een willekeurige seed.
2. improve(x): Voert lokale optimalisatie uit om een configuratie $x$ te verfijnen, waarbij een oplossing $x'$ wordt geretourneerd met een fitness die minstens even goed is als die van $x$.
3. perturb(x, \sigma): Verkent willekeurig de zoekruimte op een specifieke intensiteit $\sigma$.

Validatieschema (Basin-Hopping)

De geëvolueerde klasse wordt gebruikt binnen een tweefasig validatieschema (Algoritme 1) dat Monotonic Basin-Hopping ($T=0$) nabootst:

• Fase A (Initialisatie): Meerdere initiële configuraties worden gegenereerd en verfijnd via improve. De beste resultaten worden geselecteerd als startpunt $x^*$.
• Fase B (Iteratieve Zoektocht): Het algoritme voert $R$ rondes van perturbatie en verbetering uit. In elke ronde neemt de perturbatie-intensiteit $\sigma$ geometrisch af van $\sigma_{max}$ naar $\sigma_{min}$. Het proces omvat:
  1. Het perturberen van de huidige beste oplossing: $x' = \text{perturb}(x^*, \sigma)$.
  2. Het verfijnen van de geperturbeerde oplossing: $x'' = \text{improve}(x')$.
  3. Monotone Acceptatie: $x^*$ wordt alleen bijgewerkt naar $x''$ als de fitness strikt verbetert.

Deze decompositie verschuift de taak van het LLM van het ontwerpen van een end-to-end optimizer naar het coderen van domeinspecifieke heuristieken voor initialisatie, lokale zoektocht en exploratie, die vervolgens worden georkestreerd door het klassieke Basin-Hopping framework.

Evolutionair Framework

Het systeem maakt gebruik van het GigaEvo framework met een MAP-Elites loop. De fitness van een kandidaat-programma wordt bepaald door het volledige tweefasige validatieschema op het toe te passen. Het LLM (Gemini 3 Pro voor initialisatie, Gemini 3 Flash voor evolutie) muteert de code van de Improv klasse, geleid door fitness-feedback en lineage-inzichten.

Belangrijkste Bijdragen en Resultaten

1. Hexagon Packing (HEX $n$)

• Taak: Het verpakken van $n$ eenheden regelmatige hexagonen in de kleinste omsluitende regelmatige hexagon.
• Resultaten:
  • Voor $n=11$ ontdekte ImprovEvolve een nieuwe state-of-the-art (SOTA) verpakking met zijlengte $L=3.9245$, wat de AlphaEvolve $3.9301$ en de vorige menselijke record van $3.9434$ verbetert.
  • Het geëvolueerde programma generaliseerde naar ongeziene probleemgroottes ($11 \le n \le 24$) zonder her-evolutie, waarbij nieuwe SOTA-verpakkingen werden gevonden voor $n=12, 15, 16$.
  • ImprovEvolve+E: Met minimale menselijke edities (het wisselen van optimizers, het aanpassen van penalty weights) vond het systeem nieuwe SOTA-verpakkingen voor $n=14, 17, 23$ en bood gestructureerde verpakkingen voor $n=25-30$ waar voorheen geen resultaten bestonden.
• Vergelijking: ImprovEvolve presteerde aanzienlijk beter dan de GigaEvo-baseline (monolithische aanpak), die faalde in het generaliseren naar $n > 11$ vanwege overlapfouten.

2. Second Autocorrelation Inequality (ACI 2)

• Taak: Het vinden van een niet-negatieve functie $f$ die de constante $C_2$ maximaliseert in de ongelijkheid $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$.
• Resultaten:
  • Het basisprogramma van ImprovEvolve bereikte $C(f) = 0.9512$, waarmee het open-source baselines overtrof maar tekortschoot voor AlphaEvolve's $0.96102$.
  • ImprovEvolve+E: Door de optimalisatie te hervatten vanaf de AlphaEvolve-oplossing en mensgestuurde edities toe te passen (progressieve resolutie-opschaling tot 1.6M stappen, verwijderen van onderste clipping), bereikte het systeem een nieuwe Sote-ondergrens van $C(f) = 0.96258$.
• Betekenis: Dit demonstreert het vermogen van het framework om bestaande hoogwaardige oplossingen te verfijnen die door experts of andere modellen zijn geleverd, een capaciteit waar monolithische LLM-benaderingen moeite mee hebben.

3. Spherical Codes

• Taak: Het arrangeren van $N$ punten op een eenheidsfeer $S^{d-1}$ om de maximale paarwijze inwendige product (coherence) te minimaliseren.
• Resultaten:
  • Geëvalueerd op 90 diverse configuraties uit de Cohn-catalogus ($d \in [8, 16]$).
  • ImprovEvolve++ (een gekalibreerde algemene improver geëvolueerd over meerdere dimensies) verlaagde strikt het maximale cosinus voor 53 van de 90 configuraties, met een gemiddelde relatieve verbetering van 0.1765%.
  • Dit vertegenwoordigt een 2.35$\times$ verbetering ten opzichte van het beste eerdere programma (ImprovEvolve).
  • Diagnostiek (UMAP en inwendige productdistributies) toonden aan dat ImprovEvolve++ globale structurele herrangschikkingen uitvoerde, waarbij punten naar verschillende regio's in de zoekruimte werden verplaatst, terwijl andere varianten slechts lokale aanpassingen maakten.

Statistische Robuustheid

Multi-run studies bevestigden dat de verbeteringen van ImprovEvolve statistisch significant zijn ($p < 0.05$) vergeleken met de GigaEvo-baseline, wat valideert dat de modulaire decompositie een reproduceerbaar voordeel biedt boven het leren van een monolithische optimizer.

Betekenis en Claims

Het artikel beweert dat het decomponeren van optimalisatietaken in modulaire subproblemen een cruciaal principe is voor LLM-gestuurde ontdekking.

• Verminderde Cognitieve Belasting: Door initialisatie, lokale verbetering en perturbatie te scheiden, kan het LLM zich concentreren op het coderen van wiskundige structuur en heuristieken in plaats van het orkestreren van het gehele zoekproces.
• Mens-LLM Samenwerking: De modulaire interface stelt domeinexperts in staat om gerichte, minimale edities toe te passen (bijv. het wijzigen van optimizers, het aanpassen van resolutie-schema's), wat de kloof tussen LLM-gegenereerde code en expert-niveau tuning overbrugt.
• Generalisatie: De improve/perturb interface stelt geëvolueerde programma's in staat om te generaliseren naar ongeziene probleemgroottes en om optimalisatie te hervatten vanaf door experts geleverde oplossingen, wat de broosheid van monolithische end-to-end programma's overwint.

De auteurs positioneren dit werk als een stap naar het schalen van LLM-gestuurde wiskundige ontdekking, waarbij zij suggereren dat toekomstige systemen dergelijke op maat gemaakte decomposities moeten combineren met agentische workflows die autonoom beslissen welke modules te verfijnen. Het artikel blijft bescheiden over bredere generaliseerbaarheid en merkt op dat kwantitatieve evaluatie momenteel beperkt is tot deze drie specifieke optimalisatiedomeinen.