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

Technische Samenvatting: Een Evolutionair Raamwerk voor Automatische Generatie van Optimalisatie-benchmarks via Large Language Models

Probleemstelling
Optimalisatie-benchmarks zijn essentieel voor het evalueren van algoritmische prestaties, maar bestaande benaderingen kampen met aanzienlijke beperkingen. Conventionele kunstmatige benchmarks (bijv. COCO, CEC-suites) vertrouwen op vooraf gedefinieerde wiskundige formuleringen die vaak er niet in slagen de heterogeniteit en onregelmatigheid van real-world probleemstructuren te vatten. Daarentegen zijn benchmarks afgeleid van real-world toepassingen vaak kostbaar om te construeren, moeilijk te reproduceren en beperkt door vertrouwelijkheid. Hoewel methoden voor automatische benchmarkgeneratie bestaan, zijn deze doorgaans afhankelijk van vooraf gedefinieerde parametrische generatoren of boomgebaseerde symbolische representaties (bijv. genetische programmering), wat de diversiteit en expressiviteit van de gegenereerde probleemlandschappen beperkt. Er is behoefte aan een raamwerk dat automatisch diverse, reproduceerbare benchmark-instanties kan genereren met specifieke structurele kenmerken zonder afhankelijk te zijn van rigide, vooraf gespecificeerde sjablonen.

Methodologie: LLM-EBG
De auteurs stellen de LLM-driven Evolutionary Benchmark Generator (LLM-EBG) voor, een raamwerk dat Evolutionaire Algoritmen (EA's) integreert met Large Language Models (LLM's) om benchmarkproblemen te evolueren.

• Representatie: Benchmarkproblemen worden gerepresenteerd als tekstgebaseerde symbolische wiskundige expressies (Python-code) voor onbeperkte single-objective continue minimalisatie.
• Evolutionair Proces: Het raamwerk behandelt benchmarkproblemen als individuen in een evolutionaire populatie. De LLM dient als de generatieve operator voor initialisatie, crossover en mutatie, gestuurd door prompt engineering.
  • Initialisatie: Een initiële populatie wordt gegenereerd met behulp van een seed-functie en few-shot prompting, waarbij de LLM wordt geconditioneerd op bestaande benchmarks om structurele gelijkenis te induceren terwijl nieuwe componenten worden geïntroduceerd.
  • Crossover: Twee ouder-benchmarks worden aan de LLM verstrekt als in-context voorbeelden, waarna de LLM de instructie krijgt om een nieuw probleem te genereren dat de structurele componenten van beide ouders combineert.
  • Mutatie: Een enkele ouder wordt verstrekt, en de LLM krijgt de instructie om de expressie structureel te modificeren (bijv. het veranderen van constanten, het substitueren van functies of het toevoegen van termen).
• Prompting Strategie: Het systeem gebruikt few-shot prompting met een strikte output-formaat (single-line Python-code) om syntactische validiteit te waarborgen. De prompt definieert expliciet de beoogde prestatierelatie (bijv. "Creëer een probleem waarbij Algoritme A1 beter presteert dan Algoritme A2").
• Evaluatiefunctie: De fitness van een gegenereerde benchmark wordt bepaald door de relatieve prestaties van twee doelalgoritmen (een Genetic Algorithm [GA] en Differential Evolution [DE]) over $T$ proeven. De fitnessfunctie minimaliseert de genormaliseerde rang van de prestaties van het doelalgoritme ten opzichte van het vergelijkende algoritme. Het bevat een strafterm om te voorkomen dat de optimale oplossing naar negatief oneindig divergeert en straft benchmarks af die ongeldige (bijv. complexe of oneindige) waarden produceren.
• Validatie: Een pre-validatiestap zorgt ervoor dat gegenereerde expressies geldige reële outputs produceren voor willekeurig gesamplede ontwerpvariabelen voordat ze aan de populatie worden toegevoegd.

Belangrijkste Bijdragen

1. Nieuw Raamwerk: De introductie van LLM-EBG, die LLM's gebruikt als evolutionaire operatoren om direct in een symbolische expressieruimte te zoeken, waarmee de beperkingen van vooraf gedefinieerde parametrische generatoren worden overstegen.
2. Algoritme-specifieke Benchmarkgeneratie: De succesvolle demonstratie van het genereren van benchmarks die significante prestatieverschillen induceren tussen GA en DE. Het raamwerk kan systematisch problemen evolueren waarbij GA consequent beter presteert dan DE, en vice versa.
3. Structurele Analyse: De toepassing van Exploratory Landscape Analysis (ELA) om de gegenereerde benchmarks te karakteriseren. De studie laat zien dat GA-bevoordeelde benchmarks een hoge gevoeligheid voor variabele schaling (ill-conditioning) vertonen, terwijl DE-bevoordeelde benchmarks een meer gematigde kromming-dispariteit laten zien.
4. Evolutionaire Dynamiek: Een analyse van het operatorgedrag van de LLM, die aantoont dat mutatie (met name de introductie van nieuwe symbolische termen) cruciaal is om lokale optima te ontsnappen, terwijl crossover helpt bij het combineren van gedeeltelijke structuren.

Experimentele Resultaten
Het raamwerk werd getest in twee scenario's: "GA-preferred" en "DE-preferred" zoekopdrachten, met 10 onafhankelijke proeven voor elk.

• Succespercentage: LLM-EBG genereerde succesvol benchmarks waarbij het aangewezen doelalgoritme het vergelijkende algoritme in meer dan 80% van de proeven versloeg. Specifiek werd de theoretische minimale fitness (wat duidt op perfecte dominantie) bereikt in 8 van de 10 GA-preferred proeven en 9 van de 10 DE-preferred proeven.
• Landschapskenmerken:
  • GA-preferred benchmarks bleken zeer gevoelig voor variabele schaling, gekenmerkt door sterke anisotropie en ill-conditioned landschappen (vergelijkbaar met BBOB10 en BBOB11). Deze landschappen bevoordelen het vermogen van GA om populatiediversiteit te behouden.
  • DE-preferred benchmarks vertoonden een lagere gevoeligheid voor variabele schaling en gladdere landschappen, waardoor DE effectief relatieve positionele verschillen kon exploiteren.
• Zoekgedrag: Op GA-preferred benchmarks had DE de neiging om voortijdig te convergeren naar lokale optima, terwijl GA robuustheid behield. Omgekeerd, op DE-preferred benchmarks convergeerde DE snel naar bijna-optimale oplossingen, terwijl GA worstelde met meerdere lokale optima.
• Operatorgebruik: De DE-preferred zoekopdracht vertrouwde zwaarder op mutatie-operaties (6,9% lager crossover-ratio dan GA-preferred), wat suggereert dat lokale structurele modificaties effectiever zijn voor het evolueren van DE-bevoordeelde landschappen. De GA-preferred zoekopdracht maakte gebruik van crossover en mutatie met bijna gelijke frequenties.

Betekenis en Claims
Het artikel claimt dat LLM-EBG een meer principiële en betrouwbare methodologie voor automatische benchmarkgeneratie vestigt vergeleken met bestaande benaderingen. Door de LLM als een evolutionaire operator te behandelen, kan het raamwerk een flexibele, expressieve representatieruimte verkennen om problemen te genereren met onderscheidende geometrische kenmerken die de intrinsieke zoekgedragingen van verschillende optimalisatiealgoritmen reflecteren.

De auteurs stellen dat het raamwerk succesvol de beperkingen van kunstmatige benchmarks (gebrek aan diversiteit) en real-world benchmarks (kosten en reproduceerbaarheid) aanpakt door reproduceerbare, wiskundig gedefinieerde problemen te produceren die specifiek bepaalde algoritmische mechanismen uitdagen of bevoordelen. De studie concludeert dat LLM-EBG automatisch sleutelgeometrische eigenschappen kan identificeren en versterken, zoals anisotropie en ill-conditioning, die de zoekgedragingen van evolutionaire algoritmen differentiëren. Toekomstig werk wordt voorgesteld om het raamwerk uit te breiden naar constrained en multi-objective optimalisatie en een breder scala aan algoritmen.