Wie een Duitse auto rijdt, weet zich gerieflijk beschermd door een degelijke kooiconstructie. Maar tegelijkertijd is er geen automobilist die veel wil betalen aan de benzinepomp. Ziedaar het dilemma van de autofabrikant. Een auto moet veiligheid bieden door een stevige stalen constructie, maar al dat metaal mag de auto niet te zwaar maken.

Hoe moet een ontwerper nu bepalen waar een auto dik en stevig moet zijn, en waar er wel een onsje minder staal tegenaan mag? Hier bieden evolutionaire algoritmen uitkomst. Thomas Bäck is hoogleraar Natural Computing aan de Universiteit Leiden en gespecialiseerd in het toepassen van evolutionaire principes. Hij licht zijn werk toe aan de hand van het autoprobleem – dat ook in werkelijkheid met evolutionaire algoritmen werd opgelost. Bäck heeft een aantal Duitse autofabrikanten geadviseerd, waaronder BMW, die nu hun ontwerpen optimaliseren met de evolutionaire rekenmethode.

‘Stel dat je op honderd punten in de auto de dikte van het staal wil bepalen, en dat er tien mogelijke diktes zijn’, vertelt Bäck. ‘Dat resulteert in tien tot de macht honderd verschillende combinaties. Het is onmogelijk de computer voor al die configuraties te laten uitrekenen hoe zwaar en hoe veilig de auto ermee wordt. Computers kunnen berekeningen aan tot de ordegrootte van tien tot de dertigste, of tien tot de veertigste. Tien tot de honderdste is meer dan er deeltjes in het heelal zijn.’

Kandidaten

Met evolutionaire algoritmen kun je veel efficiënter toerekenen naar een optimale set staaldiktes, vertelt Bäck. Uitgangspunt vormt daarbij een populatie met zogeheten kandidaten. In het autovoorbeeld zijn dat vectoren met honderd getallen erin, de staaldiktes. Die vector kan worden samengesteld door een auto-expert, of willekeurig, door de computer. Een simulator berekent vervolgens van elke vector de kwaliteit: hoe presteert een auto met die set staaldiktes op het vlak van veiligheid, en hoe zwaar wordt hij. De kwalitatief beste kandidaten worden geselecteerd en vormen het uitgangspunt voor de volgende generatie.

Vervolgens creëert het programma – net als in de natuur – variatie. Dat gebeurt allereerst door mutaties: kleine veranderingen in de waarden in de vector. De getallen worden willekeurig gewijzigd, maar wel volgens een vaste waarschijnlijkheidsverdeling. Kleine veranderingen komen veelvuldig voor; grote veranderingen zijn ook mogelijk, maar veel minder frequent.

Het tweede variatiemechanisme is recombinatie. In de natuur, vertelt Bäck, zijn chromosomen vaak gelimiteerd tot acht cross-overs. Zijn computerprogramma’s kunnen per waarde kiezen welke ouderwaarde er wordt overgenomen.

Zo ontstaat een nieuwe generatie, waarbij elke geselecteerde oudervector meerdere nakomelingen voortbrengt. Dan volgt er een nieuwe ronde van toetsen, selecteren, variëren en reproduceren. Dit gaat net zo lang door tot de ideale kandidaat is gevonden, of tot de computer lang genoeg heeft gerekend. Dit kan men vooraf instellen. Per generatie die verstrijkt, komen de vectoren dichter bij een optimumconfiguratie. In het autovoorbeeld bestond de populatie uit tien individuen en werden twintig generaties gegenereerd, met in totaal dus tweehonderd ontwerpen die werden getoetst. Het leverde een veilige auto op, die toch vijf kilo lichter was geworden.

De overeenkomst met natuurlijke evolutie is evident. ‘Wij hebben de natuur als voorbeeld genomen’, vertelt Bäck. ‘Daar heb je het DNA, een enorme dataset van ongeveer drie miljard basenparen. Tijdens de evolutie is de volgorde daarvan in een heel korte tijd ontwikkeld. Die optimalisatie, zoals wij het noemen, hebben we nagebootst met de computer. Dat levert heel krachtige methoden op om problemen op te lossen.’ In het geval van het autoprobleem was het zelfs dé beste methode, durft hij te zeggen.

Optima

Evolutionairy computation ontstond in de jaren zestig en heeft zich sindsdien met name in de Verenigde Staten en Duitsland snel ontwikkeld. In Nederland werken er twee onderzoeksgroepen aan: de Leidse groep van Bäck en wetenschappers van de Vrije Universiteit. Uiteenlopende bedrijven passen de rekenmethoden al toe: van oliemaatschappijen tot metaalgieters en het LUMC, dat de beeldherkenningssoftware voor kijkoperaties ermee probeert te verbeteren.

Het proces verloopt overigens niet altijd helemaal via de computer. Van sommige producten bepaalt men de kwaliteit nog gewoon in real life. Van afwasmiddelen kan de computer bijvoorbeeld ‘kandidaatsamenstellingen’ voorrekenen die laboranten vervolgens daadwerkelijk testen. ‘Niet alles is nog te modelleren in de computer.’

Een ander probleem van de evolutionaire algoritmen is dat ze toerekenen naar één zogeheten lokaal optimum (zie afbeelding). Dat is niet per definitie de beste uitkomst, oftewel het globale optimum. In theorie, vertelt Bäck, kan de computer als hij oneindig veel tijd heeft, het globale optimum berekenen. In de praktijk is dat lastig: die berekening duurt eenvoudigweg te lang.

Bäck vindt dat de natuur hier toch nog beter functioneert dan computermodellen. Ook in de natuur zijn er meerdere lokale optima en één globaal optimum, maar door de altijd veranderende omgevingsfactoren blijven soorten voortdurend doorevolueren, richting steeds weer nieuwe optima. Onlangs heeft een promovendus een goede methode ontwikkeld om ook met de computer meerdere optima aan te wijzen, maar de voorbeelden uit de natuur blijven voor Bäck uitdagend. ‘Ik zou graag samenwerken met biologen om nog betere oplossingen te vinden.’

Lees ook

Oeps: Onbekende tag `feed’ met attributen {"url"=>"https://www.nemokennislink.nl/kernwoorden/auto/index.atom?m=of", “max”=>"5", “detail”=>"minder"}