Van de Natuur kun je leren. Computerdeskundigen passen deze aloude wijsheid met succes toe op allerlei problemen die met gewone rekenmethoden niet of nauwelijks zijn aan te pakken, bijvoorbeeld ingewikkelde planningsproblemen, voorspelling van klantgedrag, en de besturing van robots. Het gaat om `evolutionair rekenen', waarvan de basisideeën zijn ontleend aan de biologische evolutietheorie. De methode werkt met een betrekkelijk willekeurige `populatie' van mogelijke oplossingen, waarvan volgens een `fitness' criterium de meest geschikte worden uitgekozen om zich voort te planten naar een volgende generatie door middel van mutatie en recombinatie. De verwachting is dan dat binnen een beperkt aantal generaties een `goede' oplossing is bereikt. Een groot voordeel is dat in elke generatie de oplossingen parallel kunnen worden getest op hun geschiktheid, hetgeen veel rekentijd wint. Op donderdag 18 maart promoveert Cees van Kemenade op onderzoek naar recombinatief evolutionair zoeken. Het onderzoek is verricht op het centrum voor Wiskunde en Informatica (CWI) te Amsterdam.
De motivatie voor het onderzoek van Van Kemenade laat zich illustreren met het volgende voorbeeld. Het slachtoffer van een misdaad wordt gevraagd te helpen bij het maken van een compositieschets. De gebruikelijke manier is om transparanten met bepaalde gelaatstrekken over elkaar te leggen. Vaak werkt dit niet goed omdat de getuige zich niet afzonderlijke gelaatstrekken kan herinneren, en dus niet kan zeggen waarom een bepaalde compositie al dan niet lijkt. Het begin jaren negentig in de VS ontwikkelde Faceprint systeem laat een getuige 20 willekeurig gegenereerde foto's zien, die deze een gelijkenis-cijfer moet geven. Nieuwe foto's worden verkregen door twee `ouder'-foto's te selecteren en hieruit door middel van een `genetische algoritme' foto's te genereren waarin de eigenschappen van de ouders op een bepaalde manier zijn gecombineerd. De kans dat een foto wordt geselecteerd als `ouder' is groter naarmate de foto een hoger cijfer krijgt. De nieuwe generatie foto's wordt weer aan de getuige voorgelegd, enzovoort. Het idee is dat gelijkende trekken in opeenvolgende generaties steeds duidelijker naar voren komen. De methode maakt geen gebruik van enige kennis vooraf, en het doel (het gezicht van de misdadiger, zoals opgeslagen in het geheugen van de getuige) is niet precies te omschrijven. De bereikte resultaten staken gunstig af bij de traditionele aanpak. Een belangrijke vraag is hier: volgens welke regels recombineer je de eigenschappen van de twee oorspronkelijke foto's om de twee nieuwe te krijgen? De aard van de recombinatie-operatie is vaak bepalend voor het succes van het evolutionaire rekenproces. Vandaar dat Van Kemenade zich in zijn onderzoek vooral op dit aspect richtte.
Het succes van biologische evolutie door selectie berust volgens Darwin op vier pijlers: reproduktie, variatie in overlevingskans, overerving van eigenschappen, en strijd om beperkte hulpbronnen. Evolutionaire rekenmethoden vertonen ook deze karakteristieken. Zij onderscheiden zich door hun algemeenheid: speciale voorkennis is niet vereist. Zij bouwen in de loop van hun operatie impliciet kennis op over wat een `goede' oplossing is. In die zin vormen evolutionaire methoden de tegenpool van expertsystemen, waarin juist van tevoren een heleboel specifieke kennis is gestopt. Dit betekent dat hun kracht vooral ligt in het oplossen van problemen die moeilijk zijn te modelleren door de aanwezigheid van allerlei ingewikkelde of vage criteria, of doordat de oplossing niet precies is te beschrijven. Veel praktijkproblemen zijn van die aard.
Met behulp van genetische algoritmen is door Van Kemenade onderzoek verricht naar het grootschalig managen van vliegverkeer, waardoor een efficiënter gebruik van het luchtruim mogelijk wordt. De ingewikkeldheid van de problematiek laat zich goed illustreren aan de hand van realistische versies van het bekende `handelsreizigersprobleem': het vinden van de kortste route langs een aantal steden zodat elke stad slechts éénmaal wordt bezocht. Dit is de kern van veel logistieke problemen. Voor het vinden van `goede' oplossingen (niet de optimale oplossing) in aanvaardbare rekentijd zijn diverse methoden ontwikkeld. In de praktijk zijn er echter nog allerlei voorwaarden (noodzakelijke en wenselijke). Bij goederentransport moet men bijvoorbeeld rekening houden met laden en lossen, beperkingen in rijroutes, tijdgebonden aflevering, rusttijden van chauffeurs, enzovoort. Ook kan men niet altijd aan alle voorwaarden tegelijk voldoen en veranderen die voorwaarden voortdurend omdat in de praktijk de omgeving nu eenmaal dynamisch is. De oplossingsmethode moet dus `adaptief' zijn, dat wil zeggen gemakkelijk aan te passen aan veranderde omstandigheden. In dergelijke situaties is de aanpak via evolutionaire rekenmethoden de aangewezen weg, tenminste als er een kwantitatief `fitness' criterium is aan te geven op basis waarvan selectie plaatsvindt.
Evolutionaire methoden worden vooral gebruikt bij het oplossen van ingewikkelde optimaliseringsproblemen met vele lokale optima, voor het ontwikkelen van adaptieve systemen, en ook om de biologische evolutie zelf te modelleren. Van Kemenade heeft zich voornamelijk gericht op het onderzoek van genetische algoritmen, waarbij het individu van een populatie wordt gerepresenteerd als een rij bits van vaste lengte, en het gebruik daarvan bij optimaliseringsproblemen. Recombinatie kan heel goed het parallelle karakter van populatie-gebaseerde zoekmethoden uitbuiten, want met die methoden is het mogelijk om eerst verschillende sterke eigenschappen van goede oplossingen onafhankelijk van elkaar te ontdekken en daarna pas te recombineren. Van Kemenade kan recombinatie-operaties aangeven waarmee in een aantal gevallen de oplossingsmethode duidelijk beter is dan bestaande methoden.
Naast dit promotie-onderzoek heeft hij zich op het CWI ook beziggehouden met het extraheren van informatie uit remote sensing opnamen van rampgebieden.
