2. Evolution als Optimierungsprinzip · Heuristik. 9 Probleme, die auftreten können: Ableitungen der Zielfunktion nicht möglich/bekannt Güte einer Lösung wird auf Basis von Daten

1

2. Evolution als Optimierungsprinzip

Biologen betrachten Evolution als Mechanismus, der in der Natur Lösungen für spezielle Probleme erzeugt

Prinzipien der biologischen Evolution werden zur Lösung von Optimierungsproblemen verwendet

Computer stehen für Berechnungen und Simulationen zur Verfügung

Evolutionäre Algorithmen nutzen die Rechenleistung der Computer zur Simulation der Evolutionsmechanismen für gegebene Optimierungsprobleme

2

Optimierungsprobleme Treten in allen Bereichen des täglichen Lebens auf:

Industrie, Wirtschaft, Forschung, ... Scheduling: Stundenplan, Zuweisung Flugpersonal Entwurfsoptimierung: Verbesserung von Turbinen,

Autodesign, VLSI-CAD

ℜ→Ω:f

Definition: (Optimierungsproblem)Geg.: Suchraum

BewertungsfunktionVergleichsrelation

Ω

><∈ ,

Die Menge der globalen Optima ist definiert als

)()(:| yfxfyx Ω∈∀Ω∈=χ

3

Beispiel: Handlungsreisendenproblem

n Städte/Knoten Paarweise durch Straßen/Kanten verbunden Fahrzeiten Gesucht: Reihenfolge der Städte für kostenminimale

Rundreise Zielfunktion

+ℜ∈= ),(),( ijji vvvv γγ

nvv ,,1

),(),(),,( 112

1 jjn iin

jiin vvvviif −

=Σ+= γγ

7

3

11

8

5

Fahrzeit

116

512

69

84

1710

FahrzeitKanteFahrzeitKanteKante

4

Vergleich von großen ZahlenGroße Zahlen sind manchmal nur schwer vorstellbar:

ein großes Fußballstadion fasst 100.000 Menschen es gibt ca. 5.000.000.000 Menschen auf der Erde es gibt ca. 1.000.000.000.000.000.000.000 Liter Wasser auf

der Erdeund ...

ein 10-Städte TSP hat 181.000 mögliche Lösungen ein 20-Städte TSP hat mehr als 10.000.000.000.000.000

mögliche Lösungen ein 50-Städte TSP hat mehr als

100.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 mögliche Lösungen

5





nvv ,,1

),(),(),,( 112

1 jjn iin

jiin vvvviif −

=Σ+= γγ

7

3

11

8

5

Fahrzeit

116

512

69

84

1710


∑= 45

5

10

6

611

7

6





nvv ,,1

),(),(),,( 112

1 jjn iin

jiin vvvviif −

=Σ+= γγ

7

3

11

8

5

Fahrzeit

116

512

69

84

1710


5 6

11

3 8

4

∑= 37

7

Klassische Lösung eines Optimierungsproblems

Problem

ProblemanalyseEntwurf eines Algorithmus

Theoretische Analyse

Implementierung

Experimente

8

Klassische Optimierungsverfahren

Extremwertberechnungen über Ableitungen Bewertungsfunktion ist eine 2-mal stetig-differenzierbare

Funktion Suchmethoden

Systematisches Durchsuchen des (endlichen) Lösungsraumes (z.B. branch&bound)

kombinatorische Explosion Gradientenmethode (steilster Anstieg)

Bewertungsfunktion muss differenzierbar sein Konvergiert gegen den dem Startpunkt nächst

gelegenen lokalen Extremwert Simplexmethode

Bewertungsfunktion (+ Nebenbedingungen) muss linear sein Suchraum bildet dann n-dim. Simplex (n=2: Vieleck) ein Eckpunkt ist Extremwert

Heuristik

9

Probleme, die auftreten können: Ableitungen der Zielfunktion nicht möglich/bekannt Güte einer Lösung wird auf Basis von Daten bewertet, die nicht

genau gemessen werden können (Messfehler) Wert der Zielfunktion ändert sich mit der Zeit Stabilität der Lösung (d.h. Veränderungen bei kleinen

Änderungen der Parameter) ist oft genauso wichtig wie Optimalität

Güte der Lösungsstrategie hängt von der Güte anderer Strategien ab (Bewertung von Spielstrategie)

Lösung muss nach mehreren Kriterien bewertet werdenspäter mehr

Exakte mathematische Formulierung und erst recht exakte Lösungsbestimmung sind oftmals nicht möglich!

10

Simulationsbasierte und randomisierte Ansätze

Selektionsverfahren, darunter Mutation-Selektions-Verfahren Threshold Accepting Sintflut-Methode Simulated Annealing

Evolutionäre Algorithmen Genetische Algorithmen Evolutionsstrategien Genetische Programmierung Hybride Verfahren Memetische Algorithmen ...

11




12

Klassische Lösung eines Optimierungsproblems

Problem

ProblemanalyseEntwurf eines Algorithmus

Theoretische Analyse

Implementierung

Experimente

13

Anwendung randomisierter Suchverfahren

Problem P

Entwurf eines randomisierten

Suchverfahrens A

Theoretische Analysedes Verhaltens

von A auf P

ImplementierungExperimentelle

Anwendungvon A auf P

14

Mutations-Selektions-Verfahren

Wähle zufällige Startlösung Verändere x durch Zufallszahlen Falls dann setze Das Vorgehen wird mehrfach wiederholt

Für bedeutet das

Ω∈x)(' xMutx =

),()'( xfxf ': xx =

2ℜ∈x

0

1

2

3

4

5

f(x,y)

1 2 3 4 5x

Lokaler Extremwert

Nachteil: Entfernen aus lokalen Extremwerten ist nicht möglich!

15

Simulated AnnealingVerschlechterung der Zielfunktion ist mit einer gewissen

- allerdings sehr kleinen - Wahrscheinlichkeit möglich: Ursprung in der Festkörperphysik: Abkühlen von

flüssigen Materieverbindungen, so dass sie in Festkörper (z.B. Kristalle) übergehen

Kirkpatrick (1982) übertrug Methode des langsamen Abkühlens auf allgemeine Optimierungsprobleme

Algorithmus: Wähle zufällige Startlösung Verändere x durch Zufallszahlen Berechne Wähle mit Wahrscheinlichkeit p(r) x‘ als Startlösung x Das Vorgehen wird mehrfach wiederholt

Ω∈x)(:' xMutx =

),()'(: xfxfr −=

16

Eigenschaften von Simulated Annealing

Wahrscheinlichkeit p(r) muss klein sein für negative r und groß sein für positive r :

Start mit großem T (=Temperatur)alle Startlösungen sind (fast) gleichwahrscheinlich

Verkleinern von Tbessere Lösungen werden beim Austausch wahrscheinlicher

Schnelles Abkühlen bzw. Verkleinern vonSystem pendelt sich schneller auf (lokalen) Extremwert ein

Langsam Verringern von THöhere Wahrscheinlichkeit, den globalen Extremwert zu finden

0,)/exp(1

1)( >−+

= TTr

rp

170

0.2

0.4

0.6

0.8

1

-4 -2 0 2 4

1/(1+exp(-x/10))

0

0.2

0.4

0.6

0.8

1

-4 -2 0 2 4

1/(1+exp(-x/0.1))

Verlauf der Wahrscheinlichkeiten p(r) für verschiedene T

T=0.1

T=1

T=10

18

Algorithmus: Simulated Annealing1. Wähle eine Startlösung 2. Verändere die Lösung3. Berechne4. Berechne die Wahrscheinlichkeit

5. Wähle eine Zufallszahl mit Ist dann wähle x‘ andernfalls x als (neue) Startlösung

6. Verkleinere die Temperatur T7. Falls Abbruchskriterium nicht erfüllt, fahre fort bei 2.

Variable Parameter: Größe der Veränderung/Mutation der Lösung Abkühlung von T

Ω∈x)(:' xMutx =

)()'(: xfxfr −=0,

)/exp(11)( >−+

= TTr

rp

.10 ≤≤ zz )(rpz ≤

19

Threshold Accepting

Verschlechterung der Zielfunktion ist innerhalb einer Toleranzschwelle möglich:

1. Wähle eine Startlösung 2. Verändere die Lösung3. Berechne4. Ist dann wähle x‘ andernfalls x als (neue) Startlösung 5. Verkleinere die Toleranzschwelle T6. Falls Abbruchskriterium nicht erfüllt, fahre fort bei 2.

Erklimmt schneller (lokale) Extrema als SimulatedAnnealing

Kann in lokalem Extremum hängen bleiben

)(:' xMutx =Txfr −= )(:

rxf ≥)'(

Ω∈x

20

Sintflut-Methode

Verschlechterung der Zielfunktion ist möglich, allerdings muss diese mindestens gleich einem gegebenen Akzeptanzwert T sein:

1. Wähle eine Startlösung sowie eine Zahl T2. Verändere die Lösung3. Berechne4. Ist dann wähle x‘ andernfalls x als (neue) Startlösung 5. Vergrößere den Akzeptanzwert T um das Inkrement 6. Falls Abbruchskriterium nicht erfüllt, fahre fort bei 2.

Fast so gut wie Threshold Accepting, dafür schneller Kann in lokalem Extremum hängen bleiben

Ω∈x)(:' xMutx =

)'(xfTxf >)'(

ε

21




22

Der simulierte evolutionäre Zyklus

Evolutionäre Algorithmen Optimierungsverfahren analog zur Evolution Motivation durch Beobachtungen in der Natur

Lösungen sind Individuen einer Population Erzeugen neuer Individuen Selektion der besser angepassten Lösungen in nächste

Generation

Anpassung wird durch Bewertung der Individuen gemessen

Ideales Verhalten Individuen verbessern sich von Generation zu Generation mit

hoher Wahrscheinlichkeit Zufallseffekte und mehrere unterschiedliche Individuen

sorgen dafür, dass lokale Extremwerte verlassen werden

Survival of the fittest

23

Ablauf eines EAs

Initialisierung der Individuen

Bewertung der Individuen

solange Terminierungsbedingung nicht erfüllt

Erzeuge neue Individuen

Bewertung der neuen Individuen

Selektion

24

Schematische Darstellung des Zyklus

Initialisierung

Bewertung

Eltern-selektion

Rekombination

MutationBewertung

Umwelt-selektion

Terminierungs-bedingung

JA

NEIN

fertig

25

Freiheitsgrade Repräsentation

Wie wird das Optimierungsproblem kodiert?

Initialisierung Wie groß wählt man die Population, und wie generiert man

die Startlösungen? Zufällige Startlösungen

Operatoren Wie werden Individuen erzeugt, und mit welcher Häufigkeit

werden die Operatoren angewandt? Selektion

Wie werden die Elemente ausgewählt, die im weiteren Verlauf noch betrachtet werden?

Terminierung Wann bzw. unter welchen Bedingungen soll der Algorithmus

enden?

26

Ein einfacher EA

Entwicklung eines einfachen EAs am Beispiel des Handlungsreisenden - Travelling Salesman P. (TSP)

7

3

11

8

5

Fahrzeit

116

512

69

84

1710


∑= 45

5

10

6

611

7

27

Ein einfacher EAEntwicklung eines einfachen EAs am Beispiel des

Handlungsreisenden - Travelling Salesman P. (TSP) Kodierung: Menge aller Permutationen

Jedes Individuum ist ein Operatoren:

Mutation, die gültige Permutation erzeugt Vertauschen zweier Städte

Invertierende Mutation Spiegeln (Invertieren) einer Teilroute

Rekombination zweier Routen Übung

:nSnn SAAA ∈= ),,( 1

),,,,,,('),,,,,,( 11 nklnlk AAAAAAAAAA =⇒=

),,,,,,('),,,,,,( 121211 nkkknkkk AAAAAAAAAAAA ++++ =⇒=

tauschM

invertM

28

Anwendung der Mutationen auf den Weg

tauschM invertM

∑= 37

∑= 42 50∑=

29

EA für das TSP

);(

;)1(:)(

;1:);(____

);(_

);(10)3,0(

);,(();_:();_:

(();__

;0:

tP

CtPtPtt

tPinIndividuumtesschlechteslöscheConZielfunktiAuswertung

CMutationC),[uu

BArerekombinie C:IndividuumselektiereBIndividuumselektiereA

tPopulationzufälligeereinitialisi

t

aus Individuum bestes

in lZufallszahist //

stop)

:P(t)

Städte)der (AnzahlEATSP

return

thenif

dowhile

∪−=+=

=≤

===≤

==

30

Typisches Verhalten des Algorithmus

In den ersten Generationen schnelle Verbesserung der Zielfunktion

In den nächsten Generationen nur noch wenige bessere Individuen

Für größere Problemeinstanzen wird das (globale) Optimum idRnicht gefunden

Bemerkungen: Der Algorithmus ist eine Basisversion, die in zahlreichen Punkten

verbessert und auf das Problem zugeschnitten werden kann. Für das TSP gibt deutlich bessere probabilistische/evolutionäre

Verfahren, die speziell angepasst wurden.

31

Formale Einführung von EAs Darstellung der Lösungskandidaten durch Genotyp aus dem

Raum G Suchraum des Problems ist phänotypischer Suchraum

(Phänotyp) (G und können gleich sein) Dekodierfunktion: (Abbildung Genotyp – Phänotyp)

Bewertungsfunktion f arbeitet auf dem Phänotyp, die induzierte Funktion F (inkl. Dekodierung) auf dem Genotyp

Ω

ΩΩ→Gdec :

Raum des konkreten Problems Ω

Phänotyp

Genotyp mGGG ××⊆ 1

Dekodierung

Bewertungsfunktion

InduzierteBewertungsfunktion

f

F

+ℜ

32

Formale Darstellung des Individuums

Sei A ein Individuum, dann ist A.G der Genotyp A.S Zusatzinformation Strategieparameter A.F Fitnesswert/Güte

Bewertung

Genotyp A.G A.S A.FIndividuum

Phänotyp

decFitness

f

F

Evolutionäre Operatoren

Selektion

33

Notationen Komponenten des Genotyps werden mit

A.Gi oder auch Ai bezeichnet Falls keine Zusatzinformation enthalten

ist, d.h. A.S enthält keine weitere Information, schreiben wir auch A G

Speicherung des Fitnesswertes in A.F dient der einfachen Notation und ist auch bei einer Implementierung sinnvoll

∈

34

Weitere Notationen: Größe der Elternpopulation: (oder: p, |P| ) Anzahl der erzeugten Kinder: (oder: q, |K| ) k Eltern werden zur Erzeugung von k‘ Kindern

benötigt Zur Erzeugung von Kindern werden insges.

Eltern ausgewählt (wähle r und s so, dass und ganzzahlig sind

Umweltselektion wählt für die nächste Generation Individuen aus den Kindern oder aus den Individuen und Kindern aus.

µλ

λ

λ λ)/( srλµ

λµ +

35

Formale Definition der Operatoren

Da die Operatoren probabilistisch sind, werden sie im Rechner durch pseudo-Zufallszahlen gesteuert.

Der erzeugte Wert ist damit abhängig vom aktuellen Wert des Zufallsgenerators

Reproduzierbarkeit der Ergebnisse

Definition: (Mutations-, Rekombinationsoperator)Für ein durch den Genotyp G kodiertes Optimierungsproblem und

die Zusatzinformation Z wird ein Mutationsoperator durch die Abbildung

definiert. Analog wird ein Rekombinationsoperator mit Eltern und

Kindern definiert durch die Abbildung

ξ

ZGZGM ×→×:ξ

2≥r 1≥s.)()(: sr ZGZGR ×→×ξ

36

SelektionsoperatorDefinition: (Selektionsoperator)Ein Selektionsoperator wird auf eine Population, d.h. ein Tupel von

Individuen angewandt. Dabei werden q<p Individuen ausgewählt und es handelt sich um eine Abbildung

Unter der Annahme, dass die Individuen der Population nummeriertsind, d.h. einen Index besitzen, kann die Selektion vereinfacht als Indexoperator beschrieben werden:

Die ausgewählten Individuen werden anschließend neu nummeriert.

GAAAP ip ∈= )()()1( mit ,,

.)()(:,, qpfdec ZGZGS ×→×ξ

( ) .,,1

.,.:11

)()(

jiindindpind

indSAFAS

jii

qiipi

ii

≠≠∈

→≤≤≤≤

für und mit

ξ qindind ,,1 =

37

Allgemeiner EA

);(

);'''(__:)(;1:

;'''.);''_(_:'''

);'(__:''));((_)/_(:'

)();(.);(__:)(

;0:;

)(

)(

tP

PIndividuenselektieretPtt

PFAPIndividuenmutiereP

PNachkommenerzeugePtPElternsrselektiereP

stopttPFA

PopulationzufälligeereinitialisitPt

F

i

i

aus Individuum bestes

aus Individuen allefür berechne

aus Individuen allefür berechne

Kinderzahl,sgrößePopulation,onZielfunkti

return

dowhile

:Eingaben

µ

λλ

µ

λµ

=+=

===≤

==

38

Ablauf eines EAsGeneration i

39


Selektion

40


Selektion Rekombination

41



Bewertung

42



Bewertung Nachfolgende

Generation

Generation i+1

43



Bewertung Nachfolgende

Generation Terminierungskriterium

44

Vergleich mit der natürlichen Evolution

Biologische Konzepte der Mutation, Rekombination und Selektion werden übernommen

Aber: Komplexe natürliche Abläufe werden durch einfache

probabilistische Funktionen ersetzt Komplexe Kodierungen werden durch einfache

Datenstrukturen ersetzt Selbstorganisierende Spezialisierung der Zellen

mehrzelliger Organismen bleibt unberücksichtigt Evolution von Evolutionsmechanismen wird nicht

(oder kaum) berücksichtigt Weitere Konzepte wie Koevolution und Genfluss

bleiben in den meisten Verfahren unberücksichtigt

45

Ein kurzer Historischer Abriss1950

heute

Friedman 1956Friedberg 1958

Bremermann 1962

Box 1956

Evolutions-strategien

EvolutionäresProgrammieren

GenetischeAlgorithmen

GenetischesProgrammieren

Rechenberg 1964

Fogel 1965 Holland

1969Koza1992

Evolutionary ComputingJournal of Evolutionary Computing (1993), IEEE Trans. (1997) Handbook of EC (1997), GECCO, CEC

PPSN EP ICGA GP

Documents

2. Evolution als Optimierungsprinzip · Heuristik. 9 Probleme, die auftreten können: Ableitungen der Zielfunktion nicht möglich/bekannt Güte einer Lösung wird auf Basis von Daten