Getting it on, with Genetic Algorithms

Example

Knowledge

What goes into a GA?

Give me the sample data!

What’s in a GA? DNA or Genes

What's in a GA? Populations

Example: Generated Population

Example: Breeding

Randomly generated genes

Breeding Pool

• A Population is a generation of actors

• Populations have sizes
• Some GA’s might use fixed or variable population sizes

• The Population or generation size is a critical input to any GA

• Genes are a metaphor for features or traits in a problem space

• Collectively, we call the genes, “DNA”

• GA’s vary, mix and mangle DNA to discover optimal problem solutions

• Applying GA means carefully selecting the problem features to use in your DNA

What are Genetic Algorithms?

A few generations...

Actors (and their genes)

Using paired crossover:

• Pivot Point := random() * 100 % genesPerActor
• Pull genes from each contributing partner, switching the contributor at the pivot point

Genetic Algorithms (GAs) use sample populations, the fitness of each actor in that population, and evolutionary principles modeled after biological reproduction in an effort to discover some truth, prediction or optimization.

Example: RPS Fitness

RPS Generational Mutation

What's in a GA? Actors

What’s in a GA? The Game of Life

Opponent’s Strategy: Always choose Paper

Lets Talk Specifics

(RPS)

Rock, Paper, Scissors

Play

Record -1 -1 1 1 0 1 0 1 0 0 1 1

Each of every Actor’s genes in the next generation will mutate to a random value at the rate specified by the mutation rate

We Live: First Generation

We Make: Breeding

We live, we do, we make and we die.

Score -1 2 1 2

• Actors have DNA, contributed by parents or chance

• Actors are evaluated for fitness

• Actors breed, some more than others

• Actors die

Fitness Function: Lets use Exponential

ff(actor.score) := floor(2^actor.score)

• Seed your initial generation’s DNA
• Random?
• Careful selection?
• Smoothed Random?

• GA’s might work faster if an initial generation has greater variance in actor fitness

0 4 2 4

• The Pool: Based on their fitness, each actor is more or less likely to contribute DNA to each actor in the next generation

• Crossover: Given two (or more) parents, select a random cross over point, before which genes are contributed by one parent and the other after

• Mutation: For each gene in the derivative actor, randomly mutate the gene with some probability specified by the “mutation rate”

We Die: Start Over

We Do: Fitness

• Choose to make the value of the gene, a move

• Gene Expressions: Rock, Paper, Scissors

• Winning is about predicting the next move so each actor needs multiple genes

• This makes sequence length and gene position important

• The new generation is here, and we’ve learned what we could from the old guard

• Send them out for GC

• Rinse off the mess and start all over again

To evaluate each actor’s fitness, you need two things:

• Evaluation Function: the actor must be tested against some external goal, generate a score
• Did their genes correctly the next winning RPS move?

• Normalization Function: How did they do compared to their peers?
• Linear? Exponential? Logarithmic?

Getting it on, with Genetic Algorithms

by Jeff Nickoloff