Genetische Algorithmen

Überblick• Worum geht es?

• Ablauf

• Beispiele

• Praxis

• Vor- und Nachteile

Was sind genetische Algorithmen?

• Optimierungs- bzw. Suchverfahren

• „Genetisch“ da Ähnlichkeit zur Evolution

• Optimierung endet bei erreichter Abbruchbedingung

Optimierungs- bzw Suchverfahren

• Fitnessfunktion (Maximieren oder Minimieren)

• Variablenabhängigkeit

• Lokales Maximum vs globales Maximum

Genetische Operatoren• Selektion

– Bewertung der Lösungswege anhand der Fitnessfunktion

Genetische Operatoren• Selektion

– Bewertung der Lösungswege anhand der Fitnessfunktion

• Mutation– Zufällige Veränderung der „Gene“

Genetische Operatoren• Selektion

– Bewertung der Lösungswege anhand der Fitnessfunktion

• Mutation– Zufällige Veränderung der „Gene“

• Kreuzung– Kombination mehrerer „geeigneter“ Kandidaten

Genetische Operatoren• Selektion

– Bewertung der Lösungswege anhand der Fitnessfunktion

• Mutation– Zufällige Veränderung der „Gene“

• Kreuzung– Kombination mehrerer „geeigneter“ Kandidaten

• Ähnlichkeit zur Biologie aber nicht gleichzusetzen!

Ablauf1. Vorbereitung

Ablauf1. Vorbereitung

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

Ablauf1. Vorbereitung

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

– Festlegung der Anfangspopulation sowie der Abbruchbedingung, Kreuzungs- und Mutationswahrscheinlichkeit

Ablauf1. Vorbereitung:

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

– Festlegung der Anfangspopulation sowie der Abbruchbedingung, Kreuzungs- und Mutationswahrscheinlichkeit

2. Güte der einzelnen Lösungsmöglichkeiten berechnen

Ablauf1. Vorbereitung:

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

– Festlegung der Anfangspopulation sowie der Abbruchbedingung, Kreuzungs- und Mutationswahrscheinlichkeit

2. Güte der einzelnen Lösungsmöglichkeiten berechnen

3. Selektion der zur Mutation und Kreuzung geeigneten Lösungen

Ablauf1. Vorbereitung:

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

– Festlegung der Anfangspopulation sowie der Abbruchbedingung, Kreuzungs- und Mutationswahrscheinlichkeit

2. Güte der einzelnen Lösungsmöglichkeiten berechnen

3. Selektion der zur Mutation und Kreuzung geeigneten Lösungen

4. Genetische Operatoren ausführen bis Anzahl der Kinderpopulation der Elternpopulation entspricht

Ablauf1. Vorbereitung:

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

– Festlegung der Anfangspopulation sowie der Abbruchbedingung, Kreuzungs- und Mutationswahrscheinlichkeit

2. Güte der einzelnen Lösungsmöglichkeiten berechnen

3. Selektion der zur Mutation und Kreuzung geeigneten Lösungen

4. Genetische Operatoren ausführen bis Anzahl der Kinderpopulation der Elternpopulation entspricht

5. Kinderpopulation ersetzt Elternpopulation

Ablauf1. Vorbereitung:

– Analyse des Problems und Erstellung der Zielfunktion (Variablenabhängigkeit)

– Festlegung der Anfangspopulation sowie der Abbruchbedingung, Kreuzungs- und Mutationswahrscheinlichkeit

2. Güte der einzelnen Lösungsmöglichkeiten berechnen

3. Selektion der zur Mutation und Kreuzung geeigneten Lösungen

4. Genetische Operatoren ausführen bis Anzahl der Kinderpopulation der Elternpopulation entspricht

5. Kinderpopulation ersetzt Elternpopulation– Wiederholung ab Punkt 2 bis Abbruchbedingung erfüllt

Verkehrsbeispiel(Theorie)

Verkehrsbeispiel1. Zielfunktion soll benötigte Zeit vom Startpunkt über die

Zwischenstationen zum Zielort darstellen

Verkehrsbeispiel1. Zielfunktion soll benötigte Zeit vom Startpunkt über die

Zwischenstationen zum Zielort darstellen– Variablen (Durchschnittliche Auslastung der Straße, zulässige

Höchstgeschwindigkeit, Baustellen, Ampeln...)

Verkehrsbeispiel1. Zielfunktion soll benötigte Zeit vom Startpunkt über die

Zwischenstationen zum Zielort darstellen– Variablen (Durchschnittliche Auslastung der Straße, zulässige

Höchstgeschwindigkeit, Baustellen, Ampeln...)

– Anfangspopulation der Lösungswege, Kreuzungs- und Mutationswahrscheinlichkeit festlegen

Verkehrsbeispiel1. Zielfunktion soll benötigte Zeit vom Startpunkt über die

Zwischenstationen zum Zielort darstellen– Variablen (Durchschnittliche Auslastung der Straße, zulässige

Höchstgeschwindigkeit, Baustellen, Ampeln...)

– Anfangspopulation der Lösungswege, Kreuzungs- und Mutationswahrscheinlichkeit festlegen

– Abbruchbedingung: Entweder wenn Ziel unterhalb einer Stunde erreicht wird oder wenn die 5 Generation gebildet wurde

Verkehrsbeispiel1. Zielfunktion soll benötigte Zeit vom Startpunkt über die

Zwischenstationen zum Zielort darstellen– Variablen (Durchschnittliche Auslastung der Straße, zulässige

Höchstgeschwindigkeit, Baustellen, Ampeln...)

– Anfangspopulation der Lösungswege, Kreuzungs- und Mutationswahrscheinlichkeit festlegen

– Abbruchbedingung: Entweder wenn Ziel unterhalb einer Stunde erreicht wird oder wenn die 5 Generation gebildet wurde

2. Güte der einzelnen Lösungen berechnen und selektieren

Verkehrsbeispiel1. Zielfunktion soll benötigte Zeit vom Startpunkt über die

Zwischenstationen zum Zielort darstellen– Variablen (Durchschnittliche Auslastung der Straße, zulässige

Höchstgeschwindigkeit, Baustellen, Ampeln...)

– Anfangspopulation der Lösungswege, Kreuzungs- und Mutationswahrscheinlichkeit festlegen

– Abbruchbedingung: Entweder wenn Ziel unterhalb einer Stunde erreicht wird oder wenn die 5 Generation gebildet wurde

2. Güte der einzelnen Lösungen berechnen und selektieren

3. Genetische Operationen ausführen

Wikipedia Beispiel

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

– Genom des Individums (Lösungsweg) besteht aus den Variablen

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

– Genom des Individums (Lösungsweg) besteht aus den Variablen

– Minimierung als Ziel

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

– Genom des Individums (Lösungsweg) besteht aus den Variablen

– Minimierung als Ziel

• Kreuzung geschieht mit zwei zufällig ausgewählten Genomen der Elterngeneration

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

– Genom des Individums (Lösungsweg) besteht aus den Variablen

– Minimierung als Ziel

• Kreuzung geschieht mit zwei zufällig ausgewählten Genomen der Elterngeneration

– p {0, 1, 2, 3, 4} wird zufällig gewählt ∈

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

– Genom des Individums (Lösungsweg) besteht aus den Variablen

– Minimierung als Ziel

• Kreuzung geschieht mit zwei zufällig ausgewählten Genomen der Elterngeneration

– p {0, 1, 2, 3, 4} wird zufällig gewählt ∈– Kindgenom wird aus Elterngenomen zusammengesetzt, wobei die

p vorderen Elemente vom ersten und die 5-p hinteren Elemente des zweiten Elterngenoms verwendet werden

Wikipedia Beispiel• Fitnessfunktion f(a,b,c,d,e)=|a-b|+|b-c|+|c-d|+|d-e|+|e-a|

– Wobei a,b,c,d,e Variablen der Fitnessfunktion

– Genom des Individums (Lösungsweg) besteht aus den Variablen

– Minimierung als Ziel

• Kreuzung geschieht mit zwei zufällig ausgewählten Genomen der Elterngeneration

– p {0, 1, 2, 3, 4} wird zufällig gewählt ∈– Kindgenom wird aus Elterngenomen zusammengesetzt, wobei die

p vorderen Elemente vom ersten und die 5-p hinteren Elemente des zweiten Elterngenoms verwendet werden

– G‘ = (23, 33, 11, -9, -8) und G‘‘ = (44, 12, -48, -2, 29) und p=2 dann ist das Kind G = (23, 33, -48, -2, -29)

Wikipedia Beispiel• Mutation ist für jede Position p {0, 1, 2, 3, 4} im Genom ∈

eine Addition an dieser Position um q {-1, 0, 1}∈– Pro Generation und Position besteht eine 1% Wahrscheinlichkeit

auf Mutation

Wikipedia Beispiel• Mutation ist für jede Position p {0, 1, 2, 3, 4} im Genom ∈

eine Addition an dieser Position um q {-1, 0, 1}∈– Pro Generation und Position besteht eine 1% Wahrscheinlichkeit

auf Mutation

• Selektion nimmt beste Ergebnisse aus Eltern und Kindpopulation (Anzahl der Ausgangspopulation muss erhalten bleiben)

Wikipedia Beispiel• Mutation ist für jede Position p {0, 1, 2, 3, 4} im Genom ∈

eine Addition an dieser Position um q {-1, 0, 1}∈– Pro Generation und Position besteht eine 1% Wahrscheinlichkeit

auf Mutation

• Selektion nimmt beste Ergebnisse aus Eltern und Kindpopulation (Anzahl der Ausgangspopulation muss erhalten bleiben)

• Startpopulation 50– Jedes Gen erhält zufälligen Wert zwischen –50 und 50

Wikipedia Beispiel• Mutation ist für jede Position p {0, 1, 2, 3, 4} im Genom ∈

eine Addition an dieser Position um q {-1, 0, 1}∈– Pro Generation und Position besteht eine 1% Wahrscheinlichkeit

auf Mutation

• Selektion nimmt beste Ergebnisse aus Eltern und Kindpopulation (Anzahl der Ausgangspopulation muss erhalten bleiben)

• Startpopulation 50– Jedes Gen erhält zufälligen Wert zwischen –50 und 50

• Abbruchbeding: Durchschnittliche Fitness hat sich über 10 Generationen nicht verändert

Wikipedia Beispiel• Mutation ist für jede Position p {0, 1, 2, 3, 4} im Genom ∈

eine Addition an dieser Position um q {-1, 0, 1}∈– Pro Generation und Position besteht eine 1% Wahrscheinlichkeit

auf Mutation

• Selektion nimmt beste Ergebnisse aus Eltern und Kindpopulation (Anzahl der Ausgangspopulation muss erhalten bleiben)

• Startpopulation 50– Jedes Gen erhält zufälligen Wert zwischen –50 und 50

• Abbruchbeding: Durchschnittliche Fitness hat sich über 10 Generationen nicht verändert

• Genom mit dem Besten Ergebnis der Endpopulation ist Ergebnis

Wikipedia Beispiel• Behauptung:

– Nach etwa 70 Generationen lautet das Ergebnis a=b=c=d=e

– Es kann viele gleichwertige Lösungen geben z.B. (4,4,4,4,4) / (-21,-21,-21,-21,-21)...

– Das Ergebnis ist in diesem Fall eine optimale Lösung

Wikipedia Beispiel• Behauptung:

– Nach etwa 70 Generationen lautet das Ergebnis a=b=c=d=e

– Es kann viele gleichwertige Lösungen geben z.B. (4,4,4,4,4) / (-21,-21,-21,-21,-21)...

– Das Ergebnis ist in diesem Fall eine optimale Lösung

• Überprüfung:– 70 Generationen kann so nicht bestätigt werden, da sehr

abhängig von der Entwicklung der Genome

– Abbruchbedingung nicht optimal gewählt (Spielraum)

– Generell konnte die Annahme bestästigt werden

Vor- und Nachteile• Genetische Algorithmen ermöglichen Problem-

lösungen für komplexe Aufgabenstellungen zu finden

Vor- und Nachteile• Genetische Algorithmen ermöglichen Problem-

lösungen für komplexe Aufgabenstellungen zu finden

• Parallele Suche in einer Menge von möglichen Lösungen

Vor- und Nachteile• Genetische Algorithmen ermöglichen Problem-

lösungen für komplexe Aufgabenstellungen zu finden

• Parallele Suche in einer Menge von möglichen Lösungen

• Nichtlineare Probleme können gelöst werden

Vor- und Nachteile• Genetische Algorithmen ermöglichen Problem-

lösungen für komplexe Aufgabenstellungen zu finden

• Parallele Suche in einer Menge von möglichen Lösungen

• Nichtlineare Probleme können gelöst werden• Keine Garantie auf optimale Lösung

Vor- und Nachteile• Genetische Algorithmen ermöglichen Problem-

lösungen für komplexe Aufgabenstellungen zu finden

• Parallele Suche in einer Menge von möglichen Lösungen

• Nichtlineare Probleme können gelöst werden• Keine Garantie auf optimale Lösung• Gegebenenfalls großer Rechenbedarf

?