In zijn boek 'The Blind Watchmaker' uit 1986 laat zooloog Richard Dawkins zijn computer boompjes tekenen. De takken splitsen zich na een bepaalde lengte onder een bepaalde hoek, en ze doen dat een bepaald aantal keren. Deze eigenschappen, alsmede zes andere, zijn in het tekenprogramma te varieren. Dawkins noemt ze 'genen'.
Als hij de computer een nachtje heeft laten tekenen vindt Dawkins plaatjes, 'biomorfen', in een wonderbaarlijke diversiteit. Sommige lijken nog op bomen, maar er zijn ook vossekoppen, schorpioenen, schemerlampen en vliegtuigen. Vervolgens speelt de schrijver met de gedachte om een computer met een aanraakscherm in de tuin te zetten, met op dat scherm een willekeurige biomorf. Die zou dan omringd moeten zijn door een aantal varianten, waarbij steeds *een* 'gen' een beetje anders zou zijn. Er zouden ook genen bij moeten zijn die voor kleur coderen.
De computer zou bijhouden welke variant het meeste bezoek krijgt van insekten; het aanraakscherm is daar goed voor. Met het populairste exemplaar zou dan worden verder gekweekt. Die zou worden omringd door een aantal nieuwe varianten, de insekten konden weer een keus maken enzovoorts. Dawkins vraagt zich af of er op die manier mooie bloemen in de computer zouden evolueren. Dat is waarschijnlijk niet gebeurd, als hij het experiment al heeft uitgevoerd. De insekten zullen zich liever hebben beziggehouden met de kant-en-klare (en lekker ruikende) bloemen in de tuin dan mee te werken aan het ontstaan van elektronische surrogaten.
Het was geen handig idee van Dawkins om de selecterende krachten buiten de computer te houden. Biologen hebben zich intussen gestort op de computer als middel om de evolutie na te bootsen. Gesimplificeerde mannetjes, vrouwtjes, voedsel, parasieten en roofdieren krioelen vretend, parend en muterend over het scherm en als ze na een paar uur rekentijd zijn uitgeraasd kunnen de simulerende deskundigen conclusies trekken waarvoor ze anders een paar miljoen jaar natuurlijke selectie hadden moeten bijwonen.
Evolutie in de computer heeft meer toepassingen. Dat valt goed te illustreren aan de hand van het 'Prisoner's Dilemma', een beroemd model van een strategisch probleem. Het is voor te stellen als een spel. Twee spelers staan bij elke ronde van het spel voor de keus elkaar te 'helpen' of te 'verraden'. Verraden ze elkaar dan krijgen ze een kleine beloning, bijvoorbeeld 1 punt. Helpen ze elkaar dan worden ze beter beloond, zeg beide 3 punten. Als de %e%en helpt en de ander hem verraadt, dan krijgt de helper niets en de verrader een beloning die bijna twee keer zo hoog is als bij wederzijds helpen: 5 punten. Helpen is dus alleen gunstig als de ander dat ook doet. Verraden is het veiligste, maar de hoogste gezamenlijke beloning wordt bereikt als iedereen altijd helpt.
Een strategie hiervoor valt te baseren op de uitslagen van een aantal eerder gespeelde rondes, bijvoorbeeld drie stuks. Wie bijvoorbeeld drie keer achter elkaar is verraden zal dat waarschijnlijk de tegenstander de volgende keer betaald willen zetten. Elke ronde heeft vier mogelijke uitslagen (beide spelers kunnen helpen of verraden) dus drie rondes samen hebben 4x4x4=64 mogelijke uitslagen. Een strategie voor een computer die het Prisoner's Dilemma speelt bestaat eruit dat voor elk van die 64 mogelijkheden een keuze voor de volgende ronde wordt gegeven, een keuze dus tussen helpen of verraden. (Voor de eerste drie rondes van een spel moet een aparte keuze worden gemaakt.) Er zijn dus 2 tot de macht 64 strategieen. Om de beste te vinden kan men in de computer deze strategieen tegen elkaar laten uitkomen, maar het is niet doenlijk ze allemaal te testen - daarvoor zijn het er te veel.
De Amerikaan Robert Axelrod van de universiteit van Michigan heeft in plaats daarvan een soort evolutie gesimuleerd. Elke strategie valt voor te stellen als een lijst van 64 getallen: bij elk van de 64 voorgeschiedenissen een besluit voor de volgende ronde. Het besluit wordt voorgesteld door een 0 (verraden) of een 1 (helpen). Axelrod zette een aantal willekeurige strategieen bij elkaar in de computer en liet ze een competitie spelen. De slechtste gooide hij weg en de beste kruiste hij met elkaar. Dat wil zeggen, hij nam de strategie-lijsten twee aan twee, sneed elk paar op een willekeurige (maar wel op dezelfde) plaats door en verwisselde vervolgens de delen. De kop van de 'moeder' kwam aan de staart van de 'vader' te zitten en omgekeerd. De rij nullen en enen die de strategie vertegenwoordigde werd zogezegd opgevat als een chromosoom. Bij een deel van de paringen kon een mutatie voor een willekeurige verandering zorgen. Zo werden de geelimineerde slechte strategieen vervangen door nakomelingen van de betere en werd de competitie vervolgd.
In dit selectieproces ontstond al gauw 'Tit for Tat' (te vertalen als 'Oog om Oog' of 'Gelijke Munt'), een beroemde en succesvolle strategie voor het Prisoner's Dilemma. Tit for Tat begint met helpen en doet daarna telkens wat de tegenstander de vorige beurt heeft gedaan. Tit for Tat bekijkt dus niet alle drie de laatste beurten. Tot verrassing van de darwinistische programmeurs meldde zich na enige tijd een nog sterkere variant. Niet een die Tit for Tat in een rechtstreeks duel kon verslaan, maar een die meer punten kon scoren tegen dommere tegenstanders. Deze strategie hield wel rekening met alle drie de laatste beurten en pikte de zwakke broeders eruit, die twee keer of vaker konden worden verraden voor ze eventueel terugsloegen.
Voor dit soort grappen is de term 'genetische algoritmen' bedacht. Een recept dus om met een aan de biologie ontleende methode te komen tot een oplossing van een vraagstuk. Ook kunstmatige levensvormen in de computer zijn te zien als genetische algoritmen.
Het Prisoner's Dilemma lijkt misschien nog te veel een spelletje maar dat is zeker niet het geval met Evolver. Evolver is een computerprogramma; een hulpstuk voor bij het bekende spreadsheetprogramma Excel. Zo'n spreadsheet is een tabel met in elk vakje de waarde van de een of andere grootheid, bijvoorbeeld de verschillende kostenposten en bronnen van inkomsten van een bedrijf. De inhoud van sommige vakjes kan mede worden bepaald door de inhoud van andere; zo kunnen de verwachte verkoopcijfers afhankelijk worden gemaakt van de prijs van het produkt en van het bedrag dat aan reclame is besteed. De gebruiker bepaalt dit zelf omdat hij de berekeningen kan definieren. Is het spreadsheet naar wens ingericht, dan kan Evolver worden aangeroepen. Evolver zoekt de gunstigste combinatie van getalswaarden volgens een maatstaf die de gebruiker zelf vaststelt. Die moet namelijk aangeven van welk vakje in de tabel de waarde moet worden geoptimaliseerd. Het bedrijf zal de winst willen maximaliseren of de kosten willen minimaliseren.
Evolver vraagt dan eerst welke waarden niet mogen veranderen. Het kan zijn dat de salarissen niet ter discussie staan, en dat bepaalde uitgaven aan een maximum zijn gebonden. De inhoud van de vakjes waarmee Evolver wel mag 'spelen' gaat het programma nu opvatten als genen. De complete rij genen wordt weer als chromosoom behandeld. Evolver creeert een aantal willekeurige getallenreeksen en kijkt tot wat voor bedrijfsresultaat die aanleiding geven. De beste dringen dan door tot de tweede ronde, alwaar ze paren, en nakomelingen voortbrengen ter vervanging van de weggeselecteerde zwakkelingen. En zo gaat dat door tot aan een door de gebruiker opgegeven voorwaarde is voldaan. Dat kan een bepaalde tijdsduur of een bepaald aantal generaties zijn, maar ook een streefwaarde voor de te optimaliseren grootheid.
Volgens het bedrijf dat Evolver op de markt brengt, Axcelis in Seattle, zijn de gekste vraagstukken op deze manier op te lossen, als ze maar in een spreadsheet kunnen worden weergegeven. Als voorbeelden noemt Axcelis roosters ontwerpen en het probleem van de handelsreiziger: hoe de kortste weg te vinden wanneer een x-aantal plaatsen moet worden bezocht. 'Evolver begint waar andere optimalisatietechnieken het opgeven,' aldus Axcelis-woordvoerder Scott Kennedy. 'Je kunt de verzameling oplossingen van je probleem voorstellen als een heuvellandschap. De toppen van de heuvels zijn goede oplossingen. Je zoekt daarvan de beste, dus de hoogste top. Traditionele technieken gaan ergens in dat landschap staan en beginnen omhoog te wandelen tot ze een top vinden. Maar je weet dan niet of het ook de hoogste is. Evolver dropt een hele groep parachutisten. Degenen die op een veelbelovende plek staan krijgen hulp, de rest wordt in de steek gelaten. Zo heb je veel meer kans om de hoogste plaats te vinden.'
Waarom zou je eigenlijk alle slecht functionerende 'individuen' weggooien? Die kunnen toch in hun 'genoom' elementen hebben die in een andere combinatie van genen uiterst succesvol zijn? 'Klopt,' zegt Kennedy. 'Evolver kiest dan ook van 50 exemplaren de 40 beste, en dan nog tien willekeurige. De sleutel is: diversiteit. Je kunt ook het aantal mutaties per generatie bijregelen. Naarmate je dichter bij een oplossing komt is het goed om dat te laten toenemen, zodat het programma nog eens iets geks probeert. Maar dat is voor gevorderden, negen van de tien gebruikers doen dat nooit.' Zonder te adverteren heeft Axcelis in twee jaar tijd 800 exemplaren van Evolver verkocht, voor 350 dollar per stuk.
Je zult zelden zeker weten, geeft Kennedy toe, of je inderdaad de beste oplossing hebt. In het geval van het zenderpark (zie kadertekst) is dat het geval als je het maximale aantal mensen bereikt. Zolang je daaronder blijft weet je niet eens of zo'n complete oplossing bestaat. Het komt ook voor dat perfectie niet nodig is. Met behulp van Evolver heeft een Amerikaans bedrijf een systeem ontworpen dat op grond van een videobeeld de kwaliteit van munten beoordeelt voor verzamelaars. Menselijke deskundigen vertonen in hun beoordeling van de relevante eigenschappen een correlatie van 93%. Evolver wist hetzelfde niveau te bereiken.
Evolver moet voor alle zekerheid heel lang doorploeteren. Bij een bepaald voorbeeldprobleem, het indelen van een portefeuille waardepapieren in vijf ongeveer gelijke delen, is het programma na meer dan een uur nog ver verwijderd van de oplossing die het menselijk intellect in vijf minuutjes vond. 'Het gaat langzaam,' vindt ook Scott Kennedy. 'Maar je hoeft er niets voor van optimalisatie te weten en je kunt enorm complexe problemen oplossen.'
Genetiche algoritmen zijn hard bezig mode te worden, in navolging van de fuzzy (wazige) logica die tegenwoordig nogal wat Japanse wasmachines schijnt te bestieren. Met behulp van onder andere genetische algoritmen heeft General Electric een turbine ontworpen voor de motor van de Boeing 777. De motor is intussen gebouwd en wordt getest. Volgens een zegsman bij General Electric zijn er tot nu toe geen problemen en moet de motor over twee a drie jaar luchtwaardig zijn. Een elektronicabedrijfje in Oregon ontwikkelt op genetische wijze de architectuur voor chips, ook met Evolver trouwens. In Nederland werkt Cap Volmac (voorheen Cap Gemini) aan een Esprit-project waarbij met genetische technieken financiele modellen worden ontwikkeld, bijvoorbeeld voor het beoordelen van de kredietwaardigheid van klanten van een bank. Bij Cap Volmac zijn drie mensen met dit project bezig; in heel Europa zijn het er twintig. Voor een periode van twee jaar is daar vier miljoen Ecu mee gemoeid.
Aan de Katholieke Universiteit Nijmegen ontwikkelt de vakgroep Analytische Chemie op genetische wijze neurale netwerken. Dat is een manier van doen die wel bijzonder rijk is aan biologische associaties: neurale netwerken zijn immers structuren in een computer die in hun werking gelijkenis vertonen met hersenweefsel. Die netwerken worden gebruikt om aan de hand van infraroodspectra chemische stoffen te identificeren en om algen te determineren op grond van hun kleur-, reflectie- en fluorescentie-eigenschappen. Met genetische algoritmen worden de eigenschappen van het neurale netwerk gevarieerd om een architectuur te vinden die hen de gewenste taak het beste doet leren.
Een van de grootste successen met genetische algoritmen is behaald door de Amerikaanse telefoonmaatschappij US West. Onlangs moest dit bedrijf zijn communicatienetwerk herzien. In een paar uur rekentijd kwam er een ontwerp uit de bus dat menselijke ontwerpers een half jaar zou hebben gekost. Als ze al tot dat ontwerp gekomen zouden zijn: het genetisch ontwikkelde voorstel zat zo uitgekiend in elkaar dat het bedrijf 100 miljoen dollar bespaarde!
Japan doet intussen ook mee. Het roemruchte Ministerie van Handel en Industrie MITI heeft het initiatief genomen tot een Real World Computing Program, waarbij optische, parallelle en neurale computers centraal staan. Genetische algoritmen vormen daarbij een niet onbelangrijk 'bijvak'. Verschillende coryfeeen op dit gebied zijn door Japan ingehuurd. Daaronder bijvoorbeeld Thomas Ray, een van de pioniers van het gesimuleerde leven in de computer, en Bernard Manderick, een Belgisch informaticus in dienst van de Erasmus Universiteit. Manderick vertrekt in juli voor een half jaar naar Japan. 'Ze kopen inderdaad alle brains voor enige tijd op,' zegt hij. 'Het is de bedoeling om de theorie van het gedrag van genetische algoritmen beter te begrijpen. Het is daarnaast mijn opdracht om de toepassing op praktische problemen te bestuderen. Feitelijk ben ik volledig vrij in wat ik doe; ze zijn daar nog maar pas begonnen.'
Een speciale toepassing van genetische algoritmen is het genetisch programmeren. Daarbij ontstaan steeds betere computerprogramma's door kruising en selectie van ruwe versies. De uitvinder hiervan is John Koza, hoogleraar computerwetenschappen aan de Stanford Universiteit in Californie. Koza kreeg zijn eerste ideeen in deze richting in 1987. Zijn doel is te komen tot computerprogramma's zonder de machine expliciet te programmeren. De computer moet zichzelf kunnen programmeren wanneer hem een opgave onder de neus wordt gehouden. Als dat lukt, kan dat voor de praktijk betekenen dat er minder menselijke programmeurs nodig zijn. Daardoor kan de ontwikkeltijd van software korter worden en het eindprodukt goedkoper. Het is denkbaar dat er zo programmatuur tot stand komt voor problemen die voor mensen niet te overzien zijn.
Voor Koza is een computerprogramma een boomvormig schema, waarbij de uiteinden van de takken staan voor in te voeren gegevens en de kruispunten van takken voor rekenkundige of logische bewerkingen. Paren of kruisen van programma's doet Koza door takken van bomen te verwisselen. De te verwisselen takken hoeven daarbij niet van gelijke grootte te zijn. Uit twee formeel correcte programma's ontstaan op deze manier altijd twee nieuwe formeel correcte programma's.
Koza heeft een patent verkregen op programmatuur die computerprogramma's kan kruisen, beoordelen en selecteren. Hij heeft een 800 pagina's dik boek geschreven dat, volgens een deskundige, 'het vakgebied "genetisch programmeren" op poten heeft gezet'. Het boek is duidelijk geschreven voor experts op het gebied van genetische algoritmen, of mensen die dat willen worden, en daarom is het een uitkomst dat er ook een video verkrijgbaar is: 'Genetic Programming: The Movie'. De band is met weinig zorg gemaakt - Koza zit de hele tijd in hetzelfde shot zonder achtergrond het lesje op de dreunen dat kennelijk op een autocue voor zijn neus verschijnt, en op veel punten is er slordig gemonteerd. Maar instructief is het wel. Koza geeft een hele reeks voorbeelden van succesvol kweken van computerprogramma's.
Bijvoorbeeld de dubbele spiraal: in een vlak zijn twee reeksen punten getekend die elk tot een spiraal behoren. De ene spiraal blijft precies tussen de banen van de andere. De opgave voor het te kweken programma is, het vlak zo in twee domeinen te verdelen dat het ene domein de ene spiraal bevat en het andere domein de andere. Het aantal punten dat een programma goed rubriceert bepaalt de mate van 'fitheid'. De basisbewerkingen waar het programma mee werkt zijn natuurlijk geometrische functies. Die worden bij het 'paren' door elkaar gehusseld in de hoop dat er een combinatie ontstaat die goed werkt.
Het beste programma van generatie nul bestaat uit een horizontaal streepjespatroon en scoort 128 van de 194 punten goed. De beste van generatie 1, een verticaal zebrapad, doet het iets beter. De beste van generatie 3 bestaat uit onregelmatig meanderende banen (139 punten) en de winnaar van de zevende generatie is opeens weer een rij verticale balken, waarvan alleen de middelste scheidslijn in een sinusgolf is veranderd. Kennelijk is het ook hier zo dat een verzameling genen, na te zijn overtroffen, met een kleine aanpassing een comeback kan maken. Generatie 35 levert een kandidaat die maar *een* punt mist. Het is een reeks om elkaar heen geschreven vierkanten met ingewikkelde arceringen op de hoeken. Een generatie later is deze figuur met een minuscule verandering zo aangepast dat ook het laatste punt correct wordt ingedeeld. Het is, tussen twee haakjes, nagenoeg zeker dat bij herhaling van de hele procedure er een andere uitkomst uit de bus zou komen, in een ander aantal generaties. Dat is het geval bij de meeste voorbeelden van genetische algoritmen en hangt samen met het bij kruisen en muteren ingebouwde toevalselement.
Op vergelijkbare wijze komt Koza tot een programma dat een - gesimuleerde - bezem ondersteboven in evenwicht kan houden, een programma dat met maximaal succes het spelletje Pac Man speelt, *een* dat een plaatje natekent en nog veel meer. Een aantal bezwaren springt hierbij in het oog. In de eerste plaats stelt Koza met zijn voorbeelden de mogelijkheden van genetisch programmaren gunstiger voor dan ze zijn. Het programma met de spiralen classificeert alleen de punten van deze twee spiralen. Het programma dat plaatjes natekent, tekent *een* bepaald schermbeeld van 30 bij 30 pixels na. Afgezien van de zin van dergelijke operaties, als je een ander beeld eenzelfde behandeling zou wilen laten ondergaan, dan zou je daarvoor weer een heel nieuw programma moeten fokken. Gewoonlijk worden computerprogramma's juist geschreven voor een algemeen doel: het natekenen van een willekeurig plaatje, of het herkennen en classificeren van willekeurige wiskundige figuren. Het is duidelijk dat Koza daar nog lang niet aan toe is.
Een ander opvallend punt is de complexiteit van de programma's die uit Koza's selectieproces opduiken. Het zijn onnodig lange programma's met meervoudig samengestelde wiskundige functies, constanten met talloze decimalen en met een structuur die het een normaal mens onmogelijk maakt er iets van te begrijpen. Het probleem van de spiralen, te vangen in een elegant programmaatje van misschien twintig regels, wordt bij Koza een pagina vol met een onoverzichtelijke brij van getallen, letters en vooral veel haakjes. Dat is niet zo vreemd, want de hele methode van genetisch programmeren komt erop neer dat er lukraak met bewerkingen wordt gegoocheld tot er wat uit komt. Maar vervelend is het wel: aldus verkregen programma's voor werkelijk praktische toepassingen zullen veel geheugenruimte vergen, langzaam zijn in het gebruik en moeilijk op fouten te controleren.
'Die programma's worden inderdaad ingewikkelder en sowieso minder goed dan door mensen geschreven programma's,' meent Bernard Manderick van de Erasmus Universiteit. 'Eigenlijk is het een wonder dat er iets uit komt. Tot nu toe was het een one person's game. Maar sinds kort zijn er andere mensen op gesprongen die Koza's werk gaan reproduceren. Het moet nog allemaal gebeuren.' Inderdaad zijn Koza's prestaties, ondanks hun tekortkomingen, nu al verbazingwekkend. In 'The Blind Watchmaker' hamert Richard Dawkins steeds op het verschil tussen toeval en evolutie: een windvlaag kan geen berg vliegtuigonderdelen tot een Jumbo Jet assembleren. Evolutie, het door selectie gestuurde toeval, bereikt w&el de complexiteit van een Jumbo maar heeft daar miljoenen jaren voor nodig. Koza komt met zijn geforceerde evolutie in een paar uur rekentijd en een paar duizend generaties van een berg onderdelen tot iets dat werkt. Dat alleen is al een aanwijzing dat hij iets op het spoor is.