Picking the fittest

Recall our Genetic Algorithm and our definitions.

Now we need to figure out how to pick who "reproduces" in each generation.

Do only the top n, or the top n percent, get to reproduce? We could do a cut-off like that, or we could set up a scheme where fitter individuals were more probable to reproduce, and less fit less probable, as follows.

Probability of reproducing - using sum of fitnesses

Let the probability of an individual reproducing be:

p = my fitness
    ---------------------------------
    sum of fitnesses of all creatures

With this scheme, fitness must be positive.
Q. Why?
In fact, fitnesses must all be greater than zero (not equal).
Q. Why?

If fitness is positive, then p is a number between 0 and 1, and the sum of all these probabilities is 1. A separate page shows how to make a choice according to probabilities.

One problem with the above is if there is a large population. Let there be one individual with fitness 1, and 100 individuals with fitness 0.2. Then the probability of the fit individual being chosen is only 1/21. One way around this is the following:

Boltzmann "soft max" distribution

Probability of reproducing - using Boltzmann "soft max"

The Boltzmann or "soft max" distribution gives us a flexible way of choosing who reproduces.

Let individual i have fitness f(i). Then its probability of reproducing, p(i), is:

By varying the temperature T, we can change it from only the very fittest reproduce (perhaps towards the end of run) to almost everybody has a chance, probabilities are almost equal (start of run). To be precise, T large at start of run, small towards end of run. The fittest will always be strictly more probable.

Variable population size

Fitter individuals reproduce. If we allow the number of children they have to vary, we may get a variable population size.

Q. As a programmer, what could happen if we have a variable population size?

Fixed population size

Simpler to have fixed population size.


repeat (population size / 2) times 
{
  pick individual from whole population according to probabilities
  pick individual from whole population according to probabilities
   (may be the same individual!)
  construct 2 new individuals from these 2 parents 
}

entire old population is now replaced by the new population
 (keep constant population size)

If we do this, make the population size even.

Simple summation of fitness v. Boltzmann

Consider again using simple summation of fitness when deciding who reproduces:

p = my fitness
    ---------------------------------
    sum of fitnesses of all creatures

If one individual has fitness 1, and 100 individuals have fitness 0.2:
The fit individual has odds of 1/21 of being picked in any single choice.
With 100 (approx) pickings, it gets picked approx 5 times as parent.
Approx 5 of 100 parents are the fit genotype.
If one individual has fitness 1, and 1000 individuals have fitness 0.2:
The fit individual has odds of 1/201 of being picked in any single choice.
With 1000 (approx) pickings, it gets picked approx 5 times as parent.
Approx 5 of 1000 parents are the fit genotype.
It scales badly.
Q. Consider if one individual has fitness 1, and n individuals have fitness 0.2.
As n goes to infinity, prove that number of times the fit individual is picked goes to just 5 (out of huge n).
This is unsatisfactory.
If we want it to be chosen more times, we use a Boltzmann distribution with low temperature T.
Even with a huge population, as T -> 0 the probability of the fit one being picked -> 1