🤖 AI

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

ImprovEvolve führt eine LLM-gestützte evolutionäre Suche ein, die spezialisierte Initialisierungs-, Verbesserungs- und Perturbationsoperatoren entwickelt, um einen Basin-Hopping-Prozess voranzutreiben, wodurch erfolgreich neue State-of-the-Art-Lösungen für Hexagon-Packungen, Autokorrelationsungleichungen und sphärische Codes entdeckt werden, während gleichzeitig die kognitive Belastung des Sprachmodells signifikant reduziert wird.

Ursprüngliche Autoren: Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

Veröffentlicht 2026-06-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, ein unglaublich schwieriges Rätsel zu lösen, wie zum Beispiel eine bestimmte Anzahl seltsam geformter Hexagone in einen Behälter einzupassen, ohne dass sie sich überlappen, oder die perfekte mathematische Kurve zu finden, die einen bestimmten Wert maximiert. Dies sind „Optimierungsprobleme“, und sie sind notorisch schwierig, weil die Landschaft der möglichen Lösungen voller winziger Hügel und tiefer Täler ist (lokale Optima). Wenn man einen falschen Schritt macht, kann man in einem flachen Tal stecken bleiben und das tiefste jemals finden.

Lange Zeit versuchten Forscher, Künstliche Intelligenz (speziell Large Language Models oder LLMs) beizubringen, diese Rätsel zu lösen, indem sie die KI baten, ein einziges, riesiges Programm zu schreiben, das alles auf einmal erledigt: Es muss herausfinden, wie man startet, wie man sich bewegt und wann man aufhört. Es ist, als würde man einen Koch nicht nur bitten, eine Mahlzeit zu kochen, sondern auch die Küche zu entwerfen, neue Utensilien zu erfinden und das Rezeptbuch zu schreiben – und das alles in einem Rutsch. Das Paper nennt diesen Ansatz „AlphaEvolve“. Obwohl es manchmal funktioniert, überfordert es die KI oft, was zu unbeholfenen oder unvollständigen Lösungen führt.

Die neue Idee: ImprovEvolve

Die Autoren dieses Papers, Alexey Kravatskiy und Kollegen, schlagen einen klügeren Weg namens ImprovEvolve vor. Anstatt die KI zu bitten, den gesamten „Super-Optimierer“ von Grund auf neu zu bauen, unterteilen sie die Aufgabe in drei kleine, handhabbare Aufgaben. Sie bitten die KI, einen „Werkzeugkasten“ zu erstellen, der drei spezifische Werkzeuge enthält:

Der Starter (generate_config): Ein Werkzeug, das lediglich einen zufälligen, gültigen Startpunkt für das Rätsel erstellt.
Der Polierer (improve): Ein Werkzeug, das eine unordentliche Lösung nimmt und sie ein Stück besser macht, indem es die Kanten glättet.
Der Schüttler (perturb): Ein Werkzeug, das die Lösung zufällig durchschüttelt, um zu sehen, ob das Lockern hilft, damit sie in ein tieferes, besseres Tal fällt.

Der „Basin-Hopping“-Tanz

Sobald die KI diesen Werkzeugkasten gebaut hat, nutzen die Forscher nicht einfach nur das Ergebnis, sondern wenden eine klassische mathematische Strategie an, die Basin-Hopping genannt wird. Stellen Sie sich das wie einen Wanderer vor, der versucht, den tiefsten Punkt in einer nebligen Gebirgslandschaft zu finden:

Start: Der Wanderer lässt einen zufälligen Punkt fallen (unter Verwendung des Starters).
Polieren: Er läuft bergab zum nächstgelegenen Talboden (unter Verwendung des Polierers).
Schütteln: Er macht einen großen, zufälligen Sprung (unter Verwendung des Schüttlers) an einen neuen Ort, in der Hoffnung, in einem anderen, tieferen Tal zu landen.
Wiederholen: Wenn der neue Ort tiefer liegt, bleibt er dort. Wenn nicht, versucht er es vielleicht noch einmal. Er macht dies immer und immer wieder, wobei er die Sprünge allmählich kleiner macht, während er sich dem Boden nähert.

Indem sie das „Denken“ (was die KI tut) vom „Suchen“ (der Basin-Hopping-Schleife) trennen, muss sich die KI nur auf eine spezifische Sache zur Zeit konzentrieren. Dies reduziert die „kognitive Last“ für die KI, ähnlich wie ein Mensch bei der Lösung eines komplexen Problems besser zurechtkommt, wenn er es in kleine Schritte unterteilt, anstatt zu versuchen, das Ganze auf einmal im Kopf zu behalten.

Die Ergebnisse: Neue Rekorde

Das Paper testet diese Methode an drei sehr schwierigen mathematischen Herausforderungen:

Hexagon-Packung: Stellen Sie sich vor, Sie versuchen, 11, 12 oder sogar 23 Hexagone in die kleinste mögliche hexagonale Box zu packen. Die neue Methode fand neue Weltrekord-Packungen für mehrere dieser Zahlen und schlug damit bisherige Rekorde, die von anderen KI-Systemen und sogar menschlichen Experten gesetzt wurden.
Die Autokorrelations-Ungleichung: Dies ist ein komplexes mathematisches Problem über die perfekte Form einer Welle. Die KI verbesserte die bekannte mathematische Grenze (die „untere Schranke“) von 0,96102 auf 0,96258. Dies geschah, indem sie eine bereits gute Lösung, die von einer vorherigen KI gefunden wurde, mit dem neuen „Polierer“-Werkzeug weiter verfeinerte.
Sphärische Codes: Hierbei geht es darum, Punkte auf einer Kugel anzuordnen, sodass sie so weit wie möglich voneinander entfernt sind (wie die Kerne in einem Granatapfel). Die neue Methode verbesserte die Anordnung für die Mehrheit von 90 verschiedenen Testfällen und fand Konfigurationen, die effizienter waren als alles bisher Bekannte.

Die menschliche Note

Interessanterweise stellt das Paper fest, dass ein menschlicher Experte einige winzige Anpassungen am Code vornahm (wie das Ändern einer spezifischen Einstellung oder das Wechseln eines mathematischen Werkzeugs), um die absolut besten Ergebnisse zu erzielen. Dies deutet darauf an, dass die besten Ergebnisse aus einer Partnerschaft entstehen: Die KI generiert die Kernstruktur und Logik, und der Mensch liefert das abschließende „Feintuning“, das die KI vielleicht übersieht.

Zusammenfassend

Das Paper argumentiert, dass wir nicht von einer KI verlangen sollten, ein „Supergenie“ zu sein, das ein ganzes Problem in einem Durchgang löst, sondern dass wir sie dazu bringen sollten, eine „Spezialistin“ zu sein, die einen Satz an Werkzeugen baut. Dann nutzen wir diese Werkzeuge in einer smarten, iterativen Schleife (Basin-Hopping), um den Lösungsraum zu erkunden. Dieser Ansatz, ImprovEvolve, erwies sich als effektiver, robuster und fähiger, mathematische Rekorde zu finden, als bisherige Methoden, die versuchten, alles gleichzeitig zu erledigen.

Technisches Resümee: ImprovEvolve: Basin-Hopping trifft auf LLM-gestützte evolutionäre Suche

Problemstellung

Die Arbeit befasst sich mit der Herausforderung, Large Language Models (LLMs) einzusetzen, um komplexe mathematische Optimierungsprobleme zu lösen, insbesondere solche mit zerklüfteten, nicht-konvexen und nicht-glatten Landschaften (z. B. Packungsprobleme, funktionale Ungleichungen und sphärische Codes). Während vorangegangene Arbeiten wie AlphaEvolve erfolgreich monolithische Programme evolvierten, die Kandidatenlösungen direkt ausgeben, argumentieren die Autoren, dass dieser Ansatz eine übermäßige kognitive Belastung für das LLM darstellt. Das Modell muss gleichzeitig ein Initialisierungsschema, eine Suchstrategie und Abbruchkriterien entwerfen, was häufig zu generierten Programmen führt, die auf Standardroutinen (wie L-BFGS-B) zurückgreifen, welche jedoch die spezifischen Nebenbedingungen und die Nicht-Konvexität des Problems nicht effektiv handhaben können. Infolgedessen mischen die durch das LLM generierten Lösungen oft mathematische Einsicht mit Heuristiken, anstatt das Optimierungsproblem rigoros zu lösen, und sie haben Schwierigkeiten, bei ungesehenen Problemgrößen zu generalisieren oder Experten-konstruierte Lösungen zu verbessern.

Methodik: ImprovEvolve

Die Autoren schlagen ImprovEvolve vor, eine algorithmische Alternative, die die Optimierungsaufgabe in spezialisierte Subroutinen zerlegt und dabei Basin-Hopping-Techniken zur globalen Optimierung effektiv mit einer LLM-gesteuerten evolutionären Suche integriert.

Kernzerlegung

Anstatt eine einzelne Funktion zu evolvieren, die eine Lösung ausgibt, evolviert ImprovEvolve eine Python-Klasse, die drei distinkte Operatoren implementiert:

generate_config(seed): Initialisiert eine zulässige Lösung aus einem zufälligen Seed.
improve(x): Führt eine lokale Optimierung durch, um eine Konfiguration $x$ zu verfeinern, und gibt eine Lösung $x'$ zurück, deren Fitness mindestens so gut wie die von $x$ ist.
perturb(x, \sigma): Exploriert den Suchraum zufällig bei einer spezifischen Intensität $\sigma$ .

Validierungsschema (Basin-Hopping)

Die evolvierte Klasse wird innerhalb eines zweistufigen Validierungsschemas (Algorithmus 1) verwendet, das das Monotonische Basin-Hopping ( $T=0$ ) nachahmt:

Stufe A (Initialisierung): Mehrere initiale Konfigurationen werden generiert und mittels improve verfeinert. Das beste Ergebnis wird als Startpunkt $x^*$ ausgewählt.
Stufe B (Iterative Suche): Der Algorithmus führt $R$ $R$ Runden von Perturbation und Verbesserung durch. In jeder Runde nimmt die Perturbationsintensität $\sigma$ $σ$ geometrisch von $\sigma_{max}$ $σ_{ma x}$ nach $\sigma_{min}$ $σ_{min}$ ab. Der Prozess umfasst:
1. Perturbation der aktuellen besten Lösung: $x' = \text{perturb}(x^*, \sigma)$ .
2. Verfeinerung der perturbierten Lösung: $x'' = \text{improve}(x')$ .
3. Monotone Akzeptanz: $x^*$ wird nur dann auf $x''$ aktualisiert, wenn sich die Fitness strikt verbessert.

Diese Zerlegung verschiebt die Aufgabe des LLM vom Entwurf eines End-to-End-Optimierers hin zur Kodierung domänenspezifischer Heuristiken für die Initialisierung, die lokale Suche und die Exploration, die dann durch das klassische Basin-Hopping-Framework orchestriert werden.

Evolutionärer Rahmen

Das System nutzt das GigaEvo-Framework mit einer MAP-Elites-Schleife. Die Fitness eines Kandidatenprogramms wird durch die Ausführung des vollständigen zweistufigen Validierungsschemas auf diesem bestimmt. Das LLM (Gemini 3 Pro für die Initialisierung, Gemini 3 Flash für die Evolution) mutiert den Code der Improv-Klasse, geleitet durch Fitness-Feedback und Lineage-Erkenntnisse.

Wichtigste Beiträge und Ergebnisse

1. Hexagon-Packung (HEX $n$ )

Aufgabe: Packung von $n$ regulären Hexagonen der Einheit in das kleinste umschließende reguläre Hexagon.
Ergebnisse:
- Für $n=11$ entdeckte ImprovEvolve eine neue State-of-the-Art (SOTA) Packung mit der Seitenlänge $L=3.9245$ , was die AlphaEvolve-Lösung von $3.9301$ und den vorherigen menschlichen Rekord von $3.9434$ verbessert.
- Das evolvierte Programm generalisierte auf ungesehene Problemgrößen ( $11 \le n \le 24$ ) ohne erneute Evolution und fand neue SOTA-Packungen für $n=12, 15, 16$ .
- ImprovEvolve+E: Mit geringfügigen menschlichen Edits (Wechsel der Optimierer, Anpassung der Penalty-Gewichte) fand das System neue SOTA-Packungen für $n=14, 17, 23$ und lieferte strukturierte Packungen für $n=25-30$ , für die bisher keine Ergebnisse existierten.
Vergleich: ImprovEvolve übertraf die GigaEvo-Baseline (monolithischer Ansatz) signifikant, da diese aufgrund von Überlappungsfehlern bei $n > 11$ nicht generalisieren konnte.

2. Zweite Autokorrelations-Ungleichung (ACI 2)

Aufgabe: Finden einer nicht-negativen Funktion $f$ , die die Konstante $C_2$ in der Ungleichung $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$ maximiert.
Ergebnisse:
- Das Basis-ImprovEvolve-Programm erreichte $C(f) = 0.9512$ , übertraf damit Open-Source-Baselines, blieb aber hinter AlphaEvolves $0.96102$ zurück.
- ImprovEvolve+E: Durch Fortsetzung der Optimierung von der AlphaEvolve-Lösung und Anwendung menschlich geführter Edits (progressive Skalierung der Auflösung bis zu 1,6 Mio. Schritten, Entfernen des unteren Clipping) erreichte das System eine neue SOTA-Untere Schranke von $C(f) = 0.96258$ .
Bedeutung: Dies demonstriert die Fähigkeit des Frameworks, bereits vorhandene hochwertige Lösungen von Experten oder anderen Modellen zu verfeinern – eine Fähigkeit, mit der monolithische LLM-Ansätze Schwierigkeiten haben.

3. Sphärische Codes

Aufgabe: Anordnung von $N$ Punkten auf einer Einheitssphäre $S^{d-1}$ , um das maximale paarweise Skalarprodukt (Kohärenz) zu minimieren.
Ergebnisse:
- Evaluierung auf 90 diversen Konfigurationen aus dem Cohn-Katalog ( $d \in [8, 16]$ ).
- ImprovEvolve++ (ein kalibrierter allgemeiner Verbesserer, der über mehrere Dimensionen hinweg entwickelt wurde) senkte das maximale Skalarprodukt strikt für 53 der 90 Konfigurationen und erreichte eine mittlere relative Verbesserung von 0,1765 %.
- Dies stellt eine 2,35-fache Verbesserung gegenüber dem besten vorherigen Programm (ImprovEvolve) dar.
- Diagnosen (UMAP und Skalarprodukt-Verteilungen) zeigten, dass ImprovEvolve++ globale strukturelle Umordnungen vornahm, indem es Punkte in distinkte Regionen des Suchraums bewegte, während andere Varianten lediglich lokale Anpassungen vornahmen.

Statistische Robustheit

Studien mit mehreren Durchläufen bestätigten, dass die Verbesserungen von ImprovEvolve statistisch signifikant sind ( $p < 0,05$ ) im Vergleich zur GigaEvo-Baseline, was validiert, dass die modulare Zerlegung einen reproduzierbaren Vorteil gegenüber dem Erlernen eines monolithischen Optimierers bietet.

Bedeutung und Ansprüche

Das Paper behauptet, dass die Zerlegung von Optimierungsaufgaben in modulare Teilprobleme ein kritisches Prinzip für die LLM-gestützte Entdeckung ist.

Reduzierte kognitive Belastung: Durch die Trennung von Initialisierung, lokaler Verbesserung und Perturbation konzentriert sich das LLM darauf, die mathematische Struktur und Heuristiken zu kodieren, anstatt den gesamten Suchprozess zu orchestrieren.
Mensch-LLM-Kollaboration: Die modulare Schnittstelle ermöglicht es Domänenexperten, gezielte, minimale Edits vorzunehmen (z. B. Wechsel der Optimierer, Anpassung der Auflösungsschemata), um die Leistung signifikant zu steigern und so die Lücke zwischen LLM-generiertem Code und Experten-Tuning zu schließen.
Generalisierung: Die improve/perturb-Schnittstelle ermöglicht es den evolvierten Programmen, auf ungesehene Problemgrößen zu generalisieren und die Optimierung von Experten-gelieferten Lösungen fortzusetzen, wodurch die Sprödigkeit monolithischer End-to-End-Programme überwunden wird.

Die Autoren positionieren diese Arbeit als einen Schritt zur Skalierung der LLM-gestützten mathematischen Entdeckung und legen nahe, dass zukünftige Systeme solche maßgeschneiderten Zerlegungen mit agentischen Workflows kombinieren sollten, die autonom entscheiden, welche Module zu verfeinern sind. Das Paper bleibt hinsichtlich einer breiteren Verallgemeinerbarkeit bescheiden und merkt an, dass die quantitative Evaluierung derzeit auf diese drei spezifischen Optimierungsdomänen beschränkt ist.