Reproduction

Now we have decided who gets to reproduce, we have to decide what "reproduction" means.

Reproduction could involve:

Pass on copy of yourself unchanged into the next generation (cloning).
Pass on copy with small random change (mutation).
Construct a child as a mix of two (or more) parents. This is called crossover in sexual reproduction.

Mutation (Asexual reproduction, Cloning)

Parent:

  0011010110011101101

Child could be identical (clone):

  0011010110011101101

Or have occasional mutation:

  0011010110011111101

The hope of mutation as heuristic search:
Parent was somewhat fit. (That is why it was picked to reproduce.)
Small change in it might make it fitter.

Crossover (Sexual reproduction)

Parents:

  0000000000000000000

  1111111111111111111

Children could be identical:

  0000000000000000000

  1111111111111111111

Or part of one, part of other. A synchronised "crossover":

  0000000000000111111

  1111111111111000000

And can add some mutation at random also while doing this.

And might do multiple crossover points:
Child = Start of parent A, middle of parent B, end of parent A.

The hope of crossover as heuristic search:
Parents were somewhat fit. (That is why they were picked to reproduce.)
One may be good at one thing. The other at another thing.
Crossover might get child which is good at both things. (Get best parts from each parent.)

Crossover in the middle of a gene

In machine evolution (as opposed to nature) the genotype probably encodes a number of well-defined genes/parameters.
In machine evolution (as opposed to nature) we know where the genes start/end.

Parents (change of color shows new gene):

0000000000000000

1111111111111111

Crossover only at gene boundaries:

0000000000001111

1111111111110000

If we do this, we only ever reshuffle combinations of existing genes. We never create a new gene with crossover.

Crossover in the middle of a gene:

0000000001111111

1111111110000000

This will create new genes.

Only need crossover? No mutation?

Crossover (in middle of genes) in both nature and machine evolution creates so many new genes that mutation is not that important.
In machine evolution, people have said: "Sex drives evolution. Mutation is irrelevant."
May make sense: In nature, less than 1 in a million genes mutates, whereas crossover and assortment (which from our point of view is the same as crossover) happen non-stop.

However, no mutation at all turns out to be bad. See the following.

P_m and P_c

We may define probabilities:

P_m - Probability of mutation. e.g. Probability that a bit flips during reproduction.
P_c - Probability of crossover. e.g. When making 2 children from 2 parents, probability that we do a random crossover or not. (If not, they are identical to the 2 parents.)

What does P_m = 1 look like?
- Why would this be bad?
- Try it out in code.
What does P_m = 0 look like?
- Let us have P_m = 0 but you still have crossover.
- If crossover only at gene boundaries, you never get any new genes other than initial population.
- If crossover in middle of a gene, you can get new genes. But still restricted: Imagine all individuals have a "0" in position i. Then crossover can never construct an individual with "1" in position i.
- In fact, it is probably worse. It seems we may get this feedback loop:
```
Genotype X is slightly fitter and popular.
Children are crossover of X and X, i.e. child is identical to X. 
Other crossovers produce nothing interesting. There is no mutation.
X gets more popular.
More children identical to X.
Whole population becomes X.
```
- Try it out in code.
- Try out P_m = 0.0001 and see if same effect.
What does "Pick only the no.1 fittest" look like?
- Say we only ever pick the no.1 fittest to reproduce. What does that mean for mutation and crossover?

Start noisy (big jumps) and decline (smaller steps over time)

A good heuristic for search might be:

At start, solutions are bad. Do a wide exploration. Big changes in individuals.
Later, have found some ok solutions. Explore closer around them rather than explore randomly. Small changes in individuals.

Often have:
Probability of mutation starts high and declines.
Probability of crossover starts high and declines.

What if the new individual is not viable?

For many problems, it is not simply a matter of constructing the individuals out of random values of the n parameters or genes, and then testing the fitness. Say the individual will simply not run at all if gene 1 is not > 3.

If you just encode the parameters as numbers, and search for combinations of numbers, it may be that 99 percent of parameter combinations won't even run.

Our initial random population will all have zero fitness, and so will almost any mutation or crossover of a fit individual.

Work on the encoding: Might try to change the genotype encoding to reflect this complexity, so the bitstring in gene 1 was simply interpreted as from 3 upwards, the bitstring in gene 2 was interpreted as 0-7, etc.

May still have search space with many unviable individuals: Consider constraints like: "Unless gene 3 < gene 7 < gene 11, the individual will not run"? This knocks out a huge chunk of the multi-dimensional space.

One solution is a loop when we are constructing new chromosomes:


given parents:

  do
  {
   crossover, constructing child1 and child2
   cout << "searching for viable crossover .. \n"
  }
  while ( ! ( child1.viable() && child2.viable() ) )

where viable() is defined in the application.

We need a similar loop in the initial randomise population function:


repeat n times:

  do
  {
   construct new randomised individual x
   cout << "searching for viable randomisation .. \n"
  }
  while ( ! x.viable() )

This can work, but only if chromosome interpretation has already done much of the job.
If 99 percent of individuals produced still aren't viable, these loops may take a long time to terminate.

May end up spending a lot of time on:

Redefining genotype coding so most individuals viable.
Redefining crossover and mutation for this problem (problem-specific) so they preserve whatever constraints are demanded.

Nature has this problem too:
In humans, each child is unique, not a clone of either parent, and so may have new problems.
In humans, miscarriage is common.
Some estimates are that the majority of fertilized eggs do not make it eventually to birth.
Miscarriage should not really be seen as a malfunction, but rather as a normal, inevitable part of the evolutionary search process.