One of the most frequent questions that I get is: “What is it that you did before?”. And the answer to that question always ends up in what my thesis was about.

So, the title of my thesis is “Particle Swarm Optimisation for solving many-objective problems”. This most often than not results in people just saying something like “riiiiight”. It is a bit frustrating not being able to share with everyone what is it that I actually did. This post is an attempt to explain it in simple terms.

Optimisation

So, to optimise something means to make it effective or efficient as much as possible. This means that we usually want to make something as big or as little as possible. For instance,

I want to optimise the amount of money I spend.

Therefore…

I want to spend as **little** as possible.

Or…

I want to optimise the amount of money I make

So…

I want to earn as **much** as possible.

This means that, depending on the case, to optimise something means to either maximise or minimise it.

Many-objective

This is perhaps the most difficult piece to explain.

An optimisation problem can have only one objective if we want to maximise or minimise only one thing. This is fine for simple problems, but it is not enough to model real life problems. The bigger problems tend to have several things that we want to optimise. For instance, when selecting which route to take when driving home, we want the route that is:

• The fastest (to get sooner).
• The shortest (to spend less petrol).
• The cheapest (in the case of toll roads).
• The safest (if you live in a place with high crime rate).
• At least one drive-thru on the way (it is perhaps time for a snack).

It might not be super obvious at a first glance that these objectives are possibly conflicting. In rush hour, for instance, the shortest way might not be the fastest or the safest. As a consequence, a situation can arise in which you have two routes that are identically “good”:

Route A will take 20 minutes in rush-hour, but it will cost 20£ of petrol because it’s long.

Route B will take 30 minutes in rush-hour, but it will cost only 10£ because it’s short.

These are 2 possible solutions to the problem, and the decision between them is not obvious. If the long route was as cheap as the short one, then that is the best solution for sure, but now we have no option but to choose to have a long-but-fast route or a short-but-slow one.

When we have more than 3 objectives to optimise, we have a many-objective problem.

#Particle Swarm

So, we know now what a many-objective problem is, and it’s kind of clear that they can be massively difficult to solve. Also, if you want to add more objectives it only gets harder. This motivated super intelligent people into thinking “so… what can we do to actually find solutions when we have a gazillion objectives?”

Several things were proposed to solve this kind of problems. Some of them work kind of well. The one my thesis is based on is inspired by the behaviour of swarms of bees and pigeons.

I know, this is super cool!

So… what is it that the bees and pigeons do that is so cool to solve this kind of problem? They perform a collaborative search for food or shelter in a big space, and they do that in big groups. If a bee finds a particular place full of tasty flowers, she will tell all the swarm something like “hey guys, I’ve found some awesome flowers!”. The rest of the swarm will be attracted to that particular place and after some time all of the swarm will be happily feeding in a particular garden.

If we take this behaviour to the routes example, we can think of the same kind of method to solve our issue. We have many virtual “bees” that we call “particles”. They look for possible routes in the space of all possible ways home. When one of the particles finds a short path, all the other particles will be looking for even shorter paths and will be attracted by that solution. After a while, just like the real bees, the particles are overflying a particular spot in the space and that is the set of possible solutions.

What we actually did

Our job in all this thing was to implement the Particle Swarm solution to solve a set of many-objective problems. We compared that algorithm to a genetic algorithm that is the best algorithm to solve this kind of problems at the moment.

We showed that although the genetic algorithm comes up with better solutions for some problems, the swarm approach comes with better solutions in other problems and in a fraction of the time it takes the genetic algorithm to do it.

Finally, here you have a video I made of some (red) particles finding the (blue) solution on a 3D space :)

If you are interested in this stuff, please contact me. I’m more than happy to talk about it. There is a LOT that can be done with this kind of algorithms, and there is wide range of practical problems that can be tackled using them.

If you’re not happy with this explanation contact me as well and I’ll try to improve it!