Ich bin ein Student, der an einem Ameisenkoloniesimulator für ein Kursprojekt arbeitet. Der Algorithmus dafür ist (offensichtlich) ein Ameisenkolonialgorithmus. Ich weiß, dass es verschiedene Formen des Algorithmus gibt, aber all diese waren uns zu detailliert, sodass wir einen Ansatz gewählt haben, bei dem wir:
- Eine Ameise wird in einer Kolonie geboren und muss Nahrung von einer Quelle sammeln, um die Kolonie zu erhalten.
- Alle Ameisen sind ähnlich.
- Der Bereich, in dem sich die Ameise bewegt, ist ein 1000x1000-Gitter, sodass jeder Gitterpunkt als gültiger Punkt für eine Ameise dient. Bei allen Algorithmen, auf die ich gestoßen bin, werden Scheitelpunkte und Kanten getrennt behandelt, aber da wir die Ameisenbewegung auf nur vier Richtungen beschränken (nach oben, unten, links, rechts), ist es wohl egal, wo wir das Pheromon platzieren.
- Die oben genannten Gitterpunkte speichern das Pheromon.
- Eine Ameise lässt Pheromon nur fallen, wenn sie Nahrung trägt.
- Für eine Ameise an einer Position (i, j) entscheidet sie, wohin sie sich im nächsten Schritt bewegen soll, indem sie die Pheromonmengen an ihren vier benachbarten Knoten in einer einfachen Wahrscheinlichkeitsformel berücksichtigt, dh die Wahrscheinlichkeit, zu einem Knoten zu reisen, ist gegeben durch (Pheromonmenge an einem bestimmten benachbarten Knoten) / (Summe der Pheromonmengen in 4 benachbarten Knoten).
- Eine Ameise kann nicht zu der Position zurückkehren, von der sie gerade gekommen ist. Es kann dies nur tun, wenn es sich an einem Ort befindet, an dem es Nahrung gibt, oder wenn es sich in seiner Kolonie befindet.
Jetzt ist meine Sorge (und was in unserem Programm tatsächlich passiert), dass wenn eine Ameise ZUERST eine Position erreicht, die Futter enthält und es aufnimmt, sie sich auf die Art und Weise, wie unser Algorithmus funktioniert, überall bewegen kann! Dies liegt daran, dass es nur eine Pheromonspur hinterlässt, wenn es das Futter hat und nicht vorher, und da es die erste Ameise ist, gibt es keine existierende Spur.
Wenn sich die Ameise irgendwo bewegen kann, tendieren die Ameisen, die die Nahrungsquelle erreichen, ebenfalls dazu, ihr zu folgen. AUCH WENN sie sich nicht zurück in Richtung der Kolonie bewegt. Dies macht den Zweck des gesamten Algorithmus zunichte.
Also meine Fragen sind
- Ist das obige Anliegen gültig? Wenn nein, warum dann? Wenn ja, wie soll man damit umgehen?
- Müssen wir einige Änderungen an unserem grundlegenden Verständnis des Algorithmus vornehmen, damit er tatsächlich funktioniert?
- Was sind noch andere subtile, aber wichtige Dinge, die Neulinge wie ich in diesem Fall vermissen könnten?
quelle
Antworten:
So funktioniert ACO nicht. ACO lässt Pheromone erst dann fallen, wenn sich Ameisen über alle Punkte des Gitters bewegt haben. Sie werten dann etwas aus (möglicherweise Gesamtreisezeit) und lassen dann Pheromone für gute Ameisen fallen und wiederholen.
Sie werden im Allgemeinen nicht zweimal auf denselben Scheitelpunkt verschoben, obwohl Sie dies aus Gründen der Implementierungsspezifität anpassen können.
Pheromone fallen nicht bei jeder Bewegung, sie fallen, nachdem sie sich überall bewegt haben, und es wird bewertet , welche Ameisen besser sind. Ameisen, die besser sind als Phereomone (vielleicht die besten Ameisen mit 25% Leistung).
quelle
Die Implementierungen, die ich von anderen gesehen habe und die ich für mich selbst geschrieben habe, haben die Ameisen immer dazu gebracht, die Pheromone auf dem Weg zum Essen freizusetzen, sobald sie das Essen erreicht haben. Das heißt, die Ameisen marschieren nach einem zufälligen Spaziergang von ihrer Kolonie zum Futter. Die Wege, die die Ameisen von der Kolonie zum Futter zurücklegen, werden erst dann mit Pheromonen markiert, wenn die Ameisen das Futter erreicht haben. Die Rückfahrt wird nicht explizit simuliert. Im Allgemeinen durchlaufen mehrere Ameisen ihren Lauf, bevor Pheromone für die aktuelle Iteration abgelegt werden. Die Pheromone werden dann für die erfolgreichen Pfade eingesetzt, und eine neue Runde beginnt.
Normalerweise werden die Chancen der Ameise, in einen bestimmten Knoten zu gelangen, mit der Menge an Pheromon mal einem Maß an "Güte" gewichtet. Zum Beispiel könnte das Maß für die Güte so etwas wie das Gegenteil des Abstands zwischen der Ameise und dem Futter sein - dies hält die Ameisen davon ab, sich auf das Futter zu zubewegen, unabhängig von vorherigen Pheromonablagerungen. Die Güte könnte weiter gewichtet werden, um andere Faktoren zu berücksichtigen, z. B. könnten einige Knoten leichter zu durchlaufen sein als andere. Und wie Enderland hervorhebt, gibt es normalerweise eine Form der Pfad- "Auswahl", sobald alle Ameisen ihre Kurse erfolgreich absolviert haben, wobei nur ein Teil der "besten" Pfade für die Pheromonablagerung ausgewählt wird. Sie sollten jedoch auch ohne Auswahl vernünftige Pfade erhalten,
quelle