Talk To My Hand

Heute wurde bei CosmoCode gepokert und ich wurde, wie schon die meisten Male beim Kickern, vernichten geschlagen. Gespielt wurde Texas Hold’em, ohne Geldeinsätze aber um die Ehre, die ich also jetzt verloren hab’.

Immerhin konnte ich vorher meinen GA (Genetischen Algorithmus) weiter verfeinern. Die Kartenbeschriftungen bewegen sich nun auf einer Kreisbahn um ihren jeweiligen Fixpunkt und werden beim mutieren an eine zufällige Position auf dem Kreis bewegt. Dadurch ist das Problem mit der relativen Nähe erstmal gelöst. Weiterhin sollten alle Beschriftungen zur Kartenmitte orientiert sein, dazu wird der Cosinus des Schnittwinkels zwischen folgenden zwei Vektoren errechnet: Vektor a = Beschriftung zur Kartenmitte und Vektor b = Beschriftung zum Fixpunkt. Je größer der Cosinus, desto kleiner ist der Bereich zwischen den Vektoren. Außerdem werden Überschneidungen nun mathematisch korrekt berechnet und auch entsprechend bewertet, was die Fitness eines Chromosomes angeht.

Charles Darwin, Gregor Mendel & ich

Was hat Willi denn mit denen gemeinsam?
werdet ihr euch sicherlich fragen. Sehen wir uns das genauer an:

Na gut, der einen hat einen Bart und der andere ne Brille. Aber was haben die denn sonst mit Willi gemeinsam?

Ich gebe zu, es ist vielleicht etwas übertrieben, aber auch mir ist ein (persönlicher) Erfolg auf dem Gebiet der Genetik gelungen. Wie ihr euch vielleicht schon denken könnt, habe ich heute meinen ersten genetischen Algorithmus (nahezu) fertiggestellt. Da ich (leider) mit JavaScript arbeite konnte ich bis jetzt keine Messungen mit realistischen Werten (Anzahl der Chromosomen und Evolutionsschritte bzw. Generationen) durchführen, allerdings wird bereits mit nur einer 10-Chromosomen-starken Population und im Schnitt 25 Generationen bereits ein besseres Ergebnis erreicht, als vorher (Greedy).

Nochmal zur Rekapitulation: Meine Aufgabe besteht darin, auf einer Landkarte bestimmte Punkte von Interesse (POI, Stadt, was auch immer) dynamisch mit Beschriftungen zu versehen. Diese Beschriftungen sollen sicht nicht überschneiden, sollten in einem akzeptablen Abstand zu ihrem jeweiligen Punkt stehen und nach Möglichkeit zur Kartenmitte orientiert sein.
Mein Algorithmus arbeitet nun wie folgt:

Er erzeugt eine zufällige Startpopulation bestehend aus einer frei wählbaren Anzahl von (potenziellen) Lösungen, genannt Chromosome. Diese Population wird wiederum über mehrere Generationen (=Schleifendurchläufe) hin entwickelt

Einige Gene (Bestandteile der Chromosome) werden zufällig ausgewählt und wiederum zufällig verändert (Mutation). Im zweiten Schritt wird die Population verdoppelt, in dem immer zwei Chromosomen der Ursprungspopulation gekreuzt werden (Rekombination), wodurch verwandte, artähnliche Nachkommen entstehen. Zu guter letzt wird selektiert. Hierbei werden immer zufällig zwei Chromosomen der Population entnommen und direkt gegeneinander verglichen. Wer näher an den gewünschten Kriterien ist, bleibt drin, der andere wird entfernt.

Das wird solange wiederholt, bis entweder eine festgelegte Anzahl von Generationen überschritten oder aber ein passender Kandidat gefunden wurde.

Prof. Dr. Schiele wäre so stolz auf mich

Es entwickelt sich

Der Lösungsansatz, mit dem ich mich die letzten Tage beschäftigt habe, ist ein leicht modifizierter Greedy-Algorithmus. Nach einigen Tests und der Erkenntnis, dass er nicht in allen Fällen zufriedenstellende Ergebnisse liefert, bin ich heute dazu übergegangen, einen genetischen Algorithmus zu entwickeln. Wen es interessiert, hier ist der Wikiartikel über Genetische Algorithmen im Allgemeinen und hier der über ein sehr artverwandtes Problem.
Im aktuellen Stadium erzeugt mein Algorithmus bereits eine Population bestehend aus einer frei wählbaren Anzahl von zufällig erzeugten (potenziellen) Lösungen, die sich über eine bestimmte Anzahl Generation oder Evolutionsstufen hinweg weiterentwickeln. Im Moment ist die einzige implementierte Art der Entwicklung eine zufallsgesteuerte Mutation einzelner Positionswerte (bsp. einer Landkartenbeschriftung).

PS:
Ich hab’ heute schon wieder beim Kickern gewonnen. Oder anders ausgedrückt: Tilo hat, trotz meines Zutuns, nicht verloren.

läuft.

Eine Nacht drüber schlafen, einmal kurz drüber nachdenken und dann alles nochmal neumachen hilft also. Mein Algorithmus und ich verstehen uns jetzt besser. Er macht ab und zu noch wenig nachvollziehbare Sachen, im Großen und Ganzen liegen wir aber auf derselben Wellenlänge.