Date post: | 06-Apr-2016 |
Category: |
Documents |
Upload: | rosamund-kern |
View: | 224 times |
Download: | 3 times |
Ingo Rechenberg
PowerPoint-Folien zur 5. Vorlesung „Evolutionsstrategie I“
Finale der Theorie der zweigliedrigen Evolutionsstrategie
Handlungsregeln als Ergebnis der nichtlinearen Theorie
gggEN zxx
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
vergrößern für We > 1 /
5 verkleinern für We < 1 /
5
Für maximales
Mutationsschrittweite und Erfolgswahrscheinlichkeit
Erfolge
Erfolge
We ≈ 0,49 = 1: 2,04
We ≈ 0,16 = 1: 6,25
Höhenlinie
+
> 1/5
< 1/5
gggEN zxx
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
vergrößern für We > 1 /
5 verkleinern für We < 1 /
5
gz auf die Länge 1 normiert
Wie normiert man einen Zufallsvektor auf die Länge 1 ?
Wir erwürfeln die Komponenten nzzz ,, 21
und bestimmen die Länge 222
21 nzzz
Wir dividieren durch und erhaltennzzz ,, 21
die normierten Zufallzahlen n
nzzzzzz ,, 2
211
Dann ist 1222
21 nzzz !
Frage: Wie groß ist für viele normalverteilte Zufallsszahlen nzzz ,, 21
Viele quadrierte Zufallszahlen addiert ergeben einen repräsentativen Mittelwert
?
Aber für n >> 1 geht es noch viel einfacher, zu 1 zu machen
Der Zufallsschritt wird mit wachsender Variablenzahl n immer länger
Normalverteilte Zufallszahlen zi für die Mutation der Variablen xi
zi
w2
221
e21)( iz
izw
0
2
+
Wendepunkt der Kurve
Werden viele Zufallszahlen mit der
Wahrscheinlichkeitsdichte
addiert, ergibt sich der Mittelwert Null.
Werden diese Zufallszahlen aber
quadriert und aufsummiert, ergibt sich
ein Mittelwert größer als Null! Die
Wurzel daraus ist die Zufallsschrittweite.
)( izw
)(213 2
322
212e
21)(
zzz
t PPw
PP
Die Trefferwahrscheinlichkeitsdichte
Ursprung der z-KoordinatenP
P
P
P
P
P
P
‚
r
PP
Zum radialen Strecken- Erwartungswert
P
P
32123
22
21 ddd)( zzzwzzzr PPt
R3
‚Ursprung der z-Koordinaten
ntn zzzwzzzr PP ddd)( 2122
221
R
…
Für n Dimensionen
)()(
22
12 n
n
n für n >> 1
Zur Schwankung der Länge
2lim
22
1 nn
n
n
)()(
Um also werden zu lassen, müssen wir setzen 1 n1
gggEN zxx
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
vergrößern für We > 1 /
5 verkleinern für We < 1 /
5
gz auf die Länge 1 normiert eiltnormalvert -1,0 / )( n
Achtung !
Die Normierung des Zufallsvektors auf die Länge 1 gilt nur für die Anwendung des ES-Algorithmus zur Lösung eines Optimierungsproblems.
In den Formeln der Theorie der ES bleibt die Größe, welche die Mutationsschrittweite symbolisiert.
n1
Doch einmal ersetzen wir in unseren Formeln durch
1
211
2Korr
n
b
rn
rnr
n
882 erf12
Kugel8e
1
211
2Korr
n
bnn
rn
rn
nrn
882erf1
2
lKuge8e
nn n
Wir nennen die Mutationsschrittweite
Bisherige Formeln
n2
KugelKorr
Für <<1 folgt
Hurra, das kennen wir doch (Guldin)
Korridor Kugel
nb
e nr202,0
nb2
nr224,1
max
opt
opteW e21 270,0
Ergebnisse der nichtlinearen Theorie
Korridor Kugel
nb
e nr202,0
nb2
nr224,1
max
opt
opteW e21 270,0
Erweiterte Ergebnisse der nichtlinearen Theorie
optn
b2n
r224,1
ES-Suchschlauch im Korridor
für n ≈ 400
bbn
bopt 8
140022
2 b
ES-Suchschlauch im Kugelmodell
für n ≈ 900
rrn
ropt 25
190022412241 ,,
r
Text
Allgemeines Suchbild der ES für n >> 1
sondern wegenn
b 2korr opt
nr224,1
kug opt
Nicht so
so
Darwin lässt grüßen !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.
gggEN zxx
Algorithmus der (1 + 1) - ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
gz
vergrößern für We > 1 /
5 verkleinern für We < 1 /
5? Wie stark müssen
wir vergrößern bzw. verkleinern?
eiltnormalvert -1,0 / )( n
Zum Schrittweitenänderungsfaktor der (1 + 1) - ES
enGenerationder Zahl ungVerkleinerRadien
Kugel 1
)1()(Kugel
gg rrfür g =
1
Klettern mit max)(
max Kugel202,0 grn
)()1()( 202,01
ggg
rnrr
nrr
g
g 202,01)()1(
2
)()1(
)1()2(
)()2( 202,01
nrr
rr
rr
g
g
g
g
g
g
nk
g
nkg
nrr
202,01)()(
Für n / 0,202 >> 1 gilt
kkn
n n2020
2020202020201 ,,, e,lim
Text
Desh
alb
k·n
knk
g
nkg
nrr 202,0
)()(
e202,01
Die Schrittweiten müssen sich so ändern wie die Radien:
kg
nkg
g
nkg
rr 202,0
)()(
)()(
e
Für k = 1 folgt 817,0202,0)(
)1(e
g
ng
Für optimales Fortschreiten ist also nach n Generationen um
817,022,111 k zu verkleinern. Bewährt hat sich = 1,3 –
1,5.
→ Einstellregel5/1 eW für 5,1
5/1 eW für 5,1/
gggEN zxx
Algorithmus der (1 + 1) - ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
gz
1,3 für We > 1 / 5 1,3 für We < 1 / 5
Nach jeweilsn Generationen
eiltnormalvert -1,0 / )( n
gggEN zxx
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
1,5 für We > 1 / 5 1,5 für We < 1 / 5
Nach jeweilsn Generationen
eiltnormalvert -1,0 / )( ngz
gggEN zxx
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() (für gggENN QQ xxx
sonst gEx
1g)() ( für3,1 ggg
EN xQxQ
sonst 4 3,1/ gMinimalform !
eiltnormalvert -1,0 / )( ngz
Die Schrittweite wird nach jeder Generation verändert
Idealisierter richtiger Ablauf einer (1+ 1)-ES-Optimierung
Schrittweitenänderung
3,1 4 3,1/ 4 3,1/ 4 3,1/ 4 3,1/ 3,1 4 3,1/
Erfolg Misserfolg Erfolg
Erfolgshäufigkeit ist richtig Keine Schrittweitenänderung !
Bei mehr Erfolgen wird mehr mit 1,3 multipliziert
Bei mehr Misserfolgen wird mehr mit durch dividiert4 3,1
Ein Minimalprogramm in MATLAB
zur Minimierung der Testfunktion „Kugelmodell“
v=100; d=1; xe=ones(v,1); qe=sum(xe.^2);
for g=1:1000 xn=xe+d*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qe qe=qn; xe=xn; d=d*1.3; else d=d/(1.3^0.25); end semilogy(g,qe,'b.') hold on; drawnow;end
Zurück zu den Fortschrittsformeln für das Korridor- und das Kugelmodell
rn
rnr
n
882 erf12
Kugel8e
882**8** erf1
2*
Kugel e
folgt und mit **rn
rn
Kugelmodell
)( **lKuge f
1
2112Korr
n
b
1
2112
n
bn
nbn
bn
bn
n
n
nbn
2e11
21lim
bn
bn
bn
2
1e
21 *
Korr21
** e21
Quasikonstante ≈ 1, wenn mit opt vorangeschritten werden soll
Korridormodell
e11lim
n
n n
, **bn
bn
),( **Korr nf
)( **orrK f
1-e11lim
n
n n
a-n
an na
1e11lim/
für Korridormodell
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
! !
Ende
www.bionik.tu-berlin.de
Genau genommen ist das gezeigte Konvergenzbild nur richtig, wenn sich die Hyper-kugel in Richtung Startelter Kugelzentrum geringfügig zu einem Ellipsoid verformt. Bei einer exakten Kugel sind die Kugelschalen selektionsneutral. Ähnlich wie beim evolutionsstrategischen Beklettern einer ansteigenden Ebene eine Seitwärtsdrift eintritt, wird bei der exakten Kugel eine Umfangsdrift stattfinden. Der Suchschlauch wird sich also spiralförmig dem Kugelzentrum nähern.
Idee der Theorie:
Es ist das Kugelmodell, das eine besonders starke Anpassung der Mutationsschritt-weite erfordert. Die Schrittweite muss sich in dem Maße verkleinern, wie der Zielab-stand während des Fortschreitens abnimmt. Wir können die Verkleinerung des Ziel-abstands pro Generation in die mathematische Form (r
(g) – r
(g+1) ) /1 bringen. Diese
mittlere Zielabstandsverkleinerung soll nun den größten Wert annehmen; das heißt wir setzen sie gleich max. Wir wiederholen die Gleichsetzung für k·n Generations-schritte (k =1, 2, ...) Wir setzen am Ende der Rechnung willkürlich k = 1. Es bedeu-tet, dass die errechnete Schrittweitenverkleinerung erst nach n Generation ausge-führt werden darf.
Der Faktor (Schittweitenänderungsfaktor genannt) gibt an, mit welchen Wert größer als 1 die Mutationsschrittweite multipliziert werden muss, wenn die Erfolgswahrscheinlichkeit größer als 1/5 ist. Umgekehrt muss durch dividiert werden, wenn die Erfolgswahrscheinlichkeit kleinen als 1/5 ist.