1

Anwendungen evolutionärer Algorithmen

1.kontinuierliche Parameter

2.diskrete Parameter in

kombinatorischen Problemen

3.Design Optimierung

-10-5

05

10

-10

-5

0

5

100

50

100

150

200

2

t = 0InitialisiereDo

ReproduktionRekombinationMutationDekodierungEvaluierungSelektiont := t + 1

Until stop

Algorithmus:

Evolutionäre Algorithmen

• Evolutionsstrategien• Genetische Algorithmen• Genetische Programmierung• Evolutionäre Programmierung

Evolutionäre Algorithmen

3

Eigenschaften und Anwendungen

populationsbasiert (erlauben parallele Suche)

wenig Problemwissen nötig (z.B. keine Gradienteninformation)

stochastisches Suchverfahren

• diskontinuierliche Probleme

• diskrete / kombinatorische Probleme

• multimodale Probleme

• multikriterielle Probleme

• verrauschte Qualitätsfunktion

Anwendung:

Eigenschaften:

4

Parameter Optimierung (Teil I)

kontinuierliche Parameter

Evolutionsstrategien

5

Globale Schrittweitensteuerung

x1 x2 xn

Chromosome:

Nachkomme Eltern

Schrittweite

1

2

Eltern

x1

x 2

Wahrscheinlichkeit für die Erzeugung eines Nachkommens

1 > 2

zufällige Mutation

6

1/5 - Erfolgsregel

basiert auf der Analyse der Fortschrittsgeschwindigkeit für das Korridormodell und Kugelmodell.

Mutation bei pe = 0.2

Nur Nachkommen die besser sind als ihre Eltern ergeben nicht den maximalen Fortschritt!!!

Anpassung der Schrittweite:

Maximaler Fortschritt, wenn 1/5 der Nachkommen besser sind

a) bestimmen wie viele Nachkommen besser als die Eltern sindb) vergrößern / verkleinern der Schrittweite je nach Ergebnis

7

mutative Anpassung - Selbstadaptation

Idee: für die Adaptation des Strategieparameters den gleichen Prozeß zu nutzen wie bei der Optimierung der Objektparameter xi.

„Waren die Objektparameter gut, so war auch die Schrittweite gut die zu ihrer Erzeugung genutzt wurde!“

Chromosom:

Anpassung der Schrittweite

Anpassung der Objektparameter

8

mutative Schrittweitensteuerung• pseudoCode

t = 0Initialisiere Objektparameter der Eltern PopulationInitialisiere Strategieparameter der Eltern Populationdo // alle Generationen für alle Nachkommen

wähle ElternRekombination ObjektparameterRekombination StrategieparameterMutation der ObjektparameterMutation der StrategieparameterEvaluieren

endSelektion (neue Elternpopulation)t := t + 1

Until stop

9

Source

10

Selektionsdruck

Wie stark wird selektiert?

- Größe der Elternpopulation

- Größe der Nachkommenpopoulation

ES(10,100): = 10, = 100

Selektionsdruck: s = /

s = 1: keine Selektion -> kein Fortschrittzufällige Suche bei der Kommastrategie

s 0: hoher Fortschrittgeringer Einfluß des Zufallsz.B. geringe Wk. lokale Optima zu überwinden

Notation:

11

Sphere Function

-10-5

05

10

-10

-5

0

5

100

50

100

150

200

-10 -5 0 5 10-10

-8

-6

-4

-2

0

2

4

6

8

10

N

iixQ

1

2

12

Ackley‘s Testfunktion

10 20 30 40 50 60 70 80 90 100

10

20

30

40

50

60

70

80

90

100

020

4060

80

0

20

40

60

800

2

4

6

8

10

12

13

Selektionsdruck - Beispielunimodale Funktion

multimodale Funktion (40 dimensional)

-10-5

05

10

-10

-5

0

5

100

50

100

150

200

020

4060

80

0

20

40

60

800

2

4

6

8

10

12

geringer Selektionsdruck

ES(50,100)ES(20,100)

ES(10,100)

ES(10,100)

ES(20,100)

ES(50,100)

14

Ellipsoidal function

-10-5

05

10

-10

-5

0

5

100

200

400

600

800

1000

1200

-10 -5 0 5 10-10

-8

-6

-4

-2

0

2

4

6

8

10

N

iiixQ

1

2

15

Individuelle Schrittweiten

).)(,(~

)1,0(~,

)1()(

)exp()exp()1()(

2tNz

Nzz

ztxtx

zztt

i

iii

0

n2

1

Jede Variable hat eine eigene Schrittweite

Chromosome:

i

xi

globale Anpassung

n2

1'

lokale Anpassung

Standard Werte:

16

Kugel Funktion

Kugelfunktion

individuelle Schrittweite

globale Schrittweite

17

Ellipsoidal Funktion

schnelle „grobe“ Anpassung bei globaler Schrittweite

• besser in den ersten Generationen• schlechter in der Nähe des Optimums

individuelle Schrittweite

globale Schrittweite

18

Beispiel – individuelle Schrittweiten

kleine Populationen ES(1,10)

individuelle Schrittweite

globale Schrittweite

19

Probleme

Koppelung von Strategieparameter an das Individuum

Selektionsdruck zu optimaler Schrittweite

Probleme durch stochastische Fluktuationen der Schrittweite

verstärkt durch

kleine Populationen

hohe Anzahl an Strategieparametern

Prinzip der mutativen Schrittweitenanpassung

20

Ursachen

Die Stärke der Variationen von Schrittweiten innerhalb einer Population ist ähnlich zu den Variationen in aufeinander folgenden Generationen.

Innerhalb der Population wird eine ausreichende Variation der Parameter benötigt um eine wirkungsvolle Selektion zu gewährleisten.

In aufeinander folgenden Generationen sind allerdings wesentlich kleinere Variationen vorteilhaft, um stochastische Fluktuationen bei der Anpassung der Strategieparameter zu vermeiden.

Zwei mögliche Ursachen sind:

Selbst bei großen Schrittweiten kann die tatsächlich realisierte Schrittweite sehr klein sein.

Würde ein solches Individuum selektiert, wird eine große Schrittweite vererbt, obwohl eine Mutation durch eine kleine Schrittweite realisiert wurde.

Die Anpassung der Schrittweite funktioniert in diesem Fall nicht.

21

Derandomisierte Verfahren

1. Anpassung der Schrittweite aufgrund der realisierten Schrittweite

2. Dämpfungsfaktor der Adaptation

realisierte Mutation des

selektierten Individuums

erwartete Stärke

der Mutation

Dämpfung

22

Kumulation der Schrittweiten

Nutzung der Informationen aus vorhergehenden Generationen

Pfad der Evolution:

Anpassung der Schrittweite:

23

Richtung der Mutation

Wahrscheinlichkeit für die Erzeugung eines Nachkommen

1

2

1

2

globale Schrittweite individuelle Schrittweite Kovarianzmatrix

1 Parameter n Parameter n2 / 2 Parameter

Parameter 1

Par

am

ete

r 2

Parameter 1

Par

am

ete

r 2

Parameter 1

Par

am

ete

r 2

24

CMA

Kovarianzmatrix-Adaptation

1. Bestimmung der „selektierten“ Mutation2. Berechnung des Pfades3. Anpassung einer globalen Schrittweite4. Anpassen der Kovarianzmatrix5. Anpassen der Objektparameter

Mutation

korrelierte Mutationen

Eigenschaften:

• derandomisiert• Dämpfung der Schrittweitenadaptation• Anpassung der Kovarianzmatrixbasierend auf dem Pfad der Evolution

(n2 + n)/2 freie Parameter • zusätzl. globale Schrittweite

Ackley Funktion

Ellipsoidal Funktion

25

Selektionsstrategie

+ Strategie: Aus ( + ) Individuen werden die besten Individuen selektiert

, Strategie: Aus den Nachkommen werden die besten Individuen selektiert

• nur Verbesserungen möglich

• „Hängenbleiben“ in lokalen Minima• zufällig gute Lösungen (verrauschte

Qualitätsfunktion) bleiben in der Population

plus Strategie:

26

• Optimierung kontinuierlicher Parameter

• Selektionsdruck

• Selektionsmechnismen (Komma, Plus)

• Schrittweitenanpassung• globale mutative Schrittweitenanpassung

• Skalierung der Parameter

• individuelle mutative Schrittweitenanpassung• aufwendige Anpassung• Probleme bei mutativer Anpassung durch hohe Anzahl von Parametern (große Populationen nötig)

• CMA Strategie (Covarianz Matrix Adaptation)• „Derandomisierte“ Anpassung der Schrittweiten• Kummulation der Schrittweiten• korrelierte Mutationen

Zusammenfassung

27

Teil II

Diskrete Probleme

28

Gesucht:

• NP-vollständig

• unwahrscheinlich effiziente Algorithmen zur Lösung dieses Problems zu finden

• Der „primitive“ Algorithmus, der einfach alle Möglichkeiten durchprobiert hat eine Komplexität von o(n!)

• häufig „völlig ausreichend“ eine „gute“ Lösung zu finden

Das Travelling Salesman Problem

Route zwischen n Städten, die jede Stadt genau einmal besucht

29

Kodierung

• Kodierung ist problemspezifisch zu wählen

• Es gibt kein allgemeines „Kochrezept“, um eine gute Kodierung zu finden

• Ähnliche Phänotypen sollten durch ähnliche Genotypen dargestellt werden

• Ähnlich kodierte Lösungskandidaten sollten eine ähnliche Fitneß haben• Starke Kausalität

• Der Suchraum (die Menge möglicher Lösungskandidaten) sollte, soweit möglich, unter den verwendeten genetischen Operatoren abgeschlossen sein

• Alle Lösungen sollten darstellbar sein

Prinzipien:

Wie kodiere ich das Problem:

30

Binärstrings:

bei (fast) jeder Operation (sei es Crossover oder Mutation) entstehen ungültige Lösungen

Allgemein sind Binärdarstellungen für Permutationen nur sehr bedingt geeignet

Repräsentation/Kodierung

1 00 1 10

Stadt 1 Stadt 2

Stadt 1 ?

Mutation

0 01 1 10

1 00 1 10 0 01 0 10

4

3

5

2

1

67

31

Die Zahl (Stadt) j ist an i-ter Stelle aufgelistet, falls die Tour von i nach j führt.

Adjacency Representation

Tour der Länge n wird durch eine Liste natürlicher Zahlen dargestellt

Crossover: klassischer Crossover nicht praktikabel, da er ungültige Lösungen erzeugt (z.B. können Zahlen danach mehrfach in der Liste vorkommen).

Beispiel für n = 7:

(6 1 5 3 2 7 4) repräsentiert die Tour 1-6-7-4-3-5-2

Jede Tour hat somit genau eine Adjazenzdarstellung

ungültige Tour möglich: 6 1 5 3 6 7 4

32

klassischer Crossover

4 3 7 6 2 5 1

1

45

6

7

3

2

3 1 7 2 4 5 6

1

45

6

7

3

2

1

45

6

7

3

2

3 1 7 6 2 5 1

klassischer Crossover nicht praktikabel, da er ungültige Lösungen erzeugt (z.B. können Zahlen danach mehrfach in der Liste vorkommen).

Spezielle Crossover Operatoren sind nötig

Eltern 1 Eltern 2

33

• abwechselnd (und auch zufällig) Kanten vom ersten und zweiten Elternteil wählen

• sollte eine dieser Kanten vorzeitig ein Kreis erzeugen, so wird eine zufällige Kanten aus der Menge der noch übrigen Kanten gewählt.

Alternating Edges Crossover

p1 = (3 1 7 2 4 5 6) p2 = (4 3 7 6 2 5 1) könnten folgenden Nachkommen erzeugen:o = (3 1 7 6 2 5 4)

vom ersten Elternteil wird der erste Knoten (die 3) gewählt, dann vom ersten Elternteil die 1 und 7, dann die 6, 2 und die 5 vom zweiten Eltern

An die letzte Position kann weder die 6 vom ersten noch die 1 vom zweiten Elternteil eingefügt werden, ohne den Kreis frühzeitig zu schließen. Es wird also die 4 gewählt, da sie noch übrig ist.

Beispiel für n = 7:

34

Alternating Edges Crossover

4 3 7 6 2 5 1

1

45

6

7

3

2

3 1 7 2 4 5 6

1

45

6

7

3

2

1

45

6

7

3

2

3 1 7 6 2 5 4

35

Diese Liste repräsentiert eine Tour unter Zunahme einer sortierten Referenzliste C (z.B. C= (1 2 3 4 5 6 7))

(2 3 1 4 1 2 1) Tour 2-4-1-7-3-6-5.

Die 2 am Anfang besagt: Nehme das zweite Element in C als ersten Wegpunkt und lösche es aus C.

Die nächsten Zahlen in der Darstellung werden auf die selbe Art und Weise interpretiert.

Die letzte Zahl ist immer 1, da C zu diesem Zeitpunkt nur noch 1 Element enthält.

Ordinal Representation

36

Ordinal Representation

Vorteil:

p1 = (2 3 1 | 4 1 2 1) undp2 = (6 4 5 | 2 3 1 1)

o1 = (2 3 1 2 3 1 1) o2 = (6 4 5 4 1 2 1)

2-4-1-5-7-3-66-4-7-5-1-3-2

Nachteil: Teil-Tour linksseitig des Crossover Punktes wird nicht verändert. Die rechte Seite wird stark verändert.

Mutation ist möglich, indem z.B. einzelne Werte im Rahmen des für ihre Position gültigen Wertebereiches verändert werden.

keine ungültigen Routenklassische Crossover funktioniert

Beispiel für n=7:

37

Path Representation

Die einfachste Art eine Tour darzustellen ist die Reihenfolge der Elemente in einer Liste direkt als Weg zu interpretieren.

(3 4 7 6 1 2 5)

4

3

5

2

1

67

Tour 3-4-7-6-1-2-5

Problem: Mutation

(3 4 7 3 1 2 5)

4

3

5

2

1

67

Beispiel:

38

Mutation

(3 4 7 6 1 2 5)

(3 4 7 6 1 2 5)

Zufälliges Einfügen Displacement / Insertion

Zufälliges Vertauschen Reciprocal Exchange

(3 4 2 6 1 7 5)

(3 4 6 1 2 7 5)

(3 4 |7 6 1| 2 5)

Inversion

(3 4 1 6 7 2 5)

39

• zwei zufällige Crossoverpunkte wählen• Werte zwischen den Punkten vertauschen• Städte links und rechts der Crossoverpunkte wieder an ihrer

Orginalposition einfügen, sofern sie die Gültigkeit der Darstellung nicht verletzen

• Sollte dies aber der Fall sein: statt dessen den Wert einfügen, der vor der Crossover Operation an der Stelle stand, an der nun der gleiche Wert steht wie der, der eingetragen werden soll.

Partially Matched Crossover (PMX)

Es wird eine Teiltour aus einem Elternteil übernommen und versucht die Reihenfolge und Position möglichst vieler Städte aus dem anderen Elternteil zu erhalten.

Idee:

Algorithmus

40

Schritt 2: ohne Konflikt an den ursprünglichen Positionen:

Schritt 3: Lösen der KonflikteIn o1 konnte die 4 nicht eingefügt werden, da sie schon an Stelle 5 steht. Also wird sie durch das Element, welches zuvor an Stelle 5 stand, ersetzt (die 5).

Schritt 1: Vertauschung der Städte zwischen den Crossover Punkten

o1 = (1 5 7 6 4 3 2)o2 = (4 2 6 7 5 3 1)

Beispiel für n = 7p1 = (1 4 |6 7 5 3| 2) p2 = (5 2 |7 6 4 3| 1)

o1 = (x x |7 6 4 3| x)o2 = (x x |6 7 5 3| x)

o1 = (1 x |7 6 4 3| 2)o2 = (x 2 |6 7 5 3| 1)

41

Qualitätsfunktion

Mij : Distanz von Stadt i zu Stadt j

Mii = 0 für alle i

der Weg ist nicht richtungsabhängig

)1(),(

1

1)1(),()( n

n

iii MM

M symmetrisch

Qualitätsfunktion:

42

Beispiel

• PMX crossover• zufälliges Vertauschen

Fitnessverlauf bester Pfad

43

Path

beste Lösung

44

• Dauer der Optimierung (bzw. Qualität der gefundenen Lösung) wird durch die Genotype – Phänotyp Transformation und den Operatoren beeinflußt

• Kodierung im Chromosom sollte dem Problem angepaßt sein• (Binärstrings / diskret / kontinuierlich)

• Angepaßte Operatoren• Crossover: Erhalten von Informationen aus allen Eltern• Mutation: beibehalten wesentlicher Informationen des

Individuums (lokale und kleine Mutationen)

• Verbesserung der Lösungen auch bei ungünstiger Kodierung• Beurteilung der Qualität der gefundenen Lösung• Testprobleme generieren

Zusammenfassung

45

geometrisch

p pitch stagger anglew1,w2 wedge length1,2 wedge angletmax maximal thicknessR1, R2 radius of trailing and

leading edge

Spline

p pitchxi = (xi,yi) cart. coordinates of

control points

Kodierung / Modelle

46

pre

ssu

re lossOriginalOriginal

evolutionär optimiertevolutionär optimiert

45% Reduktion des Druckverlustes

Ergebnisse:

2D Schaufel Optimierung

Qualitätsfunktion:

Druckverlust Abströmwinkelgeometrische Randbedingungen

f(x) = 1 f1() + 2 f2(2) + 3 f3(xmin) + 4 f4(xmax)

Druckverlust

AbströmwinkelOptimierung in zwei Phasen:

1 << 2

47

Multikriterielle Optimierung

multikriterielle Optimierung

Qualiät – Kosten

Stabilität – Gewicht

Stabilität

Gewicht

dominated solutions

Pareto optimale Lösungen

infeasible

regionstandard Methoden:

RandbedingungenQ1 <= Q1,s (maximal weight <= Mmax)

weighted aggregationQ = w1 Q1 + w2 Q2

pareto optimisationnon-dominated solutions

pareto basierte evolutionäre Optimierung

NSGAII

48

DWA: Änderung der Gewichtung während der OptimierungMechanismus:

22

11

2211

für Gewicht :

für Gewicht :

fw

fw

wfwff

Dynamik von w1,2

Dynamic Weighted Aggregation

w1 w2

Fitness

Turbinenblatt

1. Druckverlust2. Auslasswinkel

Simulation

49

2D 3D1h/Evaluation 16h/Evaluation7Tage/Optimierung 4Monat/Optimierung12 CPUs 64 CPUs

3D Schaufel Optimierung

Repräsentation B-Spline Fläche

50

Qualitätsfunktion

outlet angle

geometry

geometry

geometry

outlet angle

pressure loss (to include mixing loss)

static outlet pressure

engine axis

51

The Pareto Front I

minimaler Druckverlust

„guter“ Kompromiss

minimale Schwankung

Optimierung

multi objective

52

Zusammenfassung

Definition der Repräsentationwenige Parameter -> schnelle Konvergenzhochdimensional -> Flexibilität der Repräsentation

Darstellbarkeit des Optimumslokale und stark kausale Repräsentation

Reale Probleme sind häufig multikriteriellLösung:

Aggregation der Kriterien ist effizient aber benötigen VorwissenSpezielle Algorithmen existieren (z.B. DWA / NSGAII)

QualitätsfunktionBerücksichtigung aller KriterienWelche Lösungen sind wirklich optimal? Iterativer Prozeß zwischen

Optimierung und Analyse

53

http://shark-project.sourceforge.net/

EA –Library: