Algoritmes zijn complexer en veelomvattender dan ooit tevoren, maar ook veel minder zichtbaar juist doordat ze in ons technologische tijdperk in alles en overal aanwezig zijn. We merken ze pas op als ze niet meer goed werken. Wat zijn algoritmes en wat doen ze zoal voor ons?
Wat is een algoritme?
Het woord algoritme roept al snel het beeld op van een computer die een moeilijk wiskundig probleem oplost. Maar in essentie is een algoritme niets anders dan een eindige set instructies voor het bereiken van een doel. Als je het op die manier bekijkt, is een recept voor het koken van een lekkere maaltijd ook een algoritme, maar de term zal toch vaker met getallen en computers geassocieerd worden. Over het algemeen wordt bij zulke algoritmes informatie verwerkt. Wiskunde is wel degelijk belangrijk, bijvoorbeeld voor het in een model beschrijven van een probleem, wat de zogenoemde oplossingsruimte bepaalt. Het algoritme is een slimme manier om daarbinnen de best mogelijke oplossing te vinden. Een goed algoritme heeft als kenmerken dat het zowel correct is als efficiënt. Dat laatste betekent dat de oplossing met zo min mogelijk stappen – zo min mogelijk rekenkracht – gevonden wordt. Dankzij een algoritme hoeft de gebruiker ervan geen inzicht in het probleem te hebben om deze te kunnen oplossen, de bedenker van het algoritme juist heel veel (zie kader).
De rol van computers
Een computerprogramma is de implementatie van een algoritme. Verschillende computerprogramma’s – verschillend in bijvoorbeeld het aantal benodigde berekeningen of de opslagcapaciteit – kunnen tot hetzelfde resultaat leiden. In het begin van het computertijdperk was de rekenkracht nog zeer beperkt en was de wetenschappelijke kant van algoritmiek met name gericht op het vinden en implementeren van zo efficiënt mogelijke algoritmes voor problemen die relatief eenvoudig zijn, zoals het vinden van de kortste route. Door de sterk toegenomen rekenkracht tezamen met de eveneens sterk toegenomen fundamentele kennis van algoritmiek, is de aandacht echter verlegd naar het oplossen van problemen die door hun omvang voorheen onoplosbaar waren. Was het snel uitvoeren van algoritmes vooraleer een drijvende kracht achter de ontwikkeling van computers, nu zijn het krachtige computers en de beschikbaarheid van grote digitale datasets die tot nieuwe algoritmiek hebben geleid. Machine Learning staat hierbij momenteel het meest in de belangstelling.
Machine Learning
Bij Machine Learning, een vorm van kunstmatige intelligentie, staat niet langer het menselijk inzicht centraal, maar bepaalt het algoritme aan de hand van een grote dataset zelf een relatie tussen invoer en uitvoer van gegevens. De rol van de mens is hierbij beperkt tot het aanleveren van een correcte trainingsdataset van afdoende omvang, het ontwerp van het onderliggende kunstmatige neurale netwerk (in het geval van het sterk populaire deep learning), en het al dan niet vrijgeven van het getrainde netwerk. Met Machine Learning zijn grote successen gehaald in onder andere de bio-informatica en op het gebied van spraak- en beeldherkenning. Bepaalde taken kunnen met Machine Learning sneller en beter opgelost worden dan dat mensen dat kunnen, maar het is niet zo dat deze netwerken als mensen denken. Sterker nog, de werking is zo complex dat het voor mensen vaak niet meer mogelijk is om te doorgronden hoe en waarom een Machine Learning netwerk tot bepaalde keuzes komt. Dat maakt ze ongrijpbaar, en misschien zelfs een beetje beangstigend, want ze beïnvloeden ons dagelijks leven meer en meer.
Eindig bereik
Als consument ben je vaak onvermoed gebruiker van een algoritme. De automatische helderheidsinstelling van je telefoon bijvoorbeeld, maar bijvoorbeeld ook als de treindienstregeling door een storing omgegooid wordt. In dat laatste geval zou een algoritme wel eens kunnen besluiten om jouw kleine station een paar uur lang te negeren. Het is dus belangrijk te weten onder welke omstandigheden een algoritme niet meer goed werkt. Bepaalde algoritmes, zoals dat van Euclides (zie kader), zullen wiskundig aantoonbaar te allen tijde correct functioneren. Voor andere algoritmes, zoals de treinroostering, zal dit ook zo zijn zolang het model (nog) een goede representatie van de werkelijkheid is. Het verwijderen van een stuk spoor vereist een ander algoritme, of in ieder geval een nieuwe optimalisatie met het bestaande algoritme. Voor Deep Learning neurale netwerken, en eigenlijk voor alle vormen van kunstmatige intelligentie, geldt sowieso dat deze wel tot een goede oplossing kunnen komen, maar nooit tot een wiskundig aantoonbaar optimale oplossing. Ook kunnen er impliciete vooroordelen in de trainingsdataset verwerkt zitten (alle trainingsfoto’s van katten hebben een huiselijk interieur als achtergrond), waardoor het netwerk toch niet goed doet waarvoor het getraind is.
Vernieuwend inzicht
Bij een probleem uit de praktijk, zoals het maken van een treinrooster, blijkt eigenlijk altijd dat deze met het gebruik van (combinaties van) bestaande algoritmes niet goed of snel genoeg op te lossen is. Dit vergt dan bijvoorbeeld te veel aanpassingen aan het model. Met het toepassen van gerichte verbeteringen bouwt een onderzoeker een passende algoritmische oplossing. De algoritmische inzichten die de onderzoeker hierbij opdoet zijn vaak breder toepasbaar dan alleen dit praktijkprobleem.
Een eerlijke energietransitie
Mathijs de Weerdt, Universitair hoofddocent in de Algorithmics groep aan de TU Delft, werkt aan algoritmes voor problemen waarbij meerdere partijen betrokken zijn. Zo onderzoekt hij algoritmes voor een efficiënt en eerlijk gebruik van het elektriciteitsnetwerk, nu de momenten van vraag en aanbod vanwege de energietransitie steeds minder met elkaar overlappen. “Zon en wind zijn niet altijd beschikbaar,” zegt hij, “dus het helpt als we onze elektrische auto opladen en de elektrische boiler juist inschakelen bij voldoende aanbod.” Daarnaast heeft het elektriciteitsnetwerk capaciteitsbeperkingen. Met een financiële prikkel voor partijen die op zo’n moment willen leveren of gebruiken, is dit theoretisch oplosbaar. De hoogte hiervan hangt dan af van hoeveel waarde een partij op dat moment aan levering hecht. “Maar dan moet je wel altijd de optimale oplossing hebben,” zegt de Weerdt, “anders kunnen gebruikers het systeem misbruiken door een valse waarde op te geven.” Omdat een optimale oplossing vereist is, past de Weerdt in principe geen Machine Learning toe. Bovendien vindt hij het belangrijk dat de oplossing eerlijk is. “We kunnen natuurlijk niet altijd dezelfde wijk of hetzelfde windmolenpark afsluiten bij capaciteitsproblemen. Dat is misschien het beste voor alle gebruikers als geheel, maar ik vind dat dan toch geen optimale oplossing.” Dankzij zijn algoritmes zijn er op termijn mogelijk minder gas- en kolencentrales nodig voor het opvangen van acute onbalans tussen vraag en aanbod. Naast een praktische component is zijn werk ook wetenschappelijk relevant. “Bij het modelleren van een uitdagend probleem uit de praktijk komen we vaak nieuwe uitdagingen tegen, zoals die eerlijke toewijzing. We houden dan rekening met de structuur van deze problemen, om zo tot snellere en betere oplossingen te komen,” licht hij toe. “Zo bouwen we een nieuw algoritme, met daarin componenten van bestaande algoritmes. Vervolgens laten we zien dat onze nieuwe aanpak ook in andere situaties zou kunnen werken.”
Spreiding van spoedambulances
Theresia van Essen komt uit een artsenfamilie en wilde vroeger chirurg worden, maar nu grijpt ze via algoritmiek in de gezondheidszorg in. Als universitair docent in de Optimization groep aan de TU Delft doet ze bijvoorbeeld onderzoek naar de optimale spreiding van spoedambulances. “De gezondheidszorg is duur, dus als we beter kunnen presteren met dezelfde middelen, dan is dat mooi meegenomen,” zegt van Essen. Vanwege de toegenomen rekenkracht kan dit probleem met veel meer detail benaderd worden dan vroeger mogelijk was. “We kijken nu in Nederland op het niveau van de numerieke postcodes. Daarbij nemen we bijvoorbeeld de huidige spreiding van spoedambulances over de locaties mee en de historische responstijden. Vooral het aantal incidenten in een gebied is bepalend.” Als startpunt streeft ze altijd naar een optimale oplossing voor het hoogst mogelijke detailniveau. “Als die optimale oplossing te lang duurt, zoek ik naar algoritmes die deze oplossing in veel minder tijd dicht benaderen. Je kan ook het model versimpelen, bijvoorbeeld door uit te gaan van gemiddelde reistijden die ook nog eens niet variëren over de dag, maar een optimale oplossing voor een versimpeld model is niet optimaal voor het echte probleem.” Dankzij haar algoritmes is er in de regio Utrecht al een dynamische ambulancepost bijgekomen, op bepaalde tijden van de dag. Met de verbeterde spreiding wordt nu voldaan aan de geldende maximale responstijd. De extra ambulancepost zal voorlopig niet verdwijnen. “Het aantal incidenten binnen een gebied verandert immers maar langzaam over de jaren heen,” licht van Essen toe. “Het is wel verstandig om toch elk jaar een keer te bepalen of het algoritme niet tot een wezenlijke verbetering in de zorg kan leiden.”
Diversiteit in aanbevelingen
Emily Sullivan is postdoc in de Web Information Systems groep aan de TU Delft, waar ze onderzoek doet naar verbeteringen in zogenoemde recommender systems. Dit zijn de systemen die je aanbevelingen voorschotelen als je bijvoorbeeld op een website een bepaalde film hebt gekeken of nieuwsartikel gelezen. “Wij proberen de diversiteit in deze aanbevelingen te vergroten,” zegt Sullivan. “Als ze allemaal te dicht bij jouw voorkeuren liggen, dan kan je in de bekende filter bubble terecht komen. Maar aanbevelingen die te veel afwijken van jouw voorkeuren, zal je sowieso negeren. Aanbevelingen moeten dus divers zijn, maar ook weer niet te divers. Als van iemand bekend is dat hij graag korte artikelen leest, kan je bijvoorbeeld korte artikelen aanraden, maar met een net andere inhoud.” Voor het bepalen van diversiteit gebruikt ze bestaande Natural Language Processing software, een vorm van kunstmatige intelligentie, om teksten te kenmerken. “In ons onderzoek gebruiken we verschillende technieken voor het wegen van deze kenmerken, om daarmee de artikelen te rangschikken en de gebruiker tot diversiteit te stimuleren.” Ook de presentatie van de aanbevelingen krijgt hierbij aandacht, bijvoorbeeld door deze te vergezellen van gerichte uitleg, zoals: ‘Als je meer achtergrondkennis over dit onderwerp zoekt, dan vind je deze artikelen misschien interessant’. “Bij onze groep ligt de focus van dit soort onderzoek niet zozeer bij commerciële doeleinden,” zegt Sullivan. “We willen met name dat het recommender systeem de normen en waarden van zowel het bedrijf als de gebruiker representeert.”
Passende radiotherapie
Peter Bosman is deeltijdhoogleraar Evolutionairy Algorithms aan de TU Delft en senior onderzoeker in Life Sciences and Health bij het Centrum Wiskunde & Informatica in Amsterdam. Naast fundamenteel onderzoek aan evolutionaire algoritmes past hij ze ook toe in bijvoorbeeld de brachytherapie, een behandeling waarbij de bestraling van kanker van binnenin de patiënt plaatsvindt. “Hierbij moeten vaak concessies gedaan worden, omdat de hoeveelheid straling naar de tumor niet afdoende is voor genezing zonder het stralingsrisico voor één of meer gezonde omliggende organen te verhogen,” licht Bosman toe. “Met onze algoritmes geven we behandelend radiotherapeuten uniek inzicht in de mogelijke afwegingen tussen deze tegenstrijdige belangen voor een specifieke patiënt. Op basis hiervan kunnen zij, als expert, het meest geschikte bestralingsplan voor de patiënt kiezen.” Het is belangrijk dat het gekozen bestralingsplan zowel technisch uitvoerbaar is als een accurate weergave van de werkelijkheid. “Wij passen daarom zo min mogelijk benaderingen toe bij het oplossen van dit probleem,” aldus Bosman. Om toch snel tot een goede oplossing te komen, bewandelt het genetisch algoritme meerdere oplossingswegen tegelijk. Hierbij combineert het algoritme via een soort natuurlijke selectie de goede eigenschappen van oplossingen tot steeds betere oplossingen. Voor een bruikbaar resultaat in de kliniek is nauw overleg met de radiotherapeuten heel belangrijk. “Zo leren wij wat hun onderliggende doelen van de bestraling zijn en komen we tot een algoritme dat hen de gewenste mogelijke bestralingsplannen aanbiedt,” zegt Bosman. “De daaruit voortkomende bestralingsplannen zijn soms zo verrassend afwijkend van wat ze verwacht hadden, dat het hen weer tot nadenken aanzet over wat nu werkelijk de belangrijkste kwaliteitseigenschappen zijn die ze gewaarborgd willen zien.”
Evolutionaire algoritmes zijn een vorm van kunstmatige intelligentie en stammen uit de jaren ’70. Tegenwoordig zijn ze zelfs relatief gemakkelijk door iedereen toepasbaar, maar volgens Bosman zijn ze zeker geen cure for all. “Bovendien komen wij dankzij ons fundamentele inzicht in hun werking veel vaker tot een goede oplossing. Voor mij is de combinatie van fundamenteel onderzoek en de toepassing daarvan dan ook ideaal.”
Theresia van Essen
Euclides algoritme
Een van de oudste (wiskundige) algoritmes, in 300 voor Christus geformuleerd door Euclides, vindt de grootste gemeenschappelijke deler van twee getallen. Het algoritme getuigt van veel inzicht bij de bedenker, is eenvoudig toe te passen door de gebruiker en werkt als volgt:
- Trek het kleinste getal van het grootste getal af.
- Herhaal dit voor het nieuwe getal en het laagste van de twee oude getallen totdat de uitkomst 0 (nul) is.
Voor de getallen 49 en 21 krijg je:
49 – 21 = 28,
28 – 21 = 7,
21 – 7 = 14,
14 – 7 = 7,
7 – 7 = 0.
De grootste gemene deler tussen 49 en 21 is het getal 7.