Evolutionary Algorithms: Painting with Polygons

Evolutionary algorithms are a family of algorithms that are inspired in natural evolution processes in order to reach a solution of a particular optimization problem. Such algorithms typically use concepts such as random mutations, reproduction, and selection to incrementally find better solutions. The general idea is that after having formulated our problem, which can consist for example on minimising certain loss function, and proposing several starting solutions, we let the algorithm work on these solutions and making them evolve. After some time, the solutions will have changed significantly and only the fittest, the ones that score better according to our problem formulation, will survive. Eventually, the algorithm will stop and the solutions will have improved. This kind of programming is used for tackling problems in a wide range of fields suchs as mathematics, engineering, economics and many more. Famous applications of evolutionary algorithms are one type of antenna NASA used in some satellites, virtual creatures that learn to behave like animals in a simulated world, or the best ever Super Mario World player.

The example we are going to see in this lab is related to art, specifically to generative art. In particular we are going to recreate Roger Johansson's project Evolution of Mona Lisa that consist in reproducing famous paintings with a collage of polygons of different shapes and colours. Fortunately, many others, inspired by the same amazing project, have coded useful interactive applets, here and here, that we can check out during our programming journey. By the end of the lab you will know how to do the same thing in Python, and with any image you want to input.

Problem formulation

The basics of this laboratory is to be able to manipulate images within Python. Implementing the evolutionary algorithms will depend a lot on how the images are processed and polygons painted. A digital image is at the end a big matrix - depending on the size and resolution - with a set of numbers that define the colour of each pixel. Manipulating images is therefore nothing else than performing mathematical operations that change those pixel values. Operations like drawing a circle on top of a picture or balancing whites can be performed by python code, but it translates to pixel-by-pixel complex mathematical operations. Fortunately, thanks to libraries like Pillow, also known as PIL, we can use handy objects such as Image and ImageDraw that make working with images a relatively simple task.

The first thing we will do is to create a function that draws a collection of polygons, the building blocks of this exercise. The main input to the function will be a list of elements (polygons) where each element is a Pyhton dictionary with two attributes; vertices and RGBA. vertices is itself a list of points in a two-dimensional space that denote each of the vertices of the polygon (the order is important). Thus, if we have lists of 3 vertices we will be drawing triangles. Remember that when processing and rendering images, the X values increase from left to right, but Y values increase from top to bottom. The other attribute, RGBA, is a tuple with integer values from 0 to 255 for each of the Red, Green and Blue channels plus the Alpha channel for the transparency. The values (0,0,0,255) would represent the colour black, (255,255,255,255) would be white, and (0,0,255,125) would be a semitransparent blue. Finally, we also need to provide the width and height of the canvas in a variable called size.

The result is a white background image with the three polygons. Notice that the overlapping of semi-transparent polygons also create regions with different colours.

The next step is to create a function that generates a collection of N triangles with their vertices placed at random over the canvas of a certain size. By default we generate the initial colours randomly as well as the transparency, however we allow for certain customization of the initial state with, for example, all triangles being black with a specific value for transparency.

Great! Now we know how to create a collection of triangles and generate an image of it. But we also need load into the program the image that we want to reproduce. Again, pillow library makes our lives easy, Image.open() does just that if we provide the local path of the png file. We also convert it to RBG format, This ensures that both the target image and the result of the draw() function - which we also convert to RGB - have exactly the same format.

One useful image manipulation trick is to subtract one image from the other using ImageChops.difference() function. Remember, this is just mathematically subtracting pixel values from two matrices. The result is a matrix with the difference values, which in turn is also an image that we can display.

But more interestingly, we can create a function that, using the same principle, returns the pixel-by-pixel difference between the triangles image and the target. ImageChops.difference() provides already the absolute difference for each RGB channel and for each pixel. Using the .getdata() attribute returns this as values in a matrix. Then, we can just sum all the elements with .sum().

The result is how far apart these two images are in all 3 RGB channels. Of course the bigger the image is or the more resolution we have, the higher the difference will be. Ideally, we want to construct a measure that does not depend on that. Because we start by default with a white empty canvas, one solution consists on considering the difference between a white image and the target as the maximum difference. This allows us to construct a fitness measure in terms of this maximum difference. Thus, 0% would be the initial empty canvas, and 100% would be the exact replication.

Expressing the fitness as similarity percentage allows us to compare quantitatively which two triangle collection is closer to the target image.

Exercise 1:
Create a new function called random_polygon() that generates a polygon, instead of triangles, with a number of vertices controlled by a parameter named "vnum". Then, use the function to create a collection of 3 polygons with 5 vertices and plot them on a white canvas to show that the code works correctly.

Hill Climbing

Now that we have the building blocks ready, it's time to implement the evolutionary algorithms that will make our collection of polygons evolve and become more and more similar to the target image. Hill Climbing is probably the most simple one we can start with. The application of this algorithm in our problem consists in introducing a mutation in our collection of triangles, then keep or discard the new mutated collection depending on whether the overall fitness has increased or decreased.

A mutation is a relatively small change in the vertex coordinates or the colour of one of the triangles. As the iterations progress, more beneficial mutations - those that increase the fitness - cumulate and allow this incremental transformation to take place. The mutations can also be of different types; This example allows the user to select between "soft", "medium" and "hard" mutations. As you will explore in the Exercise 2, this has naturally some impact on the evolution path. For the moment we will only implement the "hard" mutation that consist on replacing randomly one of the vertices and changing randomly the color of the triangle including its transparency.

As mentioned before, each of triangles in our collection is a python dictionary. There is one caveat we should consider when performing the mutation. We want to return a mutated collection object as a different object than the original. Therefore we will first copy the original collection into a new one and then perform the mutation on this new copy and return that as a new object. When copying the original list, if we did something like mutant=original, we would be doing a shallow copy rather than a deep copy. Any changes to the mutant object would also affect the original object. In order to avoid this issue we use the function deepcopy() from the copy library.

The effect of the "hard mutation" is pretty clear if we use a small initial set of black triangles. Only one triangle changes colour and one vertex from it moves somewhere else, the rest stays the same.

Let's now design the function triangle_painting_hill_climbing() that will run the whole process. The main arguments are the target image, the number of triangles of the collection, the maximum number of iterations we want to run the code for and the type of mutation, which is set to "hard" by default. As for the general structure, is rather simple. We start generating a random collection of triangles, whose initial configuration is controlled by the colour_init and alpha_init parameters. That is going to be our first best candidate. Then we compute the fitness of our initial candidate to set our initial fitness. Everything else happens within a for loop. Every certain number of iterations, defined by the parameter every, we will save the best candidate within the outdir directory and store some information in a list that will be converted to a data frame at the end. This information is the round number (or mutations inflicted), the number of improvements (mutations that produced an increase of fitness) and the corresponding image path. If the parameter logs is set to TRUE the program will also print some of this information while running. In each of the iteration we perform a mutation of our best candidate best and save it into a new collection. Then we generate the new image and calculate its pixel difference newdiff. If that difference with respect to the target image is lower than our best candidate, then we replace the best candidate and update the pixel difference and fitness. After maxit iterations we stop, create the data frame and return it. This data frame contains all the information of the evolution of our best candidates. The images will be stored within the selected folder. Make sure this folder exists in your working directory before running the function, otherwise you'll get an error.

As you can see, we get some feedback during the execution of the program. This is useful information to estimate how long is going to take and control whether we should tune the maxit value.

It is also interesting to have a look to the output images.

From the last images we can recognise how some areas such as the hair and face start to appear. We are still quite far away from the target but the evolution goes in the clear direction. Using the information returned as a data frame we can plot a nice line chart with the fitness increasing over time, which provides a much more detailed sense of the evolution path.

Observe how different is the impact of the initial mutations with respect to the latest ones. At the beginning the fitness increases very quickly, but as we approach to the end of the probability to encounter beneficial mutations reduces dramatically and the curve starts saturating. This also highlights one of the issues of Hill Climbing algorithm; the importance of initial mutations.

Exercise 2:
Implement the two other mutation types, "soft" and "medium", as explained below:

Soft mutation: This mutation consist in modifying by a small delta (small amount) either one coordinate of one polygon's vertex or one of the RGBA channels from one polygon's colour.
Medium mutation: Changing the colour and one of the vertices as in the hard mutation, but picking only one of the two options at a time.

Finally, run three difference instances of the Hill Climbing algorithm starting from the same random collection but using a different mutation type. Compare the performance curves.

Hint: The soft mutation is not as easy to implement as it seems. For the delta value consider a random integer from -10 to 10, making sure the resulting value does not fall outside the size of the of the canvas when changing vertices or is always within 0 and 255 when changing RGBA channels. Additionally, remember that the tuples are immutable, so you cannot modify the coordinates of a vector or change the value of an RGBA channel. Instead, you need to convert the value into a list, modify it, then convert it back to tuple and replace it with the original.

Genetic Algorithms

We have seen above how the hill climbing algorithm can well be a good way to reproduce a painting using polygons if we give it enough time. However, one of the problems of this that is too dependant on the path history and tends to find local optimum solutions but can struggle a lot to find a global solution. For example, having several big polygons at the bottom will help to quickly increase the fitness at the beginning. But, as the algorithm approaches late stages, where big changes are likely to reduce the fitness and fine tuning becomes more important, those big initial polygons might suppose a burden. Especially considering that all the rest have been built on top of those. Some changes on them might be necessary to reach high scores for fitness scores, but at the same time any small change in them would immediately reduce the score. Assuming that we perform only one mutation at a time, the situation could be stuck.

Genetic algorithms, inspired by the Darwinian ideas of natural selection, overcome this problem by making a whole population "evolve" rather than just one single organism. This way, a diverse initial population ensures the best candidate would not be constrained to one single evolution path and the parameter exploration can take place from multiple fronts reducing the likelihood to fall into a local maxima trap. The different organisms of the population "mate" combining their information and generating new children. The organisms with highest fitness scores are more likely to reproduce, which promotes the combinations that are closer to the target.

In our case, a collection of polygons is considered an organism and all their values for the polygons' vertices and colours represent the genes of its DNA. Thus, a population of organisms would be a list of Npop organisms. We can easily create a function create_pop() that generates a population of those with random values.

We can see above a sample of different organisms in our population. Each of them has a fitness value associated to it. We have already seen above how we can calculate it, but it's much more convenient to create a function that computes the fitness of each organism of the population.

The key step of the evolutionary algorithm is the reproduction of their organisms. In this step two organisms combine their gene sequences, represented their coloured polygons, and generate a new organism with part of both parents. The technical term for this in genetic algorithms jargon is called crossover). We can create a function that performs this given two organisms selected from the population. The output will be two children organisms with some genes of each parent. The function randomly defines a crossover point cutting each parent's genes in two parts. The first children's DNA will correspond to first part of the first parent's DNA and the second part of the second parent's DNA, while the second's children DNA will be the opposite.

title

Also, during this process a mutation can occur with a certain probability pmut. If this happens we will use the mutation() function already implemented over the children's DNA.

If we create a population with just a few triangles and set the mutation probability to 0 (no mutations), we can clearly see which childrens' triangles come from which parents' triangles. If you slightly increase the value for the mutation probability, then you'll see new triangles appearing. Check it out!

One important issue to resolve now is the way we select the two parents, who gets the chance to reproduce. Although there are many ways to select two individuals from the population we want to make the fittest more likely to be selected. One trick to implement that is by using its fitness as a probability weight. Imagine that we have four organisms A,B,C and D with fitness values of 20%, 40%, 60% and 80%. The idea is to choose one of these letters at random but with different probabilities. Thus, D would be four times more likely two be selected than A and two times more likely than B. The function choice() from the random library allows to do that:

As you can see, from the sample above the frequency of each letter is proportional to their fitness values. In our case, however we need to select couples of different parents, which is something that we can do one couple at a time with size=2 and replace=FALSE.

Creating a whole new generation will consist in selecting Npop/2 couples and performing the crossover, since each couple produces two children. We can put all that in a function new_generation() that returns an entirely new population.

Above, you have an example of three generations of a population of four organisms with four genes (triangles) in its DNA. Notice how there are genes that disappear while others survive and reproduce. This is governed by a combination of chance and the fitness vector, which in this case is does not depend on a target pictures but instead on arbitrary values that happen to favour organisms with lower index. Thus, the probability to see the triangles of the top left organisms in the bottom row are higher.

The whole process can be coded into a function genetic_triangle_painting() that uses all functions shown above, therefore it requires all their parameters to be input as well. The general structure is quite simple and similar to the triangle_painting_hill_climbing() function. It starts by computing the maximum pixel difference and generatinc an initial random population. Immediately after we calculate the fitness of this population. Then, all the evolution will happen inside a for loop for maxgen iterations. In each iteration we create a new population from the old one using the new_generation() function, then we compute the fitness for that new generation. Every certain number of rounds we compile information and save the best candidate image into the indicated directory. Finally, we create a data frame with all the information, wich is the object we return outside the function.

The execution of this program can take very long, especially as we increase the population and the number of generations. Let's have a look to the performance by plotting the line chart of both best candidate fitness and population average fitness.

The performance for this particular case is not as good as hill climbing algorithm. First of all, one stark difference is the final fitness reached. Even if more mutations are performed in total (total mutations = Npop x pmut x maxgen), the result is well below the hill climbing algorithm. Another important difference is the fitness not increasing in a monotonic fashion. This is partially good, since we avoid the local maxima trap, but it also makes the convergence very slow.

Genetic algorithms are indeed slow, mainly because make evolve a whole population rather than once single organism. This also makes them computationally expensive. There is also the challenge of coming up with a right set of parameters. For example, if the mutation rate is very high the population cannot keep up with so many changes. Similarly, the size of the population is also a key parameter that controls the initial variety of possible solutions. Correct setting of the parameters depends on the specific problem we are trying to solve. Finding it, it's not usally easy and requires much exploration. Metaheuristics is one of the possible procedures that one can try.

Exercise 3:
In the current example, the entire next generation is created by the crossover process. However, one common feature in genetic algorithms is to define a crossover probability "pcross" that controls the probability to perform a crossover process between two partners and generate two new offspring for the next generation. The rest of the population of the new generation would be organisms that have survived, hence with copies the exact DNA. Modify the next_generation() function to implement this feature.
Notebook by Mario GutiƩrrez-Roig, Lecturer in Data Science and Statistics at the University of Essex Licencia de Creative Commons