Post on 05-Apr-2015
transcript
6. Vorlesung Evolutionsstrategie I
1/n
1/ n
Gradientenstrategie
kontra
Evolutionsstrategie
Der Dumme, der einfach losgeht, kommt weiter als der Schlaue, der sitzen bleibt und sich vor lauter Nachdenken nicht entscheiden kann.
Motto des Evolutionsstrategen
Normalverteilte Zufallszahlen zi für die Mutation der Variablen xi
zi
w2
22
1
e2
1)(
iz
izw
0
2
+
)(213 2
322
212
e21)(
zzz
t PPw
P
P
Die Trefferwahrscheinlichkeitsdichte
Ursprung der z-KoordinatenP
P
P
P
P
P
P
r
PP
Zum radialen Strecken- Erwartungswert
P
P
32123
32
21 ddd)( zzzwzzzr PPt
R3
ntn zzzwzzzr PP ddd)( 2122
221
R
…
Für n Dimensionen
)()(
2
21
2 n
n
n für n >> 1
Zur Schwankung des Zufallsvektors
1
211
2Korr
n
b
rn
rnr
n
882erf1
2
Kugel8e
1
211
2Korr
n
bnn
rn
rn
nrn
882erf1
2
lKuge
8e
Korridor Kugel
nb
e nr202,0
nb2
nr224,1
max
opt
opteWe2
1 270,0
Ergebnisse der nichtlinearen Theorie
Korridor Kugel
nb
e nr202,0
nb2
nr224,1
max
opt
opteW e21
270,0
Ergebnisse der nichtlinearen Theorie
optn
b2n
r224,1
Kein zufälliges Stochern,
sondern gerichtete Diffusion
ggg zxx EN
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() ( für gggENN xQxQx
sonst gEx{
vergrößern für We > 1 /
5 verkleinern für We < 1 /
5
?Wie stark müssen wir vergrößern bzw. verkleinern?
normiert 1 Länge die auf gz
Zum Schrittweitenänderungsfaktor der (1 + 1) - ES
enGeneration der ZahlungVerkleinerRadien
Kugel
1
)1()(
Kugel
gg rrfür g =
1
Klettern mit max)(
max Kugel202,0 grn
)()1()( 202,0
1g
ggr
nrr
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 >> 1 giltk
kn
k n202,0
202,0202,0
e202,01lim
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/
ggg zxx EN
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() ( für gggENN xQxQx
sonst gEx{
1,5 für We > 1 / 5
normiert 1 Länge die auf gz
1,5 für We < 1 / 5
Nach jeweilsn Generationen
Computer-Versuche mit der 1/5-Erfolgsregel
ggg zxx EN
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() ( für gggENN xQxQx
sonst gEx{
1,5 für We > 1 / 5
normiert 1 Länge die auf gz
1,5 für We < 1 / 5
Nach jeweilsn Generationen
ggg zxx EN
Algorithmus der (1 + 1) – ES mit 1/5-Erfolgsregel
1gEx
)() ( für gggENN xQxQx
sonst gEx{
normiert 1 Länge die auf gz
1g { )() ( für3,1 gggEN xQxQ
sonst 4 3,1/ gMinimalform !
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 !
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
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
rn
rnr
n
882erf1
2
Kugel8e
882
**8** erf1
2*
Kugel e
folgt und mit **rn
rn
1
211
2Korr
n
b
1
211
2
n
bn
nn
bn
bn
n
n
nbn
2e
11
21lim
bn
bn
bn
2
1
e2
1 *
Korr
21
** e2
1
Quasikonstante für opt
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