Revue 1994 - pagina 83

Onderzoek

Strijd om het bestaan in een computer

Informatici experimenteren met evolutie Arjan Spit

De Faculteit der Wisl<unde en Informatica is niet zachtzinnig voor haar zelfgekweekte beestjes. Halve generaties worden uitgemoord en geregeld moeten de beestjes onder dwang met zijn vijven tegelijk paren. Maar wiskundige Gusti Eiben kent geen scrupules: de populaties beestjes vormen de kern van zijn genetische algoritmen. Door inzichten uit de biologische evolutieleer toe te passen op deze populaties van genetische algoritmen kunnen we problemen met een nieuwe methode oplossen. Al planten ze zich voort en sterven bepaalde variaties uit, uiteindelijk zijn de 'beestjes' niet meer dan digitale computercodes. Genetische algoritmen vormen een nieuwe onderzoeksthema van de Artificiële Intelligentie, geïnspireerd door het succes van de biologische evolutie. Vandaar dat Gusti Eiben (33), de specialist van de VU, spreekt over zijn 'beestjes', die paren, kinderen krijgen en vechten om de survival of the fittest. Als voorbeeld van een toepassing van de genetische algoritmen noemt hij het klassieke probleem van de handelsreiziger: bepaal de kortste route door pakweg dertig verschillende steden. In het genetische algoritme staat elk beestje, elk individu, in dat geval voor een willekeurige route. Het programma begint te draaien met een populatie van bijvoorbeeld honderd individuen, dus honderd routes. Van deze willekeurige routes bepaalt het programma vervolgens de fitness, die afhankelijk is van het specifieke probleem dat onder handen is. In dit geval is het individu met de kortste route de meest

vrije Universiteit

amsterdam

aangepaste. Analoog aan de biologische evolutie krijgt die ook de meeste mogelijkheden om zich te vermenigvuldigen, door te paren met andere individuen. In de nieuwe generatie ontstaan daardoor betere oplossingen. Zo ontwikkelt de populatie zich, met steeds kortere routes tot gevolg. Omdat het proces van toeval afhankelijk is, wordt de optimale oplossing niet met zekerheid gevonden. Maar na elke generatie kan het algoritme stoppen en de beste benadering geven. Waar komen de kindjes van computercodes vandaan? Eiben geeft voorlichting: "Bij de meeste genetische algoritmen is elk individu een binaire rij, een rij nullen en enen met een vaste lengte. Het paren is meestal een éénpunts cross-over. Je legt de twee lijnen boven elkaar en kiest een willekeurig punt, ergens in het midden. Daar hakje hen in tweeën en je verwisselt de uiteinden van de rijen. Dat zijn de kinderen. Het eerste stukje van een kind komt van vader, het tweede van moeder. Bij het andere kind is het andersom. Dus elk kind lijkt een beetje op vader en een beetje op moeder, net als bij biologische genen." Evenals in de biologische reproduktie treden er verder ook spontane mutaties op in de genen van de digitale individuen: een willekeurige één verandert in een nul of vice versa. Verschillende inzichten vanuit de biologie kunnen het basale algoritme verbeteren en het evolutieproces versnellen. Eiben: "Wat wij bijvoorbeeld onlangs hebben geprobeerd is incestpreventie. Dus als je de ouders kiest, let je erop dat ze geen familie van elkaar zijn, dat ze bijvoorbeeld niet van elkaar afstammen. Het blijkt datje met die incestpreventie verder komt in de evolutie, omdat incest leidt tot individuen die te veel op elkaar gaan lijken. Dat is waarschijnlijk ook de biologische achtergrond van incestpreventie." Maar sommige genetische algoritmen gaan voorbij de grenzen van de biologische evolutie.

Onderzoek

Deze tekst is geautomatiseerd gemaakt en kan nog fouten bevatten. Digibron werkt voortdurend aan correctie. Klik voor het origineel door naar de pdf. Voor opmerkingen, vragen, informatie: contact.

Op Digibron -en alle daarin opgenomen content- is het databankrecht van toepassing. Gebruiksvoorwaarden. Data protection law applies to Digibron and the content of this database. Terms of use.

Printen