GLEAM - General Learning and Evolutionary Algorithm and Methodjawi0001/EA-Vorlesung/PDF/K5_GLEAM_Handout_2... · Studiengang Wirtschaftsinformatik K5_GLEAM.ppt 4 ... Takt 0Start_Motor_2,

Planung und Optimierung mit evolutionären Verfahren

K5: GLEAM - General Learning and Evolutionary Algorithm and Method

1

Planung und Optimierung mit evolutionären Verfahren Dr. W. Jakob

Studiengang Wirtschaftsinformatik K5_GLEAM.ppt 1 1

GLEAM

General Learning and Evolutionary Algorithm and Method

Motivation (Aktionskonzept für die Steuerung von Prozessabläufen)

Aufbau

Repräsentation (statische und dynamische Interpretation)

Genetische Operatoren

Plausibilitätstest und Genetic Repair

Bewertung

Akzeptanz

Abbruchkriterien

Vergleich mit der ES und den GAs



GLEAM – Motivation

General Learning Evolutionary Algorithm and Method

Ein eigenständiger Evolutionärer Algorithmus, der Grundelemente

der Evolutionsstrategie und

der Genetischen Algorithmen

mit Konzepten der Informatik (abstrakte Datentypen)

verbindet.

Ideen:

Nutzung des Evolutionsprinzips zur Planung und Steuerung dynamischer Abläufe

breites Anwendungsspektrum durch flexible und anwendungsnahe Codierung

Nutzung von durch die Biologie inspirierten Metastrukturen bei der Evolution

Ziel: Planung, Optimierung und Steuerung von Prozessabläufen

Nebeneffekt: Erfolgreiche Anwendungen in „traditionellen“ EA-Feldern wie

Designoptimierung, Reihenfolgeplanung oder Scheduling



2




Bedeutung eines Gens in der Biologie?

Bestimmung phänotypischer Eigenschaften

Wie viel Parameter benötigt eine phänotypische Eigenschaft?

Das ist anwendungsabhängig!

Welcher Art (ganz-zahlig, reell, Wertebereich) sind diese Parameter?

Das ist auch anwendungsabhängig!

Anwendungsabhängige Darstellung der Parameter in den

Genen des Chromosoms




Biologie:

Die Erbinformation ist mehr als ein Bauplan:

Steuerung von Wachstumsprozessen

Steuerung der Geschlechtsreife bereits entwickelter Individuen

Steuerung von Heilungsprozessen

. . .

Zeitbezug der Chromosomen-Interpretation

Umsetzung in GLEAM:

► Gene sind Aktionen, die in der realen technischen Welt ausgeführt werden.

► Die Parameter der Aktionen legen die Details der Ausführung fest.

► Parameter, Aktionsanzahl und –reihenfolge unterliegen der Evolution.



3



GLEAM – Aufbau - Repräsentation

Regeln des Genmodells:

1. Ein Gen enthält so viele Parameter oder Entscheidungsvariablen

von geeignetem Datentyp, wie es die Anwendung erfordert.

2. Ein Gentyp beschreibt den Aufbau eines Gens samt Wertebereichsgrenzen

der Parameter oder Entscheidungsvariablen.

3. Chromosome enthalten als Metastruktur eine Segmentierung, auf die

viele genetische Operatoren Bezug nehmen.

Die Segmentierung selbst unterliegt ebenfalls der Evolution.

4. Konstruktionsregeln für Chromosome je nach Chromosomentyp:

Typ 1: Jeder Gentyp kommt genau einmal vor.

Gen-Reihenfolge ist nicht bedeutungstragend.

Typ 2: Jeder Gentyp kommt genau einmal vor.

Gen-Reihenfolge ist bedeutungstragend.

Typ 3: Jeder Gentyp kommt beliebig oft einschließlich gar nicht vor.

Gen-Reihenfolge ist bedeutungstragend.

Dynamische Chromosomenlänge.




Konsequenzen:

1. Das Genmodell erlaubt die Formulierung allgemeingültiger

Routinen zur Chromosomengenerierung,

genetischer Operatoren und

Mutationen, die die Wertebereichsgrenzen beachten.

2. Anwendungsnahe Darstellung von Parametern oder Entscheidungsvariable

und Genen

Beispiel eines Gentyps:

Genkennung (Typ)

Designoptimierung eines Faltenbalgs, Beschreibung einer Kerbe

obligatorischer Teil

eines Gens

Kerbentiefe double [0.5, 20]

Kerbenbreite double [4, 40]

Kerbenposition int [0, 1] // oben, unten

Kerbenabstand double [4, 100]

Optionaler

Parameterteil

eines Gens.

Unterliegt der Evolution



4




Segmentierung:

Evolvierbare Metastruktur zur Zusammenfassung und Vererbung guter Teilstücke

Organisation des Chromosoms als lineare Liste mit Listenkopf

Zusammenhängende Gene bilden die Segmente.

Anzahl und Größe der Segmente unterliegen der Evolution:

Verschiebung von Segmentgrenzen

Teilung von Segmenten

Zusammenfassung benachbarter Segmente

Mutationen und Crossover greifen auf die Segmentgrenzen zurück.

Listen-

kopf

Gen

a1

Gen

a2

Gen

a3

Gen

b1

Gen

b2

Gen

c1

Gen

c2

Gen

c3

Segment a Segment b Segment c

Beispiel eines Chromosoms als lineare Liste mit Listenkopf und drei Segmenten:

Hat das

phänotypische

Auswirkungen?




Modell-Datei:

Beschreibung des Genmodells durch eine Initialisierungsdatei,

welche der Konfiguration der evolutionären Maschine dient.

Diese enthält unter anderem:

Angabe des Chromosomentyps

Anzahl und Beschreibung der Gentypen

pro Gentyp:

Anzahl der Integer- und Real-Parameter (Entscheidungsvariable)

Unter- und Obergrenzen pro Entscheidungsvariable (Wertebereiche)

Wahrscheinlichkeit bei der Generierung (nur Typ 3)

verschiedene Benennungen zu Dokumentations- und Anzeigezwecken



5




Genmodell

Chromosom

Chromosomentyp

Gentyp

Gene

Entscheidungsvariable

Aktionsmodell

Aktionskette (AK)

Aktionskettentyp, AK-Typ

Aktionstyp

Aktionen

Parameter

Sprachliche Unterscheidung:

Statische Dynamische zeitbezogene

Interpretation eines Chromosoms:



GLEAM – Aufbau - Repräsentation - Aktionsmodell

Aktionsmodell:

Aktionsketten werden durch einen Simulator interpretiert oder „ausgeführt“.

Jede Aktion der AK führt zu einer Aktion in der simulierten oder realen Welt

und greift in den Prozessablauf ein.

Während der Aktionsausführung kann es zu Ereignissen kommen,

die die Fitness beeinflussen.

Herstellung des Zeitbezug durch einen aktionsbezogenen Zeittakt:

Aktion a1 t0

Aktion a2 t0 + Dt

. . .

Aktion an t0 + (n-1)·Dt

Für jede Aktion steht also eine (simulierte) Ausführungszeit Dt zur Verfügung.



6




Aktionsmodell (2):

Zwei Aktionen des Standardmodells zur Zeitsteuerung:

1. Block_Begin und Block_End

Alle m Aktionen zwischen Block_Begin und Block_End starten im

gleichen Zeittakt:

Aktion ai: Block_Begin tn

Aktion ai+1: tn

Aktion ai+2: tn

. . .

Aktion ai+m: tn

Aktion ai+m+1: Block_End tn

Aktion ai+m+2: tn+1

Alle m Aktionen

beginnen gleichzeitig

im Takt tn.




Aktionsmodell (3):

2. Unchanged

Die Aktion hat einen Integer-Parameter n.

Sie bewirkt, dass die Ausführung der nachfolgenden Aktion um n Takte

verschoben wird.

Sie belässt also die Einstellungen aller vorangegangenen Aktionen für

n Zyklen unverändert.

Aktion ai: ti

Aktion ai+1: Unchanged n ti+Dt

Aktion ai+2: ti+(n+1)·Dt

Mit diesen beiden Aktionen können beliebige zeitliche Abläufe

zum Starten und Beenden von Aktionen modelliert werden.



7




Anwendungsbeispiel für das Aktionskonzept: Roboterbewegungsplanung

Ansteuerung der Motoren eines Industrieroboters mit rotatorischen Achsen:

Roboter-

Steuerungs-

zyklus

Bewegung von

Roboterachse 2

beispielhafter Achsbefehl:

Motor 2 an mit 12 Grad/Sekunde,

mit 48 Grad/Sekunde2

Mitsubishi-Roboter RV-M1

mit 5 Achsen:

• Rumpf

• Schulter

• Ellenbogen

• Hand, knicken

• Hand, drehen




Achs-Befehle:

1. Start_Motor_<nr>, Rampe=<r_wert>, Geschwindigkeit=<g_wert>

Start des Motors der Achse <nr>

mit einer Rampe von <r_wert> Grad/Sekunde2

und einer Geschwindigkeit von <g_wert> Grad/Sekunde

2. Motor_aus_<nr>, Rampe=<r_wert>

Anhalten des Motors der Achse <nr>

mit einer Rampe von <r_wert> Grad/Sekunde2

Damit gibt es pro Achse zwei Bewegungsaktionen.

Welche Alternative zu dieser Codierung liegt nahe?

Universelle Achsbefehle mit der Achsnummer als Parameter

Welche Nachteile hat das?

Kleine Änderung (Achsnummer) kann enorme Wirkung haben!

Maximale Beschleunigung und Geschwindigkeit sind nicht für alle Achsen gleich! Wertebereiche der Parameter nur noch als Obermenge angebbar!



8




Geschwindigkeit-Zeit-Diagramm:

Interpretation folgender drei Aktionen:

Start_Motor_2, Rampe=48, Geschwindigkeit=12

Unchanged 10

Motor_aus_2, Rampe=17

Geschwin-

digkeit

Zeittakte

Geschwindigkeit von

12 Grad/Sekunde erreichtAktion

„Motor aus“

11

12

1

Takt 0

Takt 1

Takt 11




Beispiel zur simultanen Bewegung dreier Achsen:

Takt

1 Block_Beginn

1 Start_Motor_2, Rampe = 60, Geschw = 7 durchgezogene Linie

1 Start_Motor_3, Rampe = 55, Geschw = 12 gepunktete Linie

1 Block_End

2 Unverändert: Takt_Anzahl = 12

14 Motor_aus_3, Rampe = 60

15 Start_Motor_1, Rampe = 48, Geschw = 40 gestrichelte Linie

16 Unverändert Takt_Anzahl = 20

36 Motor_aus_1, Rampe = 12


47 Start_Motor_1, Rampe = 20, Geschw = -15


Geschwin-

digkeit

t

Motor 3

Motor 1

Motor 2

Aktions-

ketten-

ende

Der Interpreter lässt alle

Motoren, die bei AK-Ende noch angeschaltet sind,

definiert abbremsen.



9



GLEAM – Aufbau – Repräsentation - Übung

Übung:

Gegeben sei folgende Aktionskette:

1. Zu welchem Takt beginnen die Aktionen, wenn die erste Aktion mit Takt 1 startet?

2. Bestimmen Sie die Start- und Endtakte der Rampen, wobei ein Takt

0.2 Sekunden lang sei.

3. Erstellen Sie daraus ein Geschwindigkeits-Zeit-Diagramm, wobei die Zeit

in Takten anzugeben ist.

Kopf Move axis 1

10o/s by 5o/s2

Continue

30 cycles

Block

begin

Move axis 3

20o/s by 20o/s2

Move axis 4

16o/s by 4o/s2

Block

end

Continue

25 cycles

Stop 3

by 8o/s2

Continue

20 cycles

Stop 4

by 8o/s2

Stop 1

by 2o/s2




Aufgabe 2:

Achse 1: Beschl.-Rampe: Dauer = 2s = 10 Takte Takt 1 – 10

Bremsrampe: Dauer = 5s = 25 Takte Takt 80 – 104


Bremsrampe: Dauer = 2.5s ≈ 13 Takte Takt 58 – 70



Kopf Move axis 1

10o/s by 5o/s2

Continue

30 cycles

Block

begin

Move axis 3

20o/s by 20o/s2

Move axis 4

16o/s by 4o/s2

Block

end

Continue

25 cycles

Stop 3

by 8o/s2

Continue

20 cycles

Stop 4

by 8o/s2

Stop 1

by 2o/s2

1 2 32 32 32 32

33 58 59 79 80

Aufgabe 1:



10




10 20 30 40 50 60 70 80 90 100

5

15

10

20

[cycles]

[degrees/sec]




Bremsrampe: Dauer = 2.5s ≈ 13 Takte Takt 58 – 70



Aufgabe 3:



GLEAM – Aufbau

Pseudocode von GLEAM:

Initialisierung und Bewertung der

Startpopulation

REPEAT (Generationen-Schleife)

FOR alle Individuen der Population

Wähle ranking-basiert einen Partner

innerhalb der Nachbarschaft

FOR alle Gruppen genetischer Operatoren

Erzeuge Nachkomme(n) und bewerte es oder sie

Akzeptanz oder Zurückweisung des besten Nachkommen

gemäß Akzeptanzregel und positivenfalls Ersetzung des Elter

UNTIL Abbruchkriterium erfüllt (Zeit, Qualität, Stagnation, …)

Liefere bestes Individuum (und weitere, falls vorgegeben) als Ergebnis

Allgemeiner EA



11



GLEAM – Aufbau - Genetische Operatoren

Übersicht über die genetischen Operatoren:

Standard-Mutationen, Beachtung der Wertebereiche des Genmodells

Standard-Crossoveroperatoren, Beachtung des AK- oder Chromosomen-Typs

Schnittstelle für anwendungsspezifische Operatoren

Daraus werden Gruppen gebildet, die

zwei Nachkommen durch Crossover erzeugen oder

zwei Nachkommen durch Crossover + anschließenden Mutationen erzeugen oder

ein mutiertes Elterklon erzeugen

Dabei hat jede Gruppe und jeder Operator jeweils eine eigene

Ausführungswahrscheinlichkeit.

Alle Gruppen kommen dran.

Konsequenzen:

1. Die Anzahl der Nachkommen pro Paarung variiert.

2. Klone können zufallsbedingt unverändert bleiben.

Löschen!




Mutation relative Parameteränderung:

Ziele:

1. Einhaltung der Bereichsgrenzen

2. Gleiche Wahrscheinlichkeit für Vergrößerung und Verkleinerung unabhängig vom

aktuellen Wert

3. Kleine Änderungen erheblich wahrscheinlicher als große

(Vergleichbar mit der von der ES her bekannten Glockenkurve der Normalverteilung)

4. Schnelle Berechenbarkeit

Vorgehensweise:

1. Einteilung des verfügbaren Gesamtänderungsbereichs in 10 gleichgroße Teilbereiche

2. Der erste Teil bildet das erste Änderungsintervall,

der erste und zweite Teil das zweite Änderungsintervall,

der erste, zweite und dritte Teil das dritte Änderungsintervall, usw.

3. Jedem Änderungsintervall wird die gleiche Wahrscheinlichkeit von 10% zugeordnet.

Teil 1 Teil 2 Teil 4 Teil 3 Teil 5 Teil 6 Teil 7 Teil 8 Teil 9 Teil 10 Maximum aktueller Wert

2. Änderungsintervall 5. Änderungsintervall



12




Mutation relative Parameteränderung (2):

Algorithmus:

1. Entscheide gleichverteilt, ob vergrößert (vz=1) oder verkleinert (vz=-1) wird.

Daraus ergibt sich der Gesamtänderungsbereich.

2. Wähle das Änderungsintervall gleichverteilt aus.

3. Wähle den Änderungswert Dw aus diesem Intervall gleichverteilt aus.

4. Berechne neuen Parameterwert:

Einteilung und Algorithmus ergeben folgende summierte Wahrscheinlichkeiten der Teilbereiche:

1.Teilbereich ( 0 - 10% Änderung): 𝟏𝟎% ∙ 𝟏 + 𝟏𝟐 + 𝟏 𝟑 +⋯+ 𝟏

𝟏𝟎 = 𝟐𝟗, 𝟑%

2.Teilbereich (10 - 20% Änderung): 𝟏𝟎% ∙ 𝟏 𝟐 + 𝟏 𝟑 +⋯+ 𝟏𝟏𝟎 = 𝟏𝟗, 𝟑%

3.Teilbereich (20 - 30% Änderung): 𝟏𝟎% ∙ 𝟏 𝟑 +⋯+ 𝟏𝟏𝟎 = 𝟏𝟒, 𝟑%

…

10.Teilbereich (90 - 100% Änderung): 𝟏𝟎% ∙ 𝟏 𝟏𝟎 = 𝟏%

wvzpp altneu D

Teil 1 Teil 2 Teil 4 Teil 3 Teil 5 Teil 6 Teil 7 Teil 8 Teil 9 Teil 10 Maximum aktueller Wert

2. Änderungsintervall 5. Änderungsintervall





Einteilung und Algorithmus ergeben folgende

summierte Wahrscheinlichkeiten der einzelnen Teilbereiche:

Kleine Änderungen erheblich wahrscheinlicher als große

0

5

10

15

20

25

30

0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80 80-90 90-

100Änderung in % des maximal möglichen Bereichs

Wa

hrs

ch

ein

lich

ke

it



13





Beispiel für die Wahrscheinlichkeitsverteilung im Gesamtparameterintervall: (Man beachte, dass die Wahrscheinlichkeit für Vergrößerung bzw. Verkleinerung gleich ist)

UG aktueller Wert OG




Übersicht über die gen- oder aktionsbezogenen Mutationen:

Gen- oder aktionsbezogene

Standard-Mutationen

AK- od. Chromosomentyp

Typ 1 Typ 2 Typ 3

Änderung des Parameterwerts ja ja ja

Neuer Parameterwert ja ja ja

Änderung aller Parameter eines Gens ja ja ja

Erneuerung aller Parameter eines Gens ja ja ja

Verschiebung ja ja

Ersetzung ja

Einfügung ja

Verdoppelung ja

Löschung ja



14




Löschung einer Aktion oder eines Gens:

Aktion

Move axis 1

Aktion:

Move axis 3 ... Aktion:

Stop axis 4 ...

Aktion

Move axis 1

Aktion:

Stop axis 4 ... ...




Einfügung einer Aktion oder eines Gens:

Aktion

Move axis 1

Aktion:


Stop axis 4 ...

Aktion:

Move axis 5 ... Aktion


Stop axis 4

Aktion

Move axis 1

Neu eingefügt



15




Verschiebung einer Aktion oder eines Gens:

Aktion:

Move axis 5 ... Aktion


Stop axis 4

Aktion

Move axis 1

... Aktion


Stop axis 4

Aktion:

Move axis 5

Aktion

Move axis 3

Aktion

Move axis 3

verschobene

Aktion geschlossene Lücke




Übersicht über die segmentbezogenen Mutationen:

Kopf

Segmentbezogene Standard-Mutationen AK- od. Chromosomentyp

Typ 1 Typ 2 Typ 3

Parameteränderung der Gene eines Segments ja ja ja

Erneuerung von Parametern der Gene eines Segments ja ja ja

Inversion (Umkehrung der Genreihenfolge) ja ja

Verschmelzung benachbarter Segmente ja ja ja

Verschmelzung nicht benachbarter Segmente ja ja

Teilung eines Segments ja ja ja

Verschiebung ja ja

Ersetzung ja

Einfügung ja

Verdoppelung ja

Löschung ja



16




Segmentmutationen:

Invertierung der Aktions- oder Genreihenfolge eines Segments:

... ...

... Aktion

Stop axis 4 ... Aktion:

Move axis 3

Aktion

Move axis 1

Aktion

Unchanged 8

Invertiertes Segment

Aktion

Move axis 3

Aktion:

Stop axis 4

Aktion

Move axis 1

Aktion

Unchanged 8

Segment




Segmentmutationen (2):

Segmentlöschung:

Segmentduplizierung:

Segmentverschiebung:

Listen-

kopfAktion

a1

Aktion

a2

Aktion

a3

Aktion

b1

Aktion

b2

Segment a Segment b

Aktion

c1

Aktion

c2

Segment c

Aktion

a1

Aktion

a2

Aktion

a3Aktion

a1

Aktion

a2

Aktion

a3

Segment a Kopie von Segment a

Aktion

b1

Aktion

b2

verschobenes

Segment a

Aktion

a1

Aktion

a2

Segment a

Aktion

c1

Aktion

c2

Segment c

Aktion

b1

Aktion

b2

Segment b



17




Segmentmutationen (3):

Segmentaustauschung:

Segmentneuerstellung:

Aktion

a1

Aktion

a2

getauschtes

Segment a

Aktion

c1

Aktion

c2Aktion

d1

Aktion

d2

Segment d

Aktion

b1

Aktion

b2

Segment bgetauschtes

Segment c

Aktion

a1

Aktion

a2

Aktion

a3

Aktion

neu1

Aktion

neu2

Aktion

b1

Aktion

b2

Aktion

b3

Segment a Segment neu Segment b



Crossoveroperatoren:

GLEAM enthält insgesamt fünf Standard-Crossoveroperatoren,

die alle auf den Segmentgrenzen aufbauen.

Drei allgemeine Crossoveroperatoren,

die die AKs oder Chromosomen an den Segmentgrenzen aufteilen:

1-Punkt-Crossover

n-Punkt-Crossover

Austausch genau eines Segments

Sie sind bei allen AK- oder Chromosomen-Typen sinnvoll.

Sie können illegale Nachkommen erzeugen:

Bei AK-Typ 1 und 2 können Aktionen fehlen oder doppelt vorhanden sein!

Bei AK-Typ 3 kann das nicht passieren.




18




1-Punkt-Crossover:

1. Bestimme in jedem Elter eine Segmentgrenze zufällig.

2. Bilde das 1.Kind aus dem ersten Teil von Elter 1 und dem zweiten Teil von Elter 2.

3. Bilde das 2.Kind aus dem ersten Teil von Elter 2 und dem zweiten Teil von Elter 1.

4. Je nach Kettentyp Verschiebung überzähliger Gene auf das jeweils andere Kind (Reparatur)

Kopf

Kopf

Elter1:

Elter2:

Kopf Kind1:

▼

▼

Kopf Kind2:




n-Punkt-Crossover:

1. Bildung des 1. Kindes durch abwechselndes Kopieren einer ausgewürfelten Anzahl von

Segmenten der Eltern:

1. Zwei Segmente von Elter2

2. Ein Segment von Elter1

3. Ein Segment von Elter2



2. Der Rest bildet das 2. Kind


Kopf

Kopf

Elter1:

Elter2:

Kopf Kind1:

▼

▼

▼

▼

▼

▼

▼

▼



19




Segmentaustausch:

1. Bestimme in jedem Elter ein Segment zufällig.

2. Bilde beide Kinder aus Elternkopien und tausche die gewählten Segmente aus.


▼

▲

Kopf Elter1:

Kopf Elter2:

Kopf Kind1:

Kopf Kind2:




Crossoveroperatoren für kombinatorische Probleme:

Zwei Crossoveroperatoren, zugeschnitten auf kombinatorische Aufgaben:

Order-based Crossover (OX)

Precedence Preserving Crossover (PPX)

Nutzung der Segmentierung:

Die Segmentierung des 1. Elter bestimmt die Anzahl und Länge der Sequenzen.

Diese Sequenzen werden ohne Rücksicht auf die Segmentierung des 2. Elters zur

Bildung der Kinder genutzt.

Kind 1 erbt die Segmentstruktur des ersten Elter und Kind 2 entsprechend.

Können dabei illegale Nachkommen entstehen?

Bei PPX nicht. Bei OX nur, wenn die Anwendung Reihenfolgen vorschreibt.

Für welche AK- od. Chromosomen-Typen sind diese Operatoren sinnvoll?

Typ 2 und je nach Aufgabenstellung auch Typ 3.

Warum nicht auch für AK- od. Chromosomen-Typ 1?

Weil die Operatoren bei diesem AK-Typ auch nicht mehr leisten als die Standard-XOs.

siehe Kap. 3



20



GLEAM – Aufbau - Plausibilitätstest und Genetic Repair

Genetic Repair:

Unzulässige Nachkommen können im Allgemeinen entstehen durch:

Änderungen von Entscheidungsvariablen oder Parametern:

Verletzung der Unter- bzw. Obergrenzen

bei GLEAM ausgeschlossen

Werte in unzulässigen Bereichen innerhalb der Definitionsgrenzen meist und auch bei GLEAM Sache der Bewertung

Mutationen zur Genverschiebung bei kombinatorischen Aufgaben entweder Sache der Bewertung oder Reparatur (Genetic Repair)

die allgemeinen Crossoveroperatoren entweder Sache der Bewertung oder Reparatur (GLEAM)

Problem bei der Reparatur:

Sinnvolle Änderungen können nicht auf mehrere Schritte verteilt werden,

wenn die Zwischenschritte zu unzulässigen Phänotypen führen.

Alternativen: Bestrafung unzulässiger Phänotypen, Phänotypische Reparatur




Genetic Repair (2):

Fall: Mutationsbedingte unzulässige Genreihenfolgen:

Lösungsalternativen:

1. Falsch positionierte Gene bis zu einer zulässigen Position verschieben:

(genotypische Reparatur)

in Richtung Chromosomenanfang (AK-Kopf)

in Richtung Chromosomenende (AK-Ende)

2. Bei der Interpretation so lange hinten an stellen, bis das Gen zulässig wird.

(phänotypische Reparatur)

Vor und Nachteile:

Verschiebung ergibt reihenfolge-korrektes Chromosom.

Verschiebung verhindert positive Änderungen über unzulässige Zwischenschritte.

Zurückgestellte Interpretation erlaubt es, positive Änderungen auf mehrere

unzulässige Zwischenschritte zu verteilen.

Zurückgestellte Interpretation belässt unkorrekten Genotyp.



21




Genetic Repair (3):

Fall: Zu viel oder zu wenig Gene auf Grund von Crossover:

(GLEAM: nur bei AK- od. Chromosomen-Typ 1 und 2 möglich)

Lösung:

Verschiebung überzähliger Gene auf das jeweils andere Kind

Beispiel:

a b c d e g f h i j l k r s t m n o q p Kopf Elter1: ▼

A B C D E G F H I J L K R S T M N O Q P Kopf Elter2: ▼

Kopf Kind1:

Kopf Kind2:

Kopf Kind1:

Kopf Kind2:

1-Punkt-Crossover ergibt:

Genetic Repair ergibt:

a b c d e g f J L K R S T M N O Q P

A B C D E G F H I h i j l k r s t m n o q p

a b c d e g f J L K R S T M N O Q P

A B C D E G F H I

h i

j l k r s t m n o q p




Übung:

n-Punkt-Crossover und anschließendes Genetic Repair, wobei folgende

Reihenfolge ausgewürfelt wird: 2 Segmente von E1, 1 von E2, 1 von E1,

2 von E2, 1 von E1

a b c d e g f h i j l k r s t m n o q p Kopf Elter1:

A B C D E G F H I J L K R S T M N O Q P Kopf Elter2:

Kopf Kind1:

Kopf Kind2:

Kopf Kind1:

Kopf Kind2:

n-Punkt-Crossover ergibt:

Genetic Repair ergibt:



22




Plausibilitätstest und Genetic Repair beim Aktionsmodell:

Durch genetische Operatoren können widersprüchliche Situationen bei den

Aktionen der allgemeinen Zeitsteuerung auftreten:

1. Unverändert-Aktion im Startblock:

Ist unzulässig und wird entfernt.

2. Geschachtelte Startblöcke:

Sind unzulässig und werden entfernt.

3. Unvollendete Startblöcke:

Sind unzulässig und

die überflüssige Block_Begin- bzw. Block_End-Aktion wird entfernt.




Plausibilitätstest und Genetic Repair beim Roboter-Aktionsmodell:

Spezielle Reparaturmaßnahmen für das Roboter-Aktionsmodell:

1. AK enthält keine Motor_an-Aktion

AK gilt als unplausibel und wird gelöscht.

2. Motor_aus-Aktion ohne vorherige entsprechende Motor_an-Aktion

Die Aktion gilt als unplausibel und wird entfernt.

3. Unverändert-Aktion ohne dass jemals zuvor Motoren angeschaltet wurden

Die Aktion gilt als unplausibel und wird entfernt.



23




Übung:

Führen Sie einen Plausibilitätstest mit Genetic Repair und Begründung bei folgender

AK durch und geben Sie an, was der Roboter in etwa machen wird:

Motor 1 an …

Motor 2 aus …

Block_End

Unverändert …

Block_Begin

Unverändert …

Motor 4 aus …

Motor 1 an …

Block_End

Motor 1 aus …

Unverändert …

Block_Begin

Block_Begin

Motor 3 aus …

Motor 1 an …

./. weil Motor 2 nicht an ist

./. unvollendeter Startblock

Unverändert …

Block_Begin

./. darf nicht im Startblock stehen


Motor 1 an …

Block_End

Motor 1 aus …

Unverändert …




2.Frage:

Der Roboter dreht sich

um seine Grundachse.



GLEAM – Aufbau - Bewertung

Bewertung basierend auf der kaskadierten gewichteten Summe:

1. Normierung der Bewertung der einzelnen Kriterien

Abbildung der Werteskala der Kriterien auf eine einheitliche Fitness-Skala: 0 .. fmax

Verwendung von 6 Standard-Normierungsfunktionen:

linear

exponentiell

gemischt linear und exponentiell

2. Prioritäten der Kriterien

Ein Kriterium gilt als erfüllt, wenn es seinen Erfüllungswert über- bzw. unterschreitet.

Alle Kriterien der gleichen Priorität n bilden eine Gruppe, die Prioritätsgruppe.

Wenn alle Kriterien einer Gruppe erfüllt sind, gilt die Gruppe als erfüllt.

Erst wenn die Prioritätsgruppe n erfüllt ist, zählen die Kriterien der Gruppe n+1 mit,

d.h. sie sind aktiv. Daher das Adjektiv kaskadiert im Namen.

3. Bildung der Summe aller aktiven Kriterien Rohfitness

4. Berechnung der Straffunktionen, soweit zutreffend Straffaktoren

5. Multiplikation der Rohfitness mit allen Straffaktoren Endfitness

0.1,0

jeweils steigend und fallend



24




Beispiel für den Einsatz von Normierungs- und Straffunktionen:

Situation: Die Temperatur soll möglichst gering sein und einen Maximalwert tmax nicht

überschreiten. Werte bis zu tok sind unproblematisch. Es gibt weitere Kriterien.

Lösung: Normierung im Bereich bis zu tmax mit einer linearen Funktion. Die

Fitnessunterschiede zwischen minimaler Temperatur und tok sind gering. Danach

starker Abfall bis zu einem noch akzeptablen Wert tgroß.

Bei Überschreitung von tmax wirkt folgende Straffunktion:

tmax tmin tgroß

fmax

Fit

ness

tok

Temperaturbewertung

tmax terreichbar

⅓

1.0

Str

aff

akto

r

Temperatur Temperatur

Offen, wie heiß es

werden kann ...

Warum eine Straffunktion und nicht nur Abwertung auf 0 ab tmax?

Damit es Wege aus dem verbotenen Bereich gibt, denen die Evolution folgen kann.




Prioritäten:

Ein Nachteil der gewichteten Summe besteht darin, dass sich Kriterien kompensieren

können, von denen man es gar nicht oder nur in einem bestimmten Ausmaß will. (Vergleichbar mit unerwünschten Teilen der Pareto-Front)

Dem wirkt eine geeignete Priorisierung der Kriterien entgegen:

Wert und Konkurrenzwert haben unterschiedliche Priorität: Wenn jetzt der Wert unter seinen Erfüllungswert absinkt, nützt das dem Konkurrenzwert

nichts.

Wert und Konkurrenzwert haben gleiche Priorität aber vergleichsweise geringes

Gewicht und es gibt weitere Kriterien mit geringerer Priorität: Wenn jetzt einer der beiden Werte unter seinen Erfüllungswert absinkt, fallen die anderen

höher gewichteten Kriterien aus der Bewertung heraus.

Eine Kompensation von Wert und Konkurrenzwert

ist nur oberhalb ihrer Erfüllungswerte zu erwarten.



25




Kaskadierte gewichtete Summe und Pareto-Front:

Am Beispiel von zwei zu maximierenden Kriterien f1 und f2 mit den

Gewichten w1 und w2, wobei Z die Menge zulässiger Lösungen sei:

Durch geeignete Gewichte

lässt sich jeder Punkt auf

einer konvexen Pareto-

Front annähern.

Dies gilt jedoch nicht für

nicht-konvexe Bereiche

der Pareto-Front. (Bereich zwischen A und B)

Wirkung des Erfüllungswerts

Ɛ2. Nur Lösungen mit f2 > Ɛ2

profitieren von besseren

f1 –Werten.

?




Kaskadierte gewichtete Summe und Pareto-Front:

Richtung des größten

Fitnessgewinns vor und

nach Überschreitung

von Ɛ2.

Festlegung eines Zielgebiets

bei bekannter Pareto-Front.

(Wiederholte Optimierung

ähnlicher Aufgabenstellungen)

Verteilung guter Lösungen vor vollständiger Konvergenz

bei Bewertung gemäß

kaskadierter gewichteter

Summe

Zielgebiet und Front bekannt.

(Wiederholte Optimierung

ähnlicher Aufgabenstellungen)

Pareto-Optimalität

Pareto-Front unbekannt.

(Neue Aufgabenstellung)



26




Vergleich von kaskadierter gewichteter Summe und Pareto-Front:

Optimierung einer neuen

Aufgabe

Wiederholte Optimierung von

Aufgabenvariationen

Pareto-

Optimalität

Abschätzung des Bereichs der

Kriterien (Einzel-Optimierungen)

Abschätzung der Pareto-Front

nachgelagerte menschliche

Entscheidung (max 4-5 Kriterien)

erheblich steigender Aufwand bei

Bestimmung der Front aufwändig und

unnötig, wenn der Zielbereich bekannt.

Pareto-Front nicht von Interesse

nachgelagerte Ergebnisauswahl

automatisiert möglich

steigender Anzahl an Kriterien

Kaskadierte

gewichtete

Summe

Abschätzung des Bereichs der

Kriterien (Einzel-Optimierungen)

keine Abschätzung der Pareto-Front

vorgelagerte menschliche

Entscheidung (Gewichte, Prio.)

mäßig steigender Aufwand bei

Vergleichsweise geringer Aufwand,

da Konzentration auf den Zielbereich

Pareto-Front nicht von Interesse

nachgelagerte Ergebnisauswahl nicht

erforderlich

steigender Anzahl an Kriterien

[Jak14]




Kriterien und Hilfskriterien:

Bewertungskriterien:

Ergeben sich aus der Aufgabenstellung (primäre Ziele).

Hilfskriterien:

sollen die Erreichung primärer Kriterien unterstützen:

z.B. Bessere Erreichung einer Senkung der Energiespitzen durch

Bewertung des Energiespitzenwertes

Bewertung der Anzahl aller Spitzen, die ein Limit überschreiten

Bewertung des Gesamtenergieverbrauchs aller

ein Limit überschreitenden Spitzen

Sollen übergeordneten Zielen dienen, z.B. dient die Bewertung der AK-Länge bei AKs vom Typ 3 zur

sanften Begrenzung der dynamischen AK-Länge oder

die Bewertung der Befehlsanzahl der Begrenzung des generierten und

abzuarbeitenden Roboterprogramms.

Beseitigung oder

Verkleinerung einer von

mehreren gleich

großen Spitzen

???



27



Akzeptanzregeln:

Der beste Nachkomme ersetzt das Elter gemäß einer der folgenden Regeln:

1. Akzeptiere immer (always) Akzeptiere immer den besten Nachkommen.

2. Akzeptiere immer, elitäre Strategie (always, ES) Akzeptiere den besten Nachkommen, wenn entweder das Elter nicht das Deme-Beste ist

oder der Nachkomme besser als sein Elter ist.

3. Lokal Schlechtestes (local least) Akzeptiere den besten Nachkommen, wenn er besser als das schlechteste Deme-Mitglied ist.

4. Lokal Schlechtestes, elitäre Strategie (local least, ES) Akzeptiere den besten Nachkommen, wenn er besser als das schlechteste Deme-Mitglied ist

UND wenn entweder das Elter nicht das Deme-Beste ist oder der Nachkomme besser als sein

Elter ist.

5. Elter-Verbesserung (better parent) Akzeptiere den besten Nachkommen, wenn er besser als das Elter ist.

Wie lautet die elitäre Variante von „better parent“?

GLEAM – Aufbau - Akzeptanz



GLEAM – Aufbau - Abbruchkriterien

Abbruchkriterien:

Stagnationsbezogene Abbruchkriterien:

(neben Zeit, Fitness oder Generationen, vgl. Kap. 3)

GDV

Generationen ohne Deme-Verbesserung ( = Verbesserung des Deme-Besten)

GAk

Generationen ohne Akzeptanz

Rücksetzen der Zähler bei Verbesserung des Deme-Besten oder bei Akzeptanz.

Welches Kriterium führt schneller zum Abbruch und ist damit schärfer?

GDV, da Verbesserungen eines Demes eher ausbleiben als die Akzeptanz im Deme.

Stagnation vs. Konvergenz:

Stagnation: Ausbleiben von Verbesserungen

Konvergenz: Genotypische Ähnlichkeit aller Individuen einer Population

Kann durch den Hammingabstand der Individuen bestimmt werden.

(aufwändig)



28



GLEAM – Vergleich mit der ES und den GAs

Vergleich:

Selektions- und Akzeptanzmechanismen orientieren sich eher an den GAs.

Das Nachbarschaftsmodell ist eine von den klassischen Formen unabhängige Erweiterung

der ursprünglichen panmiktischen Populationsmodelle.

Die zeitbezogene dynamische Interpretation (Aktionsmodell)

ist ein GLEAM-Spezifikum

ähnelt aber etwas den späteren Formen der Genetischen Programmierung (GP).

Codierung und Segmentierung sind GLEAM-Spezifika.

Natur: klassischer GA: GLEAM: ES:

Chromosom Bitstring Aktionskette Vektor

(Chromosom)

Zusammen Entscheidungs-

Gen interpretierter Aktion (Gen) variable

Teilbitstring

Locus/Allel Bit Parameter

(Basenpaar) (Entscheidungsvariable)


Studiengang Wirtschaftsinformatik K5_GLEAM.ppt 56 56 56

GLEAM – Das Wichtigste in Kürze

Anwendungsorientiertes Genmodell (mit Datentypen, Wertebereichen) F5, F6, F8

Segmentierung (der Evolution unterworfene Metastruktur für gen.Op.) F7, F30-38

Aktionsmodell (dynamische Interpretation) F9 – F16

Zeitbezug, getaktete Interpretation der Aktionen (Gene) F10, F15, F16

Aktionen zur Zeitsteuerung: Blockbildung und Unchanged F11 – F12

Achsbefehle und deren zeitbezogene Interpretation F14 – F16

Genetische Operatoren, Nachkommenserzeugung: F21 – F38

Mutationen ((relative) Parameteränderung von Genen/Segmenten) F22-F26, F30

Verschiebung von Aktionen/Segmenten, Segmentgrenzen; Inversion F26 – F33

Crossover: 1- und n-Punkt, Order-based Crossover (OX) F34-F36, F38

Genetic Repair: F39 – F44

Ursachen, Problematik und Alternativen, Repair bei Crossover F39 – F41

Plausibilitätstest und Repair beim Aktionsmodell F43 – F44

Bewertung: kaskadierte gew. Summe, Normierungs- und Straffunktionen, Pareto-Vergl. F46 – F52

Akzeptanzregeln: alle, besser als lokal schlechtestes / Elter, elitäre Varianten F53

Abbruchkriterien: Generationen ohne Deme-Verbesserung / Akzeptanz im Deme F54 Aus der leicht messbaren Stagnation wird auf die Konvergenz geschlossen.

EA-K6_GLEAM-IRob.ppt#1. GLEAM-Anwendung Roboterbahnplanung

Documents

GLEAM - General Learning and Evolutionary Algorithm and Methodjawi0001/EA-Vorlesung/PDF/K5_GLEAM_Handout_2... · Studiengang Wirtschaftsinformatik K5_GLEAM.ppt 4 ... Takt 0Start_Motor_2,