Upload
caecilia-rad
View
109
Download
2
Embed Size (px)
Citation preview
Ingo Rechenberg
PowerPoint-Folien zur 10. Vorlesung „Evolutionsstrategie I“
Finale Theorie der Evolutionsstrategie
mit Eltern und Nachkommen
DARWINs Denkschema in maximaler Abstraktion
ES)1( 1
Genauere Nachahmung der biologischen Evolution
ES),( 1
Noch genauere Nachahmung der biologischen Evolution
ES),(
Basis-Algorithmus der (, ) - Evolutionsstrategie
1E1N zxx ggi
2E2N zxx ggj
zxx ggkEN
eiltnormalvert)1,0(,, /21 nzzz n
gg1NBE1
1 xx
,2,1,,, rankji
gg2NBE2
1 xx
gg NBE
1 xx
B1 = Qualitätsmäßig bestes Individuum
B2 = Qualitätsmäßig 2. bestes Individuum
B = Qualitätsmäßig . bestes Individuum
1 2 3 4 5 6 7 8 9 10 12 14 16 18 20
1 0,002 0,56 0,003 0,85 0,50 0,004 1,03 0,75 0,44 0,005 1,16 0,91 0,67 0,40 0,006 1,27 1,03 0,83 0,61 0,37 0,007 1,35 1,13 0,94 0,76 0,57 0,35 0,008 1,42 1,22 1,04 0,87 0,71 0,54 0,33 0,009 1,49 1,29 1,12 0,96 0,82 0,67 0,50 0,31 0,00
10 1,54 1,35 1,19 1,04 0,90 0,77 0,63 0,47 0,30 0,0012 1,63 1,45 1,30 1,17 1,04 0,93 0,81 0,69 0,57 0,43 0,0014 1,70 1,53 1,39 1,26 1,15 1,05 0,95 0,84 0,74 0,64 0,40 0,0016 1,77 1,60 1,45 1,34 1,23 1,14 1,05 0,95 0,86 0,78 0,59 0,37 0,0018 1,82 1,66 1,53 1,41 1,31 1,22 1,13 1,04 0,96 0,89 0,72 0,55 0,35 0,0020 1,87 1,71 1,58 1,47 1,37 1,29 1,20 1,13 1,05 0,98 0,83 0,68 0,52 0,33 0,0030 2,04 1,90 1,78 1,69 1,60 1,53 1,45 1,39 1,33 1,27 1,16 1,06 0,95 0,86 0,7650 2,25 2,12 2,01 1,93 1,85 1,79 1,73 1,68 1,62 1,57 1,49 1,41 1,33 1,26 1,19
100 2,51 2,39 2,30 2,22 2,16 2,10 2,05 2,00 1,96 1,92 1,85 1,79 1,73 1,67 1,62200 2,75 2,64 2,55 2,49 2,43 2,38 2,34 2,29 2,26 2,22 2,16 2,11 2,06 2,01 1,97300 2,88 2,78 2,69 2,63 2,58 2,53 2,49 2,45 2,41 2,38 2,32 2,27 2,23 2,19 2,15500 3,04 2,94 2,86 2,80 2,75 2,71 2,67 2,63 2,60 2,57 2,52 2,47 2,43 2,39 2,36
1000 3,24 3,15 3,08 3,03 2,98 2,93 290 2,86 2,84 2,81 2,76 2,72 2,68 2,65 2,61
Linearer Fortschritt: ,, c , c aus Tabelle
lin
kug
,, lin c
,1,1 lin c
rnc2
2
,1,1 kug
rnc2
2
,, kug
Kugelmodell
E
r
.. .x x2 n
x1
q
N"'N
a
nnq 1
222 arqr
rar
qa 2 2
für2
a linKugel
rnc2
2
,Kugel
a
"
Linien Fortschritt
N
Für q << r darf a auf x 1
projiziert werden
Mutation der Variablen x 2 bis x
n
Der bis auf x 1 mutierte
Nachkomme N‘ erleidet
den Rückschritt a
Eine geometrische Betrachtung für n >> 1
Das dimensionslose Fortschrittsgesetz
rnc2
2
,Kugel
2,2 cr
n
2,
2
22
,2
, 422
cr
n
cr
n
cr
n
mit
2,2 cr
n
,2 cr
nund
folgt das zentrale Fortschrittsgesetz2
Dimensionslose Fortschrittsgeschwindigkeit
Dimensionslose Schrittweite
rnc2
2
,Kugel ),,,,( rnf
-5 -3 -1 310
0,2
0,1
0,3
1 01 01 01 010
2
Evolutions Fenster
Kugelmodell
Korridormodell
10010-210-410-610-8
102 104 106 1080
0,4
0,3
0,2
0,1
*
*
Fortschrittsfenster der (1 + 1) - Evolutionsstrategie
Evolutionsfenster
1 02 0,0796 03 0,1194 0,0417 04 0,1325 0,0703 0,0242 05 0,1352 0,0828 0,0449 0,01606 0,1338 0,0884 0,0574 0,03107 0,1306 0,0912 0,0631 0,04138 0,1267 0,0930 0,0676 0,04739 0,1225 0,0925 0,0697 0,0512
10 0,1184 0,0911 0,0708 0,054111 0,1144 0,0891 0,0708 0,055612 0,1106 0,0876 0,0704 0,057013 0,1070 0,0860 0,0696 0,057014 0,1036 0,0836 0,0690 0,056815 0,1004 0,0816 0,0677 0,0566
/*max,1 /*
max,2 /*max,3 /*
max,4
Serielle Fortschrittsgeschwindigkeit /*,
Maximalwerte
0,1352
0,0930
0,07080,0708
0,05700,0570
Maximale Fortschrittsgeschwindigkeit:
(1 + 1) - ES versus (1, ) - ES
nr202,0max11
nr135,0max5,1
nr093,0max8,2
nr072,0max11,3
nr057,0max13,4
maxmax 115,1 67,0
maxmax 118,2 46,0
maxmax 1111,3 35,0
maxmax 1113,4 28,0
Warum ( , ) - ES statt (1 + 1) - ES ?
1. Selbstadaptation der Mutationsschrittweite erfordert eine Gruppe konkurrierender Individuen ( > 1)
3. Die Einführung des Vererbungsfaktors „Chromosomen-Kreuzung“ erfordert mehrere Eltern ( > 1)
2. Eine Population von Elternindividuen ( > 1) ist robuster gegenüber Qualitätsrauschen (unscharfe Selektion)
Ideale Funktion in der mathematischen Welt
Rauher Berg in der experimentellen Welt
Qualitätsfunktion mit Rauschen
QQ~
Fehler
222
1
e2
1)(
R
R
w
+
w
Linearer Fortschritt für
Nach einer ziemlich aufwendigen Ableitung
,1,1~ h
22)( Ra
ah
xaQ
Streuung- gesamteStreuung- mutative
h wird in der Biologie Fitness-Heritabilität genannt
Beispiel: 10Mutationen durch vonStreuung Rauschen durch vonStreuung
aR
linlin ,1,1 1,0~
,1,1~ chc
,,~ chc ,,
~ chc !
linlin ,12,1)/(1
1~
aR
Fortschrittsbeiwerte bei Rauschen
h = 1 h = 1/10 h = 1/100
154,0~10,1 c
242,0~10,2 c
293,0~10,5 c
54,110,1 c
90,010,5 c
35,110,2 c
015,0~10,1 c
025,0~10,2 c
037,0~10,5 c
51,2100,1 c
16,2100,5 c
62,1100,20 c
251,0~100,1 c
635,0~100,5 c
773,0~100,20 c
025,0~100,1 c
095,0~100,5 c
206,0~100,20 c
100,1100,20~24,8~ cc
und nicht 0457,0100120 h 072,062,10457,0~
100,20 c
für h = 1/100
Nichtlineare Störungstheorie für die (1, )-ES
rnc2
~~2
,1,1 kug
rnc
aR2)/(1
1~2
,12,1 kug
0d
~d
2
opt
opt 2~
hh 24
,1
,1 2~
max
max hh
22
opt21 hha
R
opt
opt~
opt
aR
max
max~
opt
aR
Optimale Mutationsstreuung am verrauschten Kugelmodell
Maximaler Fortschritt am verrauschten Kugelmodell
Der Stagnationsradius
2opt
aRFür ist 0~
max
nrc ,1
,12Stagnation ca
nr R
NeueGeneration
Nachkommenrealisieren
FlexibleBleistreifen
Messungc ca w--
Nachkommenbewerten
Elterneingeben
Evolution eines Spreizflügels im Windkanal
Generation
0
3
6
9
1215
18
21
24
27
Evolution eines Spreizflügels im Windkanal
Selektionsansicht
Subjektiv gewählte (selektierte) Figur nachGeneration 0 Generation 20 Generation 40 Generation 80
Entwicklung eines Quadrats bei subjektiver Bewertung
Weiterentwicklung des Quadrats zum Mercedes-Stern
bei subjektiver Bewertung
Subjektiv gewählte (selektierte) Figur nach
Generation 1
Generation 20
Generation 40
Generation 60
Generation 80
Generation 100
Generation 200
Subjektive Bewertung
Kaffee-Komposition mitder Evolutionsstrategie
Elter25% Columbia
40% Sumatra
13% Java
5% Bahia
17% Jamaica
Nachkomme 120% Columbia
34% Sumatra
23% Java
5% Bahia
18% Jamaica
Nachkomme 223% Columbia
37% Sumatra
12% Java
10% Bahia
18% Jamaica
Nachkomme 325% Columbia
32% Sumatra
15% Java
8% Bahia
20% Jamaica
Nachkomme 430% Columbia
38% Sumatra
8% Java
2% Bahia
22% Jamaica
Nachkomme 533% Columbia
38% Sumatra
9% Java
8% Bahia
12% Jamaica
O 1
O 2
O 3
O 4
O 5
Subjektive Bewertung
E
N 3
Evolutionsstrategische Entwicklungeiner Marken-Kaffeemischung
M. Herdy
Mimikry
Der Blauhäher frisst einen Monarchen
Der bekommt dem Vogel schlecht
Vor Übelkeit sträuben sich die Federn
Heraus mit dem Gift
Vorüber, die Lehre wird nicht vergessen
Subjektive Selektion in der Natur
Ende