Finden Ameisen wirklich den kürzesten Weg zu einer Nahrungsquelle?

Es gibt viele Computerintelligenz-Algorithmen, die auf der Beobachtung basieren, dass Ameisen Pheromone so ablagern, dass sie den kürzesten Weg zu Nahrungsquellen finden. Diese Logik wird verwendet, um Computernetzwerke zu optimieren.

Damit kann ich nicht wirklich etwas anfangen. Ich habe gesehen, wie Ameisen einen extrem langen Weg zur Nahrung zurückgelegt haben. Dies ist auch nicht immer aus Sicherheitsgründen der Fall. Was sagen Biologen dazu?

Suchen Sie auf Wikipedia nach "Ameisenmühle" oder YouTube nach "Ameisentodesspirale" und Sie werden feststellen, dass sie Pfade erstellen, die nicht nur suboptimal, sondern tatsächlich insgesamt ungültige Pfade sind.

Antworten (1)

Kurze Antwort

Finden Ameisen wirklich den kürzesten Weg zu einer Nahrungsquelle?

Nein! Aber sie können einen anständigen Weg finden

Längere Antwort

Optimierungsalgorithmen werden verwendet, um einen Möglichkeitsraum zu durchsuchen, der zu groß ist, um jede einzelne Möglichkeit zu erkunden. Solche Algorithmen versuchen, eine ausreichend gute Lösung zu finden, oft ohne notwendigerweise zu wissen, wie „gut“ die gefundene Lösung zur bestmöglichen Lösung ist. Optimierungsalgorithmen finden also nicht immer die beste Lösung. Tatsächlich finden sie meistens nicht den besten Weg, aber einen gut genug in angemessener Zeit.

Gleiches gilt für Ameisen. In der Analogie ist eine Ameisenkolonie ein agentenbasierter Algorithmus, bei dem Agenten Pheromonspuren hinterlassen. Die Konzentration des Pheromons hängt von der Länge der Spur ab. Indem sie den Spuren folgen, die am stärksten riechen, und regelmäßig kleine Fehler machen (damit sie andere Pfade erkunden können), finden sie am Ende eine anständige Lösung. Für mehr Infos einfach googeln Wie finden Ameisen ihren Weg? .

Wenn wir nicht wissen, wie gut die gefundene Lösung im Vergleich zur besten ist, woher wissen wir dann, dass sie gut genug ist?
@Ooker Wie beurteilen Sie, welchen Weg Sie zu Orten einschlagen sollen? Ich denke, Sie werden feststellen, dass Sie es nicht mit dem "besten" Weg (den Sie vielleicht nicht kennen) in Verbindung bringen, sondern mit der Situation, z. B. "ist es in Ordnung, so viel Zeit zu verbringen".
Wenn Sie mit dem Auto zu einem bestimmten Ort fahren, ist der Weg, den Sie nehmen, im Allgemeinen "gut genug" und nicht der beste. Es ist gut genug, weil es eine angemessene Zeit dauert, um zum Ziel zu gelangen ...
@Remi.b "Solche Algorithmen versuchen normalerweise, eine ausreichend gute Lösung zu finden, ohne jemals zu wissen, wie 'gut' die gefundene Lösung für die bestmögliche Lösung ist." - Optimierungsprobleme wissen zwar (in der Regel) was die wahre Lösung ist, können dies aber nicht immer rechnerisch erreichen . Beim Implementieren einer Optimierungsfunktion wird im Allgemeinen ein gewisses Epsilon definiert, wobei, wenn der Fehler der berechneten Lösung kleiner als Epsilon ist, die Lösung des Optimierungsalgorithmus als "nah genug" akzeptiert wird.
@Remi.b Wenn ein Optimierungsalgorithmus die wahre Lösung nicht kennt, die er zu erreichen versucht, hat er keine Möglichkeit, eine potenzielle Lösung zu validieren. Ich gebe zu, es gibt definitiv viele Fälle, in denen keine wahre Lösung bekannt ist, aber dies ist viel häufiger in der theoretischen Arbeit als in den viel praktizierteren, angewandten rechnerischen Ansätzen.
@Charles Danke, ich habe eine kleine Änderung mitgebracht, um zu vermeiden, dass ein Optimierungsalgorithmus nie weiß, was die beste Lösung ist.
@ Charles Ich stimme nicht zu. Sie können die Stärke einer Lösung gegen andere mögliche Lösungen testen. Sie müssen die Entfernung der bestmöglichen Route zu einem Ort nicht kennen, wenn Sie 1.000 mögliche Routen ausarbeiten und dann die kürzeste davon nehmen
@Tom.Bowen89 Wenn Sie eine Sammlung von Lösungen haben und nur eine Lösung gegen andere testen, wie können Sie dann sicher sein, dass eine dieser Lösungen auch nur annähernd der benötigten Ausgabe entspricht? Es muss eine Art „beliebteste Ausgabe“ definiert werden, sonst „kann man den Wald nicht zwischen den Bäumen sehen“. Das heißt, es muss eine ideale Lösung oder minimale Fehlertoleranz definiert werden. Wenn nicht, besteht kein Vertrauen in die Genauigkeit Ihres Algorithmus und die von ihm erzeugten Ergebnisse.
@ Tom.Bowen89 Ich werde auch hinzufügen, dass sie bei vielen Optimierungsproblemen einen probabilistischen Ansatz verfolgen, sodass mehrere Instanzen (Sammlungen von Lösungen, die aus unterschiedlichen Anfangsbedingungen stammen) des Algorithmus vorhanden sein müssen. Das heißt, dass jede Instanz des ausgeführten Algorithmus völlig unterschiedliche Lösungssätze erzeugt. Davon abgesehen muss wiederum eine Art gewünschtes Ergebnis definiert werden, um die Genauigkeit dieser Lösungen zu beurteilen.
@Tom.Bowen89 Also, um von Ihrem Beispiel des kürzesten Weges abzuweichen. Was ist, wenn der wahre kürzeste Weg 10 Meilen lang ist, die beste Lösung, die Ihr Algorithmus erzeugt, jedoch 50 Meilen ist? Wie können Sie die Genauigkeit beurteilen, wenn Sie keine Vorstellung vom wahren kürzesten Weg haben? Dies ist wichtig, da, wie in meinem vorigen Kommentar erwähnt, der Algorithmus erneut ausgeführt werden muss, um andere potenzielle Lösungen zu erhalten, wenn die beste Lösung immer noch sehr weit von der wahren Lösung entfernt ist. Es muss eine Art "externe" Bewertung der Leistung und Genauigkeit Ihres Algorithmus geben.
@Tom.Bowen89 Ich empfehle Ihnen, sich mit simulierten Annealing-Algorithmen zu befassen, da dies eine gängige Plattform in der Informatik ist, um die Dynamik von Optimierungs- und Approximationsalgorithmen einzuführen. en.wikipedia.org/wiki/Simulated_annealing
@Charles gibt es eine Möglichkeit, das Vertrauen in die Genauigkeit des berechneten Pfads zu berechnen? Korrigieren Sie mich, wenn ich falsch liege, aber kann in der Statistik das Vertrauen einer Vermutung nicht unabhängig mit dem richtigen Wert berechnet werden?
@ooker Sie können das Vertrauen nicht berechnen, ob Sie den besten Weg haben, indem Sie nur Stichproben durchführen (Lösungen ausprobieren und sehen, welche funktionieren), es sei denn, Sie können den gesamten Zustandsraum brutal erzwingen. Wenn Sie jedoch etwas über Ihren Zustandsraum wissen, können Sie anhand dieser problemspezifischen Informationen feststellen, wie gut Ihre Lösung ist. Wenn Sie beispielsweise wissen, dass der Raum differenzierbar ist, können Sie alle Informationen verwenden, die Sie möglicherweise über die maximalen Ableitungen kennen, um eine Ober-/Untergrenze zu erstellen.
@Charles: "Wenn ein Optimierungsalgorithmus die wahre Lösung, die er zu erreichen versucht, nicht kennt, hat er keine Möglichkeit, eine potenzielle Lösung zu validieren." - Das stimmt nicht - sehr oft lautet das Kriterium im wirklichen Leben "Lösung muss weniger als X kosten". Wenn eine Lösung gefunden wird, die weniger als X kostet, ist sie "gut genug" und daher gültig. Wenn es viel weniger als X ist, umso besser. Es ist nicht erforderlich, den absolut besten erreichbaren Wert zu kennen. Der Wert von X hängt von den (externen) Einschränkungen des Projekts ab, nicht von den Parametern des Optimierungsproblems selbst.
Das ist genau das, was ich in einem früheren Kommentar gesagt habe, lol. Bitte lesen Sie alle Kommentare, bevor Sie versuchen, jemanden zu korrigieren. "Bei der Implementierung einer Optimierungsfunktion wird im Allgemeinen ein gewisses Epsilon definiert, bei dem, wenn der Fehler der berechneten Lösung kleiner als Epsilon ist, die Lösung des Optimierungsalgorithmus als "nah genug" akzeptiert wird."
@Charles: Ich habe diesen Kommentar gelesen und er unterscheidet sich von dem, was ich sage. Ich sage nicht, dass Sie ein Epsilon definieren, das einen akzeptablen (proportionalen oder absoluten) Unterschied zwischen dem wahren optimalen Wert und dem besten gefundenen Wert ergibt - das erfordert immer noch eine a priori Kenntnis des optimalen Werts. Ich sage stattdessen, dass Sie einen Schwellenwert X definieren, der unabhängig vom optimalen Wert ist - dh es interessiert Sie eigentlich überhaupt nicht, wie nah Sie am wahren Optimum sind, sondern nur, ob Sie eine Lösung finden, die in welchem ​​Kontext auch immer "funktioniert". operieren in.
@psmears Wie Sie die Heuristik definieren, ist nicht immer konsistent und zu schwer zu verallgemeinern, weshalb Ihre Aussagen nicht gültig sind. Es ist von Algorithmus zu Algorithmus unterschiedlich, was letztendlich auf Informationen basiert, die Sie bereits bei der Entwicklung des Algorithmus erhalten haben.
Kommentare sind nicht für längere Diskussionen gedacht. Bitte verfolgen Sie dies im Chat (und eventuell auf einer CS SE-Site).
@Charles: Sie verwechseln den Algorithmus mit der Problemdomäne und insbesondere mit dem Akzeptanzkriterium des Problems (für die Ameisen vielleicht: Übersteigt die Energie in der Nahrung am Ende dieses Pfads die Energie, die für den Pfad aufgewendet wird, um sicherzustellen Überleben?) mit dem Stoppkriterium/der Heuristik eines bestimmten Algorithmus ("OK, wir haben genug Zeit und Energie darauf verwendet, Pfade zu überprüfen, jetzt steigen wir ein und essen."). Ersteres wird wahrscheinlich die Wahl des Letzteren beeinflussen, aber es ist wichtig, sich der Unterscheidung bewusst zu sein. Viel Erfolg im Studium, dein Proteinprojekt hört sich cool an :)
@ Pimgd xkcd.com/85
Finden Ameisen wirklich den kürzesten Weg zu einer Nahrungsquelle?
AntwortenHierDatenschutz-Bestimmungen1y, 0v