Je leest:

Digitale evolutie schiet economen te hulp

Digitale evolutie schiet economen te hulp

Auteurs: en | 30 oktober 1999

Formuleer een reeks van willekeurige mogelijke oplossingen voor een complex economisch probleem. Laat op die populatie de evolutionaire strijd van survival of the fittest los. Uiteindelijk blijven dan de beste, meest aangepaste oplossingen over. Genetische rekenmethoden kunnen complexe economische problemen kraken.

“De discipline binnen de sociale wetenschappen die het best is toegerust tot het slaan van een brug naar de natuurwetenschappen, die het meest met ze gemeen heeft qua stijl en zelfvertrouwen, is de economie… Maar de gelijkenis met ‘echte’ wetenschap is veelal oppervlakkig en is verworven ten koste van een hoge intellectuele prijs… De economie die zich in de voorhoede van de sociale wetenschappen beweegt, kampt met dezelfde problemen als de bevolkingsgenetica en de milieuwetenschappen. Economie lijdt onder ‘exogene schokken’, alle niet-verklaarbare historische en milieuveranderingen die de parameterwaarden op en neer stoten. Dat alleen al beperkt de nauwkeurigheid van economische voorspellingen,” schreef Edward Wilson in Het Fundament – Over de eenheid van kennis en cultuur.

Na het verschijnen van Charles Darwins On the Origin of Species is geleidelijk het besef doorgebroken dat we veel kunnen leren van processen in de natuur. Na miljoenen jaren van evolutie is de aarde bevolkt door een ongelooflijk diverse verzameling organismen, van microscopisch kleine bacteriën en virussen tot pinguïns, giraffen en gigantisch grote blauwe vinvissen. Een opvallend aspect van het natuurlijk ecosysteem is zijn aanpassingsvermogen. Als de natuurlijke omstandigheden op aarde veranderen, bijvoorbeeld door ontbossing, jacht, visserij of vervuiling, verdwijnen enerzijds soorten, terwijl andere soorten zich met succes weten aan te passen en juist profiteren van de veranderende omstandigheden.

De grondlegger van de evolutietheorie, Charles Darwin.

Economen hebben recent ingezien dat er belangrijke overeenkomsten bestaan tussen ecologische en economische systemen. Geïnspireerd door deze overeenkomsten, maken ze gebruik van de wiskundige techniek van de genetische rekenmethoden om meer en meer realistische modellen op te lossen. Genetische rekenmethoden zijn gebaseerd op de fundamentele mechanismen uit de evolutiebiologie: reproductie met variatie en selectie. De genetische rekenmethode bouwt zelf de kennis over goede oplossingen impliciet op. De eerste ontwikkeling van genetische rekenmethoden dateert van eind jaren zestig. Sindsdien zijn ze op beperkte schaal toegepast in de biologie, de computerwetenschappen, de sociale wetenschappen en in ingenieurswerk. Sinds ruim vijf jaar bedienen ook economen zich van deze wiskundige techniek.

Slagvaardig

Mechanismen van recombinatie en mutatie

Een economische markt bestaat, net als een natuurlijk ecosysteem, uit zeer veel ‘spelers’, zoals bijvoorbeeld particulieren, bedrijven of overheidsinstellingen. Ieder voor zich streeft naar zoveel mogelijk winst, marktaandeel of macht. Vooral in het geval van felle concurrentie en kleine marges verdwijnen slecht presterende spelers snel. Hun marktaandeel raken ze dan kwijt aan een meer slagvaardige concurrent. Vergelijk dit maar met het principe van het recht van de sterkste (survival of the fittest) in de natuur. Als zich een nieuwe markt aandient, ontstaan tevens vaak snel nieuwe aanbieders van het gevraagde product. Denk hierbij bijvoorbeeld aan de snelle expansie van bedrijven als Netscape en Microsoft op de snelgroeiende internet- en computermarkten.

Punt-tot-punt-zoekmethode

De werking en de kracht van genetische rekenmethoden laten zich illustreren aan de hand van het volgende voorbeeld. Stel dat een econoom als opdracht heeft om effectieve werkgelegenheidsplannen te ontwikkelen. Gelukkig beschikt hij over een zeer uitgebreid computermodel waarmee hij het effect van veel beleidsveranderingen, bijvoorbeeld het verlagen van het minimumloon of het starten van omscholingsprojecten, op de werkgelegenheid kan bepalen. Hij kan nu nieuw beleid ontwikkelen door het volgen van een ‘stel dat’-aanpak. In dat geval analyseert de econoom steeds opnieuw een beleidsplan. Nadat hij de resultaten van het programma heeft bekeken, kan hij het beleidsplan iets wijzigen, in de hoop dat deze wijzigingen een nog beter werkgelegenheidsplan opleveren. Dit nieuwe plan kan hij dan ook weer analyseren, en op deze manier ontwikkelt hij een hele reeks, hopelijk steeds betere beleidsplannen.

Evolutionaire rekenmethode

Werking van evolutionaire rekenmethoden

Deze methode heeft natuurlijk enkele grote nadelen: ze is tijdrovend, arbeidsintensief en er is geen enkele garantie dat ze werkelijk de allerbeste oplossingen voor het werkgelegenheidsprobleem oplevert. Onze hardwerkende econoom kan deze bezwaren omzeilen met een evolutionaire rekenmethode. Een evolutionaire rekenmethode zoekt namelijk niet van punt tot punt, maar gebruikt een verzameling van mogelijke oplossingen. Deze verzameling, of populatie, bevat vele mogelijke oplossingen voor het werkgelegenheidsprobleem. Sommige van die oplossingen zijn goed, andere minder. Nadat de econoom het effect van elke oplossing heeft geëvalueerd, gebruikt hij deze informatie om met de evolutionaire rekenmethode een nieuwe verzameling strategieën te genereren. Hij kan het zoekproces dan herhalen in opeenvolgende generaties door de verzameling oplossingen steeds verder te laten evolueren. Doordat deze methode de informatie van een verzameling oplossingen gebruikt, bestrijkt ze een veel groter zoekgebied dan de punt-tot-punt-zoekmethode. Ook als het zoeklandschap vele pieken en dalen kent, kan de evolutionaire methode relatief eenvoudig optimale oplossingen vinden.

Code

Voor het gebruiken van een evolutionaire rekenmethode moeten we de oplossingen voor een probleem vertalen naar een genetische code. Deze code bestaat uit een rij nullen en enen, bijvoorbeeld 1010110010111. Zo kan in het een voorbeeld het eerste binaire getal (bit) in deze rij bijvoorbeeld aangeven dat het minimumloon wel (1) of niet (0) moet worden verlaagd, het tweede bit of werklozen verplicht moeten solliciteren (1) of niet (0) enzovoort, totdat alle belangrijke factoren voldoende nauwkeurig zijn gespecificeerd. De lengte van de genetische code hangt sterk af van het totale aantal variabelen dat we beschouwen en de gedetailleerdheid waarmee we deze factoren representeren in de genetische code.

Om de zoektocht nu te starten, moet de genetische rekenmethode een verzameling kandidaatoplossingen ter beschikking hebben. Deze eerste generatie oplossingen kan bestaan uit reeds bekende goede oplossingen voor het probleem of, als geen voorkennis over het probleem aanwezig is, uit een willekeurige populatie van oplossingen. Uit deze beginpopulatie selecteren we dan de best presterende oplossingen. Vervolgens kopiëren we deze oplossingen niet direct naar de volgende generatie, maar kruisen we ze eerst tot twee nieuwe oplossingen. Dit noemen we recombinatie, naar analogie van de biologie. Eerst nemen we uit de geselecteerde oplossingen paren van oplossingen, die we kunnen beschouwen als een vader- en een moederoplossing. Elk paar snijden we dan op een willekeurige plaats door. Tenslotte verwisselen we de delen van de oplossingen, zodat de kop van de moederoplossing aan de staart van de vaderoplossing komt te zitten en omgekeerd (crossing over). Dit proces verloopt analoog aan het voortplantingsproces in de natuur, waarbij een kind stukken van het genetisch materiaal van beide ouders erft en ze combineert tot nieuw genetisch materiaal.

Nakomelingen

Nakomelingen van de beste oplossingen vervangen zo de geëlimineerde slechte oplossingen, totdat de populatie weer is gevuld met verse kandidaten. Deze nakomelingen presteren overigens vaak zeer goed, met name omdat goede deeloplossingen (stukjes genetische code) van de ouders worden gecombineerd in hun genetisch materiaal. Voor het waarborgen van een voldoende grote variatie in de populatie en ter voorkoming van inteelt, worden van tijd tot tijd kandidaatoplossingen ook willekeurig een beetje veranderd (mutatie). Dit komt overeen met de willekeurige veranderingen in de natuur van het genetisch materiaal, bijvoorbeeld omdat er iets fout gaat in de recombinatiefase of door de schadelijke invloed van voedingsstoffen of radioactieve straling.

Net als in de natuur bestaan de drie basisstappen van de genetische rekenmethode uit een selectie van de beste oplossingen (survival of the fittest), kruising van de geselecteerde kandidaten (recombinatie) en sporadische veranderingen in de genetische code (mutatie). Dit proces kunnen we in een computerprogramma herhalen, zodat we steeds betere oplossingen voor een probleem genereren. Het uiteindelijke doel is het vinden van een populatie van oplossingen die zo goed mogelijk is aangepast aan de uit te voeren taak, waaruit we uiteindelijk de goede oplossingen kunnen halen.

Het dilemma van de gevangene

In het dilemma van de gevangene kan elk van de spelers ofwel samenwerken, ofwel de ander verraden. Voor elke mogelijke combinatie is in de tabel de score per speler aangegeven. De score van speler A is het eerst weergegeven, gevolgd door de score van speler B.

Oplossing van het dilemma van de gevangene door een genetisch algoritme

De afbeelding toont de vijf verschillende fasen.

I De beginfase (generatie 0-20) Het experiment begint met een populatie willekeurig gekozen strategieën. De beste strategie is in dit geval systematisch tegenwerken (dit levert namelijk gemiddeld drie punten op, tegen gemiddeld anderhalve punt voor samenwerking). Het aantal verraders in de populatie neemt dan ook snel toe. Dit heeft echter tot gevolg dat het gemiddeld aantal behaalde punten daalt. Hoe meer verraders immers aanwezig zijn in de populatie, hoe moeilijker het wordt om punten te verzamelen. h3. II De evolutie van coöperatie (generatie 20-50)

Tijdens deze fase ontstaan zogenaamde ‘oog-om-oog’-strategieën, een klasse van beroemde en zeer succesvolle strategieën voor het dilemma van de gevangene. Deze spelers beginnen altijd met samenwerken, en herhalen in de rest van het spel de vorige zet van de tegenstander. Dit betekent dat een verrader nooit blijvend succes kan hebben tegen deze strategie: ze worden immers direct met eigen munt terugbetaald! Als twee oog-om-oog-spelers elkaar ontmoeten behalen ze echter wel een goed resultaat (drie punten), een stuk beter dan de uitkomst van een competitie tussen twee verraders (slechts één punt). Hun aantal neemt dus snel toe, en het gemiddelde aantal punten stijgt.

III Lange coöperatieve toestand (generatie 50-220)

De samenwerking blijft zeer lang intact, met name doordat de oog-om-oog-strategieën zo moeilijk zijn uit te buiten door verraders. Toch weten de verraders na ongeveer tweehonderd generaties hun slag te slaan. Dit komt doordat alle coöperatieve strategieën even goed presteren als oog-om-oog. Dit geldt dus ook voor zogenaamde naïeve samenwerkers, die altijd samenwerken, zelfs met een verrader. Omdat in fase III nauwelijks verraders aanwezig zijn, neemt in deze fase het aantal naïeve strategieën langzaam toe.

IV Ineenstorting van de samenwerking (generatie 220-240) Door een mutatie in de genetische code ontstaan verraders die de naïeve spelers effectief kunnen uitbuiten en de coöperatieve populatie ‘stort ineen’ door een grootscheepse invasie van verraders. Als alle exploiteerbare spelers zijn ‘uitgestorven’ blijven alleen de verraders en de oog-om-oog-strategieën over. V Herstel van de samenwerking (vanaf generatie 240).

Dilemma

Een klassiek voorbeeld van de toepassing van een genetische rekenmethode is een probleem dat bekend staat onder de naam ‘het dilemma van de gevangene’. Op het Centrum voor Wiskunde en Informatica in Amsterdam hebben we een genetische rekenmethode hiervoor ontwikkeld. Het dilemma van de gevangene (ook wel bekend als het prisoner’s dilemma) is oorspronkelijk in de jaren vijftig ontwikkeld in de economische speltheorie, maar heeft in de loop van de tijd ook wetenschappers van ander pluimage, zoals filosofen, politicologen en sociologen, in zijn ban gekregen. In zijn meest eenvoudige vorm is het dilemma van de gevangene een spel tussen twee personen die allebei slechts twee mogelijke ‘zetten’ kunnen doen: elkaar helpen of elkaar verraden. Wanneer beide spelers elkaar helpen, wordt hun coöperatieve gedrag beloond (beide spelers ontvangen dan bijvoorbeeld drie punten), terwijl ze worden bestraft wanneer ze elkaar verraden (ze krijgen dan nog maar één punt).

Het dilemma van de gevangene ontstaat nu wanneer het in een coöperatieve toestand (beide spelers werken dus met elkaar samen) aantrekkelijk is om de samenwerking te verbreken. De speler die de samenwerking verbreekt krijgt dan een extra bonus (hij krijgt maar liefst vijf punten), terwijl de speler die wel wil samenwerken berooid achterblijft met nul punten. Wanneer beide spelers tegelijk de samenwerking verbreken, worden ze echter allebei bestraft, en hadden ze dus beter de samenwerking kunnen voortzetten. Een machtige puzzel: de logica dicteert om niet samen te werken met je tegenstander, terwijl dit leidt tot een toestand waarin beide spelers worden bestraft!

Een elegante manier om deze paradox te bestuderen is het uitvoeren van een evolutionaire simulatie. Dit experiment bestaat eenvoudigweg uit een ‘populatie’ van spelers die tegen elkaar het dilemma van de gevangene spelen. Elke speler heeft de beschikking over een beperkte hoeveelheid informatie, in onze simulatie de twee vorige zetten van de tegenstander en zichzelf. Hiervan uitgaande besluit een speler om al dan niet samen te werken in de volgende ronde van het spel. Bij het begin van het computerexperiment worden deze strategieën willekeurig gekozen. Door de interactie tussen de spelers ontstaat een grillig patroon, waarbij perioden van samenwerking en tegenwerking elkaar afwisselen. Bedenk dat de spelers goed met elkaar samenwerken als het gemiddelde aantal punten in de buurt van de waarde drie ligt, terwijl een lage score erop duidt dat er relatief veel verraders aanwezig zijn in de populatie.

Het evolutionaire proces is in het algemeen sterk afhankelijk van toevallige factoren. Toch zien we dat in het algemeen coöperatieve samenlevingen relatief stabiel zijn als goed presterende spelers meerdere generaties overleven. De evolutionaire stabiliteit neemt daarentegen sterk af wanneer alle ouders al na een of enkele generaties ‘overlijden’ en direct worden vervangen door nakomelingen. Het dilemma van de gevangene is in feite een model voor elke maatschappelijke situatie waarin een bepaald gedrag weliswaar collectief is gewenst, maar waarin het voor het individu voordeliger is om zich aan het collectieve gedrag te onttrekken. Het betalen van belasting of het rekening houden met het milieu, zijn hier voorbeelden van.

Afkijken

De modellering van een economische speler in een genetisch evolutionair model wijkt fundamenteel af van de traditionele economische modellen. De meeste modellen nemen immers aan dat elke deelnemer aan het economische spel een volledig inzicht heeft in de marktwerking en altijd een optimale, rationele keuze maakt. Dit staat in tegenstelling tot evolutionaire modellen, waarbij spelers gebruik maken van een strategie met beperkte capaciteiten, die ze vervolgens op een trial-and-error-manier steeds verder aanpassen totdat ze een goede strategie hebben gevonden. Door de recombinatie van strategieën neemt het model impliciet het ‘van elkaar leren’ en ‘bij elkaar afkijken’ van de spelers mee. Zo kan een groep van spelers al lerende tot een nieuwe situatie komen.

Het onderzoek naar evolutionaire processen in de economie is jong en volop in ontwikkeling, maar op deelgebieden zijn al belangrijke resultaten geboekt. Zo heeft de Amerikaanse econoom John Miller met een evolutionaire simulatie aangetoond hoe een efficiënte markt van kopers en verkopers min of meer spontaan kan ontstaan. Economen noemen een markt efficiënt wanneer geen enkele koper of verkoper zijn positie kan verbeteren, zonder dat de positie van een andere koper of verkoper verslechtert. De vraag die Miller zich stelde was hoe zo’n efficiënte markt kan ontstaan in een vrije marktsituatie, wanneer kopers en verkopers slechts beschikken over onvolledige informatie.

Om deze vraag te beantwoorden ontwikkelde Miller een marktmodel waarin elke speler zijn eigen koop- en verkoopstrategie heeft. Om een genetisch zoekproces te kunnen gebruiken zette Miller deze strategieën om in een rijtje nullen en enen, die door crossover en mutatie kunnen worden veranderd. Elke economische speler heeft tevens slechts de beschikking over een beperkte hoeveelheid informatie over het biedgedrag van zijn concurrenten. Om het evolutionair selectieproces in werking te stellen, wordt de evolutionaire fitheid van elke speler tenslotte bepaald door zijn behaalde winst. Miller begon zijn computersimulatie met een populatie willekeurige strategieën, zette vervolgens het genetische zoekproces in werking en merkte dat na verloop van tijd een efficiënte markt van kopers en verkopers ontstond. Dit is een opmerkelijk resultaat, omdat in de simulatie het enige succescriterium de winst van individuele spelers was.

Nieuwe markten

Modellen zoals die van John Miller zijn zeer nuttig om beter te begrijpen onder welke omstandigheden markten zichzelf organiseren en hoe economen beleid kunnen ontwikkelen dat het ontstaan van inefficiënte marktsituaties voorkomt. Evolutionaire simulaties van economische problemen kunnen echter ook bijdragen aan nieuwe inzichten op andere terreinen, zoals bijvoorbeeld de optimale aansturing van computernetwerken of het ontstaan van samenwerking in een maatschappij.

In een evolutionair zoekproces kunnen we de hoeveelheid informatie die elke speler tot zijn beschikking heeft, precies instellen. Ook aspecten als van elkaar leren en elkaar beïnvloeden zijn automatisch deel van het evolutionaire zoekproces. De mate waarin dit gebeurt kunnen we instellen. Zo kunnen we de invloed hiervan en de controle hierover bestuderen met evolutionaire methoden. Met name in snel veranderende markten, zoals op het gebied van dienstverlening, informatievoorziening, amusement, kennis en financiën, waarin gevoelsmatige groepsaspecten de doorslag kunnen geven, is dit een belangrijke eigenschap. De ontwikkelingen van nieuwe markten door internet is dan ook meteen een belangrijk gebied voor dit onderzoek: al deze aspecten zijn daar zeer belangrijk. Dit levert zowel inzicht in de werking van nieuwe markten, als hoe goede elektronische markten en systemen kunnen worden ontworpen of gecontroleerd met deze aanpak. Dit is momenteel onderwerp van fascinerend en innoverend onderzoek op het gebied van elektronische markten en evolutionaire methoden.

Bronnen

Holland JH. Hidden order: How adaptation builds complexity. Reading (MA): Addison-Wesley, 1995

Mitchell M. An introduction to genetic algorithms. Cambridge (MA): MIT Press, 1996

Dit artikel is een publicatie van Natuurwetenschap & Techniek.
© Natuurwetenschap & Techniek, alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 30 oktober 1999

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.