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  xni ) 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