Ameisenkolonie in C++
Eine Ameisenkolonie in C++ implementiert? Nicht ganz, es geht um einen weiteren Algorithmus zur Pfadsuche. Im letzten Artikel habe ich euch ja bereits den AStern in der ClanLib Engine vorgestellt. Nun suchen wir etwas chaotischer, aber dank Ameisentechnologie auch sehr effizient. Wie das geht? Weiterlesen!
Ameisenkolonie in C++
Viele unserer Technologien entstanden einfach dadurch, dass die Menschen die Natur beobachteten. Auch von den Ameisen kann man viel lernen. Sogar wie man effizient einen Weg zum Ziel findet. Das klingt im ersten Moment etwas unglaubwürdig, stimmt aber zu 100%. Ameisen besitzen ein Schwarmwissen. Die einzelne dumme Arbeiterin trägt durch ihr Handeln dazu bei, dass alle weiteren Arbeiterinnen einen Informationsvorteil erhalten. Dieses Konzept ist in der IT die Basis von künstlicher Intelligenz. Die Summe aller Daten ist immer mehr als der einzelne Datensatz – sofern man versteht diese Daten zu nutzen.
Wegfindung im Chaos
Der Algorithmus funktioniert wie folgt:
- eine Ameise läuft zufällig vom Start Richtung Ziel bis sie es erreicht und hinterlässt dabei auf jedem besuchten Feld eine Duftmarke. Eine Heuristik Funktion gibt dabei die Richtung vor (zum Beispiel mit der Manhattan Metrik).
- die nächste Ameise läuft wieder zufällig, besucht aber zu einer höheren Wahrscheinlichkeit ein Feld, dass bereits eine Duftmarke besitzt. Auch diese Ameise hinterlässt wieder eine Duftmarke
- in weitere Folge starten nun immer mehr Ameisen, diese folgen mit höherer Wahrscheinlichkeit dem Pfad mit der stärksten Duftnote
Je mehr Arbeiterinnen losgeschickt werden, desto eher manifestiert sich der ideale Pfad. Da die Arbeiterinnen dennoch hin und wieder zufällig andere Felder besuchen ist der Algorithmus so dynamisch, dass dieser relativ schnell auf Veränderungen reagieren kann (der Weg ist beispielsweise durch eine plötzlich auftretende Wasserpfütze blockiert). Eine Ameise weiß nichts über den idealen Weg – die Information ist aus der Summe der Erfahrungen aller vorangegangener Ameisen für einige Zeit in der Karte gespeichert (bzw. auf dem Erdboden). Die Duftmarken werden langsam wieder schwächer.
Implementierung
Die Implementierung baut auf meinem AStern Beispiel auf und verwendet fast alle dort vorgestellter Klassen. Der Source Code ist wie immer auf meiner GitHub Seite zu finden. Neu ist die Klasse Ant, eine von GameObject abgeleitete Klasse die eine einzelne Ameise repräsentiert. Dargestellt wird das Programm mit der ClanLib Engine.
Der Algorithmus ist in der Ant::move Methode implementiert. Der Source Code ist recht gut dokumentiert, die Ameise bewegt sich um ein Feld auf der Karte weiter. Aufgerufen wird das in der App::compute Methode, so lange bis die Ameise das Ziel erreicht. Sobald das passiert wird eine neue Ameise erzeugt und darf wieder vom Start weg laufen.
Die Ant::move Methode enthält einige Optimierungen. Wichtig ist, dass man die Suche nach einer maximalen Zahl besuchter Felder abbricht, denn durch den Zufallswert kann so eine Ameise schon mal lange unterwegs sein. Außerdem muss abgebrochen werden, wenn kein Pfad gefunden wird, ansonsten endet man in einer Endlosschleife. Besonders wichtig ist die Gewichtung der Pheromone. Diese sind umso stärker, je kürzer der Weg ist. Macht man das nicht, dann findet man zwar einen Weg, der wird aber zufällig sein und kaum der ideale. Man kann gerne mit dem Code herumspielen und testen wie sich die einzelnen Optimierungen auf das Ergebnis auswirken.
Steuerung
Das Programm erlaubt das Setzen von Start (Ameisenhügel) und dem Ziel (Früchte). Die Ameisen starten danach sofort mit der Pfadsuche. Die aktuelle Pheromonspur wird mit Ameisen und einer Zahl (wie stark diese ausgeprägt ist) dargestellt. Man erkennt, dass sich diese langsam an einen optimalen Pfad anpasst. Alle Felder die nicht Start oder Ziel sind lassen sich zwischen Wassen (nicht passierbar) und Erde umschalten, dadurch kann man gut beobachten wie dynamisch der Algorithmus auf die Umgebung reagiert.
Fazit
Die Welt der Ameisen (und generell der Natur) ist sehr faszinierend. Es ist erstaunlich, dass diese einfache Regeln zu einer hoch effizienten dynamischen Wegfindung führen. Die Implementierung des AntColony Algorithmus hat besonders viel Spaß gemacht, man kann ohne die Optimierungen viel Falsch machen und es ist spannend das Chaos, dass die Ameisen dann auf der Karte hinterlassen zu analysieren.
