Projekt zur Künstlichen Intelligenz - Exam

Aufgabe 1)

Gegeben sei ein neuronales Netzwerk mit der folgenden Architektur:

• Eine Eingabeschicht mit 10 Neuronen
• Zwei versteckte Schichten: die erste mit 20 Neuronen und ReLU-Aktivierungsfunktion, die zweite mit 15 Neuronen und Sigmoid-Aktivierungsfunktion
• Eine Ausgabeschicht mit 1 Neuron und einer Tanh-Aktivierungsfunktion

Dieses Netzwerk soll zur Vorhersage von Hauspreisen eingesetzt werden, basierend auf einem Datensatz mit verschiedenen Merkmalen wie Quadratmeterzahl, Baujahr, Anzahl der Zimmer, etc.

a)

a) Beschreibe das Backpropagation-Verfahren für das gegebene neuronale Netzwerk im Detail und gib die mathematischen Formeln für die Anpassung der Gewichte in den versteckten Schichten an.

Hinweis: Verwende die allgemein gebräuchliche Mean Squared Error (MSE) Loss-Funktion. Gehe dabei auf die Ableitungen ein und wie die Gewichtsaktualisierungen konkret aussehen.

Lösung:

Zunächst einmal möchte ich das Backpropagation-Verfahren im Zusammenhang mit einem neuronalen Netzwerk erläutern. Das gegebene Netzwerk hat die folgende Architektur:

• Eine Eingabeschicht mit 10 Neuronen
• Zwei versteckte Schichten: die erste mit 20 Neuronen und ReLU-Aktivierungsfunktion, die zweite mit 15 Neuronen und Sigmoid-Aktivierungsfunktion
• Eine Ausgabeschicht mit 1 Neuron und einer Tanh-Aktivierungsfunktion

Das Ziel dieses Netzwerks ist es, Hauspreise vorherzusagen. Das Backpropagation-Verfahren dient dazu, durch Anpassung der Gewichte den Fehler zwischen den vorhergesagten Werten und den tatsächlichen Werten zu minimieren. Als Verlustfunktion verwenden wir die Mean Squared Error (MSE) Loss-Funktion.

Sehen wir uns die Schritte des Backpropagation-Verfahrens im Detail an:

• 1. Vorwärtsdurchlauf: Die Eingaben werden durch das Netzwerk propagiert, um die Vorhersage zu berechnen.
• 2. Fehlerberechnung: Der Fehler wird mittels der MSE-Loss-Funktion berechnet. Diese ist definiert als

\[ \text{MSE} = \frac{1}{n} \sum_{i=1}^{n} (y_{\text{true}, i} - y_{\text{pred}, i})^2 \]

, wobei n die Anzahl der Datenpunkte ist, \( y_{\text{true}, i} \) die tatsächlichen Werte und \( y_{\text{pred}, i} \) die vorhergesagten Werte sind.

• 3. Fehler Rückpropagieren: Der Fehler wird nun rückwärts durch das Netzwerk propagiert, um die Gradienten der Gewichte zu berechnen. Dies geschieht durch Anwendung der Kettenregel.
• 4. Gewichtsaktualisierung: Die Gewichte werden angepasst, um den Fehler zu minimieren, wobei der Gradient Descent Algorithmus verwendet wird. Die Gewichtsaktualisierung erfolgt durch die folgende Formel:

Die Gewichtsanpassungen können wie folgt mathematisch dargestellt werden:

• Für die Ausgabeschicht:

\[ W_{\text{out}} = W_{\text{out}} - \beta \frac{\partial L}{\partial W_{\text{out}}} \]

Die Ableitung der Verlustfunktion \( L \) bezüglich der Gewichte \( W_{\text{out}} \) wird durch die Kettenregel berechnet:

\[ \frac{\partial L}{\partial W_{\text{out}}} = \frac{\partial L}{\partial a_{\text{out}}} \frac{\partial a_{\text{out}}}{\partial z_{\text{out}}} \frac{\partial z_{\text{out}}}{\partial W_{\text{out}}} \]

Die einzelnen Teile dieser Ableitung sind:

\[ \frac{\partial L}{\partial a_{\text{out}}} = 2 (a_{\text{out}} - y_{\text{true}}) \]

\[ \frac{\partial a_{\text{out}}}{\partial z_{\text{out}}} = 1 - (a_{\text{out}})^2 \]

und

\[ \frac{\partial z_{\text{out}}}{\partial W_{\text{out}}} = a_{\text{hidden2}} \]

Somit ergibt sich:

\[ \frac{\partial L}{\partial W_{\text{out}}} = 2 (a_{\text{out}} - y_{\text{true}}) (1 - (a_{\text{out}})^2) a_{\text{hidden2}} \]

Die Gewichtsanpassung erfolgt daher durch:

\[ W_{\text{out}} = W_{\text{out}} - \beta \cdot 2 (a_{\text{out}} - y_{\text{true}}) (1 - (a_{\text{out}})^2) a_{\text{hidden2}} \]

• Für die zweite versteckte Schicht (15 Neuronen, Sigmoid):

Bei der zweiten versteckten Schicht werden die Ableitungen wie folgt berechnet:

\[ W_{\text{hidden2}} = W_{\text{hidden2}} - \beta \frac{\partial L}{\partial W_{\text{hidden2}}} \]

Die Ableitung der Verlustfunktion \( L \) bezüglich der Gewichte \( W_{\text{hidden2}} \) lautet:

\[ \frac{\partial L}{\partial W_{\text{hidden2}}} = \frac{\partial L}{\partial a_{\text{out}}} \frac{\partial a_{\text{out}}}{\partial z_{\text{out}}} \frac{\partial z_{\text{out}}}{\partial a_{\text{hidden2}}} \frac{\partial a_{\text{hidden2}}}{\partial z_{\text{hidden2}}} \frac{\partial z_{\text{hidden2}}}{\partial W_{\text{hidden2}}} \]

Die einzelnen Teile dieser Ableitung sind:

\[ \frac{\partial L}{\partial a_{\text{out}}} = 2 (a_{\text{out}} - y_{\text{true}}) \]

\[ \frac{\partial a_{\text{out}}}{\partial z_{\text{out}}} = 1 - (a_{\text{out}})^2 \]

\[ \frac{\partial z_{\text{out}}}{\partial a_{\text{hidden2}}} = W_{\text{out}} \]

\[ \frac{\partial a_{\text{hidden2}}}{\partial z_{\text{hidden2}}} = a_{\text{hidden2}} (1 - a_{\text{hidden2}}) \]

und

\[ \frac{\partial z_{\text{hidden2}}}{\partial W_{\text{hidden2}}} = a_{\text{hidden1}} \]

Somit ergibt sich:

\[ \frac{\partial L}{\partial W_{\text{hidden2}}} = 2 (a_{\text{out}} - y_{\text{true}}) (1 - (a_{\text{out}})^2) W_{\text{out}} a_{\text{hidden2}} (1 - a_{\text{hidden2}}) a_{\text{hidden1}} \]

Die Gewichtsanpassung lautet:

\[ W_{\text{hidden2}} = W_{\text{hidden2}} - \beta \cdot 2 (a_{\text{out}} - y_{\text{true}}) (1 - (a_{\text{out}})^2) W_{\text{out}} a_{\text{hidden2}} (1 - a_{\text{hidden2}}) a_{\text{hidden1}} \]

• Für die erste versteckte Schicht (20 Neuronen, ReLU):

Berechnung der Ableitungen für die erste versteckte Schicht erfolgt wie folgt:

\[ W_{\text{hidden1}} = W_{\text{hidden1}} - \beta \frac{\partial L}{\partial W_{\text{hidden1}}} \]

Die Ableitung der Verlustfunktion \( L \) bezüglich der Gewichte \( W_{\text{hidden1}} \) lautet:

\[ \frac{\partial L}{\partial W_{\text{hidden1}}} = \frac{\partial L}{\partial a_{\text{out}}} \frac{\partial a_{\text{out}}}{\partial z_{\text{out}}} \frac{\partial z_{\text{out}}}{\partial a_{\text{hidden2}}} \frac{\partial a_{\text{hidden2}}}{\partial z_{\text{hidden2}}} \frac{\partial z_{\text{hidden2}}}{\partial a_{\text{hidden1}}} \frac{\partial a_{\text{hidden1}}}{\partial z_{\text{hidden1}}} \frac{\partial z_{\text{hidden1}}}{\partial W_{\text{hidden1}}} \]

Die einzelnen Teile dieser Ableitung sind:

\[ \frac{\partial L}{\partial a_{\text{out}}} = 2 (a_{\text{out}} - y_{\text{true}}) \]

\[ \frac{\partial a_{\text{out}}}{\partial z_{\text{out}}} = 1 - (a_{\text{out}})^2 \]

\[ \frac{\partial z_{\text{out}}}{\partial a_{\text{hidden2}}} = W_{\text{out}} \]

\[ \frac{\partial a_{\text{hidden2}}}{\partial z_{\text{hidden2}}} = a_{\text{hidden2}} (1 - a_{\text{hidden2}}) \]

\[ \frac{\partial z_{\text{hidden2}}}{\partial a_{\text{hidden1}}} = W_{\text{hidden2}} \]

\[ \frac{\partial a_{\text{hidden1}}}{\partial z_{\text{hidden1}}} = \text{ReLU}'(z_{\text{hidden1}}) \]

und

\[ \frac{\partial z_{\text{hidden1}}}{\partial W_{\text{hidden1}}} = a_{\text{input}} \]

Die Ableitung der ReLU-Funktion ist definiert als:

\[ \text{ReLU}'(x) = \begin{cases} 1 & \text{falls } x > 0 \ 0 & \text{falls } x \leq 0 \end{cases} \]

Somit ergibt sich:

\[ \frac{\partial L}{\partial W_{\text{hidden1}}} = 2 (a_{\text{out}} - y_{\text{true}}) (1 - (a_{\text{out}})^2) W_{\text{out}} a_{\text{hidden2}} (1 - a_{\text{hidden2}}) W_{\text{hidden2}} \text{ReLU}'(z_{\text{hidden1}}) a_{\text{input}} \]

Die Gewichtsanpassung lautet:

\[ W_{\text{hidden1}} = W_{\text{hidden1}} - \beta \cdot 2 (a_{\text{out}} - y_{\text{true}}) (1 - (a_{\text{out}})^2) W_{\text{out}} a_{\text{hidden2}} (1 - a_{\text{hidden2}}) W_{\text{hidden2}} \text{ReLU}'(z_{\text{hidden1}}) a_{\text{input}} \]

Zusammengefasst ermöglicht das beschriebene Backpropagation-Verfahren die Berechnung der Gradienten und anschließende Anpassung der Gewichte, um den Fehler zu minimieren. Dies erfolgt schrittweise, wobei das Netzwerk darauf trainiert wird, immer bessere Vorhersagen zu liefern. Die Lernrate \( \beta \) bestimmt dabei die Größe der Anpassungsschritte.

b)

b) Nehmen wir an, dass das Modell Overfitting zeigt. Schlage zwei verschiedene Methoden zur Reduzierung des Overfittings vor und erläutere, wie diese Methoden in das gegebene Netzwerk integriert werden könnten.

Diskutiere die Vor- und Nachteile jeder Methode in Bezug auf dieses spezifische Problem der Hauspreisschätzung.

Lösung:

Overfitting tritt auf, wenn ein Modell so gut auf den Trainingsdaten performt, dass es spezifische Muster und Rauschen der Trainingsdaten lernt, die nicht verallgemeinerbar sind. Dadurch wird die Leistung des Modells auf neuen, ungesehenen Daten beeinträchtigt. Um Overfitting zu vermeiden, können wir zwei verschiedene Methoden anwenden: Regularisierung und Dropout.

• 1. Regularisierung:

Regularisierung fügt einen Strafterm zur Verlustfunktion hinzu, um sicherzustellen, dass die Gewichte des Modells nicht zu groß werden. Dadurch wird das Modell gezwungen, einfachere, verallgemeinerbare Beziehungen zu lernen. Es gibt verschiedene Arten von Regularisierung, die am häufigsten verwendeten sind L1- und L2-Regularisierung.

L2-Regularisierung (Ridge Regression): Bei der L2-Regularisierung wird ein Strafterm hinzugefügt, der proportional zur Summe der Quadrate der Gewichte ist:

\[ L_{\text{neu}} = L + \frac{\lambda}{2} \sum_{i} W_{i}^2 \]

wobei \( L \) die ursprüngliche Verlustfunktion (z. B. Mean Squared Error), \( W_{i} \) die Gewichte und \( \lambda \) der Regularisierungsparameter ist.

Integrierung in das Netzwerk: Füge den Regularisierungsterm zur Verlustfunktion hinzu und passe die Backpropagation entsprechend an, um die Gewichte zu aktualisieren, wobei sowohl der Gradient der ursprünglichen Verlustfunktion als auch der Gradient des Regularisierungsterms berücksichtigt werden.

Vorteile:

• Einfach zu implementieren
• Effektiv bei der Reduzierung von Overfitting

Nachteile:

• Erfordert sorgfältige Auswahl des Regularisierungsparameters \( \lambda \)
• Kann die Trainingszeit erhöhen

• 2. Dropout:

Dropout ist eine Technik, bei der in jeder Trainingsiteration zufällig Neuronen deaktiviert werden (d. h. ihre Aktivitäten werden auf null gesetzt). Dies verhindert, dass bestimmte Neuronen zu stark dominieren und zwingt das Netzwerk, robustere Merkmale zu lernen.

Integrierung in das Netzwerk: Füge Dropout-Schichten nach den versteckten Schichten hinzu. Während des Trainings wird in jeder Iteration ein bestimmter Prozentsatz der Neuronen zufällig deaktiviert. Während der Vorhersage (d. h. bei der Evaluierung oder Testen) werden keine Neuronen deaktiviert, aber die Ausgabe wird entsprechend skaliert, um den Effekt der Dropout-Schichten zu berücksichtigen.

\[ a'_{i} = \frac{a_{i}}{1 - p} \]

Hier ist \( a'_{i} \) der Skalar der Ausgabe während des Vorhersagemodus, \( a_{i} \) die Aktivierung ohne Dropout und \( p \) die Dropout-Rate.

Vorteile:

• Effektiv bei der Reduzierung von Overfitting
• Erhöht die Robustheit des Modells

Nachteile:

• Erhöht die Trainingszeit
• Erfordert sorgfältige Auswahl der Dropout-Rate

Fazit: Beide Methoden, Regularisierung und Dropout, sind effektive Strategien zur Vermeidung von Overfitting und können in das gegebene neuronale Netzwerk integriert werden. Regularisierung ist einfacher zu implementieren und kann durch eine Anpassung der Verlustfunktion erreicht werden. Dropout benötigt die Einführung neuer Schichten und erhöht die Trainingskomplexität, jedoch kann es die Robustheit des Modells erheblich verbessern. Für die Vorhersage von Hauspreisen können beide Methoden helfen, das Modell zu verallgemeinern und die Leistung auf ungesehenen Daten zu verbessern.

Aufgabe 2)

Genetische AlgorithmenKombinatorische Optimierungsverfahren, die Prinzipien der natürlichen Evolution nachahmen.

• Initialisierung: Erzeugung einer zufälligen Population von Individuen.
• Eignungsbewertung: Bewertung jedes Individuums anhand einer Fitnessfunktion.
• Selektion: Auswahl der besten Individuen zur Reproduktion.
• Kreuzung (Crossover): Kombination zweier Individuen zur Erzeugung neuer Nachkommen.
• Mutation: Zufällige Änderungen an Nachkommen zur Einführung von Variabilität.
• Iteration: Wiederholung des Prozesses über mehrere Generationen zur Optimierung der Lösungen.
• Terminierung: Der Algorithmus stoppt nach einer festen Anzahl von Generationen oder wenn eine optimale Lösung gefunden wurde.

a)

Beschreibe detailliert den Prozess der Initialisierung in einem genetischen Algorithmus. Achte darauf zu erklären, wie eine anfängliche Population erstellt wird und warum diese zufällig gewählt wird.

Lösung:

Genetische Algorithmen: InitialisierungDie Initialisierung ist der erste Schritt eines genetischen Algorithmus und spielt eine wesentliche Rolle für den Erfolg der gesamten Optimierung. In diesem Schritt wird eine anfängliche Population von Individuen erzeugt. Hier ist eine detaillierte Beschreibung des Prozesses:

• Erzeugung der anfänglichen Population: Die Initialisierung beginnt mit der Erstellung einer Population von Individuen. Ein Individuum in diesem Kontext repräsentiert eine mögliche Lösung für das zu optimierende Problem. Das kann durch verschiedene Darstellungsformen geschehen, wie beispielsweise binäre Vektoren, Permutationen oder reale Zahlen.
• Zufällige Auswahl: Die Individuen der anfänglichen Population werden zufällig erzeugt. Diese Zufälligkeit ist entscheidend, um eine breite Vielfalt an Lösungen sicherzustellen. Eine diverse Anfangspopulation erhöht die Wahrscheinlichkeit, verschiedene Bereiche des Lösungsraums zu erkunden und somit eine bessere Optimierung zu erreichen.
• Größe der Population: Die Anzahl der Individuen in der anfänglichen Population wird als Populationsgröße bezeichnet. Diese Größe wird vorher festgelegt und kann je nach Anforderungen und Ressourcen variieren. Eine größere Population kann zu besseren Lösungen führen, benötigt jedoch auch mehr Rechenressourcen.
• Warum zufällig wählen?
  • Vielfalt: Eine zufällige Population stellt sicher, dass der Algorithmus eine breite Basis an Lösungsmöglichkeiten hat. Dadurch werden viele verschiedene Bereiche des Lösungsraums abgesucht, was die Chancen erhöht, globale Optima zu finden.
  • Vermeidung von Vorurteilen: Durch die Zufälligkeit wird vermieden, dass der Algorithmus von Anfang an in eine bestimmte Richtung gelenkt wird, was zu einer voreiligen Konvergenz zu suboptimalen Lösungen führen könnte.
  • Diversität: Zufällige Initialisierung begünstigt eine hohe genetische Diversität, was wichtig ist, um die Evolution des Algorithmus über viele Generationen hinweg robust zu gestalten.

Die Initialisierung legt den Grundstein für den gesamten Optimierungsprozess des genetischen Algorithmus. Eine gut ausgewählte und vielfältige Anfangspopulation erhöht die Wahrscheinlichkeit, dass der Algorithmus effizient und effektiv optimale Lösungen findet.

b)

Gegeben sei eine Fitnessfunktion \[f(x) = x^2\] und eine Population von Individuen \[A = \{1, -3, 2, 4, -2\}\]. Berechne die Fitnesswerte der Individuen und erkläre den Selektionsprozess, der angewendet werden könnte, um die besten Individuen auszuwählen.

Lösung:

Fitnessbewertung und Selektion bei Genetischen AlgorithmenGegeben sei eine Fitnessfunktion \(f(x) = x^2\) und eine Population von Individuen \(A = \{1, -3, 2, 4, -2\}\). Der erste Schritt besteht darin, die Fitnesswerte der einzelnen Individuen zu berechnen.

• Berechnung der Fitnesswerte:Wenden wir die Fitnessfunktion \(f(x) = x^2\) auf jedes Individuum der Population an:
  • Fitness von 1: \(f(1) = 1^2 = 1\)
  • Fitness von -3: \(f(-3) = (-3)^2 = 9\)
  • Fitness von 2: \(f(2) = 2^2 = 4\)
  • Fitness von 4: \(f(4) = 4^2 = 16\)
  • Fitness von -2: \(f(-2) = (-2)^2 = 4\)
• Ergebnis:Die Fitnesswerte der Individuen lauten:
  • 1: 1
  • -3: 9
  • 2: 4
  • 4: 16
  • -2: 4
• Selektionsprozess: Es gibt verschiedene Methoden, um die besten Individuen auszuwählen. Hier sind einige gängige Methoden:
  • Roulette-Rad-Selektion (Proportionale Selektion):Jedes Individuum wird mit einer Wahrscheinlichkeit ausgewählt, die proportional zu seinem Fitnesswert ist. Das bedeutet, dass Individuen mit höheren Fitnesswerten eine größere Chance haben, ausgewählt zu werden. Um dies zu veranschaulichen, kann man sich ein Roulette-Rad vorstellen, bei dem Segmente entsprechend den Fitnesswerten gewichtet sind.
  • Turnierselektion: Eine zufällige Untermenge von Individuen wird ausgewählt, und das Individuum mit der höchsten Fitness in dieser Gruppe wird ausgewählt. Dieser Prozess wird wiederholt, bis die gewünschte Anzahl von Individuen ausgewählt wurde.
  • Elitenselektion: Die besten \(n\) Individuen werden direkt in die nächste Generation übernommen. Diese Methode stellt sicher, dass die besten Lösungen nicht verloren gehen.
  • Rangbasierte Selektion: Individuen werden nach ihrer Fitness geordnet und erhalten selektive Wahrscheinlichkeiten basierend auf ihrem Rang, nicht ihrer absoluten Fitness. Dies vermeidet das Problem der zu starken Bevorzugung weniger sehr guter Individuen.

Für das gegebene Beispiel unter Verwendung der **Roulette-Rad-Selektion**:

• Summe der Fitnesswerte: \(1 + 9 + 4 + 16 + 4 = 34\)
• Wahrscheinlichkeiten:
  • 1: \(1 / 34\)
  • -3: \(9 / 34\)
  • 2: \(4 / 34\)
  • 4: \(16 / 34\)
  • -2: \(4 / 34\)

Individuen mit höheren Fitnesswerten haben eine höhere Selektionswahrscheinlichkeit, was zur Optimierung der Lösungen über nachfolgende Generationen beiträgt.

c)

Beschreibe den Kreuzungsprozess (Crossover) für genetische Algorithmen. Benutze ein konkretes Beispiel mit zwei Elternsequenzen (z.B. \([1, 0, 1, 1, 0]\) und \([0, 1, 0, 0, 1]\)) um zu zeigen, wie neue Nachkommen erzeugt werden.

Lösung:

Kreuzungsprozess (Crossover) bei Genetischen AlgorithmenDer Kreuzungsprozess, auch als Crossover bekannt, ist ein grundlegender Mechanismus in genetischen Algorithmen, der dafür sorgt, dass neue Nachkommen durch die Kombination von Teilen zweier Elternsequenzen erzeugt werden. Dies emuliert das biologische Konzept der genetischen Reproduktion und rekombiniert Gene, um die Variabilität in der Population zu erhöhen.Es gibt verschiedene Arten von Crossover-Methoden, beispielsweise der Ein-Punkt-Crossover, Zwei-Punkt-Crossover und der Uniform-Crossover. Hier wird der Ein-Punkt-Crossover detailliert erläutert.

• Ein-Punkt-Crossover:Beim Ein-Punkt-Crossover wird ein Trennungspunkt (Crossover-Punkt) zufällig innerhalb der Elternsequenzen ausgewählt. Dieser Punkt bestimmt, wo die Sequenzen der Eltern geschnitten und rekombiniert werden.Gegeben sei ein konkretes Beispiel mit zwei Elternsequenzen:
  • Elternsequenz 1: \[1, 0, 1, 1, 0\]
  • Elternsequenz 2: \[0, 1, 0, 0, 1\]
• Schritt-für-Schritt-Anleitung:
  • Wähle zufällig einen Crossover-Punkt. Angenommen, der Crossover-Punkt ist nach dem dritten Gen.
  • Teile beide Elternsequenzen an der Crossover-Stelle:
    • Eltern 1: \[1, 0, 1 | 1, 0\]
    • Eltern 2: \[0, 1, 0 | 0, 1\]
  • Kombiniere die Teile der Elternsequenzen, um die Nachkommen zu erzeugen:
    • Nachkomme 1: \[1, 0, 1 | 0, 1\] => \[1, 0, 1, 0, 1\]
    • Nachkomme 2: \[0, 1, 0 | 1, 0\] => \[0, 1, 0, 1, 0\]
• Ergebnis:Die durch Ein-Punkt-Crossover erzeugten Nachkommen sind:
  • Nachkomme 1: \[1, 0, 1, 0, 1\]
  • Nachkomme 2: \[0, 1, 0, 1, 0\]
  Durch diesen Prozess entstehen neue Lösungen (Nachkommen) mit Eigenschaften beider Eltern, was zu einer erweiterten Suche im Lösungsraum und einer höheren Wahrscheinlichkeit führt, optimale oder verbesserte Lösungen im Laufe der Generationen zu finden.

Andere Crossover-Methoden, wie der Zwei-Punkt-Crossover oder der Uniform-Crossover, erweitern dieses Konzept, indem sie mehrere Trennungspunkte einführen oder Gene mit einer festgelegten Wahrscheinlichkeit austauschen, was zur weiteren Diversifizierung der Population beiträgt.

d)

Angenommen, dass nach der Kreuzung zwei Nachkommen entstanden sind: \([1, 1, 0, 0, 1]\) und \([0, 0, 1, 1, 0]\). Beschreibe den Mutationsprozess und zeige, wie eine Mutation auf diese Nachkommen angewendet werden könnte. Diskutiere auch kurz die Bedeutung von Mutationen in genetischen Algorithmen.

Lösung:

Mutationsprozess bei Genetischen AlgorithmenDie Mutation ist ein wesentlicher Teil genetischer Algorithmen, der zufällige Änderungen an Nachkommen einführt, um die genetische Vielfalt innerhalb der Population zu erhöhen und die Gefahr der vorzeitigen Konvergenz zu lokalen Optima zu vermindern.Hauptziel der Mutation ist es, neue genetische Strukturen in die Population einzubringen, die durch Kreuzung allein nicht entstehen könnten.

• Beschreibung des Mutationsprozesses:Bei der Mutation wird jedes Gen eines Nachkommens mit einer bestimmten Wahrscheinlichkeit (Mutationsrate) geändert. Diese Wahrscheinlichkeit ist in der Regel sehr gering (z.B. 1% oder 0,01), um die Integrität der Lösungen nicht zu stark zu beeinträchtigen.
• Beispielhafte Anwendung der Mutation:Angenommen, wir haben die zwei Nachkommen nach der Kreuzung:
  • Nachkomme 1: \[1, 1, 0, 0, 1\]
  • Nachkomme 2: \[0, 0, 1, 1, 0\]

Wir wenden die Mutation mit einer bestimmten Wahrscheinlichkeit auf jedes Gen an:

• Für Nachkomme 1 (\[1, 1, 0, 0, 1\]):Angenommen, nur das dritte Gen wird mutiert (aus \[0\] wird \[1\]). Der mutierte Nachkomme 1 könnte sein:
  • Mutierter Nachkomme 1: \[1, 1, 1, 0, 1\]
• Für Nachkomme 2 (\[0, 0, 1, 1, 0\]):Angenommen, das erste und das fünfte Gen werden mutiert (aus \[0\] wird \[1\] und aus \[0\] wird \[1\]). Der mutierte Nachkomme 2 könnte sein:
  • Mutierter Nachkomme 2: \[1, 0, 1, 1, 1\]

• Ergebnis der Mutation:Nach Anwendung des Mutationsprozesses haben wir die folgenden mutierten Nachkommen:
  • Mutierter Nachkomme 1: \[1, 1, 1, 0, 1\]
  • Mutierter Nachkomme 2: \[1, 0, 1, 1, 1\]
• Bedeutung von Mutationen:Mutationen spielen eine entscheidende Rolle in genetischen Algorithmen:
  • Erhöhte genetische Vielfalt: Mutationen sorgen dafür, dass neue Gene in die Population eingeführt werden, was die Vielfalt erhöht und die Chancen auf das Auffinden globaler Optima steigert.
  • Vermeidung von vorzeitiger Konvergenz: Durch die Einführung zufälliger Änderungen wird verhindert, dass die Population zu schnell zu einer suboptimalen Lösung konvergiert.
  • Erkundung des Lösungsraums: Mutationen ermöglichen es dem Algorithmus, Bereiche des Lösungsraums zu erkunden, die durch Kreuzung allein möglicherweise nicht erreicht werden könnten.

Durch die Balance zwischen Selektion, Kreuzung und Mutation können genetische Algorithmen effizient robuste Lösungen für komplexe Optimierungsprobleme finden.

Aufgabe 3)

Ein autonomer Roboter soll durch Verstärkungslernen (Reinforcement Learning, RL) lernen, sich in einem Labyrinth zu bewegen und das Ziel zu erreichen. Der Roboter kann sich nach oben, unten, links oder rechts bewegen. Die Umgebung (Labyrinth) gibt für das Erreichen des Ziels eine hohe Belohnung und für Kollisionen mit Wänden eine Strafe. Der Roboter startet am unteren linken Rand des Labyrinths. Implementiere und analysiere einen RL-Algorithmus, um den optimalen Weg zum Ziel zu finden.

a)

Erkläre das Grundprinzip des Verstärkungslernens (Reinforcement Learning) und beschreibe die Hauptkomponenten, die in diesem Szenario verwendet werden.

Lösung:

Verstärkungslernen (Reinforcement Learning, RL) Grundprinzip:

Das Verstärkungslernen ist ein Bereich des maschinellen Lernens, bei dem ein Agent durch Interaktion mit seiner Umgebung lernt, wie er eine Aufgabe optimal ausführt, indem er Belohnungen maximiert oder Bestrafungen minimiert. Das Grundprinzip besteht darin, dass der Agent Aktionen ausführt und basierend auf dem Feedback (Belohnungen oder Strafen) lernt, welche Aktionen in bestimmten Zuständen der Umgebung vorteilhaft sind.

Hauptkomponenten des Verstärkungslernens:

• Agent: Der lernende Roboter, der versucht, das Ziel im Labyrinth zu erreichen.
• Umgebung (Environment): Das Labyrinth, in dem sich der Roboter bewegt. Die Umgebung gibt Feedback in Form von Belohnungen oder Strafen.
• Zustand (State): Eine Repräsentation der aktuellen Situation des Roboters im Labyrinth. Zum Beispiel kann ein Zustand die aktuelle Position des Roboters sein.
• Aktion (Action): Die Bewegung, die der Agent in einem bestimmten Zustand ausführen kann. In diesem Szenario kann der Roboter nach oben, unten, links oder rechts bewegen.
• Belohnung (Reward): Feedback von der Umgebung, das dem Agenten mitteilt, wie gut seine Aktion war. Zum Beispiel erhält der Roboter eine hohe Belohnung, wenn er das Ziel erreicht, und eine Strafe bei Kollisionen mit Wänden.
• Politik (Policy): Eine Strategie, die der Agent anwendet, um Aktionen basierend auf dem aktuellen Zustand auszuwählen. Die Politik kann deterministisch oder stochastisch sein.
• Wertfunktion (Value Function): Eine Funktion, die die erwartete Belohnung angibt, die der Agent von einem bestimmten Zustand aus erhält. Dies hilft dem Agenten, langfristig bessere Entscheidungen zu treffen.
• Q-Funktion (Q-Function): Eine Funktion, die die Qualität einer Aktion in einem bestimmten Zustand bewertet. Sie hilft dabei, die beste Aktion aus einem Zustand auszuwählen.

c)

Erkläre die Balance zwischen Exploration und Exploitation im Kontext des obigen Szenarios. Welchen Einfluss hat die Explorationsrate (\epsilon) auf das Verhalten des Roboters?

Lösung:

Exploration vs. Exploitation im Kontext des obigen Szenarios:

Im Verstärkungslernen (Reinforcement Learning) steht der Agent, also in unserem Fall der Roboter, vor der Herausforderung der Entscheidungsfindung zwischen zwei Strategien:

• Exploration: Der Agent versucht neue Aktionen und Wege, um mehr über die Umgebung zu lernen. Dies hilft, bisher unbekannte Zustände zu entdecken und potenziell bessere Belohnungen zu finden.
• Exploitation: Der Agent nutzt sein bestehendes Wissen, um die aktuell als beste bekannte Aktion in einem Zustand auszuwählen. Dies maximiert die kurzfristige Belohnung basierend auf den bisherigen Erfahrungen.

Die Balance zwischen Exploration und Exploitation ist entscheidend für den Lernprozess des Agenten:

• Zu viel Exploration kann dazu führen, dass der Agent in Zuständen experimentiert, die keine besseren Belohnungen bieten, und dadurch die Gesamtleistung behindert wird.
• Zu viel Exploitation kann dazu führen, dass der Agent in eine lokale Optimallösung gerät und nicht das globale Optimum findet, da er keine neuen Zustände erforscht.

Einfluss der Explorationsrate (\( \epsilon \)) auf das Verhalten des Roboters:

• Hohe \( \epsilon \): Eine hohe Explorationsrate bedeutet, dass der Roboter häufiger zufällige Aktionen auswählt. Dies fördert die Exploration und hilft dem Roboter, mehr über das Labyrinth zu erfahren, insbesondere in den frühen Stadien des Lernprozesses.
• Niedrige \( \epsilon \): Eine niedrige Explorationsrate bedeutet, dass der Roboter häufiger die beste bekannte Aktion auswählt. Dies fördert die Exploitation und hilft dem Roboter, die Belohnung zu maximieren basierend auf seinem aktuellen Wissen.

In der Implementierung des Q-Learning-Algorithmus nutzt der Roboter eine Explorationsrate von \( \epsilon = 0.2 \). Das bedeutet, dass der Roboter in 20 % der Fälle eine zufällige Aktion auswählt (Exploration), während er in 80 % der Fälle die beste bekannte Aktion auswählt (Exploitation).

Diese Balance ist besonders wichtig für den Lernprozess des Roboters. Zu Beginn der Lernphase ist mehr Exploration hilfreich, um das Labyrinth besser kennenzulernen. Mit der Zeit kann \( \epsilon \) schrittweise reduziert werden, um die Exploitation zu erhöhen, wenn der Roboter mehr Wissen über das optimale Verhalten in verschiedenen Zuständen erlangt hat. Dies wird oft als \( \epsilon \)-greedy Strategie bezeichnet, bei der \( \epsilon \) dynamisch angepasst wird.

d)

Beschreibe, wie Du den gelernten Q-Learning-Algorithmus auf ein tieferes neuronales Netzwerk (Deep Q Network) erweitern würdest. Welche zusätzlichen Herausforderungen könnten dabei auftreten?

Lösung:

Erweiterung des gelernten Q-Learning-Algorithmus auf ein Deep Q Network (DQN):

Der Wechsel von einem tabellarischen Q-Learning-Algorithmus zu einem Deep Q Network (DQN) beinhaltet die Nutzung eines tiefen neuronalen Netzwerks zur Approximation der Q-Funktionen. Dies ist besonders nützlich in großen oder kontinuierlichen Zustandsräumen, wo eine tabellarische Darstellung nicht praktikabel ist.

Hier sind die Schritte zur Erweiterung zu einem DQN:

1. Netzwerkarchitektur: Definiere ein tiefes neuronales Netzwerk, das als Q-Funktions-Approximator dient. Das Netzwerk nimmt den aktuellen Zustand des Labyrinths als Eingabe und gibt Q-Werte für jede mögliche Aktion aus.
2. Erfahrungsspeicher (Experience Replay): Speichere Übergänge (Zustand, Aktion, Belohnung, neuer Zustand) in einem Speicherpuffer. Dieser Speicher wird verwendet, um zufällig Minibatches für das Training des Netzwerks zu erstellen. Dies hilft, Korrelationen in aufeinanderfolgenden Erfahrungen zu reduzieren und stabilere Updates zu erreichen.
3. Zielnetzwerk (Target Network): Verwende ein separates Zielnetzwerk, um stabilere Q-Werte zu berechnen. Das Zielnetzwerk wird periodisch mit den Gewichten des Hauptnetzwerks aktualisiert.
4. Training: Beim Training ziehst Du zufällige Minibatches aus dem Erfahrungsspeicher und aktualisierst die Netzwerkgewichte durch Backpropagation, indem Du die Differenz zwischen dem vorhergesagten Q-Wert und dem Ziel-Q-Wert minimierst (mittels Mean Squared Error).

Die Implementierung eines DQN kann folgendermaßen aussehen (vereinfacht):

import numpy as npfrom collections import dequeimport randomimport tensorflow as tffrom tensorflow.keras import Model, Sequentialfrom tensorflow.keras.layers import Denseclass DQNAgent:        def __init__(self, state_size, action_size):                self.state_size = state_size                self.action_size = action_size                self.memory = deque(maxlen=2000)                self.gamma = 0.9  # Diskontfaktor                self.epsilon = 0.2  # Explorationsrate                self.epsilon_min = 0.01                self.epsilon_decay = 0.995                self.learning_rate = 0.001                self.model = self._build_model()                self.target_model = self._build_model()                self.update_target_model()        def _build_model(self):                model = Sequential()                model.add(Dense(24, input_dim=self.state_size, activation='relu'))                model.add(Dense(24, activation='relu'))                model.add(Dense(self.action_size, activation='linear'))                model.compile(loss='mse', optimizer=tf.keras.optimizers.Adam(lr=self.learning_rate))                return model        def update_target_model(self):                self.target_model.set_weights(self.model.get_weights())        def remember(self, state, action, reward, next_state, done):                self.memory.append((state, action, reward, next_state, done))        def act(self, state):                if np.random.rand() <= self.epsilon:                        return random.randrange(self.action_size)                act_values = self.model.predict(state)                return np.argmax(act_values[0])        def replay(self, batch_size):                minibatch = random.sample(self.memory, batch_size)                for state, action, reward, next_state, done in minibatch:                        target = reward                        if not done:                                target = (reward + self.gamma * np.amax(self.target_model.predict(next_state)[0]))                        target_f = self.model.predict(state)                        target_f[0][action] = target                        self.model.fit(state, target_f, epochs=1, verbose=0)                if self.epsilon > self.epsilon_min:                        self.epsilon *= self.epsilon_decay        def load(self, name):                self.model.load_weights(name)        def save(self, name):                self.model.save_weights(name)state_size = 2  # Beispielgröße aus dem vereinfachten Szenarioaction_size = 4  # up, down, left, rightagent = DQNAgent(state_size, action_size)# Training Loop (vereinfacht)for e in range(1000):        state = env.reset()        state = np.reshape(state, [1, state_size])        for time in range(500):                action = agent.act(state)                next_state, reward, done = env.step(actions[action])                next_state = np.reshape(next_state, [1, state_size])                agent.remember(state, action, reward, next_state, done)                state = next_state                if done:                        agent.update_target_model()                        break                if len(agent.memory) > 32:                        agent.replay(32)

Zusätzliche Herausforderungen beim Einsatz von DQN:

• Stabilität und Konvergenz: Das Training tiefer neuronaler Netzwerke kann instabil sein. Ermüdungserfahrungen und nicht-stationäre Zielwerte können zu Divergenz führen. Erfahrungsspeicher und Zielnetzwerke helfen, diese Probleme zu mildern.
• Hyperparametereinstellung: Die Auswahl geeigneter Hyperparameter, wie Lernrate, Größe des Erfahrungsspeichers und Minibatch-Größe, sind entscheidend für den Erfolg des DQN.
• Rechenleistung: Das Training eines DQN erfordert signifikant mehr Rechenressourcen im Vergleich zu tabellarischen Methoden. GPUs oder spezialisierte Hardware können erforderlich sein.
• Overfitting: Wie bei allen neuronalen Netzwerken besteht das Risiko des Overfittings. Regelmäßiges Validieren und eventuell Early Stopping sind notwendig.
• Explorationsstrategie: Die Explorationsstrategie kann komplexer sein. Anstatt einer festen \( \epsilon \)-greedy Strategie können fortgeschrittenere Methoden wie UCB (Upper Confidence Bound) oder Thompson Sampling eingesetzt werden.