Elitism

Elitism in genetic algorithms refers to the top N members of a population P getting a free pass to the next generation. Leaving \(\vert P \vert – N\) spaces to be filled with the children of high performing parents. The goal of elitism is to add additional selective pressure to the population, causing early convergence (and higher fitness) but reducing genetic diversity. For those of you familiar with simulated annealing, adding elitism is like reducing the size of the step of your gradient descent algorithm. You’re going to climb the hill faster, but you’re less likely to find the biggest hill to climb.

In my program, there is an additional option for elitism, cloning. If cloning is set to true the top N members of the population get to skip into the next round, but they are also exempt from crossover and mutation in the next round. This has two effects:

  1. This lowers the genetic diversity even more
  2. This makes the fitness a monotonically increasing function over each generation because the highest fitnesses of each generation cannot be less than the highest fitness of the last generation.

Cloning Comparison

I ran the program with 10 triangles, 50,000 effort, simulating location with a 4 dimensional adjacency matrix and 25 members in the population on the below image:

Lina from Dota 2

“Effort” is population size \(\times\) number of generations. This is so different population sizes can be compared fairly and allows us to ask the question, which is better: 1 artist that evolves over 100 generations or 100 artists evolved over 1?  In this example, 50,000 effort translates to 2,000 generations of 25 artists.

Using these settings, I set elitism from [0,25] per-mutated with cloning set to either “true” or “false.” I ran five trials for each elitism setting and took the average to plot the following graph:

Graph comparing the runs of a genetic algorithm with varying levels of elitism, with cloning of elites set to true or false

The first thing to notice is that having any number of elites is better than having no elites. This makes sense when you notice that no elites allows the population to stabilize at lower levels, where it is unlikely that any one artist will mutate beneficially enough to dominate the gene pool and force fitness upwards, before it returns to the mean. This can be thought of as a stable period in the punctuated equilibrium model of evolution, which is not what we want, we want constant pressure to increase fitness. Elitism artificially magnifies the small differences by anchoring them in the gene pool so they can’t return to the mean.

At elitism=25, cloning=true the fitness should never change after the first. For cloning=false it is basically an exercise in naive, parallel hill climbing. However I just came to the terrible realization that I was doing elitism wrong. Instead of taking the top N members of the population after proportionally allocating them reproductive preferences by fitness. This means there is a small chance for some artists to not be cloned and that in all my previous tests some artists were being over-cloned, further tilting the balance in favor of convergence over diversity.

Fuck.

I’ll end up redoing everything but I’ve spent too much time to not write this.

The second thing to notice is that cloning produces strictly better results than non-cloning. This is probably because cloning forces the fitness to increase, where as elitism without cloning simply makes it more likely.

Cloning: True - Elitism 2
Cloning: True – Elitism: 2
Cloning: False - Elitism 2
Cloning: False – Elitism 2

Another thing to notice is that when cloning is set to true, the gap between the elite and average artists grows. In this example, the top artists in the cloning=true run are, on average 3.7 std devs above the average fitness, where in the cloning=false run the elites are, on average, 2 std devs above the average fitness. In addition, in the cloning=false run, the difference remains constant, where in the cloning=true it seems to grow linearly with the number of generations, so the average gap of the last 10 generations is 4.7 std deviations.

Elitism Proportion

The next question I had was how many elites does one need in the population? In the first study, 4 is the optimal amount. Does this mean ~4 elites are optimal, or does this mean ~16% of the population being elite is optimal?

To find out I ran the same study but with population size 100. I kept all other options the same (like effort 50,000, resulting in 500 generations). I only ran with cloning=true since the results of the previous study showed that to be the dominant setting.

Elitism Test: Population 100

You can immediately see the similarities to the population 25 run. Max fitness shoots up and then gradually decreases and flat lines as it increases. In this sample the peak occurs at the elitism=8 mark. The first thing that comes to my mind is that we quadrupled the population and only needed to double the number of elites, suggesting a half or square root relationship. Further testing is required.

Only The Best

The last thing I tried was a bit different. In this method, I bred the next generation, scored them and compared them with their parents. This means there was \(2\times\vert P\vert\) artists alive at a time. The the top \(\vert P \vert\) were spared and the bottom half were culled before starting the process over again.

This is, in no way, in the spirit of genetic algorithms. You’re not allowed to have two generations alive at once and allow parents to live eternal if they’re good enough. It’s basically parallel hillclimbing with a stupid step function, and it’s sort of comparable to classic elitism because of this.

So, how does it compare? Really well, actually. I ran it 6 times and it had an average max fitness of 6.68, which is comparable, and certainly within the margin of error, of the max elitism=8, population=100 max fitness of 6.71. It is interesting to not that the average fitness of the artists was much higher as well: 6.65 versus 6.00. This suggests that this method has the best of both worlds (cloning true/false). It’s also incredibly disheartening because it seems that the best method for arranging triangles is some sort of parallel hill climbing and not a classic GA.

The more I investigate GA’s it seems that they are just bad versions of hill climbing. Provably? Not always, but probably.

Caveats

Now, I didn’t do the stats properly because I’m lazy, so I don’t know what the margin of error is on these lines, but I imagine it’s substantial. I also don’t have the time to run everything multiple times (takes days at the moment). So in the future I’d like to run these test to significance.

There is the chance that if I ran these with more effort that the greater diversity of cloning=false would generate higher fitnesses in the long run. Based on every run I’ve ever done, I seriously doubt this is the case but is a possibility.

Also, as stated above, I screwed everything up so this is some weird stochastic form elitism instead of pure elitism.

 

 

 

Published by

Amy Jie

Not dead yet! =^__^;;=

Leave a Reply

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