Genetischer Algorithmus mit Inselmodell
Die Methode, mit der man Optimierungsprobleme löst, indem man die schlechten Lösungen aussterben lässt.
Was sind Evolutionäre Algorithmen?
Stell dir vor, du züchtest die perfekte Tomatensorte für deinen Garten. Du beginnst mit verschiedenen Sorten und wählst jedes Jahr die besten aus.
Genau wie die Natur über Generationen hinweg Lebewesen optimiert, nutzen evolutionäre Algorithmen ähnliche Prinzipien, um Probleme zu lösen:
Die besten Lösungen werden zur 'Zucht' ausgewählt
Durch Kreuzung entstehen neue Kombinationen
Kleine Mutationen bringen überraschende Verbesserungen
Analogie:
Stell dir vor, du züchtest die perfekte Tomatensorte für deinen Garten. Du beginnst mit verschiedenen Sorten und wählst jedes Jahr die besten aus.
Genau wie die Natur über Generationen hinweg Lebewesen optimiert, nutzen evolutionäre Algorithmen ähnliche Prinzipien, um Probleme zu lösen:
Die besten Lösungen werden zur 'Zucht' ausgewählt
Durch Kreuzung entstehen neue Kombinationen
Kleine Mutationen bringen überraschende Verbesserungen
Definition:
Evolutionäre Algorithmen sind stochastische, populationsbasierte Metaheuristiken zur Optimierung. Sie ahmen Prinzipien der biologischen Evolution nach und finden oft sehr gute Lösungen, garantieren aber kein globales Optimum:
Population: Eine Menge von Kandidatenlösungen für das Optimierungsproblem
Fitness-Funktion: Bewertet die Qualität jeder Lösung
Selektion: Auswahl der besten Individuen zur Fortpflanzung
Genetische Operatoren: Crossover (Rekombination) und Mutation erzeugen Variation
Wie die Demo funktioniert
Überblick
Diese interaktive Demo simuliert eine evolutionäre Optimierung mit dem Inselmodell. Sie entwickelt Kunstwerke aus farbigen Kreisen, die einem Zielbild ähneln sollen.
Wichtige Konzepte
- Generation:Eine Generation entspricht einem Evolutionszyklus. In jeder Generation werden neue Lösungen durch Selektion, Crossover und Mutation erzeugt.
- Fitness:Die Fitness misst die Bildqualität als Fehlermetrik: Sie berechnet die Pixel-Differenz zum Zielbild. Niedrigere Werte = bessere Übereinstimmung (0 = perfekte Übereinstimmung). Hinweis: In der klassischen Evolution bedeutet höhere Fitness besser, hier verwenden wir eine invertierte Fehler-Metrik.
- Inseln:Separate Subpopulationen, die parallel evolvieren. Jede Insel kann unterschiedliche Parameter haben und spezialisiert sich auf verschiedene Lösungsansätze.
- Elite-Pool:Sammlung der besten Individuen aus allen Inseln. Diese werden für spezielle Kreuzungsoperationen verwendet.
- Migration:Gelegentlicher Austausch der besten Individuen zwischen benachbarten Inseln zur Erhaltung der genetischen Vielfalt.
- Katastrophe:Drastische Reduzierung der Population einer Insel bei Stagnation. Nur die besten 20% überleben, der Rest wird neu generiert.
- Diversität:Maß für die genetische Vielfalt in der Population. Höhere Diversität verhindert vorzeitige Konvergenz zu suboptimalen Lösungen.
Interaktion
Experimentieren Sie mit verschiedenen Zielbildern, passen Sie Parameter an, beobachten Sie die Evolution in Echtzeit und nutzen Sie die Benchmark-Funktion zum Vergleich verschiedener Algorithmus-Varianten.
Performance-Optimierungen
- Fitness-Cache:Speichert bereits berechnete Fitnesswerte, um redundante Berechnungen zu vermeiden. Da die Fitnessberechnung (Pixel-für-Pixel-Bildvergleich) rechenintensiv ist, verbessert das Caching die Performance dramatisch, wenn dasselbe Individuum mehrfach bewertet wird.
- Adaptive Parameter:Passt Mutations- und Crossover-Raten automatisch an den aktuellen Evolutionsfortschritt an. Bei geringer Diversität erhöht sich die Mutationsrate, um neue Lösungen zu erkunden. Bei Konvergenz auf eine gute Lösung erhöht sich die Crossover-Rate zur Verfeinerung.
- Batch-Rendering:Gruppiert mehrere Canvas-Zeichenoperationen, um Browser-Neuzeichnungen zu reduzieren. Anstatt nach jeder Änderung zu aktualisieren, werden Updates gesammelt und in Stapeln gerendert, was die Animationsflüssigkeit erheblich verbessert.
Interaktive Evolution
Wie aus Kreisen ein Bild wird
Diese Demo malt ein Bild nach — nicht mit dem Pinsel, sondern indem sie hunderte durchsichtige Kreise so lange umordnet, bis das Ergebnis dem Zielbild ähnelt. Hier steht, was du auf dem Bild siehst.
- Was du siehst
- Zwei Bilder untereinander: oben das Zielbild als Vorlage, darunter das Bild, das die Evolution gerade zusammensetzt. Dieses untere Bild besteht aus vielen farbigen, halbdurchsichtigen Kreisen, die sich überlagern. Am Anfang ist es nur ein grober Farbfleck, nach und nach wird ein erkennbares Abbild der Vorlage daraus.
- Was passiert
- Über viele Generationen behält die Demo immer die besten Kandidaten und verändert sie leicht — verschiebt, färbt oder tauscht einzelne Kreise. Passt eine Änderung besser zur Vorlage, bleibt sie erhalten; so wird das untere Bild der Vorlage Schritt für Schritt ähnlicher. Eine kleine Kurve darunter zeigt diesen Fortschritt.
- Was du tun kannst
- Wähle ein Zielbild aus oder lade ein eigenes hoch, starte und pausiere die Evolution oder gehe Schritt für Schritt vor. In den Einstellungen änderst du zum Beispiel die Anzahl der Kreise, und im Duell treten zwei Strategien nebeneinander gegeneinander an.
- Worauf du achtest
- Kein einzelner Kreis weiß, wie das Zielbild aussieht. Das erkennbare Bild entsteht allein daraus, dass die besten Zufalls-Versuche behalten und immer wieder leicht verändert werden — Generation für Generation.
Girl with Pearl Earring - Johannes Vermeer
Globales Bestes
Steuerungsbereich für die Evolution
Evolution
Hauptsteuerungen für den Evolutionsprozess
Duell
Lass zwei Strategien direkt gegeneinander antreten. Wähle für Seite A und Seite B je ein Preset und sieh in 200 Generationen, welche Strategie das Zielbild näher trifft.
Einstellungen
Erweiterte Kontrollen
Algorithmus-Features
Aktivieren Sie verschiedene Optimierungen und beobachten Sie ihre Auswirkungen auf die Performance.
Noch keine Daten - starte die Evolution um Lernstatistiken zu sehen
Automatisierte A/B-Tests
Dieser automatisierte Benchmark führt mehrere Evolutionstests mit verschiedenen Feature-Kombinationen durch, um die optimale Konfiguration zu finden. Er vergleicht Leistungsmetriken wie Generationen pro Sekunde, Konvergenzrate und finale Fitness-Werte.
- 7 automatische Testläufe mit verschiedenen Feature-Kombinationen
- Je 500 Generationen pro Testlauf für aussagekräftige Ergebnisse
- Getestet werden: Fitness-Cache, Adaptive Parameter, Batch-Rendering
Globaler Elite-Pool
Der Elite-Pool ist leer. Starte die Evolution, um ihn mit den besten Individuen von jeder Insel zu füllen.
Inselpopulationen
Evolutionäre Algorithmen erklärt
Biologische Evolution als Vorbild
Evolutionäre Algorithmen sind von der biologischen Evolution inspiriert: Sie erzeugen Lösungen, wählen die besten aus, kombinieren sie und führen zufällige Veränderungen ein. Über viele Generationen hinweg entstehen so immer bessere Lösungen.
Der Algorithmus arbeitet mit einer Population von Lösungskandidaten. Jede Generation durchläuft drei Phasen: Selektion (die besten überleben), Crossover (Kombinieren von Lösungen) und Mutation (zufällige Änderungen). Diese Operationen ahmen die natürliche Selektion, Fortpflanzung und genetische Variation nach.
Vorteile evolutionärer Optimierung
- Globale Optimierung: Findet gute Lösungen auch in komplexen Suchräumen mit vielen lokalen Optima
- Keine Gradienten nötig: Funktioniert auch bei nicht-differenzierbaren oder diskreten Problemen
- Parallelisierbar: Mehrere Lösungen können gleichzeitig evaluiert werden
- Flexibel: Kann an verschiedene Problemtypen angepasst werden
Herausforderungen
Evolutionäre Algorithmen benötigen viele Evaluierungen der Fitness-Funktion, was rechenintensiv sein kann. Die Wahl der richtigen Parameter (Populationsgröße, Mutations- und Crossover-Raten) ist entscheidend für die Performance. Zudem gibt es keine Garantie, das globale Optimum zu finden – nur gute Annäherungen.
Praktische Anwendungen
Typische Anwendungen: Optimierung von Reiserouten (Traveling Salesman Problem), Feature Selection in Machine Learning, Hyperparameter-Tuning, Neural Architecture Search, Scheduling-Probleme in der Produktion, und Spielstrategie-Optimierung.
Probiere die Demo aus! Beobachte wie die Population über Generationen hinweg bessere Lösungen entwickelt.
1
# Evolutionärer Algorithmus
2
funktion evolutionärer_algorithmus(problem):
3
# Hauptfunktion: Evolutionäre Optimierung
4
population = initialisiere_population(größe)
5
fitness = bewerte_alle(population)
6
7
solange nicht_konvergiert:
8
# Selektion: Beste auswählen
9
eltern = selektiere_eltern(population, fitness)
10
11
# Crossover: Gene kombinieren
12
für jedes elternpaar:
13
gene_kombiniert = crossover(eltern)
14
nachkommen = erzeuge_nachkommen(gene_kombiniert)
15
16
# Mutation: Zufällige Änderungen
17
für jeden nachkommen:
18
wenn zufall < mutationsrate:
19
mutiere(nachkommen)
20
21
# Bewertung der Nachkommen
22
fitness_nachkommen = bewerte_alle(nachkommen)
23
24
# Ersetzung: Neue Generation
25
sortiere_nach_fitness(population + nachkommen)
26
überlebende = wähle_beste(population_größe)
27
population = überlebende
28
29
# Abbruchkriterium prüfen
30
wenn abbruchkriterium_erfüllt():
31
beende
32
33
return bestes_individuum(population)
👥 Population initialisieren
Erzeuge eine Anfangspopulation mit zufälligen Lösungen. Jedes Individuum repräsentiert eine mögliche Lösung des Problems.
population = initialisiere_population(größe)
🎬 Initialisierung
Erzeuge zufällige Anfangspopulation. Jedes Individuum ist eine mögliche Lösung.
❤️ Selektion
Wähle fitte Individuen als Eltern. Survival of the fittest.
🔗 Crossover
Kombiniere Gene der Eltern. Erzeuge Nachkommen mit gemischten Eigenschaften.
⚡ Mutation
Zufällige Genänderungen. Neue Variationen entstehen.
📊 Bewertung
Berechne Fitness aller Individuen. Messe Lösungsqualität.
🔄 Ersetzung
Ersetze alte durch neue Generation. Behalte die Besten.
✅ Terminierung
Prüfe Abbruchkriterium. Beende wenn Lösung gut genug.
Quiz: Evolutionäre Algorithmen verstehen
Was ist das Hauptprinzip evolutionärer Algorithmen?
1. Was ist das Hauptprinzip evolutionärer Algorithmen?
- ☐ A) Mathematische Ableitung zur Optimierung
- ☐ B) Nachahmung biologischer Evolution zur Problemlösung
- ☐ C) Neuronale Netzwerke zur Mustererkennung
- ☐ D) Statistische Analyse großer Datenmengen
2. Was passiert bei der Selektion in evolutionären Algorithmen?
- ☐ A) Die fittesten Individuen werden zur Fortpflanzung ausgewählt
- ☐ B) Zufällige Individuen werden eliminiert
- ☐ C) Alle Individuen erhalten die gleiche Chance
- ☐ D) Die Population wird komplett erneuert
3. Was ist der Hauptvorteil des Inselmodells?
- ☐ A) Schnellere Konvergenz zu einer Lösung
- ☐ B) Weniger Rechenaufwand erforderlich
- ☐ C) Erhaltung der genetischen Diversität
- ☐ D) Einfachere Implementierung
4. Welche Rolle spielt die Mutation in einem evolutionären Algorithmus?
- ☐ A) Sie kombiniert die Gene zweier Eltern zu einem Kind
- ☐ B) Sie bringt zufällige Veränderungen ein und hilft, lokale Optima zu verlassen
- ☐ C) Sie wählt die fittesten Individuen für die nächste Generation aus
- ☐ D) Sie kopiert das beste Individuum unverändert in die nächste Generation
5. Was passiert in dieser Demo bei einer „Katastrophe" auf einer Insel?
- ☐ A) Die gesamte Population aller Inseln wird gelöscht
- ☐ B) Die Mutationsrate wird dauerhaft auf null gesetzt
- ☐ C) Nur die besten Individuen überleben, der Rest wird neu erzeugt
- ☐ D) Zwei Inseln werden dauerhaft zu einer verschmolzen
Verwandte Inhalte
Artikel
Agenten in Konflikten — Spieltheorie
Was ein zweiter rationaler Spieler an einer Optimierung ändert — alles.
Der Weg ins Tal: Gradientenabstieg
Wie Gradientenabstieg in einer Landschaft mit Millionen Hügeln den Tiefpunkt findet — meistens.
Suche im Graphen — Die Anfänge
Graphsuche: das erste, was KI tatsächlich konnte — und immer noch nützlich ist.
Heuristiken & Pfadsuche: Von Dijkstra zu A*
Wie A* funktioniert — und warum Dijkstra ohne Heuristik schnell langweilig wird.
Die Knöpfe der Maschine — Parameter vs. Hyperparameter
Die feine Linie zwischen "von der Maschine gelernt" und "von dir geraten".
Was ist ein Algorithmus?
Was Euklid, IKEA-Anleitungen und Google-Suche gemeinsam haben — alle drei sind Algorithmen.
Demo
Schwarmintelligenz (Boids)
Erlebe, wie aus drei simplen lokalen Regeln das komplexe Verhalten eines Vogelschwarms entsteht.
Gradient Descent
Interaktive Demo zum Verständnis von Gradient Descent: klicke einen Startpunkt auf die Verlustlandschaft, beobachte wie der Algorithmus ins Tal rollt, und experimentiere mit Lernrate und Optimierern.
Neuroevolution
Interaktive Demonstration von Neuroevolution: Neuronale Netze lernen durch evolutionäre Optimierung das Fahren auf einer Rennstrecke
Q-Learning
Interaktive Demonstration des Q-Learning Algorithmus mit einem intelligenten Agenten im Tempel des Lernens
Travelling Salesman: Algorithmen im Wettstreit
Setze Städte, zeichne deine eigene Route und lass Greedy, Simulated Annealing und Genetic Algorithm gegen dich antreten.