Zal de technologie zich als tweede natuur waarmaken, nu softwareontwikkelaars het ontwikkelingsmechanisme ’evolutie’ inzetten voor het ’kweken’ van software? Genetische algoritmen hebben in elk geval in de letterlijke digitale evolutie hun sporen verdiend. Het genetisch programmeren van software is de
volgende stap in de toepassing van genetische algoritmen: computers die zelf software evolueren om de complexe problemen op te lossen die de mens tot nu toe boven de pet gaan.

CHRIS NAP
Sinds John Holland in het begin van de jaren zestig de idee opperde om het biologische evolutieprincipe in de vorm van genetische algoritmen te gebruiken voor het produceren van software-oplossingen, is de fascinatie voor de evolutionair bioloog Charles Darwin groot onder computertechnologen.
Niet voor niets dragen toetsenborden, werkstations, allerlei softwarepakketten, dynamische database servers,
digitale recorders en direct marketing-technologieën voor Internet zijn naam.
De toepassing van de biologische afstammingsleer in genetische algoritmen heeft computerprogrammeurs geen windeieren gelegd en is de fase van ’veelbelovende nieuwe technologie’ gepasseerd. Inmiddels zijn talloze succesvolle toepassingen van genetische algoritmen gevonden. Ze variëren van de classificatie van eiwitten en het voorspellen van structuureigenschappen van verschillende soorten naaigaren, tot de optimalisatie van ontwerpen voor vliegwielen, auto’s, bruggen en satellieten.

Genetisch programmeren
Een nieuw en belangwekkend toepassingsterrein van genetische algoritmen ligt in het genetisch programmeren: de automatische synthese van programma’s. Daarbij wordt gebruik gemaakt van Darwinistische natuurlijke selectie en op de biologie geïnspireerde bewerkingen als recombinatie, mutatie, inversie, duplicatie en verwijdering van ’genen’ in software-chromosomen. Het doel is computers problemen op te laten lossen, zonder dat ze er expliciet voor zijn geprogrammeerd.
Genetische programma’s komen tot stand door een evolutieproces dat toewerkt naar een oplossing voor een van te voren scherp gedefinieerd probleem. Een programma wordt voorgesteld als een chromosoom, een streng van enen en nullen, die alle eigenschappen van een programma representeert.
Uit een verzameling van een groot aantal van deze chromosomen, vormt een genetisch algoritme een combinatie van eigenschappen, die het programma nodig heeft om het vooraf gedefinieerde probleem zo goed mogelijk op te lossen.
Door kruising van twee chromosomen uit de verzameling en mutatie van losse chromosomen, maakt een genetisch algoritme nieuwe chromosomen, die steeds een afwijkende combinatie van eigenschappen in zich dragen. Bij kruising van chromosomen, de technische term is ’cross-over’, knipt een genetisch algoritme twee chromosomen op een willekeurige plaats doormidden. Chromosoom A krijgt het losgeknipte deel van chromosoom B en vice versa. De twee nieuwe chromosomen zijn onderdeel van de volgende generatie. Mutatie van chromosomen betekent dat in de streng enen en nullen de waarde van een enkel cijfer wordt aangepast: een één wordt een nul bijvoorbeeld.
Elke nieuwe generatie chromosomen wordt onderworpen aan een zogeheten ’fitnesstest’, om te beoordelen hoe goed of slecht een chromosoom in staat is een goed antwoord te geven op de gestelde vraag. Door met de beste chromosomen uit elke nieuwe generatie verder te ’fokken’, kan na vele generaties een zeer goede oplossing ontstaan. Een perfecte of optimale oplossing kan bij genetisch programmeren niet worden gegarandeerd. Dat komt door het inherente toevalselement in de methode. Genetisch programmeren vergt verder enorme rekencapaciteit, wat overigens een steeds minder groot probleem is.

Grondlegger
De grondlegger van genetisch programmeren, John R. Koza, is één van de eerste leerlingen van John Holland, de geestelijk vader van genetische algoritmen. Koza is professor Medische Informatica aan de Stanford University. Hij is gefascineerd door automatische programma-inductie: computers zelf problemen laten oplossen.
Koza heeft zich tot nu toe, naast het schrijven van dikke boeken over GP, vooral bezig gehouden met het oplossen van theoretische problemen (’toy-problems’) met genetisch programmeren. Nu is het volgens hem tijd voor non-triviale resultaten die kunnen concurreren met menselijke programmeerprestaties.
Koza: „Genetisch programmeren kan een resultaat geven dat iets beter, gelijk, of iets slechter is dan door mensenhanden gemaakte programma’s. Ook kan een genetisch programma gelijk zijn aan een in het verleden gedane uitvinding of nu als nieuwe uitvinding worden gepatenteerd. Een genetisch programma kan ook in een wedstrijd met menselijke tegenstanders hoge ogen scoren.” Volgens Koza zijn er van al deze categorieën voorbeelden te geven. Volgend jaar komt zijn derde dikke boek uit over genetisch programmeren (Genetic Programming III).
Recent en lopend onderzoek van Koza’s groep gaat in op de automatische synthese van analoge elektrische circuits, computingproblemen in moleculaire biologie, ’evoluerende hardware’ en het gebruik van FPGA’s (field-programmable gate arrays) en problemen met optimale controle.

Omega
In Nederland houdt vooral de academische wereld zich met genetisch programmeren bezig. Eén van de uitzonderingen is het Omega-project van Cap Gemini. Omega is een genetisch programmeersysteem voor het ontwikkelen van hoogwaardige voorspellende modellen. Cap Gemini gebruikt bijvoorbeeld een Omega-model om te voorspellen hoe groot de kans is dat patiënten na een operatie in een ziekenhuis misselijk zullen worden. Op basis van een zeer grote hoeveelheid gegevens van patiënten, zoekt een genetische zoekmachine naar verbanden in
de gegevens. Arnold Koudijs is een van de onderzoekers die bij het project is betrokken. „Het voordeel van genetisch programmeren is dat er programma’s ontstaan waarvan de structuur niet vastligt”, zegt Koudijs. „De structuur van een programma wordt bepaald door
de verbanden die in een verzameling
gegevens worden aangetroffen.”
„De voorspellende modellen worden in twee fasen gebouwd. De eerste fase bevat een data-analyse en een intensieve zoektocht in de gegevens van een databank naar paren van variabelen die de grootste voorspellende kracht bezitten. In de tweede fase dienen deze variabelen-paren als input voor de genetische modelleermachine. Vervolgens vindt er multivariabele optimalisatie plaats door middel van een genetisch programmeerschema, waarbij de parameters dynamisch bijgesteld worden voor opeenvolgende generaties.”
Het evolutionair geprogrammeerde model dat er uiteindelijk uitrolt, is in staat te voorspellen of een bepaalde patiënt na de operatie misselijk zal worden. Een ziekenhuis kan die informatie gebruiken om preventieve maatregelen te nemen.
Volgens Koudijs levert een genetisch geprogrammeerd model betere prestaties dan andere statistische methodieken. „Het toepassen van GP op problemen met een bovengemiddelde complexiteit is zinvol omdat de prestaties van GP beter zijn dan die van klassieke data-analysetechnieken. We hebben dat onderzocht. Omega-modellen verslaan concurrerende voorspellingstechnieken als neurale netwerken, logistieke regressie, discriminante analyse en ’Rough Data Analysis/Modelling’.”

Onoplosbare problemen
Volgens Steven Verver en Chris Twigt van het Amsterdamse softwarebedrijfje Basket Builders, ligt de belofte van GP in het oplossen van ’onoplosbare’ problemen. Verver: „Dat wil zeggen: problemen waar op analytische wijze geen antwoord op te geven is. Bijvoorbeeld het voorspellen van de beurskoersen of het weer en het oplossen van planningsproblemen.” GP is overigens volgens Twigt zeker geen tovermiddel. „Je wilt eigenlijk tegen je computer zeggen: ’Dit is het probleem, maak mij een programma dat het probleem oplost.’ Je geeft je computer een hoeveelheid
instructies waarmee het programma gemaakt moet worden. Dan moet je een evaluatiefunctie invoeren, op basis waarvan de computer beoordeelt hoe goed een programma het probleem heeft opgelost. Dat is de fitness-test. Het formuleren van de evaluatiefunctie is een van de moeilijkheden van GP. Hoe ingewikkelder het probleem, hoe lastiger het is om de computer die fitnesstest uit te laten voeren op basis van de evaluatie.” Inzicht in het probleem blijft volgens Twigt daarom van cruciaal belang. Het gebrek aan inzicht in de ’onoplosbare’ problemen is een belangrijke oorzaak van die onoplosbaarheid.

Simplificatie
Verver meent dat het toepassen van kruising en selectie een te grove simplificatie is van het biologische evolutieproces. „Zo is het principe van zelforganisatie van cellen een belangrijk gegeven in de natuur, waarover nog te weinig bekend is. Als we in staat zijn om ook deze aspecten in het genetisch programmeren te verwerken, kunnen we wellicht een doorbraak verwachten.”
Volgens Koudijs zijn onderzoekers die zich met genetisch programmeren bezighouden gespitst op de ontwikkelingen in de biologische genetica. „We proberen de natuur zo goed mogelijk in GP na te bootsen. Zo experimenteren we met het toekennen van een geslacht aan de gevonden modellen en zijn we op zoek naar manieren om ’incest’ onder de modellen te voorkomen. We zijn bezig ’ziektes’ of virussen in de modellen te introduceren om er een zekere resistentie in op te bouwen.
Koudijs is positiever over de doorbraak van genetisch programmeren dan Basket Builders. Hij voorziet al binnen
enkele jaren een doorbraak. „Het hoofdzakelijk wetenschappelijke wereldje dat zich met GP bezighoudt, maakt zich op voor die doorbraak. De toepassingen zijn zeer divers, alleen de bekendheid van GP laat te wensen over. Het kan een paar jaar duren, maar dan zal er zeker een sneeuwbaleffect optreden. Genetisch programmeren heeft vele beloften in zich en zal die ook waarmaken.” Ook Verver en Twigt prijzen de schoonheid van de genetisch geprogrammeerde oplossingen. Twigt: „Als je niet beter zou weten zou je gaan denken dat er intelligentie en creativiteit in het spel zijn.”
Genetisch programmeren veelbelovend? Er is een aantal op toepassingen gerichte onderzoeksprojecten dat de stempel ’vertrouwelijk’ draagt, vanwege het mogelijk concurrentievoordeel dat eruit voort kan komen.
Genetisch programmeren mag nog in de kinderschoenen staan, de bereikte resultaten zijn op zijn minst spannend te noemen. In de woorden van Koza: „We hebben nu een teen tussen de deur gekregen, vooral door aanhoudend positieve berichten van het front. Je kunt je ogen sluiten voor de eerste onderzoeksrapporten. Je kunt de eerste applicaties afdanken op tien goede gronden, maar als de bewijzen zich opstapelen, valt het steeds moeilijker te negeren.”