Session 19

Genetic Algorithms

810:161

Artificial Intelligence

Recap: Learning by Evolution of a Species

Start with a set of problems.
Start with a population of rules.

For some number of iterations:

1. For each rule,
   1. Run the rule against each problem.
      Collect the results of each run.
   2. Combine the results to determine the fitness of the rule.

2. Construct a new population of rules from the current set based on the fitness of each rule.

The effect of this sort of evolutionary learning is a preference for successful phenotypes, behaviors that perform well on the task given in the environment given.

How to Generate New Rules

Let's consider three different ways that programs can change from one generation to the next in an evolutionary system...

Direct Reproduction

Direct reproduction equates to asexual reproduction in the animal kingdom. A single parent rule gives rise to a child:

     A rule:          1#00# -> 0111#
     Generalization:  1##0# -> 0111#

     A rule:          1#00# -> 0111#
     Specialization:  1#00# -> 01110 
     Specialization:  1100# -> 0111#

Consider our rules for the wall-following robot:

     if x1 and not x2 then move east
     if x2 and not x3 then move south
     if x3 and not x4 then move west
     if x4 and not x1 then move north
     default action:       move north

Crossover

Crossover equates to sexual reproduction in the animal kingdom. Two (or more) parents rule gives rise to a child:

    Parent 1:   1#00# -> 0111#
    Parent 2:   01#10 -> 11001

    Child 1:    1#00# -> 11001

    Child 2:    1#010 -> 11001

    Child 3:    1##10 -> 1101#

Consider our rules for the wall-following robot:

     if x1 and not x2 then move east
     if x2 and not x3 then move south
     if x3 and not x4 then move west
     if x4 and not x1 then move north
     default action:       move north

Mutation

Mutation equates to mutation in the animal kingdom! Sometimes, a child differs in a seemingly random way from its intended genotype:

    Rule:       1#00# -> 0111#
    Mutation!   1#01# -> 0111#

    Rule:       1#00# -> 0111#
    Mutation!   1#00# -> 0011#

What distinguishes mutation from direct reproduction is that, in direct reproduction, a change is made to the parent rule for a reason. "Mutation happens." And it can happen to an offspring generated either directly of by crossover. Or it can just happen to an individual that survives to the next population.

Consider our rules for the wall-following robot:

     if x1 and not x2 then move east
     if x2 and not x3 then move south
     if x3 and not x4 then move west
     if x4 and not x1 then move north
     default action:       move north

Exercise: Fixing the Learning Parameters

How often should rules reproduce?

How often should rules mutate?

How many new rules should be created?

How strong should the new rules be?

The Result: Genetic Algorithms

Fill in the blank as time permits...

FILL IN THE BLANK

... as time permits.

Wrap Up

• Homework -- None for now. We will have a new assignment after a couple of weeks discussing learning.

• Lab Section -- You are now working on your project. Your current "assignment", which is due tomorrow at 4:00 PM, is specified in your project proposal. Get to work!