💻 computer science

A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees

A2DEPT is een nieuw raamwerk dat Large Language Models inzet als architecten op systeemniveau binnen een evolutionaire boomzoektocht naar programma's, gecombineerd met een feedbackgestuurde herstelmechanisme, om autonoom volledige, uitvoerbare algoritmen te synthetiseren voor combinatorische optimalisatieproblemen, waardoor de starre template-beperkingen van bestaande methoden worden overwonnen en superieure prestaties worden bereikt.

Oorspronkelijke auteurs: Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

Gepubliceerd 2026-04-28

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorm, complex puzzel moet oplossen, zoals het organiseren van een bezorgroute voor 1.000 vrachtwagens of het plannen van een fabriek met honderden machines. Dit zijn "Combinatorische Optimalisatieproblemen". Traditioneel moesten mensen neerzitten en handmatig de regels (heuristieken) ontwerpen om deze puzzels op te lossen. Dit was traag, vereiste diepgaande expertise, en de regels vielen vaak uit elkaar als het probleem ook maar iets veranderde.

Recentelijk zijn we begonnen met het gebruik van Large Language Models (LLM's) — dezelfde AI die essays en code schrijft — om bij te dragen aan het ontwerpen van deze regels. Echter, de meeste huidige methoden zijn als het geven van een Lego-set met een vast instructieboekje aan de AI. De AI kan een paar blokken verwisselen (een specifieke regel aanpassen), maar kan de algehele structuur van het kasteel niet veranderen. Als het boekje zegt "bouw een toren", kan de AI niet beslissen om in plaats daarvan een brug te bouwen, zelfs als een brug beter zou werken.

Maar dan komt A2DEPT.

De auteurs stellen een nieuw systeem voor genaamd A2DEPT (Automated Algorithm Design via Evolutionary Program Trees). In plaats van de AI een vast boekje te geven, laten ze het optreden als een hoofdarchitect die het hele gebouw van de grond af kan herontwerpen.

Hier is hoe het werkt, met behulp van eenvoudige analogieën:

1. De "Boom" van Ideeën

Stel je een stamboom voor, maar in plaats van mensen is het een boom van computerprogramma's.

De Wortels: Het proces begint met een paar basis, werkende programma's.
De Takken: De AI neemt een programma, maakt een verandering (een mutatie) en creëert een "kind"-programma.
De Selectie: Net als in de natuur zijn sommige kinderen beter in het oplossen van de puzzel dan hun ouders. Het systeem houdt de besten vast en probeert ze verder te verbeteren.

2. Het "Bouwteam" (De Drie Werknemers)

Om ervoor te zorgen dat de AI niet zomaar willekeurige, kapotte code maakt, gebruikt A2DEPT drie specifieke soorten "werknemers" om de programma's te bewerken:

De Klussert (Micro-tuning): Deze werknemer maakt kleine, veilige aanpassingen. Hij kan een getal aanpassen of een logische fout binnen een specifieke functie repareren, zoals het slijpen van een gereedschap. Hij verandert het blauwdruk niet.
De Architect (Macro-mutatie): Deze werknemer is stoutmoedig. Hij kan een muur neerhalen en een nieuwe kamer bouwen. Hij kan de hoofdstroom van het programma herschrijven, waardoor de manier waarop het algoritme denkt van begin tot eind verandert.
De Mixer (Crossover): Deze werknemer neemt de beste ideeën van twee verschillende "ouder"-programma's en smelt ze samen tot een hybride kind.

3. De "Veiligheidsinspecteur" (Programmaonderhoud)

Hier ligt de grootste uitdaging: wanneer je de AI een heel programma laat herontwerpen, creëert het vaak code die niet werkt. Het kan een functie aanroepen die niet bestaat of vergeten zijn een bibliotheek te importeren.

Het Probleem: In het verleden werd, als de code kapot ging, de hele poging weggegooid.
De A2DEPT-oplossing: Ze hebben een Veiligheidsinspecteur toegevoegd. Voordat de nieuwe code wordt getest, scant deze inspecteur deze. Als er een stukje ontbreekt (zoals een ontbrekende functie), vraagt de inspecteur de AI om dat ontbrekende stukje direct te schrijven. Als de code doodlopende straten heeft (delen die nooit worden gebruikt), snijdt de inspecteur ze weg.
Het Resultaat: Dit zorgt ervoor dat bijna elk nieuw idee dat de AI genereert daadwerkelijk uitvoerbaar is, waardoor het zoeken kan doorgaan zonder vast te lopen.

4. De "Slimme Filter" (Hybride Selectie)

Hoe beslist het systeem welke programma's bewaard moeten worden?

De "Voldoende Goed"-regel: Soms is een nieuw programma iets slechter dan het ouderprogramma, maar heeft het een unieke structuur die later tot een doorbraak kan leiden. A2DEPT gebruikt een slimme filter (gebaseerd op een methode genaamd Gesimuleerde Afkoeling) die deze "vele belovende maar momenteel slechtere" programma's laat overleven, waardoor het systeem niet vast komt te zitten in een lokaal dal.
De "Diversiteit"-regel: Het kiest ook willekeurig enkele oudere, interessante programma's uit de geschiedenisboom om het zoeken divers te houden, zodat ze er niet allemaal hetzelfde uitzien.

Wat Vonden Ze?

De auteurs testten A2DEPT op verschillende moeilijke puzzels (zoals het routeren van vrachtwagens, het plannen van banen en het vinden van patronen in grafieken).

Betere Resultaten: A2DEPT vond consequent betere oplossingen dan eerdere AI-methoden die vastzaten aan vaste sjablonen.
De Kloof: Op standaardtests verkleinde het de "kloof" tussen de oplossing van de AI en de perfecte oplossing met bijna 10% in vergelijking met de volgende beste methode.
Robuustheid: Het werkte goed, zelfs op zeer moeilijke problemen met veel strikte regels (zoals elektrische voertuigen met een beperkte batterij en krappe tijdvensters), waarbij andere methoden vaak faalden om enige geldige oplossing te vinden.

De Conclusie

A2DEPT is als het upgraden van een verf-op-nummers-set (waar je alleen de kleuren kunt veranderen) naar een volledige bouwplaats (waar je de muren, het dak en de fundering kunt veranderen). Door een slimme evolutionaire zoektocht te combineren met een "veiligheidsinspecteur" die kapotte code onderweg repareert, stelt het de AI in staat om geheel nieuwe manieren te bedenken om complexe problemen op te lossen, in plaats van alleen maar oude aan te passen.

1. Probleemdefinitie

Het artikel adresseert de uitdaging van Automated Heuristic Design (AHD) voor Combinatorial Optimization Problems (COPs).

Context: COPs (bijv. TSP, Vehicle Routing, Job Shop Scheduling) zijn doorgaans NP-hard. Traditioneel handmatig heuristisch ontwerp is arbeidsintensief, vereist diepgaande domeinexpertise en faalt vaak om te generaliseren over probleemvarianten heen.
Huidige beperkingen: Recente op Large Language Models (LLM's) gebaseerde AHD-methoden (bijv. FunSearch, EoH, ReEvo) hebben veelbelovend getoond, maar lijden onder een kritieke bottleneck: ze opereren binnen vaste algoritmische sjablonen. Ze optimaliseren alleen geïsoleerde heuristische componenten (zoals scorefuncties) terwijl de omringende solverlogica (besturingsflow, backtracking, iteratiestructuur) stijf blijft.
De kloof: Deze "sjabloongebonden" aanpak beperkt innovatie op systeemniveau. Als het sjabloon suboptimaal is voor een specifiek probleem, kan de heuristiek dit niet compenseren. Bovendien introduceert de overstap van het optimaliseren van een enkele component naar het ontwerpen van een complete solver (Open-ended Automated Algorithm Design, of AAD) enorme uitdagingen:
1. Instabiliteit van uitvoerbaarheid: Vrij-vormige codegeneratie leidt vaak tot compilatiefouten, ontbrekende afhankelijkheden of runtime-fouten.
2. Explosie van de zoekruimte: De ruimte van geldige, hoogpresterende complete programma's is enorm en schaars.
3. Onduidelijkheid in credit toewijzing: Het is moeilijk om prestatiewinst toe te schrijven aan specifieke codeveranderingen wanneer het volledige algoritme evolueert.

2. Methodologie: A2DEPT Framework

De auteurs stellen A2DEPT (Automated Algorithm Design via Evolutionary Program Trees) voor, een framework dat LLM's behandelt als architecten op systeemniveau om complete, uitvoerbare solverprogramma's te evolueren.

Kerncomponenten:

Boomgestructureerd evolutionair zoeken:
- In tegenstelling tot populatiegebaseerde methoden, onderhoudt A2DEPT een globale zoekboom waarbij knopen uitvoerbare programma's, hun scores en generatiemetadata vertegenwoordigen.
- Hybride selectiestrategie:
  - Primair selectie via Gesimuleerde Afkoeling (SA): Gebruikt het Metropolis-criterium om ouder-kindparen te accepteren op basis van scoreverbetering, waarbij een "ouder-kind verfijning"-relatie behouden blijft.
  - Supplementaire selectie via Boltzmann: Om te voorkomen dat het zoeken instort in een greedy top-k selectie en om diversiteit te behouden, steekt het systeem extra ouders uit de globale boomgeschiedenis met Boltzmann-kansen. Dit laat "onderpresterende maar structureel veelbelovende" takken overleven.
- Dynamische herafkoeling: Als het zoeken stagneert (geen verbetering gedurende $N_{stall}$ generaties), wordt de temperatuur verhoogd om de exploratiecapaciteit te herstellen.
Hiërarchische operatoren met adaptieve planning:
Om credit toewijzing aan te pakken en structurele veranderingen mogelijk te maken, gebruikt A2DEPT drie niveaus van operatoren, adaptief gepland op basis van feedback:
- Micro-tuning ( $m_1$ ): Lokale bewerkingen aan mutabele strategiefuncties (bijv. het verfijnen van een scoreformule) terwijl interfaces behouden blijven.
- Macro-mutatie ( $m_2$ ): Top-down herontwerp van het startpunt en de besturingsflow van de solver. Het stelt de LLM in staat om ongedefinieerde helperfuncties aan te roepen, die later worden ingevuld.
- Semantische crossover ( $e_1$ ): Synthetiseert een hybride programma door complementaire mechanismen uit twee ouders te integreren.
- Adaptieve planning: Een knop-specifiek gewichtvector wordt bijgewerkt op basis van de prestatieverandering ( $\bar{r}$ ) van het kind. Succesvolle operatoren worden versterkt, terwijl ongeslaagde operatoren worden gestraft, waardoor de zoeksinspanning dynamisch verschuift tussen micro-verfijning en macro-herstucturering.
Programma-onderhoudsmechanisme (Handhaving van uitvoerbaarheid):
Om open-ended generatie praktisch te maken, bevat A2DEPT een lichtgewicht, feedback-gedreven reparatielus:
- Gestructureerde representatie: Programma's worden opgesplitst in een immuut "Voorwoord" (imports, constanten) en een mutabele "Functieregister".
- Afhankelijkheidsreparatie: Wanneer een gegenereerd programma ongedefinieerde functies aanroept (vaak bij macro-mutatie), wordt een afhankelijkheidsgrafiek gebouwd. De LLM wordt iteratief geprompt om ontbrekende functies te implementeren totdat het programma "afhankelijkheidsgesloten" is.
- Uitsnijden: Onbereikbare code wordt verwijderd om accumulatie van dode logica te voorkomen.

3. Belangrijkste bijdragen

Paradigmaverschuiving: Verschuiving van sjabloongebonden AHD (optimaliseren van componenten) naar Open-ended AAD (evolueren van complete solvers), waardoor een rijker ontwerpruimte wordt ontsloten.
A2DEPT Framework: Introduceert een boomgestructureerd evolutionair zoeken met hybride selectie (SA + Boltzmann) en hiërarchische operatoren om de enorme programmaruimte te navigeren.
Betrouwbaarheidsmechanismen: Stelt een programma-onderhoudslus voor voor geautomatiseerde afhankelijkheidsreparatie en een gestructureerde representatie om uitvoerbaarheid tijdens evolutie te waarborgen.
Empirische validatie: Toont consistente superioriteit ten opzichte van state-of-the-art LLM-based baselines over diverse NP-hard benchmarks.

4. Experimentele resultaten

De auteurs evalueerden A2DEPT op zes NP-hard problemen: MIS, CVRP, CFLP, FJSP (standaard benchmarks) en CEVRPTW, MRCPSP (hoge-beperking benchmarks).

Prestaties op standaard benchmarks:
- A2DEPT presteerde beter dan alle LLM-based baselines (FunSearch, EoH, ReEvo, MCTS-AHD) op elke taak.
- Belangrijke metriek: Op standaard benchmarks verlaagde A2DEPT de gemiddelde genormaliseerde optimaliteitsgap met 9,8% ten opzichte van de sterkste concurrerende AHD-baseline.
- Het behaalde concurrerende resultaten ten opzichte van niet-LLM referenties (bijv. het evenaren van Gurobi op MIS).
Problemen met hoge beperkingen:
- Op CEVRPTW en MRCPSP behaalde A2DEPT de laagste Infeasibility Rate (IR) en beste optimaliteitsgaps, wat robuustheid aantoont in gefragmenteerde zoekruimtes waar andere methoden vaak falen om geldige oplossingen te vinden.
Generalisatie:
- A2DEPT toonde sterke generalisatie over verschillende ontwerpfraamworks (bijv. Guided Local Search) en instantieverdelingen.
- Ablatiestudies bevestigden dat het verwijderen van een component (bijv. Boltzmann-sampling, adaptieve planning, of de onderhoudslus) de prestaties aanzienlijk verslechterde.
Continue optimalisatie:
- Het framework werd ook succesvol toegepast op continue domeinen (ODE-oplossing, wortelvinding, controlebeleid), waarbij nieuwe numerieke solvers werden ontdekt die gespecialiseerde industriële baselines (bijv. LSODA) op stijve problemen overtroffen.

5. Betekenis en Impact

Innovatie op systeemniveau: A2DEPT bewijst dat LLM's kunnen fungeren als "algoritme-architecten", niet alleen als code-generators. Door de volledige solverlogica te evolueren, kan het structurele paradigma's ontdekken (bijv. verschuiven van een constructieve greedy heuristiek naar een Iterated Local Search framework) die component-niveau tuning niet kan bereiken.
Schaalbaarheid: Het framework adresseert de "uitvoerbaarheid"-bottleneck van open-ended codegeneratie, waardoor het haalbaar wordt om complexe, multi-module programma's te evolueren zonder menselijke tussenkomst.
Toekomstige richtingen: Het artikel suggereert dat hoewel huidige methoden beperkt zijn tot onderzoek-prototype schaal, de aanpak de weg baant voor geautomatiseerde synthese van industriële solvers, mits toekomstig werk modulebeheer en statische type-checking voor grote codebases aanpakt.

Kortom, A2DEPT vertegenwoordigt een significante sprong voorwaarts in geautomatiseerd algoritme-ontwerp, verder gaand dan het "invullen van de gaten" van een vast sjabloon naar het "schrijven van het hele boek", waardoor superieure prestaties en robuustheid worden bereikt bij het oplossen van complexe combinatorische optimalisatieproblemen.