Punktesimulation mit genetischem Algorithmus – Teil 1

Dieser Blogbeitrag beschreibt ein fesselndes Projekt, bei dem ein genetischer Algorithmus (GA) verwendet wird, um Punkte zu simulieren, die auf ein Ziel zusteuern und dabei Hindernissen ausweichen. Der GA ahmt die natürliche Selektion nach und verbessert iterativ eine Punktpopulation basierend auf ihrer Nähe zum Ziel.

Genetische Algorithmus-Implementierung:

Die GA folgt diesen Standardschritten:

1. Initialisierung: Erzeugt zufällig eine Anfangspopulation von Punkten.
2. Bewertung:Eine Fitnessfunktion bewertet die Leistung jedes Punkts basierend auf seiner Entfernung vom Ziel.
3. Auswahl: Die fittesten Punkte werden als Eltern für die nächste Generation ausgewählt.
4. Crossover: Genetische Informationen (Bewegungsrichtungen) von zwei Elternteilen werden kombiniert, um Nachkommen zu erzeugen. (Hinweis: Dieses Projekt verwendet der Einfachheit halber zunächst die Replikation; Crossover wird später hinzugefügt.)
5. Mutation: Kleinere zufällige Änderungen werden in die Bewegungsrichtungen der Nachkommen eingeführt, um die Vielfalt aufrechtzuerhalten.
6. Ersatz:Die vorherige Generation wird durch den Nachwuchs ersetzt.
7. Elitismus: Die leistungsstärksten Punkte der vorherigen Generation bleiben in der nächsten Generation erhalten.
8. Iteration: Die Schritte 2–7 werden für eine bestimmte Anzahl von Generationen wiederholt.

Simulationsübersicht:

Die Simulation visualisiert eine Population von Punkten, die sich entwickeln, um ein rotes quadratisches Ziel zu erreichen. Die Bewegung jedes Punktes wird durch seine „Gene“ (eine Abfolge von Bewegungsrichtungen) bestimmt. Durch Selektion, Mutation und Replikation passt sich die Population an und verbessert ihre Fähigkeit, das Ziel zu erreichen, während sie schwarze rechteckige Hindernisse umgeht.

Wichtige Simulationskomponenten:

1. Punkte:Agenten mit Bewegungsrichtungen (Chromosomen) und einem Fitness-Score basierend auf der Zielnähe.
2. Fitnessfunktion: Berechnet die Fitness basierend auf der Entfernung zum Ziel und belohnt kürzere Wege.
3. Bevölkerung: Eine Ansammlung von Punkten, die sich über Generationen hinweg entwickelt.
4. Genetischer Algorithmus: Treibt den Evolutionsprozess voran, wählt geeignete Individuen aus und führt Variationen ein.
5. Hindernisse:Schwarze Rechtecke erschweren die Navigation der Punkte.
6. Ziel: Ein rotes quadratisches Ziel, das die Punkte erreichen sollen.

Projekt-Setup (Python mit Pygame):

Das Projekt verwendet Pygame zur Visualisierung. Wichtige globale Variablen steuern die Parameter der Simulation (Populationsgröße, Mutationsrate usw.). Eine Dot-Klasse stellt einzelne Punkte dar und verwaltet deren Position, Bewegung und Fitness.

Erste Simulation (Einzelpunkt):

Der ursprüngliche Code simuliert einen einzelnen Punkt, der sich zufällig bewegt, bis er die Bildschirmgrenzen verlässt. Dies dient als grundlegender Schritt vor der Einführung einer Population und der GA.

Bevölkerungssimulation:

Eine Population-Klasse verwaltet die Gruppe der Punkte. Die Methode update verschiebt die Punkte und prüft auf Kollisionen mit Hindernissen. Die Simulation zeigt jetzt mehrere Punkte an, die sich gleichzeitig bewegen.

Hindernisse und das Ziel hinzufügen:

Die Klassen

Obstacle und Goal werden eingeführt, um Hindernisse bzw. das Ziel darzustellen. Es ist eine Kollisionserkennung implementiert, die dazu führt, dass Punkte bei einer Kollision „sterben“. Die Simulation umfasst jetzt ein rotes Zielquadrat und ein schwarzes rechteckiges Hindernis.

Implementierung des genetischen Algorithmus (Replikation):

Die get_fitness-Methode in der Dot-Klasse berechnet die Fitness. Die Population-Klasse erhält generate_next_generation- und select_best_dots-Methoden zur Implementierung von Selektion, Replikation (zunächst statt Crossover), Mutation und Elitismus. Die Simulation zeigt nun die Bevölkerungsentwicklung über Generationen hinweg.

Zukünftige Verbesserungen:

Zukünftige Blogbeiträge behandeln Folgendes:

• Elite-Punkte visuell unterscheiden.
• Hinzufügen komplexerer Hindernisse.
• Implementierung von Crossover für eine anspruchsvollere Nachwuchsgeneration.
• Anzeige einer „Erreicht“-Meldung, wenn ein Punkt das Ziel erreicht.

Der vollständige Code (bis zu diesem Punkt) ist auf GitHub verfügbar. Experimentieren Sie mit dem Code und teilen Sie Ihre Erkenntnisse! Treten Sie der AICraftsLab Discord-Community bei, um mit anderen KI-Enthusiasten in Kontakt zu treten.

Das obige ist der detaillierte Inhalt vonPunktesimulation mit genetischem Algorithmus – Teil 1. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!