UvA-students presented research in optimisation algorithms
Romi Geleijn, Marrit van der Meer, Quinten van der Post, Reitze Jansen, Yannick Vinkesteijn and Wouter Vrielink, UvA-bachelorstudents from the Minor Programmeren and the bachelor BètaGamma, presented the results of their scientific research during the EGL’2018 Workshop on Optimisation, Applied and Numerical Mathematics in Great Britain on 6 and 7 June.
All six students used the ‘Plant Progagation Algorithm’ for their investigation. This algorithm was applied to two real-world problems and one theoretical analysis.
Real world problem 1
Romi Geleijn, Marrit van der Meer and Quinten van der Post extracted real data from the room timetabling system at Science Park,and tried to optimally schedule its lectures. The Plant Propagation Algorithm outperformed more traditional methods such as Local Search and Simulated Annealing. It starts off with a random schedule, and then creates ‘offspring-schedules’. These offspring schedules are relatively similar to the original solution if the original solution was of good quality, and quite dissimilar if it wasn’t. Repeating this cycle over and over again gradually creates better and better schedules.
This routine is inspired on the behaviour of the strawberry plant, which creates many new plants nearby if it is in fertile soil, or conversely, creates a few far offshoots if it is in an infertile spot.
Real world problem 2
Reitze Jansen and Yannick Vinkesteijn are using the algorithm to route connections in chip design. Connecting two logical gates in a chip is an easy task, but as routes cannot cross, optimally connecting multiple gate pairs can be a daunting task. The key turns out to be the order in which connections are routed, but even for small chips the number of possible orders is far too large to try them all. Plant Propagation can optimize this routing procedure, starting off with random orders, and making similar or dissimilar offspring depending on the quality of the routed chip.
Thirdly, the Plant Propagation Algorithm was possibly ‘cross-published’ with the Fireworks Algorithm, a very similar method. This was discovered during a conference in 2016, and Wouter Vrielink is in the process of technically comparing the two algorithms, uncovering strengths and weaknesses as he goes along.
‘We’re very happy and proud that our students and assistents, young as they are, do real scientific research,’ says Daan van den Berg, supervisor and teacher of the Heuristics course which is a part of the Minor Programmeren. ‘It really increases our inside knowledge of these algorithms. That helps when we teach programming courses, but students also like the small anecdotes we tell about operating in the scientifc community. It’s really a win-win-win-situation.’
About EGL 2018
The EGL Workshop brings together research students, postdocs and staff of the University of Essex, the University of Greenwich, University College London and others, to present their latest work in optimisation, applied and numerical mathematics with applications.