Transcript Programming and Problem Solving with Java: Chapter 14

Chapter 14
Genetic Algorithms
1
Chapter 14 Contents (1)







Representation
The Algorithm
Fitness
Crossover
Mutation
Termination Criteria
Optimizing a mathematical function
2
Chapter 14 Contents (2)









Schemata
The Effect of Reproduction on Schemata
The Effect of Crossover and Mutation
The Schema Theorem
The Building Block Hypothesis
Deception
Messy Genetic Algorithms
Evolving Pictures
Co-Evolution
3
Representation
Genetic techniques can be applied
with a range of representations.
 Usually, we have a population of
chromosomes (individuals).
 Each chromosome consists of a
number of genes.
 Other representations are equally
valid.

4
The Algorithm

The algorithm used is as follows:
1. Generate a random population of
chromosomes (the first generation).
2. If termination criteria are satisfied, stop.
Otherwise, continue with step 3.
3. Determine the fitness of each chromosome.
4. Apply crossover and mutation to selected
chromosomes from the current generation to
generate a new population of chromosomes
(the next generation).
5. Return to step 2.
5
Fitness



Fitness is an important concept in genetic
algorithms.
The fitness of a chromosome determines how
likely it is that it will reproduce.
Fitness is usually measured in terms of how
well the chromosome solves some goal
problem.
 E.g., if the genetic algorithm is to be used to sort
numbers, then the fitness of a chromosome will be
determined by how close to a correct sorting it
produces.

Fitness can also be subjective (aesthetic)
6
Crossover (1)

Crossover is applied as follows:
1. Select a random crossover point.
2. Break each chromosome into two parts,
splitting at the crossover point.
3. Recombine the broken chromosomes by
combining the front of one with the back
of the other, and vice versa, to produce
two new chromosomes.
7
Crossover (2)

Usually, crossover is applied with one
crossover point, but can be applied with
more, such as in the following case which
has two crossover points:

Uniform crossover involves using a
probability to select which genes to use from
chromosome 1, and which from
chromosome 2.
8
Mutation
A unary operator – applies to one
chromosome.
 Randomly selects some bits (genes)
to be “flipped”

1 => 0 and 0 =>1

Mutation is usually applied with a
low probability, such as 1 in 1000.
9
Termination Criteria


A genetic algorithm is run over a number
of generations until the termination criteria
are reached.
Typical termination criteria are:
 Stop after a fixed number of generations.
 Stop when a chromosome reaches a specified
fitness level.
 Stop when a chromosome succeeds in solving the
problem, within a specified tolerance.

Human judgement can also be used in
some more subjective cases.
10
Optimizing a mathematical function

A genetic algorithm can
be used to find the
highest value for f(x) =
sin (x).

Each chromosome consists of 4 bits, to
represent the values of x from 0 to 15.
Fitness ranges from 0 (f(x) = -1) to 100 (f(x) =
1).
By applying the genetic algorithm it takes just
a few generations to find that the value x =8
11
gives the optimal solution for f(x).


Optimizing a mathematical function 2
Randomly create 4 chromosomes
Chrom Gene val f(x) f’(x) fitness ratio

C1 = 1001 = 9 = .41 = 70 = 46.3%
C2 = 0011 = 3 = .14 = 57 = 37.7%
C3 = 1010 =10 = -.54 =22 = 14.9%
C4 = 0101 = 5 = -.96 =2 = 1.34%

F’(x) = 50(sin(x) + 1) fitness value
12
Optimizing a mathematical function 3

Generate random numbers to
determine chromosomes to mate
 0 to 46 c1, 46 to 83 c2, …
Random num 1 = 56, c2 is chosen
Random num 2 = 38, c1 is chosen
Combine c1 and c2, randomly select a
crossover, bt 2nd and 3rd genes
C5 = 1011, C6 = 0001
13
Optimizing a mathematical function 3
Similarly C1 and C3 produce C7 and C8
 C1 to C4 are replaced by C5 to C8
Chrom Gene val f(x) f’(x) fitness ratio
C5
1011 11 -1 0
0%
C6
0001 1 .84 92.07 48.1%
C7
1000 8 .99 99.47 51.9%
C8
1011 11 -1 0
0%

14
Comments
Typical populations 100 to 500 chrom
 Each chrom may have 100’s of genes
 Typically provide near optimal
solutions to combinatorial problems
 Are a local search method

15
Schemata (1)




As with the rules used in classifier systems, a schema
is a string consisting of 1’s, 0’s and *’s. E.g.:
1011*001*0
Matches the following four strings:
1011000100
1011000110
1011100100
1011100110
a schema with n *’s will match a total of 2n
chromosomes.
Each chromosome of r bits will match 2r different
schemata.
101 matches 101,10*,1*0,*01,**1,*0*,1**,***16
Schemata (2)



The defining length dL(S) of a schema, S, is the distance
between the first and last defined bits. For example, the
defining length of each of the following schemata is 4:
**10111*
1*0*1**
The order O(S) is number of defined bits in S. The
following schemata both have order 4:
**10*11*
1*0*1**1
A schema with a high order is more specific than one with
a lower order.
17
Schemata (3)



The fitness of a schema is defined as the average
fitness of the chromosomes that match the
schema.
The fitness of a schema, S, in generation i is
written as follows:
f(S, i)
The number of occurrences of S in the population
at time i is :
m(S, i)
18
The Effect of Reproduction on Schemata

The probability that a chromosome c will reproduce is
proportional to its fitness, so the expected number of
offspring of c is:

a(i) is the average fitness of the chromosomes in the
population at time i
If c matches schema S, we can rewrite as:


c1 to cn are the chromosomes in the population
at time i which match the schema S.
19
The Effect of Reproduction on Schemata

Since:

We can now write:

This tells us that a schema that is fit
will have more chance of appearing
in a subsequent generation than less
fit chromosomes.
20
The Effect of Crossover




For a schema S to survive crossover, the
crossover point must be outside the defining
length of S.
Hence, the probability that S will survive
crossover is:
This tells us that a short schema is more likely
to survive crossover than a longer schema.
In fact, crossover is not always applied, so the
probability that crossover will be applied
should also be taken into account.
21
The Effect of Mutation
The probability that mutation will be
applied to a bit in a chromosome is pm
 Hence, the probability that a schema S
will survive mutation is:


We can combine this with the effects of
crossover and reproduction to give:
22
The Schema Theorem



Holland’s Schema Theorem, represented by
the above formula, can be written as:
Short, low order schemata which are fitter
than the average fitness of the population will
appear with exponentially increasing regularity
in subsequent generations.
This helps to explain why genetic algorithms
work.
It does not provide a complete answer.
23
The Building Block Hypothesis




Genetic algorithms manipulate short, loworder, high fitness schemata in order to find
optimal solutions to problems.”
These short, low-order, high fitness schemata
are known as building blocks.
Hence genetic algorithms work well when
small groups of genes represent useful
features in the chromosomes.
This tells us that it is important to choose a
correct representation.
24
Deception
Genetic algorithms can be deceived
by fit building blocks that happen not
to combine to give the optimal
solutions.
 Deception can be avoided by
inversion: this involves reversing the
order of a randomly selected group of
bits within a chromosome.

25
Messy Genetic Algorithms (1)



An alternative to standard genetic algorithms
that avoid deception.
Each bit in the chromosome is represented as
a (position, value) pair. For example:
((1,0), (2,1), (4,0))
In this case, the third bit is undefined, which is
allowed with MGAs. A bit can also
overspecified:
((1,0), (2,1), (3,1), (3,0), (4,0))
26
Messy Genetic Algorithms (2)
Underspecified bits are filled with bits taken
from a template chromosome.
 The template chromosome is usually the
best performing chromosome from the
previous generation.
 Overspecified bits are usually dealt with by
working from left to right and using the first
value specified for each bit.

27
Messy Genetic Algorithms (3)


MGAs use splice and cut instead of crossover.
Splicing involves simply joining two chromosomes
together:
((1,0), (3,0), (4,1), (6,1))
((2,1), (3,1), (5,0), (7,0), (8,0))
((1,0), (3,0), (4,1), (6,1), (2,1), (3,1), (5,0), (7,0), (8,0))

Cutting involves splitting a
chromosome into two:
((1,0), (3,0), (4,1))
((6,1), (2,1), (3,1), (5,0), (7,0), (8,0))
28
Evolving Pictures
Dawkins used genetic algorithms
with subjectives metrics for fitness to
evolve pictures of insects, trees and
other “creatures”.
 The human selection of fitness can
be used to produce amazing pictures
that a person would otherwise not be
able to produce.

29
Co-Evolution




In the real world, the presence of predators is
responsible for many evolutionary developments.
Similarly, in many artificial life systems, introducing
“predators” produces better results.
This process is known as co-evolution.
For example, Ramps, which were evolved to sort
numbers: “parasites” were introduced which
produced sets of numbers that were harder to sort,
and the ramps produced better results.
30