Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


Reproduction

Reproduction could involve:


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.

Crossover (in middle of genes) in both nature and machine evolution creates so many new genes that mutation 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.




Pm and Pc

We may define probabilities:

Imagine if Pm = 1 and Pc = 0.
Then children are clones of parents, with mutation.
Q. Why would this be a terrible search heuristic?

Imagine if Pm = 0 (no mutation) but you still have crossover. Then:


Q. If, when picking who reproduces, we only pick the single best individual each time, then what happens with mutation and crossover?



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

Good heuristic for search might be:

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:

  1. Redefining genotype coding so most individuals viable.
  2. 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.



Feeds      w2mind.org

On Internet since 1987.