Post on 05-Apr-2015
transcript
Ingo Rechenberg
PowerPoint-Folien zur 2. Vorlesung „Evolutionsstrategie II“
Der ES-Fortschritt im Quadrikgebirge und
Kalkül der geschachtelten Evolutionsstrategien
Weiterverwendung nur unter Angabe der Quelle gestattet
Klettern bei starker Kausalität
Experimentator
Suchfeld
Klettern bei linearer starker Kausalität
Experimentator
Suchfeld
(1 + 1)-ES
DARWINs Theorie in maximaler Abstraktion
Lokales Klettern der Evolutionsstrategie
linear
n
21
Lokales Klettern der Evolutionsstrategie
nichtlinear
(1 , )-ES
ES mit mehr als einem Nachkommen
= 6
Die Grundidee (in einer Dimension)
Satz von Funktionen
)sin(xxe
)log(x)arctan(x
)cosh(x)(erf x
432
241
61
21
1e xxxxx
8642
403201
7201
241
21
1)cos( xxxxx
Alle Funktionen haben dieselbe Form
9753
91
71
51
31
)arctan( xxxxxx
33
32
2
2 )0(!3
1)0(!2
1)0(!1
1)0()0( x
dx
fdx
dx
fdx
dxdf
fxf
)sinh(ar x
TAYLOR Potenzreihenentwicklung in der MACLAURINschen Form:
!
nichtlinear für welches Gebirge ?
)0(!2
1)0(!1
1)0()0(1 1
2
1
ji
n
i
n
j jii
n
i ixx
xxfx
xfff
x
TAYLOR-Entwicklungin n Dimensionen (MACLAURIN Reihe)
1 11
0 ji
n
i
n
j
jii
n
i
i xxbxaQQ
Vektor
Hauptachsentransformation =Drehung des Koordinatensystems derart, dass die Kreuzterme wegfallen
2
110 k
n
ikk
n
kk ydycQQ
ji
n
i
n
jjii
n
ii xxbxaQQ
1 11
0
x2
x1
y2
y1
Minus-Zeichen und alle d k > 0, um lokal konvexe Höhenlinien zu erhalten !
Die Hauptachsentransformation ist erlaubt, weil die Mutationen rotationssymmetrisch erzeugt werden
Konvergenzmaß „Erfolgswahrscheinlichkeit“
n
kkk
n
kkk ydycQQQQQ
1
2
10ENΔ
eiltnormalvert),0(
n
kkc
1
2 mit
n
kkd
1
2
2
110 k
n
ikk
n
kk ydycQQ
Text Text
eiltnormalvert),0( ky
Konstante für n >> 1
Mutativen Änderungen des Nachkommen
n
kkdzQ
1
2Δ
n
kkk
n
kkk ydycQ
1
2
1
Δ
eiltnormalvert),0( z
n
kkc
1
2 mit
Konstante für n >> 1
n
kkdzQ
1
2Δ
n
kkd
1
2
222
1
e2
1)(
zzw
22
12
2 erf1)()(2
e
k
kk c
ddzzwdzwW
kd
Erfolgswahrscheinlichkeit
z*
Konvergenzmaß „Fortschrittsgeschwindigkeit“
N11
N2
2
Fortschritt als Höhenlinienprojektion der Nachkommen auf den Gradienten des Elters
Universelle Fortschrittsdefinition
E
gradE
E tan
Q
2
11k
n
kkk
n
kk ydycQ
0 tan 21
22
2
2
1
n
nyyy
yQ
yQ
yQ
2tan kc
N
Q
2
22
k
k
k c
d
c
z
kdzQ 2Δ Die mutativen Q-Änderungen
Ergeben die Fortschritte
2
2
k
k
c
dz
(0, ) - normalverteilte Zufallszahlen
Konstante
- normalverteilte Zufallszahlen
2,0 kc
tan
Q
2
2
k
k
c
dz
(0, ) - normalverteilte Zufallszahlen
KonstanteBei der Erzeugung von Nachkommen wird die größte Zufallzahl z selektiert
,1c
2
2,1,1
k
k
c
dc
Aus Vorlesung ES1
2
2,1,1
k
k
c
dc
= Komplexität
2,1,1 c
2,1 c 2
,1
c
22,1
2
,12,1
ccc
2
Zentrales Fortschrittsgesetz
-5 -3 -1 310
0,2
0,1
0,3
1 01 01 01 010
2
Evolution Window
nicht so
sondern so
Ließe sich das Vorhandensein eines zusammengesetzten Organs nachweisen, das nicht durch zahlreiche aufeinander folgende geringe Abänderungen entstehen könnte, so müsste meine Theorie zusammenbrechen. Aber ich kenne keinen solchen Fall.
Charles Darwin
rn
c
d
k
k
22
r
2,1 2
r
nc
2,1,1 c Komplexität für
das Kugelmodell
Demonstration der Notwendigkeit einer Schrittweitenregelung
2erf1
21 ,1
ec
W
221
2erf1e
k
k
cdW
Erfolgswahrscheinlichkeit
Nachkommender Anzahl Gesamte
Elterder alsbesser Nachkommender Zahl e W
2erf1
21 ,1
ec
W
Schrittweitenadaption über die Erfolgswahrscheinlichkeit
0.227
2 0.25
0.20
0.15
0.10
0.05
0.1 0.2 0.3 0.4 0.5
= 10
We
50 20 60.25
0.20
0.15
0.10
0.05
0.1 0.2 0.3 0.4 0.5
= 10
We
1 / 5
Entwicklung der 1/5-Erfolgsregel
We > 1/5We < 1/5Mutationen
Biologisch unmöglichKosmische Strahlung
? ? ?
ich bin Spitze
Einschätzung des Kletterstils
im Solo- und im Gruppenklettern
Mutation
Duplikator
DNA
Hat Kopie hergestelltrer
Mutation der Mutabilität undVererbbarkeit der Mutabilität
„Knackpunkt“ der Evolutionsstrategie
Algorithmus der (1, ) – Evolutionstrategie mit MSR
11NE1Ng zxx gg
22NE2N zxx ggg
zxx gg gNEN
eiltnormalvert)1,0(,, /21 nzzz n
ggNBE
1 xx )(),(),()( N2NNNB 1minmax/ gggg QQQQ xxxx
ggNBE
1
1E1N gg
2E2N gg
ggEN
eiltnormalvert schlogarithmi5,1/1
5,1 :6für oder
654
321
Entwicklung der Evolutionsstrategie
ES-]),/(,/[
' = Zahl der Eltern-Populationen
' = Zahl der Nachkommen-Populationen
= Zahl der Eltern-Individuen= Zahl der Nachkommen-Individuen = Generationen der Isolation
'= Zahl der Populations-Generationen
' = Mischungszahl Populationen
= Mischungszahl Individuen
Darwin Mendel
Wright Haldane Fisher
Populationsgegentiker
wVariablensatz
Population
Zufallswahl
Duplikation
Mutation
Spielzeichen für Evolutionsstrategien (1)
Rekombination
Q
Bewertung
Realisation
Isolation
Spielzeichen für Evolutionsstrategien (2)
QSelektion
Q
Q
Kartenspiel: ( 1 + 1 ) - ES
Q Q QQ Q
Q
Kartenspiel: ( 1 + 5 ) ] - ES
Q Q QQ Q
Q
Kartenspiel: ( 1 , 5 ) - ES
Q Q Q Q Q Q Q
Q
w
Kartenspiel: ( 3 , 7 ) - ES
Q
w
w w w w w w
Q Q Q Q Q Q
Kartenspiel: ( 3 / 2 , 6 ) - ES
Q Q
Q
1 7
Q Q
Q
1 7
Q Q
Q
1 7
Q
1w
2 3w w w
Q
Kartenspiel: [ 2 , 3 ( 4 , 7 ) ] - ES
Q Q
Q
1 7
Q
30
Q Q
Q
1 7
30
w w
Q
Kartenspiel: [ 1 , 2 ( 4 , 7 )30 ] - ES
w1
w
6
w
w
w
w
Q Q
Q
w
w
w
Q Q
Q
Q
Q
Kartenspiel: [ 4 / 3 , 6 ( 5 / 2 , 7 ) ] - ES
(1 + 1)-ES
DARWINs Theorie inmaximaler Abstraktion
(1 , )-ES
ES mit mehr als einem Nachkommen
= 6
( , )-ES
ES mit mehrerenEltern und Nachkommen
= 7
= 2
( , )-ES
ES mit Mischung der
Variablen (Erbanlagen)
= 8
= 2 = 2
ES]),(,[
12154
Neue Gründerpopulationen
Die geschachtelte Evolutionsstrategie
Auf dem Weg zu einemAuf dem Weg zu einem
evolutionsstrategischen Kalkülevolutionsstrategischen Kalkül
1 +1( )2 - gliedrige Wettkampfsituation - ES ,+,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
( ) - ES +,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
/
Beispiel = 2
( ) - ES +,/ 2
Elter liefert nur die Hälfte der Erbinformation
Multirekombination: =
( ) - ES +,/ dominant
Zu kompliziert in der Natur aber auf dem Computer möglich
( ) - ES +,/ intermediär
( ) - ES +, intermediär (Abkürzung)
( ) - ES +,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
Beispiel:
(1+ 6)4 = (1+ 6) (1+ 6) (1+ 6) (1+ 6)(1+ 6)4 = (1+ 6) (1+ 6) (1+ 6) (1+ 6) - ES
Die Zahl der Eltern wird fett geschrieben !
Zur Kennzeichnung der Eltern in fetter Schrift
(1+ 9) = (1+3+3+3)
(1+3+3+3) = (10) Unsinn !
Trennung von Eltern und Nachkommen !(1+3+3+3) = (1+9)1 1
(1+3+3+3) = (1+3+3+3)1 1
= 4 = 6 = 9
( ) - ES +,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
Erweiterung: Populationswelle
(1+ 6) (2+ 6) (3+ 6) (2+ 6) (1+ 6) - ES
( ) - ES +,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
ES mit Drift-Phase
(1, 7)(1, 7)(1, 7)(1, 7)(7, 7)(7, 7)(7, 7)
= (1,7)4 (7,7)3 - ES
starke Selektion schwache Selektion
( ) - ES +,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
ES mit Gründer-Phase
(1, 4)(4, 16)(16, 64)(64, 256)(256, 1024) - ES
( ) - ES +,
Auf dem Weg zu einer evolutionsstrategischen Algebra
Beispiel:
= (1, 6)8 + (1, 6)8
+ (1, 6)8 + (1, 6)84 (1, 6)8
2 ,
Beste Population
Zweitbeste Population
Selektion der besten Populationen
,
( ) - ES +,
Auf dem Weg zu einem evolutionsstrategischen Kalkül
+,[ ]
' = Zahl der Eltern-Populationen' = Zahl der Nachkommen-Populationen
= Zahl der Eltern-Individuen = Zahl der Nachkommen-Individuen = Generationen der Isolation
'= Zahl der Populations-Generationen
21,1
1,1
Zwei unterschiedliche Strategien
Beispiel für eine algebraische Operation in einer geschachtelten ES
Biologische Entsprechung der Strategie-Schachtelung
| Familie Gattung { Art [ Varietät ( Individuum ) ] } |
Ende
www.bionik.tu-berlin.de
eiltnormalvert*),0(1
n
kkkzc
n
kkc
1
2* mit
Additionstheorem für (0, )-normalverteilte Zufallszahlen zk
Chiquadrat-Gesetz für n >> 1
Für große n gilt, dass n quadrierte
(0, 1) -normalverteilte Zufallszahlen
summiert wiederum normalverteilte
Zufallszahlen ergeben mit dem
Mittelwert n und der Streuung .n2
In Erweiterung gilt für den Mittelwert:
n
kk
n
kkk dzd
1
2
1
2 eiltnormalvert-mit ),0( kz
n =
Wird immer kleiner im Verlältnis zu n