Transcript evolutionary pathways?

Evolvability Analysis for Evolutionary Robotics
Sung-Bae Cho
Yonsei University, Korea
1
Agenda





Motivation
Analysis framework of evolution
– Adaptive evolution
– Adaptive behaviors
– Evolutionary pathways
Evolution of fuzzy logic controller
Simulation results
Summary
2
Motivation
Evolutionary Phenomena
Desirable Evolution
Chances
Innovative
functional
structures
Necessity
Random genetic drift
Adaptivity
3
Increased
complexity
Motivation
Evolutionary Routes




Can the same results be obtained?  Adaptive evolution ( 1 )
What properties are genetically preferred?  Adaptive behaviors ( 2 )
How the solutions are formed?  Evolutionary pathways to the solutions (
Behavioral properties?  Emergence ( 4 )
Emergence
4
Desirable
Evolutionary Causes
and Effects
Low probability
3
Good
Solution
1
High
Evolvability
NonAdaptive
Evolution
Adaptive
Evolution
2
Adaptive
Behavior
High probability
Bad
Solution
4
Low
Evolvability
3
)
Analysis Framework of Evolution
5
Analysis Framework
Role of Analysis Components
Application of the analysis framework to a real-world problem



Adaptive evolution
– Does the evolving system maintains a good level of
evolvability, especially in a real-world problem?
Adaptive behavior
– What properties make certain components more adaptive?
Evolutionary pathways
– How the solutions have evolved, i.e., evolutionary pathways?
6
Analysis Framework
Definitions of Evolvability




The capacity to produce good solutions via evolution
Genome’s ability to produce adaptive variants when acted on by
the genetic system (Wagner and Altenberg, 1996)
Capacity to generate heritable phenotypic variation (Kirshner and
Gerhart, 1998)
Capacity to create new adaptations, and especially new kinds of
adaptations, through the evolutionary process (Bedau and
Packard, 1992)
7
Analysis Framework
Evolvability Measures


Evolvability as the rate of complexity increase
– By Chrystopher L. Nehaniv
Ev(t )  maxcpx(t  1)  maxcpx(t )
– maxcpx gives the largest complexity of any entity at time t
– The complexity of an entity is the least number of
hierarchically organized computing levels needed to construct
an automata model of a target system
– Krohn-Rhodes algebraic automata theory and finite semigroup
theory
Evolutionary activity statistics
– By Mark A. Bedau
8
Analysis Framework
Evolutionary Activity Statistics (1)

Evolutionary activity
– A counter, ai (t ), of the ith component at time t
ai (t )    i (k )
k t
– Updated as the component persists
 Inherited with reproduction
 Initialized when the component changes, e.g. mutation
 Update function  i (k ) should be chosen carefully according
to the problems at hand
9
Analysis Framework
Evolutionary Activity Statistics (2)

Mean activity: Acum (t ) 
 a (t )
i
i
D (t )
– D(t) is the number of component I at time t with ai(t)>0
– Represents continual adaptive success of components

1 a1
C (t , a )
New activity: Anew (t ) 

D(t ) a  a0
– C (t , a ) is the number of components I with ai(t)>0
– Represents adaptive innovations flowing into the system
10
Analysis Framework
Evolutionary Activity Statistics (3)

Need to measure evolvability in two models
– Target model
– Shadow model
 To screen off non adaptive evolutionary forces
11
Analysis Framework
Schema Analysis




Definition (Holland, 1968)
– A similarity template that designates a set of chromosomes
having same alleles at certain loci
Consists of a set of characters and don’t-cares
Example
– Character set = {0,1}, don’t care=#
– #0000  {10000, 00000}
– #111#  {01110, 01111, 11110, 11111}
Adaptive schema = the size of the set that this schema describes
increases
12
Analysis Framework
Observational Emergence


Emergence
– “creation of new properties” – Morgan, C.L., Emergent
Evolution, Williams and Norgate, 1923
Observational emergence
– Proposed by N.A. Bass, 1992
 S : structure (system, organization, organism,
machine, …)
 P : property observed by observational mechanism, Obs
13
Evolution of Fuzzy Logic Controller
Fuzzy Logic Controller for Mobile Robot
14
Evolution of Fuzzy Logic Controller
FLC Parameters for Khepera Robot

Input variables : 8 proximity sensors of Khepera mobile robot
Output variables : 2 motors of Khepera mobile robot

Linguistic values of fuzzy sets

Membership function of fuzzy sets

15
Evolution of Fuzzy Logic Controller
Gene Encoding of FLC
Gene representation
for an individual
8 INPUT
• 8 proximity sensors
• 2 motors
VF
F
M
2 OUTPUT
d0
1
C
1
d1
2
1
d2
0
0
d3
3
0
d4
1
0
2
3
4
5
6
7
8
d5
0
0
d6
4
1
d7
3
1
1
VC
variable toggle flag
rule toggle flag
1
20 RULES
v0 v1
2
0
4
2
1
conditional part
2
consequent part
9 10 11 12 13 14 15 16 17 18 19
Decoding of a rule
Encoding of a membership function
of a variable
16
Simulation Results
Experimental Setup







Population size : 50
Maximum generation : 1000
Overlapped population by 50% with elitism
Crossover rate : 0.5
Mutation rate : 0.01
t

 n (t )dt if genotype i exists at t
Evolutionary activity ai (t )  0 i

0
otherwise

Measuring evolvability in two models
– Target model
– Neutral shadow : no selective pressure
 To screen off non adaptive evolutionary forces
17
Simulation Results
Adaptive Evolution
Evolutionary activity ai (t )    i (k )
k t
Mean activity
Acum (t ) 
3.5
 a (t )
New activity
i
i
x 10
1 a1
Anew (t ) 
 C (t , a)
D (t ) a0
D (t )
4
0.12
3
0.1
2
New Activity
Total Activity
2.5
Fuzzy Model
Neutral Shadow
1.5
1
0.08
0.06
0.04
0.02
0.5
0
0
Fuzzy Model
Neutral Shadow
200
400
600
Generation
800
1000
18
0
0
200
400
600
Generation
800
1000
Simulation Results
Adaptive Behavior
Salient Rules
6000
SR9
5000
SR7
Activation
4000
SR3
SR4
3000
SR1
2000
SR2
SR6
SR8
SR12
SR11
SR5
1000
SR10
0
With SR2
0
100
Without SR2
200
300
400
With SR8
500
Generation
600
19
Without
700
SR8
800
900
1000
With SR10
Without SR10
Simulation Results: Evolutionary Pathways
Schema Analysis
Salient Rules
6000
SR9
5000
SR7
Activation
4000
SR3
3000
SR1
2000
SR2
SR4
SR6
SR8
SR12
SR11
SR5
1000
SR10
0
0
100
200
300
400
500 600
Generation
700
800
900
1000
Best Individual
20
Simulation Results: Evolutionary Pathways
Rule B2 and B7
Activities of instances of
schemata S{1}, S{4}, and B{2}
S{1} S{4}B{2}
Activities of instances of
schemata S{6} and B{7}
21
S{6} B{7}
Simulation Results: Observational Emergence
Parameters of Emergence
22
Simulation Results: Observational Emergence
Turning Around
Int
Three Obs1s of firstorder structures
First-order structures
•
A Obs2 of a second-order
structure S2
The property observed by Obs2 of S2 constructed through the interactions
of three first-order structures S211 , S511 , S711 is quite different from the properties
observed by Obs1( Si1), i  {2,5,7}
1

By the definition of observational emergence

Turning around behavior (Obs2(S2)) is observationally emergent
23
Simulation Results: Observational Emergence
Smooth Cornering
Int
Two Obs1s of the first-order
structures
First-order structures
•
A Obs2 of a second-order
structure S2
The property observed by Obs2 of S2 constructed through the interactions
1
1
of the two first-order structures S21 , S71 is quite different from the properties
observed by Obs1( Si1), i  {2,5}
1

By the definition of observational emergence

Smooth cornering behavior (Obs2(S2)) is observationally emergent
24
Summary

Application of evolvability measure to a real-world problem

Illustration of evolutionary pathways to the best individual


The evolvability measure shows that the performance of the best
individual is the results of its rules’ adaptability
Schema analysis shows that most of the rules of the best
individual are the combination of the rules of earlier stage of
evolution
25