LLM Driven Design of Continuous Optimization Problems with Controllable High-level Properties

Technische Samenvatting: LLM-gestuurd Ontwerp van Continue Optimalisatieproblemen met Controleerbare High-level Eigenschappen

Probleemstelling
Het benchmarken in continue black-box optimalisatie wordt momenteel belemmerd door de beperkte structurele diversiteit van bestaande testsuites, zoals de BBOB (Black-Box Optimization Benchmarking) suite. Zoals eerder is opgemerkt, dekken deze suites vaak slechts smalle regio's van de probleemruimte, wat de generalisatie van Automated Algorithm Selection (AAS) modellen beperkt en de evaluatie sterk afhankelijk maakt van data-splits. Hoewel eerdere pogingen om nieuwe problemen te genereren—zoals affine combinaties van bestaande functies of willekeurige tree-gebaseerde generatoren—zijn voorgesteld, bieden deze ofwel beperkte nieuwheid, of ontbreeft het hen aan het vermogen om specifieke high-level landschapseigenschappen te controleren. Dit artikel onderzoekt of Large Language Models (LLMs), ingebed in een evolutionaire loop, gebruikt kunnen worden om automatisch optimalisatieproblemen te synthetiseren die duidelijke, interpreteerbare high-level landschapskenmerken vertonen.

Methodologie
De auteurs stellen een framework voor dat LLaMEA (Large Language Model–driven Evolutionary Algorithm) uitbreidt, oorspronkelijk ontworpen voor algoritme-generatie, naar het domein van probleemgeneratie. De methodologie volgt een driestappenproces:

1. Definitie van het Feature Model:
   De auteurs richten zich op vijf high-level eigenschappen afgeleid van Exploratory Landscape Analysis (ELA): multimodaliteit, separabiliteit, homogeniteit van bekken-grootte (basin-size homogeneity), homogeniteit van de zoekruimte en contrast tussen globaal en lokaal optimum. Machine learning-modellen (specifiek XGBoost regressoren) worden getraind op de BBOB-dataset om deze eigenschappen te voorspellen op basis van ELA-features geëxtraheerd uit Latin hypercube-stalen. Voor separabiliteit wordt een directe numerieke test gebruikt met behulp van eindverschil-schattingen van variabelen-interacties in plaats van een voorspellend model.

2. LLM Probleemgeneratie:
   Het LLaMEA-framework evolueert uitvoerbare Python-code die optimalisatiefuncties representeert. Het LLM (specifiek werd gpt5-nano geselecteerd vanwege de balans tussen prestaties en efficiëntie) ontvangt natuurlijke taal-prompts die de doeleigenschappen beschrijven.

   • Fitness Evaluatie: Gegenereerde kandidaten worden gescoord door de getrainde eigenschapsvoorspellingsmodellen.
   • Diversiteitsmechanisme: Om te voorkomen dat de populatie convergeert naar redundante landschappen, introduceren de auteurs een ELA-ruimte fitness-sharing mechanisme. Dit past de fitness van een individu aan op basis van de dichtheid in de ELA-feature-ruimte (gebruikmakend van z-gestandaardiseerde Manhattan-afstanden), waarbij oplossingen die te veel op anderen lijken worden bestraft en exploratie van diverse geometrische structuren wordt aangemoedigd. Een adaptieve niche-radius zorgt voor robuustheid over de generaties heen.

3. Eigenschapsverificatie:
   Omdat de voorspellende modellen benaderingen zijn, wordt een rigoureuze verificatiestap toegepast. Dit omvat een basin-of-attraction analyse (iteratief zoeken naar verbeterende paden om lokale optima en bekken-groottes te identificeren) en statistische toetsing. Deze stap is computationeel duur en wordt primair toegepast op 2D-instanties om te bevestigen dat de gegenereerde functies daadwerkelijk de beoogde structurele kenmerken vertonen.

Belangrijkste Bijdragen

• Eerste LLM-gestuurde Probleemsynthese: Dit werk presenteert de eerste use case van LLM-gestuurde evolutionaire computatie voor de automatische synthese van optimalisatieproblemen met vooraf gespecificeerde high-level eigenschappen, waarmee de stap wordt gezet van de generatie van solvers naar de generatie van probleeminstanties.
• Adaptieve Fitness Sharing: Het artikel breidt het LLaMEA-framework uit met een nieuw fitness-sharing mechanisme dat opereert in de ELA-feature-ruimte om diversiteit tussen gegenereerde landschappen te bevorderen.
• Verificatieframework: De auteurs stellen een veelzijdige verificatieaanpak voor en passen deze toe, waarbij voorspellende modellering, basin-of-attraction analyse en visuele inspectie worden gecombineerd om de structurele integriteit van gegenereerde problemen te valideren.
• Open Library: Het resultaat is een reproduceerbare, interpreteerbare bibliotheek van benchmarkproblemen met specifieke high-level eigenschappen, beschikbaar gesteld als een Python-bibliotheek.

Resultaten

• Modelselectie: Voorlopige experimenten vergeleken vijf LLMs. gpt5-nano behaalde de hoogste succesratio (98,7%) voor het genereren van problemen met specifieke combinatie van eigenschappen (bijv. bekken-grootte homogeniteit en separabiliteit) en werd geselecteerd voor de hoofdstudie.
• Diversiteit: Het fitness-sharing mechanisme toonde aan de diversiteit van gegenereerde landschappen significant te verhogen. Distributies van nearest-neighbor afstanden in de ELA-ruimte verschoven naar grotere waarden wanneer fitness sharing actief was, wat bevestigt dat het mechanisme de generator succesvol wegstuurt van redundante oplossingen.
• Eigenschapsverificatie: Basin-of-attraction analyse bevestigde dat veel gegenereerde functies de beoogde kenmerken vertoinden. Zo bevatten problemen die geoptimaliseerd waren voor multimodaliteit consistent meerdere attractiebekkens, en problemen die geoptimaliseerd waren voor een hoog globaal-lokaal contrast vertoonden significante fitness-verschillen tussen het globale optimum en de lokale optima.
• Expansie van de Probleemruimte: Een t-SNE visualisatie van de gegenereerde problemen tegenover de BBOB-set demonstreerde dat de door LLM gegenereerde instanties de bestaande probleemruimte uitbreiden in plaats van een ongerelateerde cluster te vormen. Ze vullen hiaten in de feature-ruimte op, met name in regio's die ondervertegenwoordigd zijn in standaard benchmarks.

Betekenis en Claims
Het artikel claimt dat LLM-gestuurde probleemgeneratie een "veelbelovende en flexibele richting" is voor het creëren van interpreteerbare benchmarks. Door groepen ELA-features te koppelen aan kwalitatieve, menselijk leesbare beschrijvingen, maakt de aanpak de generatie van diverse en verifieerbare landschappen mogelijk zonder dat er expertise nodig is om numerieke feature-targets te selecteren. De resulterende bibliotheek biedt een brede set problemen die kunnen profiteren van landschapanalyse en downstream taken zoals automated algorithm selection. De auteurs merken bescheiden op dat hoewel de aanpak effectief is, toekomstig werk nodig is om het structureel te vergelijken met andere generatoren, de gevoeligheid voor de keuze van het LLM systematisch te onderzoeken, en te verifiëren of deze instanties de generalisatie van algoritme-selectors op ongeziene probleemsets verbeteren.