## Session 19

### Genetic Algorithms

#### Artificial Intelligence

today's slides in PDF

### Recap: Learning by Evolution of a Species

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!

Eugene Wallingford ==== wallingf@cs.uni.edu ==== November 13, 2001