🤖 AI

An Evolutionary Framework for Automatic Optimization Benchmark Generation via Large Language Models

Dieses Paper schlägt den LLM-gesteuerten evolutionären Benchmark-Generator (LLM-EBG) vor, ein Framework, das Large Language Models als evolutionäre Operatoren nutzt, um automatisch diverse und strukturell komplexe Optimierungs-Benchmarks zu generieren, die die Leistung unterschiedlicher Algorithmen wie genetische Algorithmen und Differential Evolution effektiv differenzieren.

Ursprüngliche Autoren: Yuhiro Ono, Tomohiro Harada, Yukiya Miura

Veröffentlicht 2026-01-26

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Yuhiro Ono, Tomohiro Harada, Yukiya Miura

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 sind ein Trainer, der herausfinden möchte, welcher von zwei Athleten besser im Laufen ist. Wenn Sie sie nur auf einer perfekt flachen, geraden Laufbahn testen, könnten Sie denken, sie seien gleichermaßen schnell. Aber in der realen Welt finden Rennen auf schlammigen Hügeln, gewundenen Pfaden und rutschigen Oberflächen statt. Um wirklich zu wissen, wer der bessere Läufer ist, benötigen Sie eine Strecke, die gezielt die Stärken und Schwächen eines Läufers herausfordert, während sie gleichzeitig die des anderen testet.

Dieses Paper stellt einen neuen „Trainer“ für Computer-Algorithmen namens LLM-EBG vor. Seine Aufgabe ist es, diese kniffligen „Rennstrecken“ (Mathematikprobleme) automatisch zu entwerfen, um zu sehen, welcher Computer-Algorithmus gewinnt.

So funktioniert es, unterteilt in einfache Konzepte:

1. Das Problem: Die „falschen“ Strecken

Normalerweise testen Wissenschaftler Optimierungs-Algorithmen (wie Genetische Algorithmen oder Differentielle Evolution) auf Standard-Mathematikproblemen, die bereits existieren. Denken Sie an ein Fitnessstudio, das nur eine einzige Art von Laufband hat.

Das Problem: Diese Standard-Strecken sind zu perfekt und vorhersehbar. Sie sehen nicht aus wie die chaotischen, unregelmäßigen Probleme, die in der realen Welt vorkommen.
Die Alternative: Wissenschaftler könnten reale Probleme verwenden (wie etwa den Entwurf eines Automotors), aber diese sind teuer, geheim und schwer zu teilen.
Das Ziel: Wir brauchen einen Weg, um automatisch neue, einzigartige „Strecken“ zu bauen, die gerade schwierig genug sind, um den Unterschied zwischen zwei Algorithmen aufzuzeigen.

2. Die Lösung: Der „KI-Architekt“

Die Autoren entwickelten ein System namens LLM-EBG.

Der Architekt (Das LLM): Sie haben ein Large Language Model (wie die KI, mit der Sie vielleicht chatten) verwendet, nicht um Geschichten zu schreiben, sondern um als „genetischen Operator“ zu fungieren. Stellen Sie sich das LLM wie einen kreativen Architekten vor, der neue Baupläne für Mathematikprobleme zeichnen kann.
Die Evolution: Das System zeichnet nicht einfach nur einen Bauplan und hört dann auf. Es durchläuft einen „evolutionären“ Prozess:
1. Generierung: Der KI-Architekt zeichnet eine Gruppe neuer Mathematikprobleme.
2. Das Rennen: Zwei verschiedene Algorithmen (GA und DE) versuchen, diese Probleme zu lösen.
3. Selektion: Das System prüft, wer gewonnen hat. Wenn der KI-Architekt ein Problem erstellt hat, bei dem der „Ziel“-Algorithmus (z. B. GA) leicht gewonnen hat, wird dieses Problem behalten. Wenn der „Ziel“-Algorithmus verloren hat, wird das Problem verworfen oder verändert.
4. Mutation & Crossover: Die KI nimmt die gewinnenden Probleme und „paart“ sie miteinander. Sie kann Teile von zwei Problemen zusammenführen (Crossover) oder eine Zahl in einer Formel leicht verändern (Mutation), um die nächste Generation von Problemen noch besser darin zu machen, die Unterschiede hervorzuheben.

3. Das Experiment: Das „GA gegen DE“-Duell

Die Forscher testeten dieses System mit zwei spezifischen Algorithmen:

GA (Genetischer Algorithmus): Wie ein Team von Entdeckern, die sich weitläufig ausbreiten, um ein großes Gebiet zu durchsuchen.
DE (Differentielle Evolution): Wie eine Gruppe von Wanderern, die sehr schnell dem steilsten Pfad bergab folgen.

Sie baten die KI, zwei Arten von Strecken zu erstellen:

GA-freundliche Strecken: Probleme, bei denen die „Entdecker“ (GA) gewinnen sollten, weil das Gelände schwierig ist und eine breite Suche erfordert.
DE-freundliche Strecken: Probleme, bei denen die „Wanderer“ (DE) gewinnen sollten, weil der Pfad glatt und steil ist.

4. Die Ergebnisse: Die KI hat es richtig gemacht

Das System war überraschend erfolgreich:

Erfolgsrate: In 8 von 10 Versuchen, eine „GA-freundliche“ Strecke zu erstellen, schlug der GA den DE konsistent. In 9 von 10 Versuchen, eine „DE-freundliche“ Strecke zu erstellen, schlug der DE den GA.
Das „Warum“: Die Forscher analysierten die Mathematikprobleme, die die KI erstellt hatte.
- Die GA-freundlichen Probleme waren wie ein zerklüftetes, unebenes Gelände, bei dem die Größe der Schritte entscheidend war (variable Skalierung). Die „Entdecker“ waren gut darin, mit diesem Chaos umzugehen.
- Die DE-freundlichen Probleme waren glatter und konsistenter, was es den „Wanderern“ ermöglichte, direkt ins Ziel zu sausen.

5. Wie die KI „denkt“

Die Forscher beobachteten, wie der KI-Architekt die Probleme im Laufe der Zeit veränderte:

Für DE-freundliche Probleme: Die KI nahm meist nur kleine, vorsichtige Anpassungen vor (Mutationen), indem sie eine einzelne Zeile Code Schritt für Schritt verfeinerte.
Für GA-freundliche Probleme: Die KI mischte und kombinierte Teile verschiedener Probleme (Crossover) und vereinte Ideen aus verschiedenen „Eltern“, um etwas Neues und Komplexes zu erschaffen.

Das Faz-it

Dieses Paper zeigt, dass wir eine intelligente KI nutzen können, um automatisch neue, herausfordernde Mathematikprobleme zu erfinden, die die Stärken und Schwächen verschiedener Computer-Algorithmen perfekt offenlegen. Anstatt uns auf alte, statische Tests zu verlassen, können wir nun maßgeschneiderte „Rennstrecken“ entwickeln, die uns genau sagen, welcher Algorithmus der beste Läufer für ein bestimmtes Gelände ist.

Technische Zusammenfassung: Ein evolutionärer Rahmen zur automatischen Generierung von Optimierungs-Benchmarks mittels Large Language Models

Problemstellung
Optimierungs-Benchmarks sind essenziell für die Bewertung der Leistungsfähigkeit von Algorithmen, doch bestehende Ansätze stehen vor erheblichen Einschränkungen. Konventionelle künstliche Benchmarks (z. B. COCO, CEC-Suites) stützen sich auf vordefinierte mathematische Formulierungen, die oft nicht in der Lage sind, die Heterogenität und Unregelmäßigkeit realer Problemstrukturen abzubilden. Umgekehrt sind Benchmarks, die aus realen Anwendungen abgeleitet werden, häufig kostspielig in der Konstruktion, schwer reproduzierbar und durch Vertraulichkeit eingeschränkt. Zwar existieren Methoden zur automatischen Benchmark-Generierung, diese hängen jedoch typischerweise von vordefinierten parametrischen Generatoren oder baumbasierten symbolischen Repräsentationen (z. B. genetische Programmierung) ab, welche die Diversität und Ausdrucksstärke der generierten Problemlandschaften einschränken. Es besteht ein Bedarf an einem Framework, das automatisch diverse, reproduzierbare Benchmark-Instanzen mit spezifischen strukturellen Merkmalen generiert, ohne auf starre, vorgegebene Templates angewiesen zu sein.

Methodik: LLM-EBG
Die Autoren schlagen den LLM-driven Evolutionary Benchmark Generator (LLM-EBG) vor, ein Framework, das Evolutionäre Algorithmen (EAs) mit Large Language Models (LLMs) integriert, um Benchmark-Probleme zu evolvieren.

Repräsentation: Benchmark-Probleme werden als textbasierte symbolische mathematische Ausdrücke (Python-Code) für unbeschränkte, eindimensionale kontinuierliche Minimierung dargestellt.
Evolutionärer Prozess: Das Framework behandelt Benchmark-Probleme als Individuen einer evolutionären Population. Das LLM dient als generativer Operator für Initialisierung, Crossover und Mutation, gesteuert durch Prompt Engineering.
- Initialisierung: Eine initiale Population wird mittels einer Seed-Funktion und Few-Shot-Prompting generiert, wobei das LLM auf bestehende Benchmarks konditioniert wird, um strukturelle Ähnlichkeiten zu induzieren und gleichzeitig neue Komponenten einzuführen.
- Crossover: Zwei Eltern-Benchmarks werden dem LLM als In-Context-Beispiele bereitgestellt, woraufhin es angewiesen wird, ein neues Problem zu generieren, das die strukturellen Komponenten beider Eltern kombiniert.
- Mutation: Ein einzelner Eltern-Benchmark wird bereitgestellt, und das LLM wird angewiesen, den Ausdruck strukturell zu modifizieren (z. B. durch Änderung von Konstanten, Substitution von Funktionen oder Hinzufügen von Termen).
Prompting-Strategie: Das System nutzt Few-Shot-Prompting mit einem strikten Ausgabeformat (einzeiliger Python-Code), um die syntaktische Validität sicherzustellen. Der Prompt definiert explizit die angestrebte Leistungsbeziehung (z. B. „Erstelle ein Problem, bei dem Algorithmus A1 den Algorithmus A2 übertrifft“).
Evaluationsfunktion: Die Fitness eines generierten Benchmarks wird durch die relative Leistung zweier Zielalgorithmen (eines Genetischen Algorithmus [GA] und einer Differential Evolution [DE]) über $T$ Versuche bestimmt. Die Fitnessfunktion minimiert den normalisierten Rang der Leistung des Zielalgorithmus im Verhältnis zum Vergleichsalgorithmus. Sie enthält einen Strafterm, um zu verhindern, dass das Optimum gegen minus Unendlich divergiert, und bestraft Benchmarks, die ungültige (z. B. komplexe oder unendliche) Werte erzeugen.
Validierung: Ein Vorvalidierungsschritt stellt sicher, dass die generierten Ausdrücke für zufällig beprobte Designvariablen gültige reelle Ausgaben liefern, bevor sie in die Population aufgenommen werden.

Wesentliche Beiträge

Neuartiges Framework: Die Einführung von LLM-EBG, welches LLMs als evolutionäre Operatoren nutzt, um direkt in einem Raum symbolischer Ausdrücke zu suchen und damit über die Beschränkungen vordefinierter parametrischer Generatoren hinauszugehen.
Algorithmenspezifische Benchmark-Generierung: Die erfolgreiche Demonstration der Generierung von Benchmarks, die signifikante Leistungsunterschiede zwischen GA und DE induzieren. Das Framework kann systematisch Probleme entwickeln, in denen GA DE konsistent übertrifft und umgekehrt.
Strukturanalyse: Die Anwendung der Exploratory Landscape Analysis (ELA), um die generierten Benchmarks zu charakterisieren. Die Studie zeigt, dass GA-bevorzugte Benchmarks eine hohe Sensitivität gegenüber der Skalierung der Variablen (Ill-Conditioning) aufweisen, während DE-bevorzugte Benchmarks moderatere Krümmungsunterschiede zeigen.
Evolutionäre Dynamik: Eine Analyse des Operator-Verhaltens des LLMs, die zeigt, dass die Mutation (insbesondere die Einführung neuartiger symbolischer Terme) entscheidend ist, um lokale Optima zu verlassen, während Crossover die Kombination partieller Strukturen erleichtert.

Experimentelle Ergebnisse
Das Framework wurde in zwei Szenarien getestet: „GA-preferred“ und „DE-preferred“ Suche, jeweils mit 10 unabhängigen Versuchen.

Erfolgsrate: LLM-EBG generierte erfolgreich Benchmarks, in denen der bezeichnete Zielalgorithmus den Vergleichsalgorithmus in mehr als 80 % der Versuche übertraf. Speziell wurde die theoretische minimale Fitness (was perfekte Dominanz anzeigt) in 8 von 10 GA-bevorzugten Versuchen und in 9 von 10 DE-bevorzugten Versuchen erreicht.
Landschaftscharakteristika:
- GA-bevorzugte Benchmarks wiesen eine hohe Sensitivität gegenüber der Skalierung der Variablen auf, charakterisiert durch starke Anisotropie und ill-conditioned Landschaften (ähnlich wie BBOB10 und BBOB11). Diese Landschaften begünstigen die Fähigkeit des GA, die Populationsdiversität aufrechtzuerhalten.
- DE-bevorzugte Benchmarks zeigten eine geringere Sensitivität gegenüber der Skalierung der Variablen und glattere Landschaften, was es der DE ermöglicht, relative Positionsunterschiede effektiv zu nutzen.
Suchverhalten: Bei GA-bevorzugten Benchmarks neigte DE dazu, vorzeitig in lokalen Optima zu konvergieren, während GA Robustheit bewahrte. Umgekehrt konvergierte DE bei DE-bevorzugten Benchmarks schnell zu nahezu optimalen Lösungen, während GA mit multiplen lokalen Optima zu kämpfen hatte.
Operator-Nutzung: Die DE-bevorzugte Suche verließ sich stärker auf Mutationsoperationen (eine um 6,9 % niedrigere Crossover-Rate als die GA-bevorzugte Suche), was darauf hindeutet, dass lokale strukturelle Modifikationen effektiver für die Entwicklung von DE-begünstigenden Landschaften sind. Die GA-bevorzugte Suche nutzte Crossover und Mutation in nahezu gleicher Häufigkeit.

Bedeutung und Ansprüche
Das Paper behauptet, dass LLM-EBG eine fundiertere und zuverlässigere Methodik zur automatischen Benchmark-Generierung im Vergleich zu bestehenden Ansätzen etabliert. Indem das LLM als evolutionärer Operator behandelt wird, kann das Framework einen flexiblen, expressiven Repräsentationsraum explorieren, um Probleme mit distinkten geometrischen Charakteristika zu generieren, die das intrinsische Suchverhalten unterschiedlicher Optimierungsalgorithmen widerspiegeln.

Die Autoren betonen, dass das Framework die Limitationen künstlicher Benchmarks (Mangel an Diversität) und realer Benchmarks (Kosten und Reproduzierbarkeit) erfolgreich adressiert, indem es reproduzierbare, mathematisch definierte Probleme erzeugt, die bestimmte algorithmische Mechanismen gezielt herausfordern oder begünstigen. Die Studie kommt zu dem Schluss, dass LLM-EBG in der Lage ist, zentrale geometrische Eigenschaften wie Anisotropie und Ill-Conditioning, die die Suchverhaltensweisen von evolutionären Algorithmen differenzieren, automatisch zu identifizieren und zu verstärken. Als zukünftige Arbeit wird die Erweiterung des Frameworks auf eingeschränkte (constrained) und Multi-Objective-Optimierung sowie auf eine breitere Palette von Algorithmen vorgeschlagen.