Ingo Rechenberg PowerPoint-Folien zur 3. Vorlesung „Evolutionsstrategie II“ Anwendungsfelder...

Ingo Rechenberg

PowerPoint-Folien zur 3. Vorlesung „Evolutionsstrategie II“

Anwendungsfelder geschachtelter Evolutionsstrategien -

Programmierung einer geschachtelten ES

( ) - ES +,

Auf dem Weg zu einer evolutionsstrategischen Algebra

Beispiel: = 2, = 6, ´ = 4, = 8

= (2, 6)8 + (2, 6)8

+ (2, 6)8 + (2, 6)84 (2, 6)8

2 ,

Beste Population nach 8 Generationen

Zweitbeste Population nach 8 Generationen

Selektion der besten 2 Populationen

,[ ]

, ´ = 2

+

(2, 6)·(2, 6)·(2, 6)·(2, 6)·(2, 6)·(2, 6) )·(2, 6)·(2, 6)

21,1

1,1

Zwei unterschiedliche Strategien

Beispiel für eine algebraische Operation in einer geschachtelten ES

ES-]),/(,/[

Die Geschachtelte Evolutionsstrategie

Höchste Nachahmungsstufe der biologischen Evolution

' = 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

Biologische Entsprechung der Strategie-Schachtelung

| Familie Gattung { Art [ Varietät ( Individuum ) ] } |

ES]),/(,/[

Strategievariablen Objektvariablen

Sprungvariablen Gleitvariablen

Qualität Q1 Qualität Q 2

Springen Klettern

Vergangenheit Gegenwart

Strategie-Evolution

Gemischt ganzzahlige Optimierung

Zwei-Ziele-Optimierung

Globale Optimierung

Ortho-Evolution

Anwendungsfelder für geschachtelte Evolutionsstrategien

ES]),/(,/[

Strategievariablen Objektvariablen Strategie-Evolution


N

Angsthase

Hitzkopf

Kolumbus

Amundsen

Vier Kletterstrategien im Wettbewerb

ES-)10,(4,[ 2011

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

5,1/1 5,1 :6für z.B.

654

321

Es ist problematisch anzunehmen, dass sich schon nach einer Generation die beste Fortschrittsgeschwindigkeit selektieren lässt.

Korrekte mutative Schrittweitenanpassung mit

einer geschachtelten Evolutionsstrategie

= 1,1 … 1,5

Notation auf der linken Klammerseite bedeutet : Die Schritt-weite ist eine Populationseigenschaft. Sie wird in der jewei-ligen inneren Klammer benutzt und dort nicht mehr variiert.

ES]),(,[

12154

Neue Gründerpopulationen

Die geschachtelte Evolutionsstrategie

ES]),/(,/[

Strategievariablen Objektvariablen Strategie-Evolution


Sprungvariablen Gleitvariablen Gemischt ganzzahlige Optimierung

Gewicht Minimum

Gleitvariable !Sprungvariable !

y

x

ES]),/(,/[



Strategie-Evolution



Qualität Q1 Qualität Q 2 Zwei-Ziele-Optimierung

Schlagwort „multikriterielle Optimierung“

Mehr-Ziele-Optimierung


Pareto-OptimierungEin 2-Ziele Pareto-Optimum ist ein Zustand, bei dem es nicht möglich ist, eine Qualität Q1 besser zu machen, ohne dass sich die Qualität Q2 verschlechtert. Die Menge der Pareto-Optima bildet die sogenannte Pareto-Front.

Besser wir lösen eine Zwei-Ziele-Optimierung mit der gewichteten globalen Qualität:

MaximumMinimumQgQgQglobal 2211

Für die verschiedenen Gewichtungen g1 und g2 ergibt sich die Pareto-Front!

Die Idee der globalen Qualität lässt sich leicht auf mehr als zwei Qualitäten erweitern.

Q1

Q2Das Management entscheidet über die Realisation

Pareto Front

Der -Denker-klein

Eine 2-Ziele-Optimierung

Mintan AW

Der W-klein-A-groß-Denker

A

W

AW

)/1log()log()log(tan AW

MinStZa 32

AW

)/1log(3)log(2)StZalog( AW

SteigZahl

ES]),/(,/[




Strategie-Evolution




Springen Klettern Globale Optimierung

[1, 3 ( , ) ]-ES

Gipfelspringen und mit der geschachtelten Evolutionsstrategie

Gipfelklettern

[1, 3 ( , ) ]-ES


Gipfelklettern

GründerPopulationen

[1, 3 ( , ) ]-ES


Gipfelklettern

[1, 3 ( , ) ]-ES


Gipfelklettern

[1, 3 ( , ) ]-ES


Gipfelklettern

KomplexaugenKameraaugen

Einfache Lichtwahrnehmung

Vorstufen derKomplexaugen

Augen mitengem Loch

Becheraugen mit Pigment

Becheraugen mitreflektierendem Pigment

Super-positions-augen

Augen mitengem Loch

Pfeilschwanz-krebs

Zwischenformen

Appositions-augenNeurale

Superposition

Augen mitGlaskörper

Augen mitSpiegeln

Fitnesslandschaft der Augen-Evolution (nach M. Land)

Nautilus

Linsenaugeder Kopffüßer

FischaugenSpinnen

Tapetum-Bergrücken

RuderfußkrebseDetritus

mit Hornhaut ausgestatteteAugen der Landwirbeltiere

9

9

34

56

78

9

3 4 5 6 7 8

3 4 5 6 7 8

3 4 5 6 7 8

34

56

73

45

67

34

56 3 4 5 6 7

3 4 5 6 7 8

Für n >> 1 sind die weißen Einzugsgebiete der Berge vernachlässigbar klein gegenüber dem schwarzen Gebiet dazwischen !

Wir sind hier

Lückenwert L

L =ZwischenraumKugelraum

1122)(

)()( nnn L

2732,0)2( L

69)100( 1035,5 L„weiß“: Einzugsgebiete der Berge

„schwarz“: Zwischenräume

Evolutionsstrategische Optimierung eines Freiträgers mit minimalem Gewicht

ES]),/(,/[




Springen Klettern

Strategie-Evolution



Globale Optimierung


Vergangenheit Gegenwart Ortho-Evolution

( ) - ES +,

Geschachtelte Evolutionsstrategie

+,[ ]

Aktuelle PositionGründerposition

Ortho-Evolution !

n

kkk ddh

bkhhRQ1

21streu Min))(1()1(2 ][

n

kkdnhQ

1vol Min 0 allefür ddk

Minvolstreuges QwQQ

bbh 1)( ( )d d2 1

h

h

hR

d0

d1

d2

q2F

Strahl 2

k

= Brechungsindex

w = GewichtsfaktorZwei-Ziele-Optimierung

Das Wunder der Koordinatentransformation

D‘ARCY THOMSONs Transformationen

Polyprion

Scorpaena sp.Antigonia capros

Pseudopriacanthus altus

Koordinatentransformation nach Albrecht Dürer

Bauanweisung für Protein „Dunkle“ DNA

Das Rätsel der sogenannten Schrott-DNA (junk DNA) ?

Und das könnte auch eine Koordi-naten-Transforma-tion sein

über 95%

Heute weiß man: Die Schrott-DNA bildet einen riesigen Steuerungsapparat

5554543532521515

5454443432421414

5354343332321313

5254243232221212

5154143132121111

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

Lineare Transformation: Polygenie und Polyphänie

n = 5 !

Pleiotropie

Ein Gen (x) steuert viele Merkmale (y)

Ein Merkmal (y) wird von vielen Genen (x) gesteuert

Schiefwinklige lineare Koordinaten-Transformationen

5554543532521515

5454443432421414

5354343332321313

5254243232221212

5154143132121111

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

Zu viele Koeffizienten für Transformation eines orthogonalen Systems

Für ein orthogonales System benötigen wir statt:

nur Koeffizienten21)( nn2n

2nKoeffizienten

5554543532521515

5454443432421414

5354343332321313

5254243232221212

5154143132121111

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

xaxaxaxaxay

Orthogonalisierungsverfahren

Matrizenrechnung

CMA-Methode

ES-Hybridverfahren

Covarianz-Matrix-Adaptation

Programmierung einer

geschachtelten Evolutionsstrategie

[1, (1, ) ]-ESAlgorithmus:

zgNk

gE

gNk

gE

gNk

xx

gNb

gE

gNb

gE

xx

1

1

gNb

gE

gNb

gE

xx

1

1

k

zgNk

gE

gNk

gE

gNk

xx

k = 1, ... k = 1, ...

bgE

gNb )( xx

bgE

gNb )(

gNkk

gE xx )(g

NkkgE )(

Farbe anstelle eines Index !

MATLAB-Programm der (1, ) ES


v=100;gg=1000; kk=10; xe=ones(v,1); de=1; aa=1.5;

Variablenzahl, Generationszahl,

Nachkommenzahl und

Startwerte für Variablenwerte

und Schritt-weite des Start-

Elters



for g=1:gg

endErzeugen der

Generationenschleif

e



for g=1:gg qb=1e+20;

end

Initialisierung der Qualität im

Bestwert-Zwischenspeicher

auf nicht verschlechterbaren

Wert


for g=1:gg qb=1e+20; for k=1:kk

end

endGenerierung der

Nachkommenschleife




for g=1:gg qb=1e+20; for k=1:kk dn=de*aa^(2*round(rand)-1);

end

end

Deterministische Variation der

Mutationsschrittweite



for g=1:gg qb=1e+20; for k=1:kk dn=de*aa^(2*round(rand)-1); xn=xe+dn*randn(v,1)/sqrt(v);

end

end

Erzeugung eines mutierten Nachkommen



for g=1:gg qb=1e+20; for k=1:kk dn=de*aa^(2*round(rand)-1); xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2);

end

end

Bestimmung der Qualität

des mutierten Nachkommen



for g=1:gg qb=1e+20; for k=1:kk dn=de*aa^(2*round(rand)-1); xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end

end

Bei Q-Verbesserung Zwischen-

speicherung der Qualität,

Schritt-weite und Variablenwerte



for g=1:gg qb=1e+20; for k=1:kk dn=de*aa^(2*round(rand)-1); xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end qe=qb; de=db; xe=xb;

end

Nachkomme aus dem

Bestwert-Zwischenspeicher

wird zum Elter der nächsten

Generation



for g=1:gg qb=1e+20; for k=1:kk dn=de*aa^(2*round(rand)-1); xn=xe+dn*randn(v,1)/sqrt(v); qn=sum(xn.^2); if qn < qb qb=qn; db=dn; xb=xn; end end qe=qb; de=db; xe=xb; semilogy(g,qe,'b.') hold on; drawnow;end

Darstellung der Qualität als

Funktion der Generationszahl

Programmverdopplung





Von der einfachen zur geschachtelten ES

Programmdifferenzierung

v=100;gg1=1000; kk1=10; xe1=ones(v,1); de1=1; aa1=1.5;

for g1=1:gg1 qb1=1e+20; for k1=1:kk1 dn1=de1*aa1^(2*round(rand)-1); xn1=xe1+dn1*randn(v,1)/sqrt(v); qn1=sum(xn1.^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end qe1=qb1; de1=db1; xe1=xb1; semilogy(g1,qe1,'b.') hold on; drawnow;end



Programmschachtelung


v=100;



gg0=1000; kk0=10; xe0=ones(v,1); de0=1; aa0=1.5;




for g1=1:gg1 qb1=1e+20; for k1=1:kk1 dn1=de1*aa1^(2*round(rand)-1); xn1=xe1+dn1*randn(v,1)/sqrt(v);

qn1=sum(xn1.^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end qe1=qb1; de1=db1; xe1=xb1; semilogy(g1,qe1,'b.') hold on; drawnow;end


de0=dn1; xe0=xn1;

dn1=de0; xn1=xe0;

1.00

50 2


for g0=1:gg0 qb0=1e+20; for k0=1:kk0 dn0=de0*aa0^(2*round(rand)-1); xn0=xe0+dn0*randn(v,1)/sqrt(v); qn0=sum(xn0.^2); if qn0 < qb0 qb0=qn0; db0=dn0; xb0=xn0; end end qe0=qb0; de0=db0; xe0=xb0;

end


for g1=1:gg1 qb1=1e+20; for k1=1:kk1 dn1=de1*aa1^(2*round(rand)-1); xn1=xe1+0*randn(v,1)/sqrt(v);

qn1=sum(xn1.^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end qe1=qb1; de1=db1; xe1=xb1; semilogy(g1,qe1,'b.') hold on; drawnow;end


de0=dn1; xe0=xn1;

dn1=de0; xn1=xe0;

MATLAB-Programm einer geschachtelten ES


for g0=1:gg0 qb0=1e+20; for k0=1:kk0 dn0=de0*aa0^(2*round(rand)-1); xn0=xe0+dn0*randn(v,1)/sqrt(v) qn0=sum(xn0.^2); if qn0 < qb0 qb0=qn0; db0=dn0; xb0=xn0; end end qe0=qb0; de0=db0; xe0=xb0; semilogy(g0,qe0,'b.') hold on; drawnow;end



qn1=sum(xn1.^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end qe1=qb1; de1=db1; semilogy(g1,qe1,'b.') hold on; drawnow;end


de0=dn1; xe0=xn1;

dn1=de0; xn1=xe0;

MATLAB-Programm einer geschachtelten Ortho-ES

xe1=xb1;

oo=xb1-xe1;

+oo*randn/sqrt(v);

;

MATLAB-Programm einer geschachtelten ES

oo=ones(v,1)


for g0=1:gg0 qb0=1e+20; for k0=1:kk0 dn0=de0*aa0^(2*round(rand)-1); xn0=xe0+dn0*randn(v,1)/sqrt(v) qn0=sum(xn0.^2); if qn0 < qb0 qb0=qn0; db0=dn0; xb0=xn0; end end qe0=qb0; de0=db0; xe0=xb0; semilogy(g0,qe0,'b.') hold on; drawnow;end



qn1=sum(xn1.^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end qe1=qb1; de1=db1; semilogy(g1,qe1,'b.') hold on; drawnow;end


de0=dn1; xe0=xn1;

dn1=de0; xn1=xe0;


xe1=xb1;

oo=xb1-xe1;

+oo*randn/sqrt(v);

;

oo=ones(v,1);

Zum Kopieren (Qualitätsfunktion = „Zigarre“ )

v=100;gg1=1000; kk1=2; xe1=ones(v,1); de1=1; aa1=1.5;gg0=50; kk0=10; xe0=ones(v,1); de0=1; aa0=1.0; oo=ones(v,1);

for g1=1:gg1 qb1=1e+20; for k1=1:kk1 dn1=de1*aa1^(2*round(rand)-1); xn1=xe1+0*randn(v,1)/sqrt(v); de0=dn1; xe0=xn1; for g0=1:gg0 qb0=1e+20; for k0=1:kk0 dn0=de0*aa0^(2*round(rand)-1); xn0=xe0+dn0*randn(v,1)/sqrt(v)+oo*randn/sqrt(v); qn0=xn0(1)^2+1000*sum(xn0(2:v).^2); if qn0 < qb0 qb0=qn0; db0=dn0; xb0=xn0; end end qe0=qb0; de0=db0; xe0=xb0; end dn1=de0; xn1=xe0; qn1=xn1(1)^2+1000*sum(xn1(2:v).^2); if qn1 < qb1 qb1=qn1; db1=dn1; xb1=xn1; end end

qe1=qb1; de1=db1; oo=xb1-xe1; xe1=xb1; semilogy(g1,qe1,'b.') hold on; drawnow;end


ES]),(,[

12154

Neue Gründerpopulationen liegen übereinander (bisher)


ES]),(,[

12154

Neue Gründerpopulationen variieren ihre Startposition


zgNk

gE

gNk

gE

gNk

gE

gNk

xx

zgNk

gE

gNk

xx

gNb

gE

gNb

gE

gNb

gE

xx

1

1

1

gNb

gE xx 1

gNkk

gE xx )(

bgE

gNb )( xx

k

,1k,1k

Algorithmus einer geschachtelten ES, bei der nicht nur jede Population eine eigene Schrittweite besitzt, sondern die Startposition jeder Gründerpopulation noch variiert wird

Schrittweite für das Setzen von Gründerpopulationen

Schrittweite für das lokale Bergklettern zum Optimum

Mathematische Formulierung einer (1, ) - Ortho-ES in ungeschachtelter Form

gE

gNk

zxx gNk

gE

gNk

zmgE

gE )( xx

Variation k = 1, 2, … Nachkommen

Selektion ( B = Bester Nachkomme)gNB

gE 1

gNB

gE xx 1

Elter vor m Generationen

Endewww.bionik.tu-berlin.de

Date post:	06-Apr-2016
Category:	Documents
Upload:	gertrude-laun
View:	217 times
Download:	3 times

Ingo Rechenberg PowerPoint-Folien zur 3. Vorlesung „Evolutionsstrategie II“ Anwendungsfelder...

Documents