UvA-studenten presenteren onderzoek in algoritme verbeteringen

19 juni 2018

Romi Geleijn, Marrit van der Meer, Quinten van der Post, Reitze Jansen, Yannick Vinkesteijn en Wouter Vrielink, UvA-bachelorstudenten uit de Minor Programmeren en de bachelor BètaGamma, hebben afgelopen maand op de EGL’2018-Workshop on Optimisation, Applied and Numerical Mathematics in Engeland hun onderzoek gepresenteerd.

Alle zes studenten hebben onderzoek gedaan naar het ‘Plant Progagation Algorithm’, het zogenaamde aardbeien algoritme. Een onderzoek  langs lijnen van een theoretische analyse en twee onderzoeken langs een toegepast probleem.

Toegepast probleem 1

Romi Geleijn, Marrit van der Meer and Quinten van der Post hebben zich gewaagd aan het notoire lesroosterprobleem. Met echte (geanonimiseerde) data van zaalgrootte, vakinschrijvingen en vakgegevens van enkele opleidingen op Science Park is er een applicatie van het Plant Propagation Algorithm ontwikkeld die relatief goede lesroosters produceert.

Het werkt als volgt: er wordt een willekeurig lesrooster gegenereerd dat met behulp van een doelfunctie een score krijgt toegewezen. Hoe beter het rooster, hoe hoger de score en ieder lesrooster produceert ‘nageslacht’ – afgeleide roosters. Alle afgeleide roosters lijken dus op het orgineel maar hoe beter het rooster, hoe kleiner de veranderingen en vice versa. Ook het aantal nageslacht-roosters is afhankelijk van de doelfunctie: hoe beter de score, hoe meer nageslacht en vice versa. Daarna worden alleen de beste roosters bewaard en begint de hele cyclus opnieuw.

Het algoritme is afgeleid van de reproductiestrategie van de aardbeienplant, die in vruchtbare grond veel nageslacht produceert maar in mindere grond een paar lange uitschieters maakt, in de hoop betere plekken te bereiken.

Toegepast probleem 2

Reitze Jansen en Yannick Vinkesteijn gebruiken hetzelfde algoritme voor het optimaliseren van chips. Twee logische poorten op een chip optimaal verbinden is relatief eenvoudig, maar als er meerdere poortparen verbonden moeten worden ontstaan er problemen. Paden mogen elkaar namelijk niet kruisen vanwege kortsluiting, en zodoende is de volgorde waarin paden worden aangesloten cruciaal voor de kwaliteit van de uiteindelijke padconfiguratie.

Die volgorde wordt geoptimaliseerd met het Plant Propagation Algorithm, maar net als bij de lesroosters is de term ‘geoptimaliseerd’ erg relatief. We kunnen de beste oplossing, noch de score ervan exact bepalen, en dus kunnen we alleen verbeteringen ten aanzien van andere algoritmes en theoretische grenzen vaststellen.

Theoretische analyse

Tenslotte heeft Wouter Vrielink een theoretische analyse gemaakt van zowel het Plant Propagation Algorithm en het Fireworks Algorithm, dat niet geheel ontoevallig van Chinese makelij is. Het lijkt erop dat de twee algoritmes veel overeenkomsten vertonen, maar het is voor wetenschappers belangrijk te weten op welke problemen ieder algoritme het best toepasbaar is, en welke onderdelen verantwoordelijk zijn voor welke onderdelen van de perofrmance.

‘Dit vergt een geduldige dissectie, en veel rekenwerk, zegt Daan van den Berg, supervisor van de drie projecten en docent Heuristieken in de Minor Programmeren. “’Maar ik ben erg verheugd over de vorderingen. Het is werk wat voldoening geeft, maar ook belangrijk, omdat vooral onze assistenten in de Minor Programmeren (Wouter, Quinten en Yannick) dan echt beseffen wat het betekent om onderzoek te doen en je te verantwoorden aan de gemeenschap. Dat echoot door in ons onderwijs, en in de aansturing die we onze studenten geven in het vak Heuristieken. Maar we vinden het vooral ook erg leuk om ons op dit soort problemen te storten. Het is echt een win-win-win-situatie.’

Bachelor studenten presenteren onderzoek op EGL 2018. Vlnr:

Vlnr: Marrit van der Meer (UvA BG), Yannick Vinkestein (UvA), Abdellah Salhi (Essex), Eric Fraga (UCL), Romi Geleijn (UvA), Reitze Jansen (UvA). Zittend: Daan van den Berg (UvA), Quinten van der Post (UvA), Wouter Vrielink (UvA)

Over EGL 2018

De EGL-Workshop is voor research students, postdocs en staf van de University of Essex, de University of Greenwich, University College London en anderen een gelegenheid om hun meest recente vorderingen in optimalisatie en toegepaste wiskunde te presenteren.

Gepubliceerd door  Faculteit Natuurwetenschappen, Wiskunde en Informatica