Einfacher genetischer Algorithmus
Als Einstieg in mein W-Seminar “Küstliche Intelligenz und ‘Nature of code’ ” habe ich anhand eines einfachen genetischen Algorithmus meinen Schülern meine aktuelle Lieblingsumgebung processing näher gebracht.
Die Idee hinter einem genetischen Algorithmus ist schnell erklärt.
- Es werden ein odere mehrere Versuchsballons gestartet
- Das Ergebnis wird mit einer sogenannten Fitnessfunktion beurteilt.
- Man wählt das Beste Ergebnis aus, mutiert bzw. verändert dies etwas und fängt wieder bei 1. an.
Und da processing wurderbar mit Bildern umgehen kann, habe ich den Schülern diese Kernidee angelehnt an der Software primitive vorgemacht. Bei dieser Software wird ein Bild durch geometrische Formen angenähert. Der Ablauf des genetischen Algorithmus sah dann ungefähr so aus:
- Ich mache eine Kopie der aktuellen Näherung und male anschließend per Zufall einen halbtransparenten Kreis mit zufälligem Radius an einer Stelle, deren RGB-Wert ich mir aus dem Originalbild genommen habe.
- Dann wird zum Beispiel die Summe der quadrierten Abweichungen der RGB Werte (bei SW-Bildern genügt auch nur die Helligkeit) für jedes Pixel im Vergleich zum Originalbild berechnet.
- Ist die Abweichung geringer als beim letzten Bild, so wird der Kreis beibehalten. Sonst wird das Bild aus der Kopie wieder hergestellt.
Im Ablauf sieht es dann wie folgt aus (100 Kreise, 1000 und 2000 Kreise):
Das Originalbild ist ein Einhornkuchen, den ich mal in London fotografiert habe. Kein perfektes Motiv, aber jeder darf es gerne benutzen. Besser geeignet sind Portraitfotos. Wenn man die Augen etwas zusammenkneift ist es erstaunlich, wie schnell eine Ähnlichkeit entsteht.
In der Originalsoftware primitive sieht es besser aus. Vor allem, wenn man das erste Bild vergleicht.
So richtig zufällig scheinen die Kreise nicht zu sein, wenn man sich die Kuchenschichten anschaut. Wahrscheinlich macht er etwas was ich nicht mache: Mehrere Versuche pro Generation und nur einer, der beste/fitteste, überlebt. Das war mir aber für die erste Doppelstunde dann doch zuviel.
Hier noch der Quelltext mit allen Bildern: GenetischerAlgBsp
Und zum Abschluss die Aufgabe, die ich auch meinen Schülern gegeben habe, da ich in der nächsten Doppelstunde auf Fortbildung zum Thema “Change Management an Schulen” bin.
Aufgabe
Lade dir den Quelltext herunter und verändere das Programm u.a. wie folgt:
1. Überlege dir eine andere Fitnessfunktion und implementiere diese.
2. Benutze statt Kreisen Rechtecke.
3. Die Anzahl der Generationen (Rechtecke, Kreise) kann im Quelltext, besser wäre natürlich interaktiv, begrenzt werden.
4. Um die Annäherung zu beschleunigen, werden die Kreise nicht ganz zufällig gesetzt bzw. die Größe wird nicht zufällig gewählt bzw. der Farbton entspricht vielleicht nicht unbedingt dem zentralen Pixel.