Guten Tag,
ich habe mich mal an mutierende Algorithmen als Amateur Programmierer herangewagt. Mein erstes Projekt ist ein Algorithmus, welcher den effizientesten Weg durch ein Labyrinth finden soll (Ich weiß, dass A* besser ist).
Ich bin wie folgt vorgegangen:
- Labyrinth als zwei dimensionales Array (0 = Frei, 1 = Mauer)
- Start- und Endpunkt festgelegt
- STart Population erstellt aus zufälligen Pfaden (Ein Pfad ist ein Array, welches als Elemente 0,1,2 oder 3 enthalten, welche wiederum die Bewegungsrichtung vorgeben, die anschließend abgelaufen wird. Bspw. Hoch, hoch, links, rechts, runter.
- Dann score für jeden Agent aus Entfernung zum Ziel (Satz des Pythagoras) und Länge des Pfades gebastelt. Kürzere Entfernung gibt mehr Punkte, unnötiger Weg Abzug
- Danach werden für die 500 neuen agents jeweils zwei Eltern mit der Wahrscheinlichkeit basierend auf dem Score ausgewählt.
- Das „Kind“ wird aus den zwei Hälften der Pfade der Eltern erstellt, wobei jedes Element des neuen Pfades eine Chance hat zu mutieren (Hier sehe ich bedarf zur Verbesserung)
- Dies wiederholt sich solange ich will
Mein Problem ist, dass es bei kleinen Labyrinths den weg auch findet, aber die Wege noch teilweise sehr unnötig sind, obwohl ab dem Punkt, wo die meisten agents das Ziel erreichen, ja der längere weg rausselektiert werden sollte. Hatte überlegt auch minus punkte zugeben, wenn eine wand oder der Rand berührt wird, aber das hat nicht so funktioniert.
Mich würden eure Gedanken dazu interessieren und einfach ein paar Tipps zu der Thematik.
Code: https://hastebin.skyra.pw/aboladewoc.java
