The Value of Crossover

In my last (real) post I wrote about the effects of elitism on a population, and concluded that a small amount of elites, who cloned themselves, produced the greatest increase in population fitness. Just like in real life.

I also wrote:

I also don’t have the time to run everything multiple times (takes days at the moment).

I am pleased to say that I rewrote the program a weekend ago using the CUDA runtime library, allowing me to use my GPU and speed things up quite a bit. Which is good, because I screwed up running this test 3 times and had to restart it – if I was on the old version I would not have the time for such second chances.

This program is mostly similar to the first, with a few differences:

No Elitism

Using the findings of the previous post, I decided to set this one up using the “Only the Best” method. As a reminder, in this heuristic parents and kids are both evaluated and on the top N are passed onto the next generation. Flexible elitism.

Pixel Fitness

The fitness metric was changed slightly – it’s still RMSE – but at the pixel level instead of color channel level. Conceptually there is almost no difference, what’s important to know is that fitness still increases without bound the more similar the images are, and that the fitness levels in this post cannot be directly compared to the CPU version.

Haploid Chromosomes

In the previous model, the “chromosomes” had two genomes each, a “dominant” one and a “recessive” one. During crossover, the dominant and recessive genomes would crossover. This all happens within a single artists. Babies are made by taking combining the dominant genome from one parent with the recessive genome of the other.

In the haploid model of crossover, the parents combine their genomes at the crossover point to make a new, child genome. i.e. the child might get the first 20% of its genome from parent 1 and the remaining 80% from parent 2.

I also changed genome initialization so that all triangles are set to invisible in the beginning (previously the first triangle was made visible).

No Bit Level Crossover

I didn’t have time to implement it and I don’t think it makes a difference. Bit level crossover is basically byte level crossover with an extra point mutation.

No Location Simulation

In this version genomes are free to mate with anyone other genome (in stochastic proportion to their fitness).

Randomness Fixed

The random seed actually works in this version – I can guarantee that all runs started with the same set of genomes and all runs are repeatable.

Effort

Another difference is that you no longer specify the number of generations you want to run, but instead the effort you want the algorithm to put into searching for the best image.

$$effort = \text{population size} + \left(\text{number of children} \times \text{number of generations}\right)$$

This allows me to compare settings with different numbers of population and children on even footing.

Methodology

This time I ran the program on three different types of images: a picture, a drawing and a drawing with a transparent background. I wanted to see if a different type of image would affect the results.

From left to right: A picture of a robotic girl, a picture of a red panda, a transparent of Lina from DotA 2I ran the program with 100,000 effort, 100 population that produces 100 children each round with 100 triangles in their genomes and adjusted their crossover chance between [0,1] in 0.1 increments. I ran the program 10 times per image per increment to produce the average I used for the graph below:



The error bars represent the 95% confidence interval.

From this light testing it seems that crossover does indeed improve fitness. This is a relief because despite there being theory on why it should improve fitness, I have not personally discerned a difference. This is probably because the difference is only dramatic between 0 and 0.25. I seems that it’s more important to have some crossover than how worry about how much crossover.

I’ll be using a 100% crossover chance going forward and I’ll try to tease out the difference between crossover at the byte level and crossover at the triangle level.

 

Published by

Amy Jie

Not dead yet! =^__^;;=

Leave a Reply

Your email address will not be published. Required fields are marked *