Genetische Algorithmen (GA) basieren auf einem evolutionären Ansatz der KI, bei dem Methoden der Evolution einer Population genutzt werden, um eine optimale Lösung für ein gegebenes Problem zu finden. Sie wurden 1975 von John Henry Holland vorgeschlagen.
Genetische Algorithmen basieren auf den folgenden Ideen:
- Gültige Lösungen des Problems können als Gene dargestellt werden.
- Durch Crossover können zwei Lösungen kombiniert werden, um eine neue gültige Lösung zu erhalten.
- Selektion wird verwendet, um mithilfe einer Fitnessfunktion optimalere Lösungen auszuwählen.
- Mutationen werden eingeführt, um die Optimierung zu destabilisieren und uns aus lokalen Minima herauszuführen.
Wenn Sie einen genetischen Algorithmus implementieren möchten, benötigen Sie Folgendes:
- Eine Methode, um Problemlösungen mithilfe von Genen g∈Γ zu kodieren.
- Auf der Menge der Gene Γ muss eine Fitnessfunktion fit: Γ→R definiert werden. Kleinere Funktionswerte entsprechen besseren Lösungen.
- Einen Crossover-Mechanismus, um zwei Gene zu kombinieren und eine neue gültige Lösung zu erhalten: crossover: Γ²→Γ.
- Einen Mutationsmechanismus: mutate: Γ→Γ.
In vielen Fällen sind Crossover und Mutation recht einfache Algorithmen, die Gene als Zahlenfolgen oder Bitvektoren manipulieren.
Die spezifische Implementierung eines genetischen Algorithmus kann je nach Fall variieren, aber die allgemeine Struktur ist wie folgt:
- Wählen Sie eine Anfangspopulation G⊆Γ.
- Wählen Sie zufällig eine der Operationen aus, die in diesem Schritt ausgeführt werden sollen: Crossover oder Mutation.
- Crossover:
- Wählen Sie zufällig zwei Gene g₁, g₂ ∈ G.
- Berechnen Sie das Crossover g=crossover(g₁, g₂).
- Wenn fit(g)<fit(g₁) oder fit(g)<fit(g₂), ersetzen Sie das entsprechende Gen in der Population durch g.
- Mutation - Wählen Sie ein zufälliges Gen g∈G und ersetzen Sie es durch mutate(g).
- Wiederholen Sie ab Schritt 2, bis ein ausreichend kleiner Wert von fit erreicht ist oder bis das Limit der Schrittanzahl erreicht ist.
Aufgaben, die typischerweise mit genetischen Algorithmen gelöst werden, umfassen:
- Optimierung von Zeitplänen
- Optimales Packen
- Optimales Schneiden
- Beschleunigung von erschöpfenden Suchverfahren
Setzen Sie Ihr Lernen in den folgenden Notebooks fort:
Gehen Sie zu diesem Notebook, um zwei Beispiele für die Verwendung genetischer Algorithmen zu sehen:
- Gerechte Aufteilung eines Schatzes
- 8-Damen-Problem
Genetische Algorithmen werden verwendet, um viele Probleme zu lösen, einschließlich Logistik- und Suchprobleme. Dieses Feld ist inspiriert von Forschung, die Themen aus der Psychologie und der Informatik miteinander verbindet.
"Genetische Algorithmen sind einfach zu implementieren, aber ihr Verhalten ist schwer zu verstehen." Quelle Recherchieren Sie eine Implementierung eines genetischen Algorithmus, z. B. zur Lösung eines Sudoku-Puzzles, und erklären Sie, wie er funktioniert, als Skizze oder Flussdiagramm.
Sehen Sie sich dieses großartige Video an, das zeigt, wie ein Computer lernen kann, Super Mario zu spielen, indem neuronale Netzwerke mit genetischen Algorithmen trainiert werden. Wir werden mehr darüber lernen, wie Computer lernen, solche Spiele zu spielen, im nächsten Abschnitt.
Ihr Ziel ist es, die sogenannte diophantische Gleichung zu lösen – eine Gleichung mit ganzzahligen Lösungen. Betrachten Sie zum Beispiel die Gleichung a+2b+3c+4d=30. Sie müssen die ganzzahligen Lösungen finden, die diese Gleichung erfüllen.
Diese Aufgabe ist inspiriert von diesem Beitrag.
Hinweise:
- Sie können Lösungen im Intervall [0;30] betrachten.
- Verwenden Sie als Gen die Liste der Lösungswerte.
Nutzen Sie Diophantine.ipynb als Ausgangspunkt.