problem with evolutionary algorithms degrading into simulated annealing: mutation too small?

Question

i have a problem understanding evolutionary algorithms. i tried using this technique several times, but i always ran into the same problem: degeneration into simulated annealing.

lets say my initial population, with fitness in brackets, is:

A (7), B (9), C (14), D (19)

after mating and mutation i have following children:

AB (8.3), AC (12.2), AD (14.1), BC(11), BD (14.7), CD (17)

after elimination of the weakest, we get

A, AB, B, AC

next turn, AB will mate again with a result around 8, pushing AC out. next turn, AB again, pushing B out (assuming mutation changes fitness mostly in the >1 range).

now, after only a few turns the pool is populated with the originally fittest candidates (A, B) and mutations of those two (AB). this happens regardless of the size of the initial pool, it just takes a bit longer. say, with an initial population of 50 it takes 50 turns, then all others are eliminated, turning the whole setup in a more complicated simulated annealing. in the beginning i also mated canditates with themselves, worsening the problem.

so, what do i miss? are my mutation rates simply too small and will it go away if i increase them?

here's the project i'm using it for: http://stefan.schallerl.com/simuan-grid-grad/ yeah, the code is buggy and the interface sucks, but i'm too lazy to fix it right now - and be careful, it may lock up your browser. better use chrome, even thought firefox is not slower than chrome for once (probably the tracing for the image comparison pays off, yay!). if anyone is interested, the code can be found here.

here i just dropped the ev-alg idea and went for simulated annealing.

ps: i'm not even sure about simulated annealing - it is like evolutionary algorithms, just with a population size of one, right?

Answer 1

In evolutionary algorithms, you don't necessarily cross everyone in your population with everyone else to produce a much larger set of offspring. There are many methods for determining the outcome of the breeding stage, but the most basic is to take the fitness of all elements, and use them as weights to randomly select partners for each member of the population. This usually ends up with the next generation having the same number of members as the previous population though some mating schemes end up with more (based on some kind of reasoning about the problem at hand) and chop off the lowest values (again for some kind of domain specific reasoning). You also throw out the previous generation for most problems.

Also, your fitness needs to be determined by the goal of reproduction, and can be very challenging to adequately derive for each scenario.

Answer 2

What you appear to be doing is generating all possible offspring and then selecting the fittest. That is both inefficient (because you are generating more candidates than you need) and will lead to premature convergence.

Instead you should generate just enough offspring to replace the population for the next generation. Select the appropriate number of candidates to use as parents (favouring fitter individuals) and then if you keep the offspring and discard the parents you should have the same number of individuals that you started with (glossing over elitism for the moment) - this is your next generation. Repeat until your termination condition is met.

The "favouring fitter individuals" qualification in the previous paragraph is intentionally vague. There are many different ways that you can do selection. It seems that you are choosing the strictly fittest individuals. This is truncation selection. It's only really effective for certain types of problem. Because you are ruthlessly culling the weaker individuals it often leads to premature convergence.

Ideally you want to give a weaker individual some chance of surviving because it might potentially produce fit offspring if paired with the right partner or mutated in the right way. That's why most selection strategies are probabilistic. For example, roulette wheel selection assigns a probability to each individual that is proportionate to its fitness score. So fitter individuals will survive more often but weak individuals still have some small chance.

Selection is usually with replacement, so the same individual might get selected to be a parent more than once for a given generation.

Another commonly used selection strategy is tournament selection. You may be interested in this documentation I wrote describing different selection strategies and elitism.