Transcript Genetic Algorithm

EE479
Introduction to Artificial Intelligence
Genetic Algorithms
Kasin Prakobwaitayakit
Department of Electrical Engineering
Chiangmai University
The Role of Search
Many (AI) problems can be formulated in
terms of searching for a solution in a list
of possibilities
Chess,
Route finding,
Bandwidth allocation,
Optimize circuit’s topology and values,
Determining neural network weights.
The Role of Search
Usually, each candidate solution has
associated with it some measure of how
good it is
cost function,
error measure,
RMS error,
Other error
An Example
sugar
Consider the
problem of choosing
the correct amount
of sugar and flour to
produce the best
quality biscuit
This grid shows
the axes are
amount of flour
amount of sugar
giving
quality of biscuit
flour
1 2 3 4 5 6 7 8 9
1
2
3
1 2 3 4 5 4 3 2 1
2 3 4 5 6 5 4 3 2
3 4 5 6 7 6 5 4 3
4
5
6
7
4
5
4
3
8
9
2 3 4 5 6 5 4 3 2
1 2 3 4 5 4 3 2 1
5
6
5
4
6
7
6
5
7
8
7
6
8
9
8
7
7
8
7
6
6
7
6
5
5
6
5
4
4
5
4
3
Exhaustive Search
Evaluate each combination in turn using
some systematic method, e.g.
start
(1,1) 
(2,1) 
…
(9,1) 
(1,9)
(2,9)
(9,9)
sometimes called the ‘brute-force’ approach
This cannot be done for most real problems
there are too many combinations
too computationally expensive
Hill Climbing
The hill climbing algorithm
start at either a fixed or random position
evaluate the current position
at each step
evaluate in each of the surrounding directions
– up, down, left, right
move in direction of greatest improvement
stop if all moves are lower than current position
This is guaranteed to find the ‘peak’ (maximum)
but only if there is just one (global) maximum
Local Maxima
flour
1 2 3 4 5 6 7 8 9
Suppose the quality
grid changes to this
sugar
1
If the hill-climbing starts 2
at e.g. (5,1) and heads 3
right first
4
the global maximum at
5
(5,5) is found
However, if the hill6
climbing starts at e.g.
7
(5,1) and heads up first
8
a local maxima at (3,1) is
9
found
1 2 3 2 1 2 3 2 1
2 3 2 1 2 1 2 3 2
3 2 1 2 3 2 1 2 3
2
1
2
3
1
2
1
2
2
3
2
1
3
4
3
2
4
5
4
3
3
4
3
2
2
3
2
1
1
2
1
2
2
1
2
3
2 3 2 1 2 1 2 3 2
1 2 3 2 1 2 3 2 1
Monte Carlo
Suppose we just guess random positions
The ‘Monte Carlo’ algorithm
generate a random stating position
evaluate the starting position and store it as best
repeat
generate a new random position
evaluate the new position
if the new position is better than the best found so far
– store the new position as the best
until we decide to stop (e.g. not improved for 20
goes)
This may or may not find the global maximum
Evolutionary Methods
EA’s use nature as an inspiration
the principles of evolution
birth and death of individuals in a population
survival of the fittest
multiple generations
mating or ‘crossover’ (two parents creating one offspring)
mutation (random variation)
There are many variations of the EA model
genetic algorithms
evolution strategies
evolutionary / genetic programming
Genetic Algorithms
Genetic algorithms (GA’s) were originated by
John Holland, University of Michegan, 1970’s
GA’s use the following principles
a population contains multiple individuals
each individual comprises a fixed-length string
a string of genes is a chromosome
crossover and mutation generate new individuals
operate on the chromosomes
fitness used to choose survivors at each generation
Evolution Strategies
Evolution strategies (ES’s) were originated by
Rechenberg, Schwefel and Bienert at the
Technical University of Berlin in the mid 1960’s
ES’s use the following principles
direct floating point representation of parameters
apply mutation by changing these parameters
according to normal probability distributions
small changes most likely
large changes unlikely (but still possible)
originally just one parent and one offspring
since extended to multiple individuals and maybe
crossover