Genetic Algorithms

This talk is based on

Tom M. Mitchell. Machine Learning. [1] McGraw Hill. 1997. Chapter 9.
and his slides [2].

John Holland, father of Genetic Algorithms

Genetic Algorithms are a learning method that simulates biological evolution.
Instead of searching general-to-specific, or simple-to-complex hypothesis, they generate hypothesis like offsprings
Evolution is known to be successful.
GAs can search over hypothesis that contain complex interacting parts.
GAs are easily parallelized.

GA(Fitness, Fitness-threshold, $p, r, m$)
Initialize: $P \leftarrow p$ random hypotheses.
Evaluate: for each $h$ in $P$, compute $Fitness(h)$
While [$max_{h}$ Fitness(h)] < Fitness-threshold do
1. Select: Probabilistically select $(1-r)p$ members of $P$ to add to $P_{S}$, select each $h_i$ with probability \[ \Pr(h_{i}) = \frac{Fitness(h_{i})}{\sum_{j=1}^{p} Fitness(h_{j})} \]
2. Crossover: Probabilistically select $\frac{r \cdot p}{2}$ pairs of hypotheses from $P$. For each pair, $\langle h_{1}, h_{2} \rangle$, produce two offspring by applying the Crossover operator. Add all offspring to $P_{s}$.
3. Mutate: Invert a randomly selected bit in $m\cdot p$ random members of $P_{s}$. $m$ is the mutation rate.
4. Update: $P \leftarrow P_{s}$
5. Evaluate: for each $h$ in $P$, compute $Fitness(h)$
Return the hypothesis from $P$ that has the highest fitness.

Hypotheses in GA are binary strings.
They can be tricky to generate.
For example, if Outlook can be either Sunny, Overcast, or rain, and Wind can be Strong or Weak, how do re represent \[ (Outlook = Overcast \vee Rain) \wedge (Wind = Strong) \] With something like

Outlook Wind

011 10
We can then use this as rule preconditions. For example the rule

IF Wind = Strong THEN PlayTennis = yes

can be represented with the string

Outlook Wind PlayTennis

111 10 10

Outlook	Wind
011	10

Outlook	Wind	PlayTennis
111	10	10

Single-point crossover splits the strings into two parts and merges them.
Two-point crossover splits the strings into three parts and merges them.
Uniform crossover each bit is chosen with equal and independent probability.
Point mutation makes small random changes to the string.

Fitness proportionate selection: \[ \Pr(h_{i}) = \frac{Fitness(h_{i})}{\sum_{j=1}^{p} Fitness(h_{j})} \] ... can lead to crowding (aka inbreeding).
Tournament selection Pick $h_1, h_2$ at random with uniform probability and then, with probability $p$, select the more fit.
Rank selection Sort all hypotheses by fitness then the probability of selection is proportional to rank.

The GABIL [3] system was developed in 1993 by DeJong, Spears, and Gordon.
Learn disjunctive set of propositional rules, competitive with C4.5.
Fitness: \[ Fitness(h) = (correct(h))^2 \]
Representation: the hypothesis consisting of the rules

IF $a_1 = T \wedge a_2 = F$ THEN $c = T$; IF $a_2 = T$ THEN $c=F$
is represented by the string

$a_1$ $a_2$ $c$ $a_1$ $a_2$ $c$

10 01 1 11 10 0
Notice that this means we will have variable-length bitstrings.

$a_1$	$a_2$	$c$	$a_1$	$a_2$	$c$
10	01	1	11	10	0

Given

$a_1$ $a_2$ $c$ $a_1$ $a_2$ $c$

10 01 1 11 10 0

and

$a_1$ $a_2$ $c$ $a_1$ $a_2$ $c$

01 11 0 10 01 0

and the crossover points for the first parent are the points following bit positions 1 and 8

$a_1$ $a_2$ $c$ $a_1$ $a_2$ $c$

1[0 01 1 11 1]0 0

then the allowed pairs of crossover points are \[\langle 1,3 \rangle, \langle 1,8 \rangle, \langle 6,8 \rangle \]
In most GA implementations we have to come up with similar tricks to ensure that offsprings are viable.

$a_1$	$a_2$	$c$	$a_1$	$a_2$	$c$
10	01	1	11	10	0

$a_1$	$a_2$	$c$	$a_1$	$a_2$	$c$
01	11	0	10	01	0

$a_1$	$a_2$	$c$	$a_1$	$a_2$	$c$
1[0	01	1	11	1]0	0

They also tried adding new genetic operators (who doesn't?)
The AddAlternative generalizes a constraint on a specific attribute by changing a 0 to a 1. It was applied with probability .01.
The DropCondition replaces all bits for an attribute with 1. It was applied with probability .6.

In another experiment they added a new field to the bitstring. The two new bits determine which of the previous two operators can be applied.

$a_1$	$a_2$	$c$	$a_1$	$a_2$	$c$	AA	DC
10	01	1	11	10	0	1	0

means that AddAlternative can be applied but not DropCondition.

Its performance was comparable with rule/tree learning methods: C4.5, and ID5R.
The average performance on a set of 12 synthetic problems was:
92.1% accuracy, without AA and DC operators.
95.2 accuracy, with AA and DC operators.
Rule/tree learning methods ranged from 91.2 to 96.6.

In Backpropagation we moved smoothly from one hypothesis to a nearby one. In GA search we can take longer jumps and maintain a population of hypotheses.
Q: How do we characterize the evolution of a population?
A Schema is a string containing 0, 1, or *. The * means “don't care.” e.g.

Schema: 10**0*

Instances: 101101, 100100, ...
We can then characterize the population by the number of instances representing each possible schema.
$m(s,t)$ = number of instances of schema $s$ in population at time $t$.

$\bar{f}(t) =$ average fitness of population at time $t$.
$m(s,t) =$ instances of schema $s$ in population at time $t$.
$\hat{u}(s,t) =$ average fitness of instances of $s$ at time $t$.
Probability of selecting $h$ in one selection step is \[ \array{ Pr(h) & = & \frac{f(h)}{\sum_{i=1}^{n} f(h_i)} \\ & = & \frac{f(h)}{n \bar{f}(t)} } \]
Probabilty of selecting an instance of $s$ in one step \[ \array{ \Pr(h \in s) & = & \sum_{h\in s \cap p_{t}} \frac{f(h)}{n \bar{f}(t)} \\ & = & \frac{\hat{u}(s,t)}{n \bar{f}(t)}m(s,t) } \]
Expected number of instances of $s$ after $n$ selections \[ \array{ E[m(s,t+1)] & = & \frac{\hat{u}(s,t)}{\bar{f}(t)}m(s,t) } \]

Holland's Schema Theorem states that \[E[m(s,t+1)] \geq \frac{\hat{u}(s,t)}{\bar{f}(t)}m(s,t) \left(1 - p_{c}\frac{d(s)}{l-1}\right) (1 - p_{m})^{o(s)} \] where
- $m(s,t) =$ instances of schema $s$ in population at time $t$.
- $\bar{f}(t) =$ average fitness of population at time $t$.
- $\hat{u}(s,t) =$ average fitness of instances of $s$ at time $t$.
- $p_c =$ probability of single point crossover operator.
- $p_m = $ probability of mutation operator.
- $l = $ length of single bit strings.
- $o(s)$ number of defined (non *) bits in $s$.
- $d(s) = $ distance between leftmost, rightmost defined bits in $s$.
More fit schemas will tend to grow in influence, especially those containing a small number of defined bits and when these bits are close together.
It is incomplete, e.g., it fails to consider the possitive effects of crossover and mutation.

Represent the hypothesis using a program, instead of a string.
Popularize by John Koza's [4] books on the subject.
The program is represented by its parse tree.
As such, the programs are always in Lisp.
The crossover operator is applied by choosing two nodes and exchanging their subtrees.

Find program that turns any block configuration into a single stack that spells “UNIVERSAL.”
CS = name of top block on stack, or F.
TB = name of topmost correct block on stack.
NN = name of next block that needs to be on stack.
MS x = if x is on table then move to stack, else return F.
MT x = if x is on stack then move the block on top of tack to table.
EQ x y, NOT x
DU x y = do x until y returns true.
What happened? After 10 generations, with 166 test problems, the program found

(EQ (DU (MT CS)(NOT CS)) (DU (MS NN) (NOT NN)))

which solved all 166 problems.

Individuals are programs that transform beginning circuit to final circuit, by adding/subtracting components and connections.
Use population of 640,000, run on 64 node parallel processor.
Discovers circuits competitive with best human designs.

Lamarckism [5] proposes that individual's experience has a direct effect of DNA.
It has been discredited.
The Baldwin effect states that the ability to learn reduces the need to hard wire traits in DNA. So, learning individuals enable a more diverse gene pool and diverse pools evolve faster.
So, individual learning indirectly increases the rate of evolution!
This technique has been used to solve GP problems.

Conduct randomized, parallel, hill-climbing search through $H$.
Approach learning as optimization problem (optimize fitness).
GAs are most successful when the hypothesis are complex and the object to be optimized is an indirect function of the hypothesis (e.g., the set of rules that controls a robot).
GP is a variant of GA and has been successful at robot control and recognizing objects in visual scenes.
The art, as usual, lies in choosing the representation.

Genetic Algorithms

1 Introduction

2 Genetic Algorithm

2.1 Representing Hypothesis

2.2 Genetic Operators

2.3 Fitness and Selection

3 GABIL

3.1 Crossover with Variable-Length Bitstrings

3.2 GABIL Extensions

3.3 GABIL Results

4 Hypothesis Space Search

4.1 Just Selection

4.2 Schema Theorem

5 Genetic Programming

5.1 GP Example

5.2 GP Example: Circuits

6 Biological Evolution

7 Summary

URLs