12    Evolutie / Revolutie

Materialisme en de seksuele teeltkeuze
Menno Wiegman

Gezocht: Kosmisch ontwerper
Iris Groen en Sjoert van Velzen
- 1 reactie

Genetische modificatie van planten: een duurzame revolutie?
Jeroen Melief
- 1 reactie

Een bron van inspiratie
Annemie Ploeger
- 1 reactie

De evolutie van taal
Jelle Zuidema
- 3 reacties

Meer van hetzelfde?
Mineke Schipper

De immer veranderende vampier
Sabrina Verbeek
- 5 reacties

Sinds the Sixties
Jetske van Heemstra
- 1 reactie

Che! Een commerciële revolutie
Maud Dahmen
- 2 reacties

Emergentie, evolutie en revolutie in Artificial life
Ella Keijzer

Genetische algoritmen en het handelsreizigersprobleem
Mark Kooijman
- 3 reacties

colofon  issn 1879-8144  2 juni 2007

Alle edities   Vakgebieden            
English   Over Blind       Vacatures
Volg ons:               
© 2004–2019 Blind    disclaimer   cookies

 

BLIND
12
 online interdisciplinair tijdschrift  
BLIND 12
alle edities      



zoeken + vakgebieden       



random editie       



vorige editie       



volgende editie       
naar boven       

In exacte wetenschappen is het bij het zoeken naar oplossingen vaak handig om eerst te kijken naar de oplossingen die er in de natuur voor vergelijkbare problemen zijn gevormd. Aan de andere kant kan het bij het toetsen van hypotheses over de natuur handig zijn om de natuur eerst na te bouwen. Op deze manier wordt met behulp van de artificiële intelligentie veel vooruitgang geboekt op het gebied van evolutie (zie hierover het artikel van Mark Kooijman in ditzelfde nummer). Maar tegelijkertijd blijkt een evolutionaire methode van berekenen vaak veel efficiënter dan een exacte methode. Ella Keijzer legt in het volgende artikel aan de hand van vele voorbeelden uit op welke manier dit gebeurt en wat hierbij allemaal komt kijken.

Ella Keijzer heeft Cognitieve kunstmatige intelligentie gestudeerd aan de Universiteit Utrecht en volgt tegenwoordig de master Mediatechnology in Leiden.


Lees het artikel

BLIND 12 - Evolutie / Revolutie
sluiten

Hoofdredactie

Inge van der Bijl


Eindredactie

Inge van der Bijl


Redactie

Maud Dahmen
Iris Groen
Elisa Hermanides
Arno Verweij (webmaster)


Redactieraad

prof. dr. Johan van Benthem
drs. Kim van den Berg
dr. Casper de Groot
prof. dr. Michel Haring
prof. dr. Ed van den Heuvel
drs. Machiel Keestra
dr. Bernard Kruithof


klik hier voor huidige redactie


sluiten

Emergentie, evolutie en revolutie in Artificial life

              
alle bijdragen van deze auteur
korte inleiding & meer over de auteur
all articles by this author
short intro & about the author
artikel door Ella Keijzer

Kunstmatig leven, ofwel leven gemaakt door mensenhanden: Artificial life (Alife) is een vakgebied dat leven en levende processen bestudeert met behulp van bijvoorbeeld computersimulaties. De vraag wanneer iets levend is, levert nog altijd een goede discussie op. Je kan denken dat met leven een organisme bedoeld wordt dat erop gericht is te groeien en/of zich te vermenigvuldigen. En dat leven iets is met een beperkte duur: leven wordt geboren en gaat dood. Met deze intuïtieve, maar onuitgewerkte gedachten over leven in ons achterhoofd vertel ik iets over de geschiedenis en de belangrijkste elementen van Alife, namelijk emergentie en evolutie, waarna ik aan het eind van dit artikel de revolutie binnen Alife bespreek.

Emergentie

Kan een machine zichzelf reproduceren? Deze vraag stelde de beroemde wiskundige John von Neumann zich rond 1950.1 Hij maakte op ruitjespapier een zelfreplicerend patroon met zijn potlood: de eerste cellulaire automaat. In het grid (het ruitjespapier) van een cellulaire automaat kunnen cellen aan of uit zijn. Als een cel aan is, wordt dat een levende cel genoemd, als een cel uit is een dode. Wanneer door regels de cellen in een telkens verversend grid aan en uit gaan kan er een zelfreplicerend patroon ontstaan. Een bekend voorbeeld van een cellulaire automaat is Conway's Game of life.2 Conway bedacht de volgende set regels voor elke cel in het grid:

1. Elke levende cel met één buur overlijdt, als gevolg van eenzaamheid.
2. Elke levende cel met vier of meer buren overlijdt, als gevolg van overpopulatie.
3. Elke levende cel met twee of drie buren overleeft.
4. Elke dode cel met drie buren komt tot leven.

Het grid wordt, alle regels voor alle cellen in acht nemend, meermalen ververst, waardoor er telkens nieuwe generaties ontstaan. Zo kunnen er bijzondere patronen te zien zijn in de vorm van explosies en ruimteschepen. Je kan bekijken hoe ze eruitzien, ze aanpassen of zelf een cellulaire automaat maken in dit programma: http://www.bitstorm.org/gameoflife/.

Als je er even mee gespeeld hebt zul je al snel zien dat door de vier simpele regels toe te passen een ingewikkeld patroon kan ontstaan, waar geen enkele individuele cel weet van heeft. Neem bijvoorbeeld de ruimteschepen; als ik niet beter zou weten zou ik denken dat iemand dit patroon met voorbedachte rade heeft geprogrammeerd. Wanneer een extra patroon door het toepassen van simpele regels ontstaat, wordt dit emergentie genoemd.

Conway's Game of life is een softwaremodel. Het idee dat het geheel meer is dan de som der delen en dat complex gedrag van een systeem niet afhangt van een centrale besturing wordt ook toegepast op echte robotjes. Als je hier meer over wilt weten, verwijs ik je graag door naar een artikel en een filmpje van Noorderlicht: 'Werken als een mier' en 'Robotmieren aan het werk', zie: http://noorderlicht.vpro.nl/dossiers/16463881/hoofdstuk/16077744/.

Een leuke speculatie over de toekomst wordt aan het eind van deze uitzending gegeven. Robotwetenschapper Chris Melhuish stelt zich voor dat duizenden nanobotjes ingewikkeld werk voor ons kunnen doen. Je zou ze bijvoorbeeld, zo speculeert hij, over een brug kunnen laten lopen en verfscheurtjes kunnen laten repareren. Omdat elk nanobotje afzonderlijk zijn werk kan doen, maakt het niet uit als een botje stuk gaat. Verderop in het artikel kom ik hier op terug.

Conway's Game of life is een model zonder referentie naar een levend proces. Emergentie is wellicht ook in de natuur te vinden (zie bijvoorbeeld de mieren uit bovenstaande link) en kan nieuw licht op levende processen werpen.

Emergentie in de natuur

Voor dat het vakgebied Alife zijn naam kreeg (in 1978)3, was men onder andere in de biologie al bezig artificiële modellen te maken van levende processen. Een mooi voorbeeld hiervan is het onderzoek van Hogeweg en Hesper in 1983 over de levenscyclus van de hommelkolonie.4 Er zijn verscheidene theorieën over de cycli in deze kolonies geweest, want het is curieus dat in elke kolonie een cyclus precies drie weken duurt. Verklaringen werden gezocht in externe signalen, zoals bijvoorbeeld de zon, waardoor de hommels zouden 'weten' wanneer ze de kolonie op moesten heffen, maar geen enkele theorie was echt bevredigend. Hogeweg en Hesper maakten een kunstmatig model, met enkele simpele regels over de leefgewoonten van een kolonie en lieten de kolonie kunstmatig leven. Gek genoeg had ook deze kunstmatige kolonie een levenscyclus van drie digitale weken. Door een simulatie te gebruiken sloten de auteurs de invloed van een extern signaal, zoals bijvoorbeeld de zon, uit. De oorzaak van de cyclus blijkt een bepaald feromoon dat de koningin verspreidt en haar de nodige dominantie over de werkers geeft. Wanneer de kolonie een bepaalde grootte bereikt, kunnen sommige werkers minder frequent bij de koningin zijn en hebben daardoor minder 'last' van het dominante feromoon. Ze worden hierdoor zelf dominanter en exact na de drie weken is de kolonie groot genoeg, met genoeg dominante werkers die de kolonie om zeep kunnen helpen. Met een paar simpele gereedschappen en regels, het feromoon, de grootte van de kolonie en de afstand van de werkers tot de koningin, ontstaat de bijzondere eigenschap van een drie weken durende kolonie. Ziehier de emergentie. Voor de precieze details over de structuur binnen de hommelkolonie verwijs ik naar het artikel van Hogeweg en Hesper.

De twee voorbeelden laten emergent gedrag zien, Conway's Game of life op een zelfgecreëerde manier en de hommelkolonie in de natuur. Een ander belangrijk element in Alife is evolutie. Evolutie is een simpel algoritme dat erg effectief blijkt te zijn om allerlei problemen op te lossen.

Evolutie als algoritme

Met Darwin in ons achterhoofd ziet een evolutionair algoritme er als volgt uit: eerst wordt er een beginpopulatie geïnitialiseerd. Hiervoor worden elementen uit een genenpoel gebruikt om individuen te vormen. De genenpoel kan uit van alles bestaan; uit nullen en enen of uit legoblokjes. Een individu is dan bijvoorbeeld een string van nullen en enen of een legobouwsel. Alle individuen worden geëvalueerd aan de hand van een fitheidsfunctie. In de fitheidsfunctie staat het doel van deze evolutie. De fitheidsfunctie kijkt hoe goed een individu op dit doel scoort. De volgende stap is het uitzoeken van ouders. De individuen die het beste scoorden op de fitheidsfunctie – degene die het fitst zijn – worden met elkaar gekruist. Hierbij wordt een deel van een ouder gecombineerd met een deel van een andere ouder. Er ontstaan dan kinderen. De kinderen worden vervolgens gemuteerd door een of meer van hun genen te vervangen met een willekeurig gen uit de genepool. Op de populatie die nu is ontstaan, wordt wederom de fitheidsfunctie toegepast, er worden opnieuw ouders geselecteerd, ouders gekruist, kinderen gemuteerd enzovoorts.

Evolutie ter inspiratie

Een evolutionair algoritme wordt in de computerwetenschap vooral gebruikt om optimalisatieproblemen op te lossen. Een voorbeeld van een optimalisatieprobleem is het handelsreizigersprobleem, zoals wordt besproken in het artikel 'Genetische algoritmen en het handelsreizigersprobleem' van Mark Kooiman in ditzelfde nummer. Als de oplossing door brute force (alle mogelijkheden uitproberen) gevonden zou moeten worden, heb je veel meer rekentijd nodig om tot de goede oplossing te komen dan wanneer je het probleem door een evolutionair algoritme laat oplossen.

Karl Sims gebruikte evolutie als inspiratie bij het maken van zijn block creatures.5 Een blokbeest is een virtueel beestje dat is opgebouwd uit blokken. De blokken kunnen op allerlei manieren gestapeld worden. Het beestje heeft de mogelijkheid zich te bewegen doordat de blokken ten opzichte van elkaar kunnen draaien of schuiven. Elk blokbeest wordt getest op zijn performance bij een gegeven taak. Sommige beesten ontwikkelen strategieën die lijken op strategieën in de natuur. In het filmpje bij de volgende link kan je precies zien hoe dat in zijn werk gaat: http://www.archive.org/details/sims_evolved_virtual_creatures_1994.

Evolutie als onderwerp van onderzoek

In complexe systemen met complexe opdrachten is het moeilijk een effectieve fitheidsfunctie te bedenken of te schrijven. Soms zelfs moeilijker dan om zelf de oplossing te bedenken. Wanneer bij een Alife-model de omgeving erbij betrokken wordt, bijvoorbeeld door eten te verspreiden of door een competitie-element toe te voegen, ontstaat er een impliciete fitheidsfunctie waarbij de selectiedruk niet expliciet gedefinieerd wordt, maar uit de omgeving ontstaat. Dit wordt endogene fitheid genoemd. Door een endogene fitheid ontstaat ongerichte, of open-ended evolutie, waarbij een ecosysteem zelf de richting van de evolutie bepaalt; de selectiecriteria komen tenslotte uit het systeem zelf.

Het computermodel Tierra6 is een artificieel systeem met open-ended evolutie. Tierra bestaat uit kleine, zelfreplicerende computerprogrammaatjes. Elk programmaatje is een instructiereeks, ofwel een levend proces in het werkgeheugen van de computer. De programmaatjes competeren om CPU-tijd (de tijd die de processor nodig heeft) en om computergeheugen. Thomas Ray, de ontwerper van Tierra, wilde met behulp van evolutie steeds betere programmaatjes krijgen. Tijdens het evolutieproces ontstonden programmaatjes die te klein waren om de taken te kunnen uitvoeren, maar ze bleven wel leven! Bij nader onderzoek bleek dat er parasieten waren ontstaan. De parasieten kregen zoveel succes dat er niets meer was om op te parasiteren; ze hadden hun eigen graf gegraven. Ray maakte een nieuwe set programmaatjes die immuun waren voor de parasieten. Maar dat mocht niet baten, want er ontstonden nieuwe, sterkere parasieten die dit immuunsysteem omzeilden. Ray had onbedoeld een stabiel ecosysteem gebouwd.

Meer realistisch en visueel aantrekkelijker dan Tierra is het programma Framsticks (http://www.frams.alife.pl/). In Framsticks kan je evolutie als onderwerp van je onderzoek gebruiken. Je kan er beestjes bouwen met ledematen, sensoren en spieren en dit alles laten besturen door een setje neuronen. Je kunt zelf een fitheidsfunctie instellen of de omgeving zo maken dat er vanzelf een fitheidsfunctie ontstaat, bijvoorbeeld door het toevoegen van eten. Je kunt seksuele selectie bestuderen, een jager-prooimodel maken of een heel ecosysteem bouwen. Framsticks kan worden gebruikt in biocomputing, voor adaptieve systemen, robotica en zelfs neurofilosofie.

Emergentie als revolutie...

Voor veel natuurlijke fenomenen is er nooit een lineair model gevonden. In een lineair model is het geheel niet meer of minder dan de som van zijn delen. Een kleine verandering in een van de delen heeft een klein effect op het geheel, in tegenstelling tot een emergerend systeem, waarin de som wel meer is dan zijn delen. Het gegeven dat er uit simpele regels complex gedrag kan ontstaan (emergentie) kan heel goed gebruikt worden om natuurlijke fenomenen te bestuderen.

Naast onderzoek naar levende processen kan emergentie ook gebruikt worden in allerlei andere toepassingen. De duizenden nanobotjes die over een muur rijden en kleine scheurtjes in de verf repareren zouden bijvoorbeeld zo'n toepassing kunnen zijn. Wanneer één nanobotje stuk is, zal het systeem als geheel nog steeds goed functioneren. Bij een centrale besturing is het meestal een veel groter probleem als een onderdeel wegvalt of stuk gaat. Denk maar aan een grasveld dat je wilt maaien. Als je een automatische grasmaaier hebt, die het hele veld kan overzien, en altijd keurig langs de randjes maait, ben je een gelukkig mens tot hij stuk gaat. Dan wordt je gras niet meer gemaaid. Stel nu dat je in plaats van de grote intelligente maaier heel veel kleine, simpele maaiertjes hebt die rijden tot ze lang gras zien en dan gaan maaien. Als er dan eentje stuk gaat, zal je gras nog steeds gemaaid worden.

De ontdekking dat evolutie goed als algoritme gebruikt kan worden om moeilijke problemen op te lossen is een slimme ontdekking geweest. Daarop voortbordurend kwam Tierra; het systeem dat open-ended evolutie gebruikt. De werkelijkheid lijkt (voor ons) meer op een model met open-ended evolutie dan een systeem met een voorgedefinieerde fitheidsfunctie. Misschien dat er in de toekomst ook open-ended evolutie op fysieke robotjes toegepast kan worden. Hier zouden weer verbazingwekkende oplossingen uit kunnen komen.

...en revolutie in Alife

Dankzij Alife zijn nieuwe inzichten ontstaan in oude problemen doordat componenten uitgesloten worden. Bijvoorbeeld in het voorbeeld van Hogeweg en Hesper. Maar of een artificieel model datgene weergeeft wat zich in de natuur afspeelt, blijft altijd de vraag. Als tegenwerping bij emergerende uitkomsten wordt wel gegeven dat dit emergerende gedrag helemaal niet zo opzienbarend is. De regels waar het gedrag uit voortvloeit zijn er tenslotte zelf door de programmeur ingestopt.

Interessanter wordt het als er verschillende vormen van emergent gedrag ontstaan. Wanneer er meerdere gedragingen emergeren en deze in elkaar uitgelegd kunnen worden, kunnen we spreken van revolutie! Dan doen de simpele regels die in het model zijn gestopt er niet meer toe en kan een artificieel model met dezelfde terminologie van de biologie uitgelegd worden. Dat is precies wat er op dit moment in Alife gebeurt. Een mooi voorbeeld daarvan zag ik in het werk van Walter de Back. Hij heeft drie emergerende patronen uit zijn Alife laten ontstaan. Dit zijn populatiedynamiek, evolutionaire dynamiek en ruimtelijke patronen. Hij bouwde het model om te laten zien dat interactie tussen patronen of processen licht kan werpen op complexe vraagstukken in de biologie.7 Je kunt het hier bekijken: http://walter.deback.net/media/netlogo/CA-restraint-web.html.

Noten

1. Neumann, John von en Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press, 1966.
2. Gardner, Martin, 'Mathematical games: The fantastic combinations of John Conway's new solitaire game "life"', in: Scientific American, 223, 1970, pp. 120-123.
3. Tijdens een workshop in Los Alamos National Galerie is de naam Artificial Life ontstaan. Deze eerste workshop over Artificial Life werd georganiseerd door Christopher G. Langton van het Center of the Santa Fe Institute (SFI).
4. http://www-binf.bio.uu.nl/BINF/littlinks/Hogeweg83.pdf.
5. Sims, K., 'Evolving Virtual Creatures', in: Computer Graphics (Siggraph '94 Proceedings), juli 1994, pp.15-22.
6. Ray, T.S., 'Evolution and optimization of digital organisms', in: K.R. Billingsley e.a. (eds.), Scientific Excellence in Supercomputing: The IBM 1990 Contest Prize Papers, The Baldwin Press, 1991, pp. 489-531.
7. Back W. de, Virtual Life: eco-evolutionary experiments, scriptie aan de filosofiefaculteit, Universiteit Utrecht, 2006.

Lees nóg een artikel over

biologie

kunstmatige intelligentie


of lees verder in

of deel

                   

Reageren




De redactie behoudt zich het recht voor om reacties in te korten of te verwijderen indien daar reden toe is.


           


Lees nóg een artikel over

biologie

kunstmatige intelligentie



Alle edities   Vakgebieden  
             
Wilt u op de hoogte gehouden worden van nieuwe edities en activiteiten van Blind? Meldt u aan voor onze digitale nieuwsbrief:



Het e-mailadres wordt alleen gebruikt voor toezending van de e-mail met de links naar de nieuwe editie. Het adres staat opgeslagen bij MailChimp. MailChimp hanteert een eigen privacybeleid waarmee u instemt als u zich abonneert op onze nieuwsbrief. Elke nieuwsbrief toont een link waarmee toezending kan worden gestopt. Om uw adres eventueel nog te laten verwijderen uit het opzeggingenbestand stuurt u een e-mail aan redactie@ziedaar.nl.