Genetic algorithm for emoji-art
===

## Introduction

I had no idea what will be "art" for me in this assignment. Occasionaly, I've seen this in the comments to the youtube video:

I decided to implement something similar. This is just like ascii art, but cooler. I've found pack of 842 emojis, and even though pictures are not that much precise, some cool stuff can be done with it.

## To run:
You need PIL, matplotlib and skimage packets to be installed ether on your PC or in python virtual environment. You can simply write `pip install` to get them. Then, change some constants in `main.py` if necessary and just run `pyton3 main.py`. Results will be in `results` folder (please, do not change structure of archive, I have folders for results and for emojis in it and code will not work without them).

## Couple of words about the algorithm

My algorithm is a classical genetic algorithm. Population is initialized randomly, and then selection, crossover and mutation applied to find next generation. Selection uses simple mean square error to find out the fittest members of population, they said to "survive" natural selection. Coefficient of this survival of the best-fit members can be configured in the `main.py` file. Then, this best-fit members reproduce until dead members of population are replaced by new one. This new members usually have genes of the ones who survived selection, however, mutation is possible. It will happen more likely, if parents' chromosomes coinside, just like in real life (this property helped me to increase speed of convergence very much). Afterwards, we have new population, or, more precisely, next generation of the previous one.

## Data representation in the algorithm
Every population member has genotype and phenotype. Phenotype is a final picture, constructed out of genes, and genotype is collection of genes. In my case genotype is just an array of chromosomes. Actually, for this emoji picture chromosome contains only one gene, which is number of emoji, but I decided to leave this chromosome data structure to make everything just like in real world.

In short: each picture is divided into either 32x32 or 16x16 cells (can be configured), and for each such cell we have 842 possible genes, each encodes one of emojis.

## Selection mechanism and fitness function

Selection is as simple possible. Each genotype object has method to calculate phenotype, that return numpy array with image. This image then is compared to the original one: for each pixel differrence is calculated, then squared and mean of such differrencies will be our error. This is not exactly fitness, as fitness should increase over generation, while error decreases, but it is not a big deal to make something like fitness = initial_MSE - current_MSE, just no reason to put this into a code. After MSE calculation I choose part of the population with the least MSE (this amount is determined by `selection_coefficient` in `main.py`), and they are said to survive natural selection. Here is my code of selection:

def select_fittest(original_path, population_genome, selection_coefficient):
    fittest = []
    for i in range(len(population_genome)):
        fittest.append({
            "fitness": population_genome[i].calculate_fitness(original_path),
            "genotype": population_genome[i],
        })
    fittest.sort(key=operator.itemgetter("fitness"))
    fittest = fittest[0:int(len(population_genome) * selection_coefficient)]
    return fittest

And here is `calculate_fitness`:

    def calculate_fitness(self, original_path):
        original = imread(original_path)
        current = self.get_phenotype()
        return mse(original, current)

## Image manipulation techniques

In fact, I didn't use any special technique. All images are 512x512x3 numpy array, and when I construct phenotype of some member, I just copy this 32x32 or 16x16 emoji into some part of image. Member with the least MSE is saved to a directory result on each generation, no rocket science here as well.

## Crossover function

Crossover function is method of`genotype` class. Here is the code:

def crossover(self, another_genotype, mutation_coefficient):
        # we create fully random creature
        new_genotype = genotype(self._chromosomes_count)
        for i in range(self._chromosomes_count):
            """
            as creature is random, we leave small probability (mutation coefficient)
            to get chromosome not from one of parents, but random one. This will be
            our mutation.

            """
            if random.random() > mutation_coefficient and  not \
            (random.random() < mutation_coefficient * 10 and \
            self._chromosomes[i].get_genes == another_genotype._chromosomes[i].get_genes):
                if random.random() > 0.5:  # chromosome from first parent with probability 0.5
                    new_genotype._chromosomes[i] = self._chromosomes[i]
                else:  # chromosome from second parent with probability 0.5
                    new_genotype._chromosomes[i] = another_genotype._chromosomes[i]
        return new_genotype

This fuction gets genotype of another creature, and then produce new creature out of `self` genes, `another_genotype` genes and, possibly, random genes if there were mutation. Just like mother, which gets genes of father and then baby has something from both mother and father.
1. New creature is initially random. It is not quite natural, but it will help us to handle mutation later.
2. We have small chance for chromosome to remain random. It will be ten times bigger, if chromosomes of parents coinside, but still not that huge.
3. If there were no mutation, we have equal chances to get each chromosome either from mother(self in terms of python) or from father(another_genotype)
4. After each chromosome is calculated we return this new genotype
## Mutation criteria

In `main.py` there is a variable called `mutation_coefficient`, which corresponds to a chance for a chromosome to get new, random value on each generation. Mutation is performed during crossover, adult organisms cannot change their genotype (again, as in nature). Interesting point is that probability of mutation is 10 times higher if parent's genes are the same. This helps to improve so called biodiversity, and improve results even if initially there is not so much good genes.

## Art for me

Art is not necessarily mean object made by hand. Someone "does" art if:
* It is a hobby for him/her, no real masterpiece is done by a person who does not like doing this;
* This person is very good in this job.
I think, this is enough. No matter what it is: painting, pottery, writing songs, cooking or teaching, if you like it and you are good at it, this is definitely art.

## Artistic aspect of output images.

I can't say this is art from the perspective "this computer did some art". I did this art, and the algorithm is as much an instrument as brush or violin. And from this perspective this is definitely art: I enjoyed writing this algorithm and playing with an input very much and this output pictures look good, at least for me. Second is quite subjective, but I hope art contest will decide objectively. What I like about this kind of pictures is that it is not always obvious what is depicted here, and you start guessing, your fantasy can find something you like on this pictures.

## Picture examples:
original:

GENERATIONS = 200
POPULATION = 100
PICTURE_SIZE = 32
MUTATION_COEFFICIENT = 0.001
SELECTION_COEFFICIENT = 0.30

Generated with the following parameters:

##



##

Another example:

Results are like stereoimages: it's hard even to recognize an object, but if you've seen an original image, the output looks very similar to the original, especially if algorithm runs not very long. The previous one and the following are good examples.

Here, are just 150 generations, and population is just 100 members, which is quite not enough for 16x16 emojis, but I left this photo as well as you can see silhouette of UI, you can imagine it even by this picture (at least for me it is so).
See this nice blue ski, this yellow UI with blue windows? I do. You can see this even better if you squint
Let's observe another example. Actually, approximation is not very precise, it is hard to understand what is depicted on it. However, shape and colours are preserved, I think, If we blur original image it will be very similar to blurred approximation.


This is me out of 16x16 emoji: