Genetischer Algorithmus mit Inselmodell

Die Methode, mit der man Optimierungsprobleme löst, indem man die schlechten Lösungen aussterben lässt.

Das Mädchen mit dem Perlenohrgehänge – Johannes Vermeer

Das Bild, dem sich die Evolution nähern soll. Zeigt das ausgewählte Referenzbild.

Globales Bestes

Das beste entwickelte Bild der aktuellen Evolution Zeigt das beste Ergebnis der letzten Evolution
Best-FitnessMigrationKatastrophe

Steuerungsbereich für die Evolution

EvolutionDuellEinstellungen

Evolution

Hauptsteuerungen für den Evolutionsprozess
Hauptsteuerung zum Starten, Pausieren oder Ausführen einzelner Evolutionsschritte
Generation0Kreise1 / 200Ähnlichkeit0.0%Nächste Migration25Ø Diversität0.00Gen/Sek0

Globaler Elite-Pool

Der Elite-Pool ist leer. Starte die Evolution, um ihn mit den besten Individuen von jeder Insel zu füllen.

Inselpopulationen

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.

Definition

Was sind Evolutionäre Algorithmen?

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

Ü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.

TheoriePseudo-CodeSchritt für SchrittFlussdiagramm

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.

Prüfen

Quiz: Evolutionäre Algorithmen verstehen

Noch offen

Was ist das Hauptprinzip evolutionärer Algorithmen?

Wähle eine Antwort

Auflösung: 1) B · 2) A · 3) C · 4) B · 5) C

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Evolution als Problemlöser

Was die Demo zeigt

Diese Demo zeigt einen evolutionären Algorithmus. Evolutionärer Algorithmus heißt: Die Natur ist das Vorbild. Viele Lösungen konkurrieren miteinander. Die besten Lösungen überleben. Daraus entsteht eine bessere Lösung.

Wie du die Demo benutzt

Klicke auf den Knopf Auto starten. Die Evolution beginnt. Das Programm zeigt ein Zielbild. Es baut das Bild mit bunten Kreisen nach. Du beobachtest die Verbesserung.

Was du lernst

Die Demo zeigt: Viele schwache Lösungen können eine gute Lösung erzeugen. Das ist die Kraft der Evolution. Mutation heißt: Kleine zufällige Änderungen. Crossover heißt: Teile von zwei Lösungen mischen.

Zielbild auswählen

Das Mädchen mit dem Perlenohrgehänge – Johannes Vermeer
Das Mädchen mit dem Perlenohrgehänge – Johannes Vermeer
Der Schrei – Edvard Munch
Der Schrei – Edvard Munch
Die Sternennacht – Vincent van Gogh
Die Sternennacht – Vincent van Gogh
Die Nachtwache – Rembrandt van Rijn
Die Nachtwache – Rembrandt van Rijn
Bonaparte beim Überschreiten der Alpen – Jacques-Louis David
Bonaparte beim Überschreiten der Alpen – Jacques-Louis David
Die große Welle vor Kanagawa – Katsushika Hokusai
Die große Welle vor Kanagawa – Katsushika Hokusai
Die Freiheit führt das Volk – Eugène Delacroix
Die Freiheit führt das Volk – Eugène Delacroix
Washington überquert den Delaware – Emanuel Leutze
Washington überquert den Delaware – Emanuel Leutze
Selbstbildnis als Spötter – Joseph Ducreux
Selbstbildnis als Spötter – Joseph Ducreux
Eigenes Bild hochladen