Genetic/Evolutionary algorithm - Painter

Question

My task:

Create a program to copy a picture (given as input) using primitives only (like triangle or something). The program should use evolutionary algorithm to create output picture.

---

My question:

I need to invent an algorithm to create populations and check them (how much - in % - they match the input picture). I have an idea; you can find it below.

So what I want from you: advice (if you find my idea not so bad) or inspiration (maybe you have a better idea?)

---

My idea:

Let's say that I'll use only triangles to build the output picture.

My first population is P pictures (generated by using T randomly generated triangles - called Elements).

I check by my fitness function every pictures in population and choose E of them as elite and rest of population just remove:

    To compare 2 pictures we check every pixel in picture A and compare his R,G,B with
    the same pixel (the same coordinates) in picture B.
    I use this: 
           SingleDif = sqrt[ (Ar - Br)^2 + (Ag - Bg)^2 + (Ab - Bb)^2]
    then i sum all differences (from all pixels) - lets call it SumDif
    and use:
           PictureDif = (DifMax - SumDif)/DifMax
    where
           DifMax = pictureHeight * pictureWidth * 255*3

The best are used to create the next population in this way:

    picture MakeChild(picture Mother, picture Father)
    {
             picture child;
             for( int i = 0; i < T; ++i )
             {
                      j //this is a random number from 0 to 1 - created now
                      if( j < 0.5 ) child.element(i) = Mother.element(i);
                      else child.element(i) = Father.element(i)
                      if( j < some small % ) mutate( child.element(i) );
             }
             return child;
    }

So it's quite simple. Only the mutation needs a comment: So there is always some small probability that element X in child will be different than X in his parent. To do this we make random changes in element in child (change his colour by random number, or add random number to his (x,y) coordinate - or his node).

So this is my idea... I didn't test it, didn't code it. Please check my idea - what do you think about it?

Chlodwig

You could maybe try to vary the objective function so that in the beginning you are trying to match bigger patches than single pixels. Maybe apply a filter so that it coarsens the picture and candidates, and you can do the mating and mutation in such a way that all the elements within one such patch get moved. You reduce the size of the patches progressively until you get to pixels. (Now that I think about it, it's like using simulated annealing within a genetic algorithm.) – Aspiration

This blog post appears to detail what you're trying to achieve, though he doesn't select from a population at each step, simply compares it to the previous iteration. That feels more like simulated annealing than anything genetic to me, but nevertheless I think looking over it would be of value to you. – Sushi

Answer 1

I would make the number of patches of each child dynamic and get the mutation operation to insert/delete patches with some (low) probability. Of course this could result in a lot of redundancy and bloat in the child's genome. In these situations, it is usually a good idea to use the length of an individual's genome as a parameter of the fitness function so that individuals get rewarded (with a higher fitness value) for using fewer patches. So for example if the PictureDif of individuals A and B are the same but the A has fewer patches than B, then A has a higher fitness.

Another issue is the reproductive operator that you proposed (namely, the crossover operation). In order for the evolutionary process to work efficiently, you need to achieve a reasonable exploration and exploitation balance. One way of doing this is by having a set of reproductive operators that exhibit a good fitness correlation [1] which means the fitness of a child must be close to the fitness of its parent(s).

In the case of single parent reproduction you only need to find the right mutation parameters. However, when it comes to multi-parent reproduction (crossover) one of the frequently used techniques is to produce 2 children (instead of 1) from the same 2 parents. For the first child, each gene comes from the mother with the probability of 0.2 and from the father with the probability of 0.8, and for the second child the other way around. Of course after the crossover, you can do the mutation.

Oh and one more thing, for the mutation operators, when you say

... make random changes in element in child (change his colour by random number, or add random number to his (x,y) coordinate - or his node)

it's a good idea to use a Gaussian distribution to change the colour, coordinate etc.

[1] Evolutionary Computation: A unified approach by Kenneth A. De Jong, page 69

Snapper