Transcript Evolutionary Computing Dialects, Gusz Eiben

Evolutionary Computing
Dialects
Presented by A.E. Eiben
Free University Amsterdam
with thanks to the EvoNet Training Committee and its
“Flying Circus”
Contents


General formal famework
Dialects:





genetic algorithms
evolution strategies
evolutionary programming
genetic programming
Beyond dialects
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
2
General EA Framework
t := 0
initialize
P(0) = {a1(0), … , an(0)}
evaluate
F(a1(0)), … , F(an(0))
while (stop(P(t))  true)
recombine: P’(t) = rpar(r)(P(t))
mutate:
P’’(t) = mpar(m)(P’(t))
evaluate
F(a1’’(t)), … , F(an’’(t))
select:
P(t + 1) = spar(s)(P’’(t)  Q)
t := t + 1
where
• F is the fitness function
• r, m, s are recombination, mutation, selection operators
• par(x) contains the paramteres of operator x
• Q is either  or P(t)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
3
From framework to dialects

In theory:



every EA is an instantiation of this framework,
thus:
specifying a dialect needs only filling in the
characteristic features
In practice


this would be too formalistic
there are many exceptions (EAs not fitting into this
framework)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
4
Genetic algorithm(s)



Developed: USA in the 1970’s
Early names: J. Holland, K. DeJong, D. Goldberg
Typically applied to:


Attributed features:



discrete optimization
not too fast
good solver for combinatorial problems
Special:


many variants, e.g., reproduction models, operators
formerly: the GA, nowdays: a GA, GAs
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
5
GA: representation
Required accuracy determines the # of bits to represent a trait (variable)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
6
GA: crossover (1)
Crossover is used with probability pc

1-point crossover:




n-point crossover:




Choose a random point on the two parents (same for both)
Split parents at this crossover point
Create children by exchanging tails
Choose n random crossover points
Split along those points
Glue parts, alternating between parents
uniform crossover:



Assign 'heads' to one parent, 'tails' to the other
Flip a coin for each gene of the first child
Make an inverse copy of the gene for the second child
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
7
GA: crossover (2)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
8
GA: mutation
Mutation:

Alter each gene independently with a probability pm

Relatively large chance for not being mutated
(exercise: L=100, pm =1/L)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
9
GA: crossover OR mutation?
If we define distance in the search space as Hamming distance then:


Crossover is explorative, it makes a big jump to an area somewhere
‘in between’ two (parent) areas.
Mutation is exploitative, it creates random small variations, thereby
staying near the parent.

To hit the optimum you often need a lucky mutation.

GA community: crossover is mission critical.
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
10
GA: selection

Basic idea: fitness proportional selection.

Implementation: roulette wheel technique.



Assign to each individual a part of the roulette wheel (size proportional
to its fitness).
Spin the wheel n times to select n individuals.
Example:



f  max
3 individuals
f (A) = 6, f (B) = 5, f (C ) = 1
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
11
GA: reproduction cycle
Generational GA model
1. Select parents for the mating pool (size of mating pool equals population size).
2. Shuffle the mating pool.
3. For each consecutive pair apply crossover with probability pc.
4. For each ‘new-born’ apply mutation.
5. Replace the whole population by the mating pool.
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
12
GA: Goldberg ‘89 example (1)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
13
GA: Goldberg ‘89 example (2)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
14
Evolution strategies



Developed: Germany in the 1970’s
Early names: I. Rechenberg, H.-P. Schwefel
Typically applied to:


Attributed features:




numerical optimization
fast
good optimizer for real-valued optimization
relatively much theory
Special:

self-adaptation of (mutation) parameters standard
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
15
ES: representation



Problem: optimize f : n  
Phenotype space (solution space): n
Genotype space (individual space):


object values directly (no encoding)
strategy parameter values:



standard deviations (’s) and
rotation angles (‘s) of mutation
One individual:
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
16
ES: mutation (1)





One step size for each xi (coordinate direction)
Individual: (x1, …, xn, )
xi is mutated by adding some xi from a normal
probability distribution
 is mutated by a “log-normal” scheme: multiplying
by e, with  from a normal distribution
 is mutated first ! (why?)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
17
ES: mutation (2)



Each xi (coordinate direction) has its own step
size
Individual: (x1, …, xn, 1, …,  n)
0, , ’ are parameters
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
18
ES: mutation (3)
Case 1: n = 2, n = 1
Case 2: n = 2, n = 2
Equal probability to place an offspring
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
19
ES: recombination (1)
Basic ideas:

I  I,  parents yield 1 offspring

Applied  times, typically  >> 

Applied to object variables as well as strategy parameters

Per offspring gene two corresponding parent genes are involved

Two ways to recombine two parent alleles:


Discrete recombination: choose one of them randomly

Intermediate recombination: average the values
Might involve two or more parents (global recombination)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
20
ES: recombination (2)
The “standard” operator:
1 For each object variable:
a Choose two parents
b Apply discrete recombination on the corresponding variables
2 For each strategy parameter:
a Choose two parents
b Apply intermediate recombination on the corresponding
parameters
Global recombination: re-choosing the two parents for each variable
anew (step a above).
Local recombination: same two parents for each variable (position i).
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
21
ES: recombination (3)
Recombination
illustrated
=3
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
22
ES: selection

Strictly deterministic, rank based

The  best ranks are handled equally

The  best individuals survive from



the  offspring: (, ) selection

the parents and the offspring: ( + ) selection
(, ) selection often preferred for it is

important for self-adaptation

applicable also for noisy objective functions, moving optima
Selective pressure: very high
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
23
Evolutionary programming



Developed: USA in the 1960’s
Early names: D. Fogel
Typically applied to:



Attributed features:




traditional EP: machine learning tasks by finite state machines
contemporary EP: (numerical) optimization
very open framework: any representation and mutation op’s OK
crossbred with ES (contemporary EP)
consequently: hard to say what “standard” EP is
Special:


no recombination
self-adaptation of parameters standard (contemporary EP)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
24
Traditional EP: Finite State Machines
Initial state: C
Input string: 011101
Output string: 110111
Good predictions: 60%
Fitnesss = prediction capability: outputi = inputi+1
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
25
EP: mutation & crossover
Mutation:
representation naturally determines the operators


For FSMs: change a state-transition, add a state, etc.
For numerical optimization: see later
Crossover: none !
“no crossover between species”
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
26
Modern EP:
representation & mutation
Representation:  x1,…,xn, 1,…, n 
Mutation:
 x is mutated by adding some x from a normal
i
i
probability distribution
  is mutated by a “normal” scheme (ES: log-normal)
’i = i  (1 +   Ni(0, 1))
x’i = xi + ’I  Ni(0, 1)
  is mutated first !
 other prob. distributions, e.g., Cauchy, are also applied
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
27
EP: selection



Stochastic variant of ( + )-selection
P(t):  parents, P’(t):  offspring
Selection by conducting pairwise competitions in roundrobin format:




Each solution x  P(t)  P’(t) is evaluated against q other
randomly chosen solutions from the population
For each comparison, a "win" is assigned if x is better than its
opponent
The  solutions with the greatest number of wins are retained
to be parents of the next generation
Typically: q = 10
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
28
Genetic programming



Developed: USA in the 1990’s
Early names: J. Koza
Typically applied to:


Attributed features:




machine learning tasks
competes with neural nets and alike
slow
needs huge populations (thousands)
Special:


non-linear chromosomes: trees, graphs
mutation possible but not necessary (disputed!)
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
29
GP: representation



Problem domain: modelling (forecasting, regression,
classification, data mining, robot control).
Fitness: the performance on a given (training) data set,
e.g. the nr. of hits/matches/good predictions
Representation: implied by problem domain, i.e.
individual = model = parse tree


parse trees sometimes viewed as LISP expressions 
GP = evolving computer programs
parse trees sometimes viewed as just-another-genotype 
GP = a GA sub-dialect
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
30
GP: mutation
Replace randomly chosen subtree by a randomly
generated (sub)tree
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
31
GP: crossover
Exchange randomly selected subtrees in the parents
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
32
GP: selection

Standard GA selection is usual

Sometimes overselection to increase efficiency:

rank population by fitness and divide it into two groups:



when executing selection




group 1: best c % of population
group 2: other 100-c %
80% of selection operations chooses from group 1
20% from group 2
for pop. size = 1000, 2000, 4000, 8000 the portion c is
c = 32%, 16%, 8%, 4%
%’s come from rule of thumb
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
33
Beyond dialects





Field merging from the early 1990’s
No hard barriers between dialects, many
hybrids, outliers
Choice for dialect should be motivated by given
problem
Best practical approach: choose representation,
operators, pop. model pragmatically (and end
up with an “unclassifiable” EA)
There are general issues for EC as a whole
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
34
General issues
• WHAT
is an evolutionary algorithm ?
(HC, SA, TS)
• WHEN does it work ?
(problem X, setup Y, performance Z)
• WHY
does it work ?
(Markov chains, schema theory, BBH)
• WHO
invented evolutionary algorithms first ?
(Turing, Fogel, Holland, Schwefel, …)
• WHERE are we going next for a nice conference ?
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
35
The end
EC Dialects by A.E. Eiben, Free University Amsterdam, for the EvoNet Summer School 2001
36