Evolutionary Computation

Screen%20Shot%202012-05-07%20at%2010.18.24%20AM.png

Human Genome

The human genome consist of 3 billion DNA base pairs. Each base pair can be one of four nucleotides

  • (A)denine
  • (G)uanine
  • (C)ytosine
  • (T)hymine

We know of 30,000 genes that each code for a specific protein. 97% of the genomes do not code for proteins - we know they're not junk because there are sequences of up to 200/300 pairs that occur across many other species.

Evolutionary Computation

look at slide 5

Bit String Operators (Genetic Algorithm)

The aim of this is to emulate biology - creating children with genes from both parents.

  • One-Point Crossover: Start copying from one pair then flip over and copy from the other

Screen%20Shot%202012-05-07%20at%2010.34.19%20AM.png

  • Two-Point Crossover: Start copying from one pair, flip over and copy from the other, then flip back again.

Screen%20Shot%202012-05-07%20at%2010.34.31%20AM.png

  • Point Mutation: Give it a length and witch one bit randomly

Screen%20Shot%202012-05-07%20at%2010.34.36%20AM.png

S-expression Trees (Genetic Programming)

Swap branches of the trees (subtrees) to create combined children.

Screen%20Shot%202012-05-07%20at%2010.34.56%20AM.png

Continuous Parameters (Evolutionary Strategy)

Reproduction is essentially just copying - eventually you'll have seen everything.

Mutation is adding random noise to each weight (or parameter), from a Gaussian distribution with speciļ¬ed standard deviation.

  • Sometimes, the standard deviation evolves as well

Fitness Functions

  • "Deceptive" Landscapes
    • Local optima
    • Premature Convergence

Example:
"1001110101001"
a) Fitness = number of 1s
b) Fitness = 100 if all zeroes, 0 otherwise
c) Fitness = 100 if all zeroes, num 1s otherwise
d) Fitness = 7 if there's a run of 7 zeroes or 1s, and 14 if 7 run of both

These are the fitness functions.

a) = small change in string = small change in fitness (pointing either upwards or downwards, in correct direction).
this is super easy to work out. hill climbing would get it.

b) Needle in a haystack problem. Fitness is completely flat everywhere except one good point. You get no information from adjusting the string. A totally random search would work just as well.

c) deceptive landscape - local optima for more 1s, even tho that's worse than all 0s. string of length 20, so it'll be much worse than all 0s.

d) also chance.
shock physics example: