A walk through an evolutionary algorithm

Cars       Planes

What is this?

This is Genetech, a project we've developed about evolutionary algorithms. What that means is we use techniques that are found in nature (in evolution) to find solution to some problems, for example, how to approximate a picture with triangles.

The main idea is to see how can a set of individuals evolve after a certain number of generations, where only the "best" ones can survive and reproduce to keep swag going.

How does it work?

The study begins with an initial set of individuals that have random properties: the first generation. Every individual has a genetic code, which contains all the information about the individual: the position of the vertices of each triangle and their color. The evolutionary method is based on mixing two individuals' genetic code. For every piece of genetic information there's a chance both will get crossed. See how much the crossing chance affects the outcome of the mixing.
Crossing chance:  


It might be difficult to picture what that means in a practical setting. Let's cross some triangular pictures instead:
Crossing chance:  

Notice how, with a low percentage, you can see traces of the first parent in the second offspring.

How we can know what genes should we compare? In order to get the best results, we want to mimic nature. Thus, we choose the best, most prepared individuals and mix their genes. But, how do we decide which ones are the best?
Well, we use what's called a fitness function. The fitness of an individual tells us, for example, how much a set of triangles ressembles a certain picture. In fact, we check each pixel and determine how close both pictures are.

Now we are ready to roll! We can start processing generations of individuals and see how their fitness goes up as their goal is achieved.

Now let's add a little chance that the genetic code will be mutated every time we copy, and see how that works.
Mutation chance:  
    Mutation effect:  

That's pretty much it, but there are a few details me missed. You can play with different configurations below, see if you can get the most efficient one. The titles are pretty self explanatory.
Mutation chance:  
    Mutation effect:  

Extreme mutation chance:  

Individuals per generation:  
,     New individuals each generation:  

Crossing chance:  

Well yea, we know, they still don't look very alike. We can't predict where the generations are going to converge, and if it depends on the initial random generation or on the contrary it always ends on the same "superindividual".

In this case, the triangle image stabilizes after coming close to the color of the walls, but it doesn't really paint Nil (yes, that sexual beast in the picture is one of us).

In general, the only thing that we can really expect is a reduction (or stabilization) of the fitness in each new generation. Other than that, the result is always a surprise!

Who are Isomorphic To Ourselves ©?

We are a group of four mathematics students formed by Guillem Garcia, Nil Garcés, Josep Esquirol and the amazing Taras Yarema. We are Isomorphic to Ourselves ©! We love maths and we love to mix the life and hack the fun, so we decided to attend HackUPC Fall 2016. As it was our second time in this event we decided to do something that would challenge ourselves. We end up with the idea of studying the genetic algorithms and its applications.