EVOLUTIE PER COMPUTER HEEFT VELE TOEPASSINGEN

Eschers fokken

Ontwerpen via darwinistische methoden, waarbij de mooiste tussenresultaten zich mogen `voortplanten', levert verrassende resultaten op. De grillige uitkomsten van evolutionary computing.

`IS DIT EEN Escher? Echt niet', zegt de jongen tegen zijn klasgenoten. De klas in het Haags Gemeentemuseum is onverbiddelijk. Achter elkaar drukken vijf leerlingen op de rode knop onder het platte beeldscherm, dat als een klein kleurig schilderij tussen de gewone Escher-prenten hangt. De afbeelding, een patroon van vervormde vierkanten, opgevuld met lijntjes en stipjes die op ogen lijken, lijkt op een poging van Escher om eens een keer amoeben te gebruiken voor zijn vlakvullende patronen, in plaats van de gebruikelijke vogels, vissen en salamanders.

`Hier kunt u zelf Escher-achtige motieven kweken', aldus de uitleg onder het scherm. Computers simuleren evolutie volgens Darwin: het publiek selecteert van de zes verschillende plaatjes de mooiste door te stemmen met de rode of de groene knop. De plaatjes met de meeste stemmen krijgen de grootste kans om zich voort te planten. Uit een kruising van zulke uitverkorenen ontstaat om de twintig minuten een een nieuwe generatie: zes nep-Eschers, die hopelijk al wat meer trekken hebben van het werk van de meestergraficus.

``Het is een evolutie-experiment, met subjectieve selectie in plaats van natuurlijke', zegt Guszti Eiben. Eiben is hoogleraar informatica bij het informatica-instituut LIACS (Leiden Institute of Advanced Computer Science) van de Universiteit Leiden en bij de Vrije Universiteit in Amsterdam. Zijn Leidse studenten hebben het Escher-evolutieprogramma geprogrammeerd. De patronen zijn opgebouwd aan de hand van een reeks getallen bij wijze van erfelijk materiaal, legt Eiben uit. De reeks codeert voor de verschillende vormen, vervormingen, aantallen strepen en stippen in het patroon van de nep-Escher. Eiben: ``Je zou het het digitaal DNA kunnen noemen.' Bij het kruisen van twee afbeeldingen worden stukken uit twee reeksen genomen en aan elkaar geplakt tot één reeks, net zoals dat met DNA van levende organismen gebeurt bij seksuele voortplanting. Naar analogie van mutaties in echt DNA worden er ook wat willekeurige veranderingen in de code aangebracht.

Het Escher-DNA bevat maar enkele tientallen tekens in plaats van de duizenden tot miljarden in echt DNA. Daardoor is mogelijke variatie en complexiteit in de gekweekte Eschers beperkt. ``Het experiment hoeft ook niet per se een echte Escher op te leveren', nuanceert Eiben dan ook. ``Ik ben al heel tevreden als er interessante plaatjes uit voortkomen, en af en toe heb ik wel intrigerende patronen voorbij zien gaan.'

``Het begon met een grap in de kantine over een Mondriaan-generator', vertelt Eiben. Een student programmeerde vervolgens een computerprogramma dat Mondriaan-achtige afbeeldingen laat evolueren. Snel was het idee geboren om het Haags Gemeentemuseum te benaderen. ``Aanvankelijk waren ze afhoudend, maar toen ze erachter kwamen dat het plan niet neer hoefde te komen op een reeks pc's in een computerruimte, werden ze enthousiaster', vertelt Eiben. Besloten werd het idee aan te passen voor Eschers vlakverdelingen, om de jaarlijkse Escher-tentoonstelling luister bij te zetten.

Het idee om kunst op een darwinistische manier te laten evolueren is niet nieuw. Eerder is het gebruikt voor het ontwerpen van koffietafeltjes, muzikale composities en koffiemelanges. Maar vaker worden darwinistische methoden toegepast op ontwerpproblemen. Telecommunicatienetwerken, vliegwielen, verfmengsels, elektronische schakelingen, onderdelen voor vliegtuigmotoren, medicijnen en erg toepasselijk eiwitten zijn langs deze weg ontworpen. Ook abstractere taken zijn met deze methoden aangepakt: routes plannen, roosters optimaliseren, strategieën voor data mining (zoeken in grote bestanden), dammen en het ontwikkelen van nieuwe manoeuvres in vliegtuiggevechten. Eibens toegepaste onderzoek richt zich onder andere op het laten evolueren van formules waarmee banken de kredietwaardigheid van klanten in kunnen schatten op grond van persoonlijke gegevens uit een database.

alan turing

Informatica-pionier Alan Turing noemde het idee van kunstmatige darwinistische evolutie voor het eerst in een artikel in 1948, in een terzijde over de methoden waarop computers intelligentie zouden kunnen simuleren. Sinds het midden van de jaren zestig werkte een handjevol onderzoeksgroepen vrijwel onafhankelijk aan zulke methoden, onder de noemers `genetische algoritmen', `evolutionair programmeren' en `evolutionaire strategieën'. Deze benaderingen verschillen in belangrijke onderdelen van elkaar: het gaat achtereenvolgens om de structuur van het DNA, de manieren van kruisen en nakomelingen verwekken en de manier om de grootte van het nageslacht te bepalen. Maar het basisidee is hetzelfde: oplossingen voor een gegeven probleem laten evolueren zoals de natuur het zelf doet.

In de loop van de jaren tachtig kwamen de verschillende onderzoeksgroepen met elkaar in contact, en namen anderen het idee over. Het vakgebied werd bekend onder de paraplu-term Evolutionary Computing, met eigen congressen, tijdschriften, en een toenemend aantal industriële en wetenschappelijke toepassingen. De mogelijkheden groeien door snellere computers en de ontwikkeling van technieken om computers parallel, in teamverband, te laten rekenen.

Een opvallend succes van de techniek is het onorthodoxe ontwerp voor een antennehouder voor satellieten van de hand van Andy Keane, industrieel ontwerper aan de universiteit van Southampton. De antennehouder, een frame van aluminium buizen, zou zo weinig mogelijk trillingen van de satelliet naar de antenne door moeten geven. De positie van de antenne luistert vaak heel nauw: op fracties van een millimeter nauwkeurig.

bizar

Keane gebruikte de reeks posities waar de buizen van het frame met elkaar verbonden zijn als erfelijk materiaal, en zette elf computers aan het rekenen. Bij elke stap `fokte' hij honderd verschillende virtuele antennehouders, nakomelingen van de vorige generatie. De computers berekenden het trillingsgedrag en de minst trillingsgevoelige houders kregen de beste kansen op nageslacht. De totale rekentijd voor tien generaties kwam uit op 2.000 uur, door de computers volgemaakt in twee weken. Het resultaat is bizar. De antennehouder, met een 200 keer betere demping van trillingen in het uitgekozen frequentiegebied, ziet er gedraaid en schots en scheef uit. Niet iets waar een menselijke ontwerper snel mee aan zou komen. Keane bouwde de houder in het echt na: de trillingseigenschappen bleken goed met de berekende karakteristieken overeen te komen. Hij is nu bezig een prototype te bouwen voor het Frans-Britse satellietenbouwersconsortium Astrium.

Daarnaast werkt Keane aan het evolutionair stroomlijnen van vliegtuigvleugels voor de vliegtuigonderdelenproducent British Aerospace Systems. Volgens de Brit toont de antennehouder aan hoe evolutionary computing een ontwerper kan wijzen op nieuwe of uit het oog verloren ontwerpprincipes. ``We hebben uitgezocht waarom het nieuwe ontwerp er zo raar uit zag', zegt hij. ``Trillingen in balken worden bij iedere verbinding deels overgedragen, en deels teruggekaatst. Verbindingen die van elkaar verschillen in de hoeken tussen de buizen, laten verschillende frequenties door. Als je dus zoveel mogelijk verschillende verbindingen gebruikt, is het mogelijk om een groot deel van de frequenties weg te filteren vóór het uiteinde van de houder. Dat lijkt een heel simpel principe, maar niemand was er eerder opgekomen.' Evolutionaire methoden brengen vaak uitkomst als het te optimaliseren ontwerp veel parameters telt, is Keane's ervaring. Is dat niet het geval, dan zijn traditionele optimaliseringsmethoden meestal sneller.

``Het kost inderdaad vaak veel rekentijd', noemt Eiben een nadeel van de evolutionaire rekenmethoden. ``Het resultaat is bovendien vaak onvoorspelbaar. Je weet nooit van tevoren of het werkt. En soms hangt dat sterk af van de variant van evolutionary computing die je gebruikt.' Een voordeel is dat je je ontwerpprobleem niet diepgaand hoeft te analyseren om een evolutionaire methode er op los te kunnen laten, aldus Eiben. Al is zulke kennis wel nodig voor het analyseren van een nieuw geëvolueerde oplossing, zoals Keane deed. Eiben: ``En sommige problemen, zoals vertalen via de computer of het doen van nauwkeurige berekeningen, liggen volkomen buiten het bereik van evolutionary computing.'

De tentoonstelling `Echt en Virtueel' in het Haags Gemeentemuseum is nog te zien t/m 8 oktober.

Bruno van Wayenburg, NRC Handelsblad, 1 juli 2000