Den kreativen Prozess der Natur nutzen
Einstieg in die simulierte Evolution mit Java
Evolution ist ein sehr kreativer Prozess und vollbringt in der Natur erstaunliche Anpassungsleistungen. Lebewesen haben den ganzen Planeten und selbst unwirtliche Lebensräume erobert. Im biologischen Umfeld dauert diese Anpassung oft viele Jahre. Aber hauptsächlich, weil jede neue Generation und die Weitergabe der Eigenschaften viel Zeit beansprucht. Das Prinzip ist gut auf andere Anwendungsbereiche übertragbar. Dieser Artikel bietet einen Einstieg in das Thema und demonstriert Code-Beispiele in Java.
Evolution ist ein fortlaufender Prozess mit einem geschickten Zusammenspiel von Selektion und Variation auf besonders gut angepasste Kombinationen von Eigenschaften. Schon in den 1960er-Jahren gab es erste erfolgreiche Ansätze der Umsetzung. Während des KI-Hypes der letzten Jahre hatten es alternative Ansätze schwer, breite Aufmerksamkeit zu finden. Aber simulierte Evolution kann ebenfalls gut mit neuronalen Netzen kombiniert werden und so seine Stärken ausspielen.
Um das Grundprinzip auf eigene Optimierungsprobleme zu übertragen, sind folgende fünf Fragen zu klären:
- Welche Informationen sind notwendig, um Lösungsversuche zu beschreiben?
Dazu braucht man eine Datenstruktur, die die fachliche Aufgabe abbildet und dem biologischen Erbgut entspricht. Sie muss leicht änderbar sein, gleichzeitig kompakt genug, da vermutlich viele Lösungen über den Optimierungsprozess hinweg entstehen werden. - Was zeichnet gute Lösungsversuche aus?
Die Daten jedes Lösungsversuchs sind zu interpretieren und es ist je eine Berechnung oder Simulation notwendig. Zum Schluss muss eine Fitnessfunktion einen numerischen Wert liefern, der die Güte der Ergebnisse dokumentiert und vergleichbar macht. Diese Frage ist entscheidend, damit das Verfahren konvergieren kann. - Welche der Lösungsversuche überleben und welche sterben aus?
Ein Mechanismus muss Lösungen gemäß ihres Fitnesswertes vergleichen und filtern (Selektion). Gute Lösungen leben mit einer höheren Wahrscheinlichkeit weiter bzw. geben ihre Eigenschaften an ihre Nachkommen in der nächsten Generation weiter. - Wie erfolgt die Weitergabe der Eigenschaften?
Die ausgewählten Lösungsversuche werden – u. U. mit kleinen Modifikationen – in die nächste Generation übertragen. Dazu benutzt die simulierte Evolution an die Natur angelehnte genetische Operatoren, wie zum Beispiel Mutation oder Rekombination (Crossing-Over). Ganz praktisch gesehen kopieren wir Daten der Lösungen absichtlich mit kleinen, zufälligen Fehlern oder kombinieren Eigenschaften von zwei guten Lösungen. - Wie kann ein iterativer Ablauf die einzelnen Aspekte geschickt zusammenführen?
An dieser Stelle hilft es den Ablauf zu beschreiben und den Zusammenhang zu klären.
Der Ablauf ist in der Abb. 1 dargestellt und besteht im Wesentlichen aus einer Schleife:
- Im ersten Schritt wird eine initiale Population von Lösungsversuchen mit gänzlich zufälligem Inhalt erstellt.
- Alle Lösungsansätze werden zum Leben erweckt und simuliert.
- Jeder Lösungsversuch erhält auf Grundlage seiner Ergebnisse eine numerische Fitness.
- Die Optimierung ist beendet, wenn eine ausreichend gute Lösung gefunden oder eine maximale Anzahl von Generationen durchlaufen ist.
- Ist das Abbruchkriterium nicht erfüllt, werden aus den vorhandenen Lösungsansätzen neue und veränderte Nachkommen für eine nächste Generation erzeugt. Danach wiederholen sich die Schritte zwei bis fünf.
Die Liste mit den fünf Aspekten sieht auf den ersten Blick aufwändig aus. Der Eindruck täuscht, denn die letzten drei Punkte (Selektion, genetische Operatoren und den Ablauf) delegieren wir komplett an ein Framework.
Für viele populäre Programmiersprachen existieren gute Frameworks für Evolution. Die folgende Tabelle zeigt nur eine kleine Auswahl:
Tabelle 1: Auswahl von Frameworks für simulierte Evolution
| Framework | Programmiersprache | Bemerkung |
| Jenetics [1] | Java | Modernes Framework mit flexiblen Erweiterungsmöglichkeiten und vielen Beispielen. |
| JGAP [2] | Java | Sehr klassisches und ausgereiftes Framework. |
| Geneticalgorithm [3] | Python | Bietet nur die Basisfunktionen und ist für den Einstieg geeignet. |
| PyGAD [4] | Python | Bietet eine recht breite Funktionspalette an und die Integration mit neuronalen Netzen. |
| Eaopt [5] | Go | Bibliothek mit verschiedenen Optimierungsverfahren. |
Trocken ist alle Theorie
Nach den theoretischen Grundlagen soll ein Beispiel den praktischen Einsatz zeigen. Das Beispiel verwendet das Framework Jenetics[1].
In Zeitschriften und Illustrierten finden sich Wortsuchspiele, die eine große Fangemeinde besitzen (mehr zum Thema Rätsel [6]). Dabei sind Wörter in einem Buchstabengitter zu finden, die sich zwischen zufällig gefüllten Zellen verstecken. Meist sind die Wörter horizontal, vertikal und diagonal angeordnet und überschneiden sich sogar. Ziel ist es, im nachfolgenden Beispiel diese Art von Denksportaufgaben mit Hilfe von Evolution und Java zu erzeugen.
Definition der Struktur von Lösungen
Das Erbgut eines Lösungsversuchs definiert eine Liste von 20 Worten mit der Position und Lage im Wortgitter. Dazu definieren wir folgende Informationen für jedes Wort:
- Index des Wortes aus einer gegebenen Wortliste,
- Position des ersten Buchstaben im Feld mit Zeile und Spalte und
- Ein Kennzeichen für die Lage des Wortes (0: waagrecht, 1: senkrecht, 2: diagonal).
Diese Angaben beschreiben einen Lösungsversuch in einem Feld vollständig.
Die Fitness-Funktion
Was macht ein ansprechendes Rätsel aus? Jeder der Lösungsversuche muss zum "Leben" erweckt werden, denn nur vollständig erzeugte Wortgitter machen eine sinnvolle Bewertung möglich. Es ist zu erwarten, dass bei zufällig befüllten Lösungen (in der ersten Generation) und durch die Mutationen einiges schief geht. Es ist somit sinnvoll, positive und negative Eigenschaften zu berücksichtigen:
- Die Worte müssen in das Feld passen und dürfen nicht über den Rand hinausragen.
- Das Überlagern und Überkreuzen von Worten ist durchaus gewünscht, wenn diese Kreuzungspunkte gleiche Buchstaben enthalten.
- Außerdem sollten möglichst viele Worte und Buchstaben in dem Rätsel vorkommen.
Die Fitness muss alle diese Vorgaben widerspiegeln. Verstöße, wie das Überschreiten der Feldgrenze oder das Überschreiben von Buchstaben sollten sich durch eine starke negative Gewichtung die Fitness empfindlich reduzieren. Die Kunst besteht darin, diese Vorgaben in einer Formel zu kombinieren.
Die Fitness könnte sich ergeben aus dem Produkt von Anzahl der Worte, Anzahl der Buchstaben und mehrfach genutzter Buchstaben geteilt durch die Verstöße zum Quadrat:
Die Implementierung
Als Voraussetzung für die Umsetzung nehmen wir eine Klasse für ein zweidimensionales Feld von Buchstaben als gegeben. Diese bietet Funktionen für das Einfügen von Worten mit einer Startposition und einer Richtung. Dabei protokolliert die Klasse ebenfalls die Anzahl der Wörter, Anzahl der Buchstaben und wie viele Verstöße das Eintragen provoziert. Das entstandene Feld, so wie alle anderen Details können vom Feld erfragt werden.
Code 1: Generator für die Erbinformation der Lösungsversuche
Der erste Code-Abschnitt zeigt den Generator (Factory), der das Erbgut je Lösungsversuch zufällig erzeugen kann: Ergebnis ist jeweils ein Feld mit vier Integer-Werten je Wort jeweils aus dem Wertebereich 1 bis 100. Jenetics bietet zusätzlich für fachlich umfangreichere Aufgaben auch die Möglichkeit, strukturierte Gene zu definieren.
Factory<Genotype<IntegerGene>> gtf = Genotype.of(IntegerChromosome.of(1, 100, (COUNT_WORDS * 4)));
Code 2: Umwandeln der Erbinformationen zu einem Wortgitter
Um einen Lösungsversuch zu simulieren, interpretiert die Methode decode() das enthaltene Erbgut. Dazu erzeugt diese eine Liste von Worten mit allen oben definierten Informationen und trägt diese in ein Buchstabenfeld mit der Methode putWord() ein. Der Modulo-Operator leistet hilfreiche Dienste beim Einhalten der gewünschten Wertebereiche.
protected static Field decodeToField(Genotype<IntegerGene> genotype) {
Field field = new Field();
IntegerChromosome chromosome = (IntegerChromosome)genotype.chromosome();
IntStream.range(0, COUNT_WORDS-1)
.forEach( i -> {
int wordIndex = Math.abs(chromosome.get(i).allele()) % WORDS.length;
int xpos = Math.abs(chromosome.get(i+1).allele()) % Field.MAX_WIDTH;
int ypos = Math.abs(chromosome.get(i+2).allele()) % Field.MAX_HEIGHT;
int direction = Math.abs(chromosome.get(i+3).allele()) % Field.DirectionEnum.values().length;
Field.DirectionEnum d = Field.DirectionEnum.values()[direction];
String word = WORDS[wordIndex];
field.putWord(word, xpos, ypos, d);
}
);
return field;
}
Code 3: Umsetzung der Fitness-Funktion
Mit dieser Vorarbeit konzentriert sich die Fitness-Funktion ganz auf das Berechnen der Fitness gemäß der vorgestellten Formel. Das ausgefüllte Feld liefert alle notwendigen Informationen.
public static float fitness(Genotype<IntegerGene> chromosome) {
Field field = decodeToField(chromosome);
float violations = field.getViolations() + 1;
float letters = field.getLetters() + 1;
float multiUsed = field.getMultiUsedChars() + 1;
float wordCount = field.getWordCount() + 1;
return ((letters * multiUsed * wordCount) / ((violations * violations * violations)));
}
Code 4: Integration aller Teile
Jetzt kann der Evolutionsprozess (Engine) mit Generator und der Fitness-Funktion initialisiert werden. Als wesentliche Steuerungsparameter der Evolution geben wir die Größe der Population (z. B. 2000 Lösungsversuche) und die Wahrscheinlichkeiten für verschiedene genetische Operationen an. Zum Einsatz kommen Mutation und Rekombination (Crossing-Over) mit definierten Wahrscheinlichkeiten.
Das Ergebnis ist ein Java-Stream von Lösungsversuchen. Die Funktion limit() begrenzt diesen Stream auf die maximale Anzahl von Generationen. Meist interessiert nur die beste gefundene Lösung, die man mit dem Aufruf collect(EvolutionResult.toBestGenotype()) erhält.
final Engine<IntegerGene, Float> engine = Engine.builder(Crossword::fitness, gtf)
.offspringSelector(
new RouletteWheelSelector<>())
.populationSize(1500)
.alterers(
new Mutator<>(0.1),
new MultiPointCrossover<>(0.2),
new SinglePointCrossover<>(0.3))
.build();
Genotype<IntegerGene> result = engine.stream()
.limit(2500)
.collect(EvolutionResult.toBestGenotype());
Field field = decodeToField(result);
System.out.println(field.printToString());
Ergebnisse und Fazit
Als Beispiel sind hier Ergebnisse aus unterschiedlichen Programmläufen zu sehen, inklusive der entstandenen Felder, der Fitness und weitere Informationen. Meist werden 10 bis 12 Wörter mit insgesamt 50 Buchstaben in den Feldern versteckt. Für die fertigen Rätsel sind als letzter Schritt die noch leeren Zellen mit zufälligen Buchstaben zu füllen.
_SONNE__
EUTISCH_
RH_A____
DREKLTZE
E__UAL__
APFELB__
FELD_EE_
___DORFL
Fitness: 72.688
Violations:4
Words:13/20
Letters:58 used in multiple words:10
[TISCH, APFEL, GABEL, EULE, KABEL, ERDE, KATZE, FELD, STALL, UHR, ZEIT, DORF, SONNE]
_CAMPUSB
GELDD__U
_SH_BO_R
BO_U_URG
AN_HN_CF
LN_O_D_H
LE_S____
APFELD__
Fitness: 2940.0
Violations:0
Words:11/20
Letters:48 used in multiple words:4
[HUND, BALL, CAMPUS, GELD, BUCH, FELD, APFEL, BURG, HOSE, SONNE, DORF]
Die Resultate zeigen, wie Evolution recht interessante Rätsel erzeugen kann, obwohl (bis auf die Fitness-Funktion) wenige Vorgaben formuliert sind. Das Finden passender Werte für Populationsgröße und der Wahrscheinlichkeiten der genetischen Operationen erfordert meist etwas Erfahrung oder Testläufe. Gerade diese Werte entscheiden zusammen mit einer sinnvollen Fitness-Funktion, wie schnell und sicher gute Lösungen entstehen. Der initiale Einstieg ist mit Hilfe guter Frameworks gering, macht Spaß und führt meist schnell zu ersten Resultaten.
Zumindest ein wichtiger Nachteil des Verfahrens soll erwähnt werden: Es garantiert nicht immer eine gute Lösung zu erstellen. Der Zufall spielt eine entscheidende Rolle. Sehr oft liefert der Ansatz Lösungen, die für einen praktischen Nutzen "gut genug" sind.
Simulierte Evolution bietet sich für Problemstellungen an, die nicht (leicht) analytisch in vertretbarem Aufwand lösbar sind, weil zu viele mögliche Lösungen existieren. Es sollte einfach sein, eine Formel für die Berechnung der Fitness zu formulieren und zu berechnen. Diese Eigenschaft trifft auf erstaunlich viele Aufgaben zu.
Ein interessantes Beispiel für die professionelle Anwendung stellt Ray Kurzweil in seinem Buch "How to create a Mind" vor [7]. Ein Kapitel beschreibt, wie simulierte Evolution hilft, gute Konfigurationen für neuronale Netze zur Spracherkennung zu finden.
