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

transcript

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

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)

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

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

1 xx )(),(),()( N2NNNB 1minmax/ gggg QQQQ xxxx

1E1N gg

2E2N gg

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

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]),(,[

Neue Gründerpopulationen

Die geschachtelte Evolutionsstrategie

ES]),/(,/[

Strategievariablen Objektvariablen Strategie-Evolution

Sprungvariablen Gleitvariablen Gemischt ganzzahlige Optimierung

Gewicht Minimum

Gleitvariable !Sprungvariable !

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.

Q2Das Management entscheidet über die Realisation

Pareto Front

Der -Denker-klein

Eine 2-Ziele-Optimierung

Mintan AW

Der W-klein-A-groß-Denker

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

MinStZa 32

)/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

3 4 5 6 7 8

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 !

kkk ddh

bkhhRQ1

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

kkdnhQ

1vol Min 0 allefür ddk

Minvolstreuges QwQQ

bbh 1)( ( )d d2 1

Strahl 2

= 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

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

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

Orthogonalisierungsverfahren

Matrizenrechnung

CMA-Methode

ES-Hybridverfahren

Covarianz-Matrix-Adaptation

Programmierung einer

geschachtelten Evolutionsstrategie

[1, (1, ) ]-ESAlgorithmus:

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

gNb )( xx

gNb )(

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

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

Initialisierung der Qualität im

Bestwert-Zwischenspeicher

auf nicht verschlechterbaren

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

endGenerierung der

Nachkommenschleife

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

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);

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);

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

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;

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;

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;

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]),(,[

Neue Gründerpopulationen liegen übereinander (bisher)

ES]),(,[

Neue Gründerpopulationen variieren ihre Startposition

gE xx 1

gE xx )(

gNb )( xx

,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

zxx gNk

gE )( xx

Variation k = 1, 2, … Nachkommen

Selektion ( B = Bester Nachkomme)gNB

gE xx 1

Elter vor m Generationen

Endewww.bionik.tu-berlin.de

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

Documents