Large Language Model Assisted Automated Algorithm Generation and Evolution via Meta-black-box optimization

Dit paper introduceert AwesomeDE, een door grote taalmodellen aangedreven methode voor het automatisch genereren en evolueren van geconstrueerde evolutionaire optimalisatie-algoritmen, die via het $RTO^2H$-kader voor promptontwerp superieure prestaties en generalisatie toont ten opzichte van bestaande methoden.

De kern

De Slimme Architect: Hoe een AI Zelf de Beste Bouwplannen Ontwerpt voor Moeilijke Puzzels

Stel je voor dat je een enorme, ingewikkelde puzzel moet oplossen. Maar dit is geen gewone puzzel; het is een beperkte puzzel. Je mag niet zomaar elke stukje ergens leggen. Er zijn strakke regels: "Deze hoek moet binnen de lijn blijven," "Dit stukje mag niet groter zijn dan 10 centimeter," en "Deze twee stukken mogen elkaar nooit raken." In de wereld van computerscience noemen we dit een geconstrueerd optimalisatieprobleem.

Vroeger moesten mensen (wiskundigen en ingenieurs) handmatig regels bedenken om deze puzzels op te lossen. Ze schreven algoritmen (rekenregels) op papier, probeerden ze, keken of het werkte, en pasten ze weer aan. Dit was als een timmerman die elke nieuwe deur zelf moet ontwerpen, meten en zagen, terwijl hij tegelijkertijd de muren in de gaten moet houden.

De Nieuwe Speler: De "Awesome" AI

In dit artikel presenteren de auteurs een nieuwe manier: AwesomeDE. Dit is een systeem dat een Groot Taalmodel (LLM) – denk aan een super-slimme AI zoals de voorloper van wat wij nu kennen – gebruikt om die bouwplannen (de algoritmen) zelf te ontwerpen.

Hier is hoe het werkt, vertaald naar alledaagse beelden:

1. De Meester-Architect (De LLM als Meta-Optimizer)

Stel je voor dat je een meester-architect hebt die nog nooit een huis heeft gebouwd, maar wel miljoenen boeken over architectuur heeft gelezen. In plaats van dat jij hem vertelt hoe hij een muur moet metselen, geef je hem een opdracht: "Ontwerp een methode om een huis te bouwen dat voldoet aan deze specifieke, gekke regels."

De AI (de LLM) denkt na, leest de regels, en schrijft een nieuw bouwplan (een update-regel). Dit plan vertelt de computer precies hoe hij de puzzelstukjes moet verplaatsen om dichter bij de oplossing te komen, zonder de regels te overtreden.

2. De Oefenhal (Meta-black-box optimalisatie)

Hoe leert de AI dit? Ze wordt niet zomaar ingeschakeld. Ze gaat naar een enorme oefenhal vol met verschillende soorten puzzels (de CEC2010 benchmark).

• De Oefening: De AI probeert een bouwplan te maken.
• De Test: Ze past dit plan toe op een puzzel. Lukt het? Breekt ze de regels?
• De Feedback: Als het plan faalt, krijgt de AI een "rood briefje" met uitleg. Als het werkt, krijgt ze een "gouden sterretje".
• De Evolutie: De AI gebruikt deze feedback om haar volgende bouwplan te verbeteren. Ze leert van haar fouten, net zoals een kind dat leert fietsen door te vallen en weer op te staan.

Dit proces noemen ze Meta-black-box optimalisatie. Het is alsof je niet alleen de fiets rijdt, maar de AI leert hoe je het beste fietsen kunt leren.

3. De "RTO2H" Sjabloon (Het Recept)

Om ervoor te zorgen dat de AI niet in de war raakt, hebben de auteurs een speciaal sjabloon bedacht (de RTO2H framework). Dit is als een heel duidelijk recept voor een chef-kok.
Het recept zegt de AI precies:

• "Wie ben je?" (Je bent een architect).
• "Wat is de taak?" (Bouw een huis met deze regels).
• "Wat heb je gezien?" (Hier zijn de fouten van vorige pogingen).
• "Hoe moet je antwoorden?" (Geef me een stap-voor-stap plan).

Zonder dit recept zou de AI misschien praten over koken in plaats van bouwen. Met dit recept weet ze precies wat er van haar verwacht wordt.

4. Het Resultaat: Sneller en Slimmer

De auteurs hebben hun AI getest tegen de beste menselijke ontwerpers (bestaande algoritmen).

• Het Succes: De AI vond oplossingen voor puzzels waar de menselijke algoritmen volledig vastliepen (ze vonden geen enkel geldig antwoord).
• De Snelheid: Hoewel de AI even langzaam denkt als een mens (ze moet nadenken over het plan), is ze uiteindelijk sneller in het vinden van de oplossing omdat haar plannen zo slim zijn. Ze maakt minder fouten en hoeft minder vaak terug te gaan.
• De Veiligheid: De AI houdt zich strikt aan de regels. Ze bouwt geen huizen die instorten of buiten de lijn vallen.

Waarom is dit belangrijk?

Vroeger moesten experts jarenlang studeren om een goed algoritme voor een specifiek probleem te maken. Met AwesomeDE kan een computer dit nu zelf doen, zonder dat een mens hoeft in te grijpen.

Het is alsof we zijn overgestapt van het handmatig zagen van elke plank, naar het hebben van een robot die zelf de perfecte zaagmachine ontwerpt voor elke nieuwe klus die je hebt.

Kort samengevat:
Deze paper laat zien dat we een slimme AI kunnen gebruiken als een "ontwerper van ontwerpers". In plaats van dat mensen regels schrijven voor computers, laten we de AI de regels schrijven voor zichzelf, zodat ze elke soort moeilijke, beperkte puzzel kan oplossen. Het is een enorme stap richting volledig geautomatiseerde, slimme probleemoplossing.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Large Language Model Assisted Automated Algorithm Generation and Evolution via Meta-black-box optimization", geschreven in het Nederlands.

Titel: Groot Taalmodel-ondersteunde Automatische Algoritmegeneratie en Evolutie via Meta-black-box optimalisatie

Auteurs: Xu Yang, Rui Wang, Kaiwen Li, Wenhua Li, en Weixiong Huang (National University of Defense Technology, China)

---

1. Het Probleem

Traditionele evolutionaire algoritmen (EA's) voor beperkte optimalisatieproblemen (COP's) vertrouwen vaak op handgemaakte zoekstrategieën en technieken voor het hanteren van beperkingen (zoals straf-functies). Deze handmatige benaderingen hebben vaak te kampen met:

• Gebrek aan aanpassingsvermogen: Ze presteren niet consistent over diverse probleemdomeinen.
• Menselijke interventie: Het ontwerpen van effectieve update-regels vereist expertkennis en veel tijd.
• Beperkte generalisatie: Bestaande machine learning-methoden voor COP's missen vaak flexibiliteit en interpreteerbaarheid.

Hoewel Grote Taalmodellen (LLM's) al succesvol zijn toegepast in onbeperkte optimalisatie, blijft hun toepassing op beperkte evolutionaire optimalisatie (CEO) onderbelicht, vooral wat betreft het automatisch genereren van algoritmen die strikt voldoen aan complexen beperkingen.

2. Methodologie

De auteurs stellen een nieuw raamwerk voor genaamd AwesomeDE (of llmEA), dat LLM's inzet als een "meta-optimizer" binnen een Meta-black-box optimalisatie (MetaBBO)-kader.

Kerncomponenten:

• Bi-niveau optimalisatie (MetaBBO):
  • Buitenste lus (Meta-training): De LLM fungeert als meta-optimizer. Deze analyseert historische optimalisatiegegevens en elite-update-regels om nieuwe, verbeterde update-regels voor evolutionaire algoritmen te genereren.
  • Binnenste lus (Algoritme-executie): De gegenereerde regels worden toegepast op een steekproef van COP's om de prestaties te evalueren. De feedback (succes/falen) wordt teruggevoerd naar de buitenste lus voor verdere verfijning.
• RTO2H Framework: Een gestructureerd raamwerk voor het ontwerpen van prompts voor de LLM. Een prompt bevat vijf essentiële onderdelen:
  1. Roldefinitie: De LLM fungeert als algoritmedesigner.
  2. Taakbeschrijving: Informatie over beslissingsvariabelen, beperkingsschendingen en objectivewaarden.
  3. Operationele eisen: Stappen voor het genereren van regels.
  4. Geschiedenisfeedback: Eerdere regels en hun prestaties.
  5. Outputformaat: Gestructureerde uitvoer voor extractie.
• Automatische Regelgeneratie: In plaats van dat de LLM direct oplossingen manipuleert, genereert het update-regels (F) die het evolutionaire proces sturen. Deze regels houden rekening met besluitvariabelen, objectieven en beperkingen, wat de interpreteerbaarheid vergroot.

3. Belangrijkste Bijdragen

1. Volledig geautomatiseerd ontwerp: Een data-gedreven methode die LLM's gebruikt om update-regels voor beperkte evolutionaire algoritmen te genereren zonder menselijke tussenkomst.
2. Verbeterde interpreteerbaarheid: Door het genereren van expliciete update-regels in plaats van "zwarte doos" zoekoperatoren, wordt het proces transparanter.
3. Empirische validatie: Uitgebreide experimenten tonen aan dat de methode superieur presteert ten opzichte van bestaande handontworpen methoden in termen van rekenefficiëntie en oplossingsnauwkeurigheid.
4. Generalisatie: Het bewijs dat LLM's in staat zijn om principes te leren die zowel de beperkingen respecteren als de evolutionaire effectiviteit behouden.

4. Resultaten

De methode is getest op de CEC2010 benchmark-suite (18 schaalbare COP's) met dimensies van 10 en 30, vergeleken met algoritmen zoals DE, LSHADE, IMODE en SHADE.

• Prestaties:
  • llmEA behaalde de beste resultaten op 6 van de 18 benchmark-functies (C02, C09, C14-C18).
  • Voor de moeilijkste problemen (C16-C18) werden de gemiddelde minimale waarden met 55,1% tot 96,5% verbeterd ten opzichte van de tweede beste methode.
  • Robuustheid: llmEA vond voor 66,7% van de testfuncties een haalbare oplossing, terwijl concurrenten dit slechts in 33,3% tot 50% van de gevallen deden. Veel concurrenten faalden volledig (NaN-resultaten) op complexe functies waar llmEA wel slaagde.
• Rekenefficiëntie:
  • Ondanks de extra complexiteit van de LLM, is de rekentijd slechts 12,8% tot 34,7% hoger dan de basis-DE.
  • De dynamische beperkingenhantering reduceert onnodige fitness-evaluaties, wat leidt tot een efficiëntere doorlooptijd in vergelijking met zwaardere methoden zoals MadDE en LSHADE.
• Stabiliteit: De standaardafwijkingen van llmEA waren aanzienlijk lager (tot 78,9% reductie) dan bij traditionele methoden, wat wijst op stabielere convergentiepatronen.

5. Betekenis en Toekomstperspectief

Dit onderzoek markeert een verschuiving in het veld van evolutionaire optimalisatie door te bewijzen dat LLM's niet alleen als zoekoperatoren kunnen dienen, maar als architecten van algoritmen zelf.

• Impact: Het biedt een schaalbare, datagedreven aanpak voor het ontwerpen van algoritmen die specifiek zijn afgestemd op complexe beperkingen, wat essentieel is voor real-world engineeringproblemen.
• Beperkingen:
  • De invoerlimieten van LLM's beperken de toepasbaarheid op zeer grote schaalproblemen (hoge dimensies).
  • De generalisatie over domeinen heen is nog beperkt door de gebruikte EA-based meta-learning.
• Toekomst: De auteurs suggereren het gebruik van "sparse attention" mechanismen voor schaalbaarheid en het integreren van transfer learning om de generalisatie te verbeteren. Het raamwerk is ook open voor uitbreiding naar multi-objectieve en dynamische COP's.

Conclusie: AwesomeDE/llmEA demonstreert dat geautomatiseerd algoritmedesign via LLM's een krachtige, reproduceerbare en superieure alternatief is voor handmatige ontwerpmethodieken in het domein van beperkte optimalisatie.