Transcript Genetic Algorithm

EE749
Introduction to Artificial Intelligence
Genetic Algorithms
The Simple GA
Principles of Genetic Algorithms
Genetic algorithms (GA’s) are iterative,
adaptive, general-purpose search strategies
They are driven by the following principles
evolution operates on chromosomes
chromosomes are strings of genes
chromosomes define the characteristics of an
individual
less fit individuals tend not to survive (natural
selection)
offspring inherit properties from their parents by the
process of reproduction
individuals that are more successful reproduce
more
Individuals
Each possible candidate solution is an
individual
A set of possible solutions is maintained
a population of individuals
Each individual consists of a string of symbols
from a fixed set of symbols (an alphabet)
in the simple GA, the symbols are ‘0’ and ‘1’
each variable is represented by a binary string
each variable is the equivalent of a biological gene
the total string of genes is a chromosome
Fitness Functions
Each chromosome is evaluated and assigned
a value known as its fitness value
the chromosome is split into its constituent genes
each gene is decoded to give the corresponding
variable’s value
the variables are used to evaluate the fitness
function
The fitness value is used to determine
the individual’s rate of reproduction
the higher the fitness, the more change of being selected
Each iteration is called a generation
GA Overview
At each generation, each individual is
evaluated by a fitness function and assigned a
fitness value
the fitness value somehow measures how good the
individuals is as a solution to the problem
New individuals are produced by selecting
individuals from the current population on the
basis of their fitness values
Some individuals within the population may be
altered by the application of genetic operators
This is repeated until a decision is made to
stop
GA Outline
Let P represent a population and P(t) represent
the state of population P at time t
Then
Initialise P(t = 0);
/* P(0) is the starting
population */
Evaluate P(t = 0);
/* evaluate each individual */
WHILE ( NOT termination condition )
DO
Generate P(t + 1) from P(t);
/* by a process of
reproduction */
t = t + 1;
Evaluate P(t);
END (* while*)
Selection Strategy
Determine how many new offspring to produce
there are many variations, but in the simple GA we
produce a new population of the same size as the
old
Determine which individuals are to be used
again, there are variations, but the simplest is
termed ‘roulette’ selection
each individual is assigned a probability based on
their fitness as a straight proportion of overall fitness
individuals are randomly picked, according to their
fitness proportion, to survive into the next
generation
‘Roulette’ Example
For example: f(x) = x2, x = [0, 31]
No.
1
2
3
4
String
01101
11000
01000
10011
x
13
24
8
19
x2
169
576
64
361
S 1170
ps
0.144
0.492
0.055
0.309
Range
0.000  0.143
0.144  0.635
0.636  0.690
0.691  0.999
The following random numbers are generated:
0.521, 0.968, 0.112, 0.753
so individuals 2, 4, 1, 4 survive to the next generation
Genetic Operators
Reproduction produces a new generation
selected according to fitness, but it does not
introduce any new variation into the population
genetic operators are applied to generate variation
The two operators used in the simple GA are
crossover
mutation
Each operator is applied to each newly
selected individual with a certain probability
it’s very hard to guess what these probabilities
should be
Crossover
Two individuals are chosen randomly
a crossover point is selected at random
the strings are swapped to the right of crossover
point
For example
OLD1 = 01010111
OLD2 = 11110101
and position five is chosen, giving
NEW1 = 01010101
NEW2 = 11110111
Mutation
One individual is chosen randomly
one or more mutation points are selected at random
the symbols in the string are changed (somehow)
in simple GA with binary ‘0’s and ‘1’s, the bit is
‘flipped’
For example
OLD = 10010101
is selected for mutation at points 2, 4 and 8
NEW = 11000100
Operator Probabilities
The probability of applying each operator is
application dependent and is usually
discovered empirically (i.e. by trying several
alternatives)
As a heuristic (‘rule of thumb’)
crossover
often applied so that 50 to 75% of the individuals in the
population undergo crossover
i.e. 0.50 to 0.75 probability of being applied
mutation
often applied to each bit with prob. 1 / (total number of bits)
e.g. 10 individuals of 10 bits = 100 bits; pmutate = 0.01 per bit