Dr. Mark Humphrys School of Computing. Dublin City University. My big idea: Ancient Brain Search:

# Reproduction

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.

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:
• Pm - Probability of mutation. e.g. Probability that a bit flips during reproduction.
• Pc - 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.)
```
```
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:
• If crossover only at gene boundaries, you never get any new genes other than initial population. Very limited search.
• If crossover in middle of a gene, you can get new genes. But still might be restricted: Imagine if somehow all individuals have a "0" in position i. Then crossover can never construct an individual with "1" in position i.

```
```
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:
• 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:

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      ancientbrain.com

On the Internet since 1987.