Incorrect results with genetic algorithm image evolution
Question: I'm attempting to implement a program originally created by [Roger
Alsing](http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-
mona-lisa/). I've done quite a bit of research on what other people have
implemented. I decided to write my program in python, and use basic triangles
as the shapes. When I run the program, it does not show improvement after more
generations (The triangles tend to just disappear). I'm assuming something is
wrong with my mutate function. Can anyone tell me why its producing less than
satisfactory results?

My code:

    
    
    import random
    import copy
    from PIL import Image, ImageDraw
    
    optimal = Image.open("mona_lisa.png")
    optimal = optimal.convert("RGBA")
    
    size = width, height = optimal.size
    
    num_shapes = 128
    
    generations = 50000
    
    def random_genome():
        elements = []
    
        for i in range(num_shapes):
            x = (random.randint(0, width), random.randint(0, height))
            y = (random.randint(0, width), random.randint(0, height))
            z = (random.randint(0, width), random.randint(0, height))
            r = random.randint(0, 255)
            g = random.randint(0, 255)
            b = random.randint(0, 255)
            alpha = random.randint(10, 255)
    
            elements.append([x, y, z, r, g, b, alpha])
    
        return elements
    
    def render_daughter(dna):
        image = Image.new("RGBA", (width, height), "white")
        draw = ImageDraw.Draw(image)
    
        for item in dna:
            x = item[0]
            y = item[1]
            z = item[2]
            r = item[3]
            g = item[4]
            b = item[5]
            alpha = item[6]
    
            color = (r, g, b, alpha)
    
            draw.polygon([x, y, z], fill = color)
    
        return image
    
    def mutate(dna):
        dna_copy = copy.deepcopy(dna)
    
        shape_index = random.randint(0, len(dna) - 1)
        roulette = random.random() * 2
    
        if roulette < 1:
    
            if roulette < 0.25:
                dna_copy[shape_index][3] = int(random.triangular(255, dna_copy[shape_index][3]))
    
            elif roulette < 0.5:
                dna_copy[shape_index][4] = int(random.triangular(255, dna_copy[shape_index][4]))
    
            elif roulette < 0.75:
                dna_copy[shape_index][5] = int(random.triangular(255, dna_copy[shape_index][5]))
    
            elif roulette < 1.0:
                dna_copy[shape_index][6] = int(0.00390625 * random.triangular(255, dna_copy[shape_index][6] * 255))
    
        else:
    
            if roulette < 1.25:
                dna_copy[shape_index][0] = (int(random.triangular(width, dna_copy[shape_index][0][0])), int(random.triangular(height, dna_copy[shape_index][0][1])))
    
            elif roulette < 1.5:
                dna_copy[shape_index][2] = (int(random.triangular(width, dna_copy[shape_index][3][0])), int(random.triangular(height, dna_copy[shape_index][4][1])))
    
            elif roulette < 1.75:
                dna_copy[shape_index][3] = (int(random.triangular(width, dna_copy[shape_index][4][0])), int(random.triangular(height, dna_copy[shape_index][5][1])))
    
        return dna_copy
    
    def fitness(original, new):
        fitness = 0
    
        for x in range(0, width):
            for y in range(0, height):
                r1, g1, b1, a1 = original.getpixel((x, y))
                r2, g2, b2, a2 = new.getpixel((x, y))
    
                deltaRed = r1 - r2
                deltaGreen = g1 - g2
                deltaBlue = b1 - b2
                deltaAlpha = a1 - a2
    
                pixelFitness = deltaRed + deltaGreen + deltaBlue + deltaAlpha
    
                fitness += pixelFitness
    
        return fitness
    
    def generate():
        mother = random_genome()
        best_genome = mother
        best_fitness = fitness(optimal, render_daughter(best_genome))
    
    
        for i in range(generations):
            daughter = copy.deepcopy(best_genome)
            daughter = mutate(daughter)
    
            daughter_fitness = fitness(optimal, render_daughter(daughter))
    
            if daughter_fitness < best_fitness:
                best_genome = daughter
                best_fitness = daughter_fitness
    
            if i % 50 == 0:
                print i
    
            if i % 1000 == 0:
                render_daughter(best_genome).save("iterations/output_" + str(i) + ".png")
    
    if __name__ == "__main__":
        generate()
    

The beginning image I am using:

![Mona Lisa](http://i.stack.imgur.com/IclTk.png)

The output image after 1,000 generations:

![Output 1000](http://i.stack.imgur.com/5cWEC.png)

Output image after 5,000 generations:

![Output 5000](http://i.stack.imgur.com/bwdwm.png)


Answer: You're checking wheter the new fitness is smaller than the current fitness:

    
    
    if daughter_fitness < best_fitness:
    

The fitness you calculate, however, can be negative:

    
    
    deltaRed = r1 - r2
    deltaGreen = g1 - g2
    deltaBlue = b1 - b2
    deltaAlpha = a1 - a2
    
    pixelFitness = deltaRed + deltaGreen + deltaBlue + deltaAlpha
    
    fitness += pixelFitness
    

The various `delta*` variables can be negative or positive; your test will
favour negative deltas, increasing the whiteness of the "best" image (the
higher values of `r2`, `g2` etc, the lower the fitness, and the whiter the
image, until they are all at 255, 255, 255. I don't know if increasing alpha
increases or decreases the transparency).

Thus, you should take the absolute value of the differences:

    
    
    deltaRed = abs(r1 - r2)
    deltaGreen = abs(g1 - g2)
    deltaBlue = abs(b1 - b2)
    deltaAlpha = abs(a1 - a2)
    

You could also consider the sum of the square, or square root of the sum of
squares (which, basically, turns it into a least-squares fitting routine):

    
    
    deltaRed = r1 - r2
    deltaGreen = g1 - g2
    deltaBlue = b1 - b2
    deltaAlpha = a1 - a2
    
    pixelFitness = math.sqrt(deltaRed**2 + deltaGreen**2 + deltaBlue**2 + deltaAlpha**2)
    
    fitness += pixelFitness
    

Finally, I noticed your program doesn't work for me. It's in the second half
of your `mutate()` function, where you assign new values to x, y or z, but use
indices above 2. `random_genome()` shows that you try to access colour values
instead, which are integers, and even attempt to index those.

This leads to exceptions, so I don't even know how you could get this program
running. It either never ran in the first place, or you didn't properly copy-
paste. I've changed that to

    
    
    if roulette < 1.25:
        dna_copy[shape_index][0] = (int(random.triangular(
            width, dna_copy[shape_index][0][0])), int(
                random.triangular(height, dna_copy[shape_index][0][1])))
    elif roulette < 1.5:
        dna_copy[shape_index][1] = (int(random.triangular(
            width, dna_copy[shape_index][1][0])), int(
                random.triangular(height, dna_copy[shape_index][1][1])))
    elif roulette < 1.75:
        dna_copy[shape_index][2] = (int(random.triangular(
            width, dna_copy[shape_index][2][0])), int(
                random.triangular(height, dna_copy[shape_index][2][1])))
    

which seems to do what you want.

