🤖 AI

A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

Dit artikel stelt een nieuwe aanpak voor om optimalisatieproblemen te karakteriseren door het Halstead-volume en de entropie van hun programmatische implementaties te berekenen, waarbij wordt aangetoond dat deze op code gebaseerde complexiteitsmaten dienen als effectieve, sampling-vrije voorspellende meta-kenmerken voor algoritme-selectie.

Oorspronkelijke auteurs: Marcus Gallagher, Katherine M. Malan

Gepubliceerd 2026-08-11

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Marcus Gallagher, Katherine M. Malan

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 robot probeert te leren hoe hij een doolhof moet oplossen. Soms is het een eenvoudig, recht gangetje; andere keren is het een kronkelend, draaiend labyrint met doodlopende wegen en vallen. In de wereld van de informatica wordt dit optimalisatie genoemd: het vinden van de best mogelijke oplossing voor een probleem. Maar hier is het lastige deel: niet alle doolhoven zijn gelijk. Sommige zijn makkelijk voor een robot om op te lossen, terwijl andere zelfs de slimste algoritmen doen verdwalen.

Om robots te helpen de juiste strategie te kiezen, proberen wetenschappers deze doolhoven te "karakteriseren" of te beschrijven voordat de robot überhaupt begint te rennen. Ze zoeken naar aanwijzingen, zoals hoe hobbelig de grond is of hoeveel doodlopende wegen er zijn. Meestal moet de robot om deze aanwijzingen te vinden een paar stappen zetten, rondkijken en het terrein meten. Dit is als het sturen van een verkenner de duisternis in om een grot in kaart te brengen. Maar wat als de robot gewoon naar de blauwdruk van het doolhof kon kijken en kon raden hoe moeilijk het zou zijn om op te lossen, zonder ooit een voet binnen te zetten? Dat is de grote vraag die dit artikel stelt. Het suggereert dat de manier waarop een probleem in computercode is geschreven, het geheim kan bevatten van hoe moeilijk het is om op te lossen, net zoals de complexiteit van een recept een hint kan geven aan hoe moeilijk het koken zal zijn.

De Code als Kristallen Bol

In dit artikel stellen Marcus Gallagher en Katherine Malan een frisse, licht magische manier voor om naar deze moeilijke problemen te kijken. In plaats van een verkenner te sturen om het landschap te meten, suggereren zij dat we simpelweg het "recept" lezen dat de computer gebruikt om het probleem te creëren.

Beschouw een optimalisatieprobleem als een level in een videogame. Om het level te bouwen, schrijft een programmeur code. Sommige levels zijn simpel: "Ga naar voren, spring over een kuil, verzamel de munt." De code hiervoor is kort en gebruikt basiscommando's. Andere levels zijn chaotisch: "Als de lucht blauw is, vermenigvuldig je de snelheid met het aantal sterren, maar trek vervolgens de vierkante wortel van je gezondheid af, maar alleen als je een hoed draagt." De code hiervoor is lang, rommelig en gebruikt een enorme variëteit aan commando's.

Het grote idee van de auteurs is dit: Hoe rommeliger en complexer de code is, hoe moeilijker het algoritme het probleem zal oplossen.

Ze lenen twee instrumenten uit de wereld van software engineering om deze "rommeligheid" te meten.

Halstead Volume: Stel je voor dat je elke letter en elk symbool in een paragraaf telt. Als je een kort verhaal met eenvoudige woorden hebt, is de telling laag. Als je een roman hebt met een complexe woordenschat en lange zinnen, is de telling hoog. Deze maatstaf telt de "operators" (zoals wiskundige symbolen) en "operanden" (zoals getallen en variabelen) in de code.
Shannon Entropy: Dit is een beetje als het meten van de verrassingsfactor. Als een paragraaf steeds dezelfde vijf woorden gebruikt, is het voorspelbaar (lage entropie). Als het een enorme variëteit aan unieke woorden in een willekeurige volgorde gebruikt, is het onvoorspelbaar (hoge entropie).

Het Experiment: Van Simpele Cirkels tot Chaotische Pieken

Om hun theorie te testen, namen de auteurs een beroemde set van 24 testproblemen die door wetenschappers over de hele wereld worden gebruikt (bekend als de BBOB-suite). Deze variëren van de "Sphere"-functie (een perfect gladde, ronde heuvel die gemakkelijk naar beneden rolt) tot de "Lunacek bi-Rastrigin"-functie (een grillig, rotsachtig landschap met duizenden kleine pieken en dalen).

Ze schreven de computercode voor elk van deze 24 problemen op en draaiden hun "rommeligheids"-calculators op de code. De resultaten waren precies wat ze hoopten:

De simpele, gladde Sphere-functie had de laagste complexiteitsscores.
De grillige, moeilijke Lunacek-functie had de hoogste complexiteitsscores.
Sterker nog, de Lunacek-functie was ongeveer 9,3 keer zo complex in zijn codestructuur als de Sphere-functie.

Ze testten dit zelfs op een ander soort probleem: het trainen van een neuraal netwerk (een type AI-brein). Ze ontdekten dat de code voor een netwerk dat een "Tanh"-activatiefunctie gebruikt, iets complexer is dan een netwerk met "ReLU", en dit kwam overeen met het idee dat de Tanh-versie een iets moeilijker puzzel is om op te lossen.

De Magische Connectie: Codecomplexiteit Voorspelt Prestaties

De echte magie gebeurt wanneer ze deze codescores vergelijken met hoe goed verschillende algoritmen daadwerkelijk presteerden. Ze keken naar de gegevens van vijf verschillende "robot"-algoritmen die probeerden deze 24 problemen op te lossen.

Ze vonden een duidelijk patroon: Hoe complexer de code, hoe slechter de robots presteerden.

Het is een negatieve relatie. Wanneer de code simpel was (lage Halstead-volume), losten de robots het probleem snel en gemakkelijk op. Wanneer de code complex was (hoge Halstead-volume), hadden de robots moeite, deden ze er langer over of kwamen ze vast te zitten. Bijvoorbeeld, in 5-dimensionale problemen was de connectie tussen codecomplexiteit en slechte prestaties vrij sterk.

De auteurs zijn echter voorzichtig om op te merken dat dit geen perfecte kristallen bol is. Er waren een paar "outlier"-problemen waarbij de code zeer complex was, maar de robots niet zo slecht presteerden als de code deed vermoeden. Dit suggereert dat hoewel codecomplexiteit een goede aanwijzing is, het niet het enige is dat ertoe doet.

Waarom Dit Belangrijk Is

De schoonheid van deze aanpak is dat het ongelooflijk snel gaat en geen extra werk vereist. Traditionele methoden om een probleem te begrijpen, vereisen vaak het duizenden keren draaien van het algoritme om te zien hoe het landschap eruitziet. Dit is als het sturen van een verkenner om het hele doolhof af te lopen, alleen maar om een kaart te tekenen.

In tegen testelling hiermee is de methode van de auteurs als het bekijken van de blauwdruk van het doolhof. Je kunt de complexiteit van de code in een fractie van een seconde berekenen, zonder het probleem ook maar één keer uit te voeren. Het maakt niet uit hoe groot het probleem is of hoeveel dimensies het heeft; het kijkt simpelweg naar de structuur van de instructies.

De auteurs suggereren dat deze nieuwe "codecomplexiteit"-maatstaf een nuttige toevoeging kan zijn aan de gereedschapskist van wetenschappers die algoritmen ontwerpen. Het vervangt de oude manieren om naar problemen te kijken niet, maar het voegt een nieuwe, supersnelle manier toe om te raden hoe moeilijk een probleem zal zijn voordat je zelfs maar begint met oplossen. Het is een veelbelovende stap naar het helpen van computers om het juiste gereedschap voor de taak te kiezen, simpelweg door de instructies te lezen.

Technische Samenvatting: Karakterisering van Optimalisatieproblemen middels Programmatische Representatie

Probleemstelling
Het karakteriseren van instanties van optimalisatieproblemen is fundamenteel voor het begrijpen van algoritmisch gedrag, het faciliteren van algoritmekeuze en het configureren van optimizers. Bestaande benaderingen, zoals Exploratory Landscape Analysis (ELA), vertrouwen op het bemonsteren van de zoekruimte om kenmerken (features) te extraheren. Deze methoden kampen echter met praktische beperkingen: ze verbruiken kostbare evaluaties van de objectfunctie, zijn gevoelig voor de steekproefomvang en de strategie, en kunnen er niet in slagen robuuste representaties van complexe landschappen te bieden. Bovendien leveren verschillende feature-sets vaak complementaire in plaats van overlappende informatie, wat wijst op een behoefte aan diverse karakteriseringsbenaderingen.

Methodologie
De auteurs stellen een nieuwe benadering voor die optimalisatieproblemen karakteriseert op basis van de programmatische representatie van hun objectfuncties, in plaats van het bemonsteren van de zoekruimte. De kernintuïtie is dat de complexiteit van de code die nodig is om een objectfunctie te implementeren, correleert met de complexiteit van het resulterende zoeklandschap. Eenvoudige wiskundige structuren leiden tot eenvoudige code en gladde landschappen, terwijl complexe functies langere, operator-zware code vereisen en zich manifesteren als onregelmatige landschappen.

De studie maakt gebruik van twee specifieke maten voor programmacomplexiteit, afgeleid uit software engineering en informatietheorie:

Halstead Volume ( $V_H$ ): Een maat voor programmagrootte en complexiteit, gedefinieerd als $V_H = (N_1 + N_2) \log_2(\eta_1 + \eta_2)$ , waarbij $N$ het totaal aantal operatoren/operanden vertegenwoordigt en $\eta$ het aantal unieke operatoren/operanden.
Shannon Entropie ( $H$ ): Een maat voor de informatie-inhoud per token, geschaald door het totaal aantal tokens ( $N$ ). De auteurs merken op dat $H$ , onder aannames van een uniforme waarschijnlijkheid, $V_H$ benadert.

Deze metrieken worden statisch berekend vanuit de broncode (specifiek C-implementaties) van de objectfuncties. De studie evalueert deze maten op:

De BBOB (Black-Box Optimisation Benchmarking) ruisloze testsuite (24 functies).
Optimalisatietaken voor neurale netwerkgewichten (het trainen van feed-forward netwerken met ReLU en Tanh activatiefuncties).

Belangrijkste Bijdragen en Resultaten

Statische, Steekproefvrije Karakterisering: De voorgestelde methode vereist geen bemonstering van de zoekruimte en geen evaluaties van de objectfunctie. Het is invariant voor transformaties (bijv. rotatie, conditionering) en de dimensionaliteit van het probleem (aangezien dimensionaliteit wordt behandeld als een loop-telling of een enkel operand in de codestructuur).
Correlatie met Algoritme-prestaties: Bij toepassing op de BBOB-suite werd vastgesteld dat het Halstead-volume en de entropie negatief correleren met de prestaties van algoritmen (gemeten aan de hand van de genormaliseerde Area Under the Curve van de empirische cumulatieve distributiefunctie).
- Hogere complexiteitswaarden (bijv. voor $f_{24}$ , Lunacek bi-Rastrigin) corresponderen met lagere algoritmische prestaties.
- Lagere complexiteitswaarden (bijv. voor $f_1$ , Sphere) corresponderen met hogere prestaties.
- Spearman's rangcorrelatiecoëfficiënten waren negatief voor alle geteste algoritmen (dCMA, COBYLA, DE, mCMA, L-SHADE) en dimensies (2D en 5D), hoewel de sterkte van de correlatie varieerde (van zwak tot matig).
Differentiatie van Probleemtypen: De metrieken slaagden erin om probleemklassen te onderscheiden. Zo konden de complexiteitsmetrieken bij het trainen van neurale netwerken onderscheid maken tussen netwerken die gebruikmaken van ReLU versus Tanh activatiefuncties, wat overeenkomt met eerdere bevindingen dat activatiefuncties cruciale differentiators zijn voor landschapskenmerken, onafhankelijk van de specifieke regressietaken of de netwerkomvang.
Geobserveerde Beperkingen: De metrieken legden specifieke parameters van problemen niet vast die de codestructuur niet significant veranderen, zoals het aantal pieken in de Gallagher-functies ( $f_{21}, f_{22}$ ) of de dimensionaliteit van het probleem. Daarnaast vertoonden uitschieters met zeer hoge $V_H$ -waarden (bijv. $f_7, f_{21}, f_{22}, f_{24}$ ) een minder duidelijke trend in de scatterplots van complexiteit versus prestaties.

Betekenis en Claims
Het artikel positioneert deze programmatische complexiteitsmaten als complementair aan bestaande landschap-analysebenaderingen in plaats van als een vervanging. De auteurs beweren dat de benadering duidelijke voordelen biedt:

Efficiëntie: Het is zeer snel automatisch te berekenen.
Invariantie: Het is invariant voor transformaties van de zoekruimte en is niet afhankelijk van bemonsteringsstrategieën.
Voorspellend Potentieel: De negatieve correlatie met algoritmische prestaties suggereert dat deze metrieken potentieel hebben als voorspellende meta-kenmerken voor algoritmekeuze en configuratie.

De auteurs concluderen dat hoewel programmatische representatie niet elke eigenschap van een probleemlandschap relevant voor prestaties kan vatten, het een uniek, statisch perspectief biedt dat de computationele overhead van bemonstering vermijdt. Zij suggereren dat toekomstig werk deze metrieken moet verkennen op reële problemen waarbij uitgebreide code-executie (bijv. numerieke simulaties) plaatsvindt, en de bruikbaarheid ervan moet onderzoeken voor het verbeteren van algoritmekeuze-"wizards".

De Code als Kristallen Bol

Het Experiment: Van Simpele Cirkels tot Chaotische Pieken

De Magische Connectie: Codecomplexiteit Voorspelt Prestaties

Waarom Dit Belangrijk Is

Meer zoals dit