Transcript Dvouúrovňová evoluční optimalizace regulátorů

Dvouúrovňová evoluční optimalizace
regulátorů
|Bio-inspirované metody a jejich využití
Two level Evolutionary Optimization of
|Controllers
Basic Principles of Transplant evolution
Pave l Ošmera
Institute of Automation and Computer Science
Brno University of Technology, Technická 2,
616 69 Brno, Czech Republic
osmera @fme.vutbr.cz,
Introduction
We are trying to piece together the knowledge of
evolution with the help of biology, informatics and
physics to create a complex evolutionary structure. It can
speed up the creation of optimization algorithms with
high quality features. The emergent properties of
complex adaptive systems are presented.
One of the most highly developed skills in contemporary
Western civilization is the capability to split up problems
into their smallest possible components.
But we often forget to put the pieces together again. In
this way we can ignore the complex interaction between
our problems and the rest of the universe.
Kauffman’s enzyme nets
ecosystems Dawkins theory of memes
memory III (memes of mankind )
culture
social environment
books & school & television &
newspaper & Internet & religions & ..
laws & morale & society & friends &
enemy & terrorism & ..
&
family
mother & father & wife/husband &
sexual partner & children & ....
Lamarckian imitation of memes
memes memů
body
carrier of genes
imunitní
hormones
systém
Baldwin effect
individual (descendant)
brain memory II
carrier of memes
behavior
learning
(instincts)
(rules)
instinctive
behavior
immune system
chemical messenger
conscious behavior
central nervous system
mitochondrial genes (epigenetic information), order of cells (epigenetic structure )
DNA
memory Ia
genes for structure of the body
memory Ib
genes for structure of the brain and instincts
diploidy chromosomes & sexual reproduction
integrated fitness
Mendelian genetics
memory IVa
Darwinian selection process
parasites
memory IVb
prey-predator interaction (living part of nature)
influence of memes
Fig. 1 Complex evolutionary structure
environment (energy of sun and earth....)
influence of genes
direction of influence
Computational Intelligence
Game Theory and Collective Behavior Intelligence
memory III (genome & memes)
social environment
culture
Particle Swarm Optimization, Multi-Agent EA
Agent-based Multiobjective Optimalization
Ant Colony Optimization, Dynamical Systems
Modeling Niches, Team Optimization
Culture Algorithms
family
Evolutionary Computation:
Evolution Strategies
Genetic Programming
Genetic Algorithms, Parallel GAs
body
individual (descendant)
brain memory II
Hormone Systems
Clonal Selection
Enzyme Behavior
Artificial Immune Algorithms
Fuzzy Systems
Fuzzy-rough Sets
Hybrid Learning
Neural Networks
Fuzzy-neural Modeling
Intelligent Control
Mitochondrial Systems
memory Ia
genes for structure of the body
memory Ib
genes for structure of the brain and instincts
Diploid GA with Sexual Reproduction
DNA Computing , Messy GA
memory IVa
Cooperative co-evolutionary Algorithms
Parasitic Optimization, Bacterial EA
Artificial Life Systems, Differential EA
Parallel Hierarchical EA, Meta-Heuristics
Evolutionary Multi-objective Optimization
Fig. 2 Soft Computing
memory IVb
Evolutionary Design , Robotics
Evolvable Hardware, Embryonic Hardware
Human-Computer Interaction
Molecular-Quantum Computing
Data Mining, Chaotic Systems, Scheduling
order
new state of
evolution
(ordered structure)
negative mutation
negative selection
negative cross-over
neutral mutation
edge of chaos
phase transition
(complex structure)
positive mutation
positive selection
positive crossover
old state of
evolution
sexual selection
chaos
(chaotic structure)
Basic strategy of the evolutionary optimization
Example:
antenna designs
NASA Ames (http://ic.arc.nasa.gov/projects/esg/research/antenna.htm)
Classical method
Evolutionary approach
all solutions
Classical and evolutionary design
Grammatical evolution
The PGE is based on the grammatical evolution GE [1], where BNF grammars consist of terminals
and non-terminals. Terminals are items, which can appear in the language. Non-terminals can be
expanded into one or more terminals and non-terminals. Grammar is represented by the tuple
{N,T,P,S}, where N is the set of non-terminals, T the set of terminals, P a set of production rules
which map the elements of N to T, and S is a start symbol which is a member of N. For example,
below is the BNF used for our problem:
N = {expr, fnc}
T = {sin, cos, +, -, /, *, X, 1, 2, 3, 4, 5, 6, 7, 8, 9}
S = <expr>
and P can be represented as 4 production rules:
1. <expr> := <fnc><expr>
<fnc><expr><expr>
<fnc><num><expr>
<var>
2. <fnc> :=
sin
cos
+
*
U3. <var> := X
4. <num> := 0,1,2,3,4,5,6,7,8,9
Forward processing
(classical approach)
phenotype tree:
DNA sequence (genotype):
I
N
I
N
NON
NON
0 I N
0 ZD
0 N(NON)
1 ZZZ
1 NR
0 D0
2 NZ
1 D1
0 Rx
2 D2
1 RZ
3 D3
2 RZ.Z
4 D4
3 RN^N
5 D5
0 O+
6 D6
1 O-
7 D7
2 O*
8 D8
3 O/
9 D9
•
•
•
•
The symbol "I" is always root.
The rules are processed from the
left to the right.
The rules are applied on the
leftmost non-terminal symbol.
The rule chosen is determined by
the result of the modulo operation:
ZON
ZON
ZZON
ZZON
DZON
DZON
7ZON
7ZON
7DON
7DON
74ON
74ON
17
13
4
12
6mod
5
8
2
4
mod10
2
3
4
1=0
2
1
47
translation table
74+N
74+N
74+R
74+R
74+x
74+x
Crossover
When using grammatical evolution the resulting phenotype coded by one gene depends on the value of
the gene and on its context. If a chromosome is crossed at random point, it is very probable that the
context of the genes in second part will change. This way crossover causes destruction of the
phenotype, because the newly added parts code different phenotype than in the original individual.
This behavior can be eliminated using a block marking system. Crossover is then performed as an
exchange of blocks. The crossover is made always in an even number of genes, where the odd gene
must be BB gene and even must be EB gene. Starting BB gene is presently chosen randomly; the first
gene is excluded because it encapsulates (together with the last used gene) the whole individual.
The operation takes two parent chromosomes and the result is always two child chromosomes. It is also
possible to combine the same individuals, while the resulting child chromosomes can be entirely
different.
Given the parents:
1) cos( x + 2 ) + sin( x * 3 )
2) cos( x + 2 ) + sin( x * 3 )
The operation can produce children:
3) cos( sin( x * 3 ) + 2 ) + sin( x * 3 )
4) cos( x + 2 ) + x
This crossover method works similar to direct combining of phenotype trees, however this method
works purely on the chromosome. Therefore phenotype and genotype are still separated. The result
is a chromosome, which will generate an individual with a structure combined from its parents. This
way we receive the encoding of an individual without backward analysis of his phenotype. To
perform a crossover the phenotype has to be evaluated (to mark the genes), but it is neither used nor
know in the crossover operation (also it doesn’t have to exist).
The PGE algorithm was tested with the group of 6 computers in the computer
network. Five computers calculated in the structure of five subsystems MR1,
MR2, MR3, MR4, and MR5 and one master MR. The male subpopulation M of
MR in the higher level follows the convergence of the subsystem. Every figure
presents 10 runs of the PGE- program. The shortest time of computation is
only 10 generation. All calculation were finished before 40 generation. This is
better to compare with backward processing on one computer. The forward
processing on one computer was the slowest.
1
Fitness
1
0,8
Fitness
0,8
0,6
0,6
0,4
0,4
0,2
0,2
Generation
0
1
25
50
75
100
Generation
0
1
25
50
75
100
Fitness
1
0,8
0,6
0,4
0,2
Generation
0
0
50
100
Results:(a) forward and (b) backward processing, (c) the PGE with 5 PC using backward processing (average in bold
)
Logical function XOR
Input values are two integer numbers a and b; a, b 2< 0, 1 >. Output number c is the value of
logical function XOR. Training data is a set of triples (a, b, c):
P = {(0, 0, 0); (0, 1, 1); (1, 0, 1); (1, 1, 0)}.
Thus the training set represents the truth table of the XOR function. The function can be expressed
using _, ^, ¬ functions:
a + b = (a ^ ¬b) _ (¬a ^ b) = (a _ b) ^ (¬a _ ¬b) = (a _ b) ^ ¬(a ^ b)
The grammar was simplified so that it does not contain conditional statement and numeric
constants, on the other hand three new terminals were added to generate functions _, ^, ¬. Thus
the grammar generates representations of the XOR functions using other logical functions.
1a)
function xxor($a,$b) {
$result = "no_value";
$result = ($result) |
((((~(~(~(~(~($result)))))) | (($a) & (($a) & (~($b))))) & ($a))
| ((~($a)) & ($b)));
return $result;
}
Number of generations: 32
1b)
function xxor($a,$b) {
$result = "no_value";
$result = ($result) | (((~$result | ($a & ($a & ~$b))) & $a) | (~$a & $b));
return $result;
}
Logical function XOR
2a)
function xxor($a,$b) {
$result = "no_value";
$result = ($result) | ((((~(~(~(~(~($b)))))) & (($a) & (($a) &
(~($b))))) & ($a)) | ((~($a)) & ($b)));
return $result;
}
Number of generations: 53
2b)
function xxor($a,$b) {
$result = "no_value";
$result = ($result) | (((~$b & ($a & ($a & ~$b))) & $a) |
(~$a & $b));
return $result;
This paper describes the application of Two-Level Transplant
Evolution (TE) that can evolve control programs using a variable
length linear genome to govern the mapping of a Backus Naur
Form grammar definition. TE combines Grammatical Evolution
(on the genotype level) with Genetic Programming (tree structures
on the phenotype level). To increase the efficiency of Transplant
Evolution (TE) the parallel Diferential Evolution was added. The
adaptive significance of Parallel Transplant Evolution (PTE) with
male and female populations has been studied.
Initialise of population
The best solution is
result
Yes
For all individual in
population
No
Is stopping
condition
satisfied?
Compute
fitness
Layer of Grammatical
evolution
No
Crossover
Mutation
Is count
of actual
population >=
condition
Yes
Selection
Compute
fitness
Join populations
For all individual in
new population
If an individual of
grammatical's evolution has
some abstract parameters,
differential evolution will be
run for solve them, otherwise
simulation of regulation will
be run directly.
Has the grammatical
individual some abstract
parameters?
Yes
Initialise of population
The best solution is
result for grammatical
evolution
Layer of Differential
evolution
For all individual in
population
Yes
No
Is stopping
condition
Satisfied?
Compute
fitness
Initialise of regulator
Flow chart
For entered
regulation interval
No
Selection
Layer of Regulator
Value of criteria
stability is result of
fitness
Compute
regulator error
and system
response
Crossover
Calculate
regulation
criteria of
statility
.. Fitness criterions of control process
. Step response for integration system with time delay
• Each of these systems is a network of many ”agents”
acting in parallel .
• There is Complex adaptive systems share certain
crucial properties (a nonlinearity, a complex mixture of
positive and negative feedback, nonlinear dynamics,
emergence,
collective
behavior,
spontaneous
organization, and so on).
• There is not the master agent.
• A complex adaptive system has many levels of
organization (the hierarchical structure).
COMPLEX ADAPTIVE SYSTEMS
• the traditional science in the Age of the Machine
tended to emphasize stability, order, uniformity,
and equilibrium.
• today’s science: disorder, instability, diversity,
disequilibrium, nonlinear relationships (in which
small inputs can trigger massive consequences),
and temporality ( a sensitivity to the flow of time).
Conclusions
• The Parallel Transplant Evolution can be used for the automatic
generation of programs. We are far from supposing that all difficulties
are removed but first results with TPEs are very promising.
MENDEL 2012
Call for Papers
18th International Conference
on Soft Computing
Evolutionary Computation, Genetic Programming, Bayesian
Method, Fuzzy Logic, Neural Networks, Rough Sets, Fractals
June 27 - 29, 2012
Brno, CZECH REPUBLIC
http://www.mendel-conference.org/