Transcript Tutorial 1
Tutorial 1
Temi avanzati di Intelligenza Artificiale - Lecture 3
Prof. Vincenzo Cutello
Department of Mathematics and Computer Science
University of Catania
Types of Evolutionary Algorithms
1) Genetic Algorithms (GAs)
Proposed and studied by John Holland and his
students
Numerical optimization and adaptive systems
design
Simulate Darwinian Evolution
Recombination (Crossover) important
Mainly binary representation
Schema Theorem classical GA theory
Tutorial 1 - Lecture 3
2
Types of Evolutionary Algorithms
2) Genetic Programming (GP)
Developed by Koza et al.
Evolved LISP programs
Tree Representation
Widest variety of application
Term also used by De Garis for evolution of
artificial neural networks
Tutorial 1 - Lecture 3
3
Types of Evolutionary Algorithms
3) Evolutionary Programming (EP)
Developed by Fogel for simulated intelligence
Finite State Machine (FSM) representation
close to Lamarckian inheritance
No recombination
Adaptive Mutation (and others)
Applied to Phenotypes
Tutorial 1 - Lecture 3
4
Types of Evolutionary Algorithms
4) Evolution Strategies
Introduced by Rechenberg and Schwefel for
numerical optimzation
Real-valued representation
Mutation Based
Adaptive Mutation
Tutorial 1 - Lecture 3
5
Search Operators and Bias
1) Mutation Bias
Example: Integer variables in binary representation
2 variables, each 3 bit integer - 6 bit genotype
Current value:<4,4> (<100100>)
Single-bit bitflip mutation
Where can we go in one mutation?
How many mutations are required to get to <3,3> ?
Tutorial 1 - Lecture 3
6
Search Operators and Bias
Crossover Bias
One-Point vs. Uniform Crossover
Example Representation: Strings of integer values
(0 - m) of length n
Two fitness functions:
1: Fitness =
n
2
i 0
( xi xni ) 2
n
2
i 0
( x2i x2i 1 ) 2
2: Fitness =
Minimzation problem
Suggestions ?
Tutorial 1 - Lecture 3
7
Search Operators and Bias
Crossover Bias
Example System
m=4
n=200
Population size: 400
Mutation: single-gene random raplacement, 1.0 perindividual mutation probability
Crossover: uniform or one-point crossover, 1.0 crossover
probability
Replacement: keep best
Termination: when fitness == 0
Tutorial 1 - Lecture 3
8
Selection Pressure
Different selection operators produce different
behaviour
Exploration vs. Exploitation
Example: Roulette Wheel and Tournament
selection
Tutorial 1 - Lecture 3
9
Selection Pressure
Example Case
Two-optima function
Genotype: real-valued vector, -10.0 to 10.0
Mutation: gaussian mutation, 1.0 probability, 0.7 deviation;
Crossover: none
Population size: 20, Replacement: keep best
Maximization problem
Tutorial 1 - Lecture 3
10
Excercise sheet
1. Write an evolutionary algorithm...
... to find the maximum of the function on slide 10:
f(x,y) = e(- 0.7 * (x+2.0) *(x+2.0)) * e(-0.9 * y * y)
+ 2.0 * e(- (x -5.0) * (x-6.0)) * e (-(y-2.0) * (y-2.0))
For values -10.0 < x,y < 10.0
Two versions...
Describe the differences
Version one: binary representation (e.g. 2 x 16 bit)
Version two: real-value representation (see next week's lectures)
Run a few runs, and write a short (1/2 page) description of the differences in
search behaviour between the two representations. E.g. how long does it need to
find the optimum? Does it always find the global optimum? How close to the
optimum does it get?
2. Think about...
If you have a genotype of length n, what is the difference between n-1 point
crossover and uniform crossover ? Describe the difference in a few lines.
Tutorial 1 - Lecture 3
11