Background
Back in high school, I went through almost an entire book on C++. It was extremely interesting but the things I created were always command-line applications and – never once in my life – I’ve built a C++ application with a GUI, even the simplest one. It just seemed to be too much of an overhead. Then, I stumbled upon a web development course that quickly turned out to be a solution to the whole problem. Visual cues, truly interactive applications, client-server architectures. It sparked my interest in Computer Science and made me start to think differently (in many fields) on daily basis. A lot of time passed since then. Today I’m a CS graduate and a Software Engineer @appliscale given an opportunity to share some of the latest events.
Introduction
I applied to appliscale in early 2021 with a good dose of JavaScript and React knowledge. Working on a real project and putting what I’ve learned on my own into practice was a real thrill. In addition, the company offered me great resources to pursue the things I’m really curious about and allowed me to study in the meantime.
At about that time my friend Jonatan (@jonatanklosko) and I were searching for an engineering thesis topic. As a matter of fact, he got very interested in the Elixir programming language and has rewritten some of his backend solutions to use the Elixir ecosystem.
“What happened?” – I thought since we were both JS guys.
One day he called me asking if I’d be interested in a rather sophisticated topic – A platform for testing multi-population evolutionary algorithms using the Beam virtual machine. Knowing nothing about Elixir back then (not to mention genetic algorithms), I’ve agreed to it anyway. It had to be more interesting than writing another CRUD application, right?
Engineering thesis
Getting to know evolutionary algorithms
Evolutionary algorithms help you solve optimization problems in an efficient manner. These could be “typical” optimizations like multivariate functions that are hard to optimize with gradient-based methods or combinatorial optimizations like the Travelling Salesman Problem (finding the shortest route) which is actually an NP-hard problem.
A potential solution to a given problem is called a genome. To determine how good a genome is, we need to provide a fitness function that will tell us just that.
From genomes, we form a population. Such a population evolves over time going through steps like selection, crossover, and mutation in every generation. Eventually, keeping track of the best genome across all generations, it’s drawn out as a solution to the whole problem.
Our idea
After familiarizing ourselves with the requirements and exploring existing solutions we came up with an idea. It was inspired by LEAP (a similar platform in Python), where all of the operations that a population goes through in a given generation are called a pipeline.
An operation takes in a population and returns a population. This way, combined with the pipeline concept, the algorithm definition is very readable and declarative. What’s more, our platform’s API has pre-implemented operations and is extendable at the same time, so that the user can implement their own.
Built-in parallelism
Evolutionary algorithms are inherently parallelizable.
In terms of one population, given our choice to represent it as a two-dimensional tensor, we were able to achieve lower-level parallelism with Elixir Nx and tensor computations. None of the existing solutions we’ve checked performed the aforementioned operations (like fitness computation) for a population as a whole, but rather separately for each genome. What’s more, thanks to the tensor abstraction in Nx, it is possible to configure the operations to run on a GPU, which makes them even faster.
In terms of many populations, there’s a high-level parallelism thanks to Erlang VM and its distributed features like nodes and message-passing. Populations can evolve on different nodes and exchange genomes with each other in a defined topology during a migration step.
Outcome
The platform is called Meow (Multi-population evolutionary optimization workbench) and you can find it on GitHub.
Publishing a paper
The platform turned out so good, that with the help of our supervisor, an MSc student, and a Ph.D. from our university we’ve written a publication showing our efforts and benchmarks for the GECCO 2022 conference. It was accepted and published. You can find it on acm.org.
Benchmarks
The benchmarks for the paper were done on the AGH Prometheus supercomputer with up to 32 GPUs but since the paper is not really public, I present our own benchmark below. It shows how Meow compares with other solutions when it comes to optimizing the Rastrigin function.
Winning the E4S2022 contest
Not long after our defense, we decided to enter the E4S2022 contest that picked the best theses per almost every technology-oriented faculty in Poland, The Faculty of Computer Science, Electronics and Telecommunications at AGH UST being one of them.
We were awarded first place in our faculty and advanced to the next, national stage of this contest.
Lambda Days
Winning the contest helped me gain some traction in the Elixir world. My friend Jonatan was already pretty well-known there thanks to his contributions to Livebook, which is by the way an amazing piece of software.
Erlang Solutions (one of the organizers) invited us to Lambda Days, a functional-programming conference taking place in Kraków, Poland. It was my first conference to attend, a chance to network with people in the community and get to know fascinating things that other developers do. I’ve also realized that there’s a lot more to functional programming than just Erlang and Elixir.
Thanks to the amazing R&D policy at appliscale, I was able to be there during my work hours.
WKS
As you may have read in one of our previous blog posts, we are cultivating weekly knowledge sharing meetings amongst our employees where everyone can share something interesting with the others.
At the end of the day, being a Software Engineer is not only coding so I started my little shift into doing other things as well, preparing for and presenting at one of such meetings being one of them.
My presentation included a conference summary and some news from the Elixir world. Hopefully, it encouraged someone to check out functional programming.
Erlang Solutions Meetup
I had the pleasure to be a speaker at Krakow Erlang & Elixir Meetup October 2022 where together with Jonatan we presented Meow to a broader audience using an interactive Elixir notebook instead of Google Slides.
You can find the presentation here.
GitHub is capable of nicely displaying the .livemd format but in case you want to get your hands dirty, you can try out the Livebook Desktop App that works out of the box and import those notebooks to it in order to play with them.
Summary
It took a lot of time to convince myself that Elixir is the way to go. Nowadays, I work with it day to day, listen to podcasts to stay updated, and maintain an enormous Notion page with books, libraries, and features that I want to try out. To be honest I still find myself thinking in an imperative/object-oriented way a lot but I do my best to make that slowly drift away. For anyone interested in getting started I would recommend checking out the Elixir School website and for a firm grasp of it – the Elixir in Action book.
Written based on the engineering thesis Benecki M., Kłosko J., A platform for testing multi-population evolutionary algorithms using the Beam virtual machine.
