In de natuur bestaan verschillen tussen soorten, maar ook binnen een soort. Nakomelingen krijgen hun genen (het erfelijk materiaal) van beide ouders. Hierdoor zijn ze niet identiek aan hun ouders of broers en zussen. Ook kunnen er spontane veranderingen optreden in de genen – mutaties – waardoor er nog meer verschil ontstaat. Evolutie door natuurlijke selectie is het proces dat uit al die genetische variatie de organismen selecteert die het best aan hun omgeving zijn aangepast. Dat zijn de organismen die overleven, ofwel: ‘survival of the fittest’.
Dit proces is de inspiratiebron voor een methode die bekendstaat als evolutionaire strategie. Het wordt veelvuldig toegepast bij problemen die niet eenvoudig (wiskundig) zijn op te lossen. Evolutionaire strategie bootst de principes van de evolutie door natuurlijke selectie na: het doorgeven van door elkaar gehusselde genen van ouders op kind, toevallige mutaties en selectie van de meeste ‘fitte’ nakomelingen.
In de ICT is het ‘genetisch algoritme’ zeer bekend, maar evolutionaire strategieën worden op allerhande gebieden toegepast, zoals marketing, robotica, sociale wetenschappen en natuurkunde. En bij koffierecepten.
Koffie is volksdrank nummer één in veel landen en de best smakende merken zijn meestal ook de duurste. Koffie is een mengsel van soorten. Door variërende oogsten stellen experts de melange telkens opnieuw samen, maar wel zó dat de koffie altijd dezelfde smaak heeft.
Gefinetuned
In een experiment werd een evolutionaire strategie losgelaten op het mengen van koffie. De gebruikte koffiemachine doseert tot op de milliliter nauwkeurig en mengt vijf goedkope koffiesoorten met elkaar. Bij de start van het experiment combineerde de machine de vijf soorten willekeurig tot vijf nieuwe koffievarianten. Een testpanel van studenten beoordeelde welke smaak het dichtst in de buurt kwam van een bepaalde dure merkkoffie.
De koffiemachine veranderde (evolueerde) de samenstelling van het beste mengsel een beetje, en weer proefde het testpanel de nieuwe varianten. Na diverse rondes was de samenstelling zo gefinetuned dat de smaak niet meer te onderscheiden was van de merkkoffie – maar wel 25 procent goedkoper.
Een voorbeeld van evolutionaire strategieën in de techniek is lopende robots. Stel, een op een mier geïnspireerde robot heeft zes poten. Om deze kunstmier te programmeren zodat hij kan lopen is een enorme klus. En als de robot uiteindelijk netjes over een gladde vloer kan lopen, dan zit hij bij de eerste de beste drempel vast of ligt hij met zijn pootjes in de lucht. Dan kunnen de programmeurs opnieuw aan de slag om de robot te programmeren om over een drempel te lopen. En over alle andere obstakels.
Geduld
Een andere manier om robots te laten lopen is door ze het zelf uit te laten zoeken. De kunstmier kan dan zijn poten bewegen, maar van lopen – welke poot, wanneer en in welke volgorde – ‘weet’ hij niets. De robot wordt voorzien van software met een evolutionaire strategie. Ook hier begint de kunstmier willekeurig zijn poten te bewegen, wat natuurlijk in een amechtig gespartel resulteert.
Maar sommige pogingen zijn vruchtbaarder dan andere. Deze probeersels worden geselecteerd en geëvolueerd. Wederom doet de robot een dappere poging om te lopen, enzovoort. Na een tijd gaat het spartelen uiteindelijk over in succesvol voortbewegen. Ook leert de robot zichzelf om met obstakels om te gaan.
Het programmeren van een evolutionaire strategie is veel minder werk dan het ‘hard’ inprogrammeren van de pootbewegingen. Het is vooral een kwestie van geduld. Terwijl de kunstmier leert lopen, kunnen de programmeurs rustig weggaan om (goedkope) koffie te drinken.
Gepubliceerd in dagblad Trouw op 6 juni 2017
De evolutionaire strategie vindt optimale waarden voor de factoren die de oplossing van een gegeven probleem bepalen. Deze factoren worden gerepresenteerd door ‘genen’, in de figuur voorgesteld als de vorm van de ogen, de oren, het gezicht en de mond. De methode begint met een willekeurige startpopulatie, in de figuur te zien als individuen met willekeurige vormen van de ogen, oren, enzovoort. Vervolgens wordt bepaald welke individuen het beste (of het minst slecht) in de buurt komen van een goede oplossing. Deze worden geselecteerd en dienen als ‘ouders’ voor de volgende generatie. Door de genen van de ouders te mengen en ze een beetje te muteren, ontstaat zo een nieuwe populatie. De nakomelingen in de figuur zijn ontstaan door de ogen, oren (enzovoort) van de ouders te combineren (reproductie) en door sommige vormen een beetje te veranderen (mutatie). Ook van deze nieuwe populatie wordt weer bepaald welke individuen het dichtst in de buurt komen van een goede oplossing. Dit proces herhaalt zich totdat aan een bepaald stopcriterium is voldaan, en de beste waarden voor de factoren (‘genen’) die de oplossing bepalen bekend zijn.
Overzicht van alle columns