Schwarmintelligenz in der Tourenplanung

Inhaltsverzeichnis

Inhaltsverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

Abbildungsverzeichnis

1 Einleitung
1.1 Problemstellung
1.2 Zielsetzung dieser Arbeit

2 Futtersuche bei natürlichen Ameisen

3 Travelling Salesman Problem

4 Ameisenalgorithmen
4.1 Ant System (AS)
4.2 Ant Colony System (ACS)

5 Konzeption und Umsetzung eines didaktischen Beispiels
5.1 Modellierung
5.2 Umsetzung des Beispiels in einen Algorithmus
5.3 Implementierung eines weiteren TSP
5.4 Evaluation des ACO-Algorithmus

6 Resümee

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

Abbildung 1: Doppelbrücken – Experiment, mit zwei unterschiedlich langen Wegen zur Futterquelle 3

Abbildung 2: Ergebnisse des Doppelbrücken-Experiments, wobei ein Weg von dem Nest zur Futterquelle doppelt so lang ist als der andere Weg 5

Abbildung 3: Beispiel eines ungerichteten Graphen, wobei dij, die Distanz von Knoten i zu Knoten j angibt 8

Abbildung 4: Wahrscheinlichkeit zur Auswahl des nächsten Knotens 9

Abbildung 5: Ant System Algorithmus zur Lösung des TSP) 12

Abbildung 6: ACO Algorithmen, Überblick über den Namen, den Autor, das Jahr und die Kompatibilität des Algorithmus auf das TSP 15

Abbildung 7: Parameterdefinition 16

Abbildung 8: Einfaches TSP-Beispiel mit 4 Städten 17

Abbildung 9: Heuristische Informationen, berechnet 18

Abbildung 10: Kumulierte Wahrscheinlichkeiten 20

Abbildung 11: Umsetzung von Beispiel 5.1 in ein Koordinatensystem 22

Abbildung 12: ACO Parameterangabe im Algorithmus 23

Abbildung 13: Ergebnisse aus MATLAB 24

Abbildung 14: Koordinaten von 11 Städten24

Abbildung 15: Ergebnisse aus MATLAB bei einem TSP mit 11 Städten im 1.Versuch 25

Abbildung 16: Ergebnisse aus MATLAB in mehreren Durchläufen 26

Abbildung 17: Ant System Algorithmus im Vergleich zu Tabu Search (TS) und Simulated Annealing (SA) 27

Abbildung 18: Vergleich der Performance von ASC mit anderen Algorithmen (Durchschnittliche Länge einer Tour in 25 Durchläufen) 28

1 Einleitung

1.1 Problemstellung

Im Zuge zunehmenden Wettbewerbsdrucks auf Lieferantenmärken rückt ein Gebiet der kombinatorischen Optimierungsprobleme immer mehr in den Fokus der Forschung: die Klasse der Tourenplanungsprobleme. Gegenstand der Tourenplanung ist die Aufgabe, Touren zu geografisch verteilten Kunden nach bestimmten Zielvorgaben (z.B. kostenminimal) zu bestimmen.

Eines der bekanntesten kombinatorischen Optimierungsprobleme stellt das Problem des Handlungsreisenden (engl.: Travelling Salesman Problem (kurz: TSP)) dar. Ein Handlungsreisender soll in einer Rundreise (kurz: Tour) n vorgegebene Städte besuchen. Er startet dazu in einer dieser Städte, besucht nacheinander einmalig die übrigen Städte und kehrt schlussendlich zu der Anfangsstadt zurück. Es gilt dabei, die Tour mit minimaler Gesamtlänge zu finden. Die Zahl aller möglichen Rundreisen wächst mit der Städteanzahl n sehr rasch. Sind von einem Depot aus beispielsweise nur neun Städte anzufahren (n=10), so sind hier schon zur exakten Lösung 181.440^[1] Touren zu berechnen. Es ist somit erkenntlich, dass optimale Lösungen, z.B. durch vollständige Enumeration^[2], bei einer realistischen Größenordnung von täglich hunderten von Transportaufträgen mit vertretbarem Rechenaufwand nicht möglich sind. Geeignete Verfahren zur Lösung des Problems stellen daher beispielsweise approximierende Algorithmen bzw. Heuristiken dar. Es handelt sich bei Heuristiken um Algorithmen, die häufig gute^[3], wenn auch nicht exakte, jedoch annähernd optimale Lösungen in annehmbarer Rechenzeit hervorbringen. In den letzten beiden Jahrzehnten zeigte sich ein verstärktes Interesse an Verfahren, die von der Natur inspiriert sind. In Bezug auf das Travelling Salesman Problem wurde ein Phänomen bei Ameisenkolonien betrachtet und erforscht. In der Kolonie finden Ameisen stets den kürzesten Weg von ihrem Nest zu der Futterquelle, obwohl sie stark eingeschränkte visuelle Fähigkeiten^[4] besitzen. Das Phänomen ist auf der indirekten Kommunikation unter den Ameisen zu begründen, denn die Tiere hinterlassen auf ihrem Weg einen Duftstoff^[5], den die anderen Ameisen wahrnehmen und so dem Weg folgen. Dadurch, dass die Duftmenge durch jede Ameise, die dem Weg folgt, akkumuliert, verringert sich die Wahrscheinlichkeit für die Wahl eines alternativen Pfades der Ameisen und die kürzeste Strecke etabliert sich.

1.2 Zielsetzung dieser Arbeit

Das Ziel der folgenden Arbeit ist es, eine Konzeption und die dazugehörige Umsetzung eines didaktischen Beispiels für den Einsatz eines schwarmbasierten Algorithmus in der Tourenplanung zu erstellen. Um dieses Ziel zu erreichen, wird der Ameisenalgorithmus untersucht

und in einem Beispiel mit selbst definierten Parameterwerten modelliert. Anschließend wird der Algorithmus mittels einer geeigneten Software implementiert; dabei bilden die Parameterwerte aus dem erstellten Modell die Inputdaten.

Die grundlegende Fragestellung dieser Arbeit ist die Möglichkeit, Optimierungsmethoden durch das Verfahren aus der Natur analog auf das Travelling Salesman Problem anzuwenden. Das Verhalten der Ameisen bei der Futtersuche ist hierbei Gegenstand der Untersuchung. Eine wichtige Frage ist dabei ist zum einen die Umsetzung der natürlichen Begebenheiten in einen Algorithmus, die es zu erörtern gilt. Zum anderen soll eruiert werden, warum sich das Travelling Salesman Problem als gutes Anwendungsbeispiel für den Einsatz des Ameisenalgorithmus herausstellt. In einem didaktischen Beispiel wird die Performance des Algorithmus bewertet, sodass als Ergebnis dieser Arbeit die Vorstellung, Konzeption, Umsetzung und Evaluation des Ameisenalgorithmus herauskommt.

2 Futtersuche bei natürlichen Ameisen

Ameisen weisen ein komplexes soziales Verhalten auf, welches die Menschen seit Jahrzehnten fasziniert. Das wahrscheinlich am meist betrachtete Phänomen ist die Entstehung einer sogenannten Ameisenstraße. Als Individuen sind Ameisen relativ eingeschränkt in ihren kognitiven Fähigkeiten. In der Gruppe können sie sich allerdings so gut organisieren, dass selbst komplexe Probleme wie die Futtersuche schnell zu lösen sind. Die Komplexität des Verhaltens entsteht nicht etwa auf der Ebene des Individuums, sondern erst durch die lokale Interaktion zwischen den Individuen und ihrer Umwelt: Was eine einzelne Ameise nicht bewerkstelligen kann, wird durch die sogenannte „Schwarmintelligenz“ möglich. Interessant ist die Fähigkeit der Ameisen stets den kürzesten Weg zur Futterquelle zu finden.^[6] Biologen haben durch Experimente aufgezeigt, dass dieses Phänomen durch die Kommunikation zwischen den Ameisen, basierend ausschließlich auf den Pheromonen (griech.zustande kommt.^[7] Dabei handelt es sich um einen chemischen Geruchsstoff, welchen Ameisen ausstoßen und wahrnehmen können. Dieses Prinzip wird auch Stigmergie (engl. Stigmergy) genannt, d.h. zur Wegesuche kommunizieren Ameisen ausschließlich indirekt über die Pheromonablagerungen.^[8]

Im Folgenden wird auf das Phänomen des kürzesten Weges eingegangen und anhand eines Beispiels das Prinzip der Pheromone erläutert.

Das Doppelbrücken-Experiment (engl. Double – Bridge – Experiment)

Auf der Suche nach Nahrung hinterlässt jede Ameise ihren individuellen Duftpfad. Folglich erschließen die Ameisen im Kollektiv ein für das Auge unsichtbares Netz an möglichen Strecken zur Futterquelle. Wie sich aus der Anzahl der möglichen Strecken schlussendlich der kürzeste Weg zur Futterquelle herausbildet, wurde in dem sogenannten „Doppelbrücken-Experiment“^[9] anhand der argentinischen Ameise Linepithema humile untersucht. Bei dem Experiment wurde ein Ameisennest und eine weiterliegende Futterquelle angebracht, die ausschließlich über zwei Brücken zu erreichen ist, wobei eine der beiden Brücken deutlich kürzer ist (siehe Abbildung 1).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Doppelbrücken – Experiment, mit zwei unterschiedlich langen Wegen zur Futterquelle (Quelle: Dorigo, M.; Stützle, T. (2004), S.3)

Nacheinander verlassen die Ameisen nun das Nest. Da die Ameisen praktisch blind^[10] sind, können sie nicht erkennen, welcher der beiden Strecken kürzer ist und wählen somit anfangs zufällig und mit der gleichen Wahrscheinlichkeit einen der beiden Wege aus, da noch keine Pheromone vorhanden sind. Jeder Weg wird von den Ameisen mit Pheromonen markiert; die Ameisen, welche die kürzere Strecke wählen, sind schneller an der Futterquelle und treten früher den Rückweg zum Nest an. Dadurch befindet sich auf dem kürzeren Weg eine erhöhte Menge des Pheromons, da dieser doppelt beim Hin- und Rückweg der Ameisen begangen wird. Die höhere Menge an Pheromonen führt dazu, dass sich eine höhere Zahl an Ameisen für diesen Weg entscheiden. Das bedeutet, dass nach kurzer Zeit aufgrund der indirekten Kommunikation durch die Pheromone mit hoher Wahrscheinlichkeit nur noch der kürzere Weg zur Futterquelle gewählt wird. Das Prinzip wird auch Autokatalyse genannt: Je mehr Pheromon bereits auf einem Weg vorzufinden ist, desto mehr Ameisen wählen diesen Weg; je mehr Ameisen einem Weg folgen, desto mehr Pheromon wird auf ihm abgelegt.^[11]

Die Pheromone haben dabei eine entscheidende Eigenschaft: Sie verdampfen mit der Zeit, was mit dem Begriff Evaporation bezeichnet wird. Das heißt, auch wenn anfangs nur ein Teil der Ameisen dem kürzesten Pfad folgt und mehrere Ameisen zunächst auf einem längeren Pfad bleiben, wird der kürzeste Pfad im Laufe der Zeit immer mehr Ameisen anlocken^[12]. Einige Ameisen folgen trotz der Spuren des Pheromons alternativen Wegen, was das Erforschen von neuen Wegen sicherstellt. Das Ergebnis in Abbildung 2 lässt jedoch erkennen, dass der Großteil (80-100%) der Ameisen sich für den kürzeren Weg zur Futterquelle entscheidet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Ergebnisse des Doppelbrücken-Experiments, wobei ein Weg von dem Nest zur Futterquelle doppelt so lang ist als der andere Weg (Quelle: Dorigo, M.; Stützle, T. (2004), S.3)

3 Travelling Salesman Problem

Inspiriert von dem Experiment von Goss et al^[13]., konzipierte Marco Dorigo et al. 1991 eine Heuristik zum Lösen des Travelling Salesman Problems. Informal lässt sich das TSP folgendermaßen definieren: Ein Kaufmann möchte n unterschiedliche Städte bereisen und dabei jede Stadt einmal besuchen, es gilt die kürzeste Strecke zwischen den Städten zu finden.^[14] Das Problem wird anhand eines Graphen dargestellt, wobei die Städte als Knoten und die Strecken zwischen ihnen als Kanten definiert sind. Dorigo war der Erste^[15], welcher das Schema der Futtersuche bei Ameisen auf ein klassisches, kombinatorisches Optimierungsproblem übertrug. Bei dieser Art von Optimierungsproblemen entstehen die Lösungen durch Kombinieren und Reihen von Lösungselementen.^[16] Ferner handelt es sich bei dem Travelling Salesman Problem um ein NP-hartes Problem. Die Komplexität eines NP-harten Problems wächst mit der Anzahl der zu untersuchenden Elemente exponentiell^[17], d.h. dass bei einer Bildung von Reihenfolgen für n Elemente n! verschiedene Möglichkeiten existieren. Da schon mittlere Rechenprobleme für die exakte Berechnung die zur Verfügung stehende Rechenzeit übersteigt, wird meist nicht nach der besten Lösung, sondern nach einer möglichst guten Annäherung mittels einer Heuristik gesucht. Ameisenalgorithmen sind den Metaheuristiken zuzuordnen und scheinen daher für das NP-harte Problem des Travelling Salesman bestens geeignet. Diesem Anwendungsbeispiel liegt eine vollständige Strukturbeschreibung bezüglich der Lage und Anzahl der zu besuchenden Städte sowie die Entfernungen zwischen ihnen zugrunde. Diese Struktur kann damit problemlos in ein Graphenmodell umgesetzt werden. Dorigo et al. nannten darüber hinaus weitere Gründe, warum sie sich für das TSP zur Untersuchung entschieden haben:

- Es handelt sich um ein „Shortest Path Problem“^[18], weshalb das Vorgehen in Ameisenkolonien leicht zu adaptieren ist.
- Es wurde intensiv erforscht, weshalb es viele Testszenarien mit vergleichbaren Werten gibt.
- Es ist ein didaktisches Problem, was Selbiges einfach zu verstehen macht^[19]

Da Dorigo et al. unter anderem einen wesentlichen Einfluss zur Entstehung und Entwicklung von Ameisenalgorithmen beigetragen haben, wird im Folgenden auf deren Literatur, insbesondere auf das Buch „Swarm Intelligence: From Nature to Artificial Systems", Bezug genommen.

4 Ameisenalgorithmen

Wie aus dem in Kapitel zwei geschilderten Ameisenverhaltens bei der Futtersuche hervorgeht, führt die kollektive Lösungsstrategie nach einiger Zeit zu einem kürzesten Pfad. Diese Beobachtung erweckte das Interesse im Hinblick auf die möglich erscheinende Erstellung eines Optimierungsverfahrens. Das von Dorigo et al. entworfene Ant System (AS) stellt dabei den einfachsten Algorithmus nach dem natürlichen Vorbild dar. Neben diesem wird im Folgenden auch der Algorithmus Ant Colony System (ACS) vorgestellt, der eine Erweiterung des AS darstellt. Der Begriff „Ant Colony Optimization“ (kurz: ACO) bezeichnet dabei jede Variante eines Ameisenalgorithmus. Künstliche Ameisen werden bei ACO Algorithmen ihren natürlichen Vorbildern nachempfunden. Um eine eindeutige Unterscheidung zwischen natürlicher und künstlicher Ameisen zu erhalten, werden die künstlichen Ameisen im Folgenden mit dem Begriff „Ant“ betitelt.

Zunächst wird ein Modell für künstliche Ameisen vorgestellt, das die Basis für die vorgestellten Algorithmen liefert.

4.1 Ant System (AS)

Im Folgenden wird von einem Modell ausgegangen, das bestimmte vordefinierte Strecken der Ants abbildet, und sich somit von dem natürlichen Vorbild unterscheidet, bei dem die Strecken willkürlich begangen werden können. Abgebildet wird das Modell durch einen Graphen, der aus Knoten und Kanten besteht. Die Stationen eines Weges werden als Knoten bezeichnet; durch Kanten werden diese wiederum miteinander verbunden.

Zudem wird von einem nicht gerichteten Graphen ausgegangen. Bei einem nicht gerichteten Graphen entspricht die Distanz von Knoten i zu Knoten j immer auch der Distanz des umgekehrten Weges von Knoten j zu Knoten i, im Gegensatz zu einem gerichteten Graphen, bei welchem die Distanz der Strecke von Knoten i zu Knoten j unterschiedliche Werte im umgekehrten Fall aufweisen kann. Im Falle eines gerichteten Graphen, handelt es sich um ein symmetrisches TSP. Mit dem Ant System können Probleme beider Fälle gelöst werden. Im Folgenden wird der Verständlichkeit halber ein nicht gerichteter Graph betrachtet.

Die Entfernung von einem Ausgangsknoten i zu Knoten j wird mit dij angegeben, dabei stellt dij die Gewichtung der einzelnen Kanten dar. Die Anzahl der Ameisen wird mit m definiert. Abhängig von der Art des Ameisenalgorithmus sollte die Anzahl der gewählten Ameisen beim symmetrischen TSP nach Dorigo et al. genau der Anzahl der Städte n entsprechen.^[20] Die Ants haben die Aufgabe eine vollständige Tour durch die Städte (Knoten) zu konstruieren. Dazu starten sie an einem Knoten und laufen nacheinander die Knoten ab, bis alle Knoten genau einmal besucht wurden. Wenn alle Ants ihre Tour beendet haben, endet eine Iteration. Die Variablelegt fest, wie viele Iterationen (t) durchlaufen werden, bis der Algorithmus beendet ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Beispiel eines ungerichteten Graphen, wobei dij, die Distanz von Knoten i zu Knoten j angibt (Quelle: Eigene Darstellung)

Für jede Ant gelten bei dem Übergang von Knoten i zu Knoten j drei Restriktionen:

- Tabuliste: Eine Ameise darf jeden Knoten nur einmal besuchen. Eine Ameise muss sich also merken, an welchem Knoten sie bereits gewesen ist. Um diese Restriktion zu implementieren, gibt es für jede Ameise k und jeden Knoten i eine Liste (Tabu-Liste) , die alle Knoten i enthält, die von einer Ameise k in der aktuellen Iteration noch nicht besucht worden sind.

- Sichtbarkeit: Ist die Ameise an einen Knoten i gelangt, stellt sich die Frage, zu welchem Knoten j sie als nächstes wandert. Die Ameise hat dabei Kenntnis darüber, welcher Knoten j die kürzeste Entfernung zu ihrem derzeitigen Knoten i besitzt. Dies setzt voraus, wie bereits erwähnt, dass die Länge der Kanten bekannt ist. Diese lokale Information wird als „heuristic desirability" (bezeichnet, und entspricht der inversen Distanz zwischen den Städten . Die Auswahlwahrscheinlichkeit für einen betreffenden Knoten j erhöht sich somit bei einer geringen Distanz. Diese lokale Information über das Wissen des nächstgelegenen Knotens wird als statisch betrachtet, da sie sich im Laufe des Problemlösungsprozesses nicht verändert.

- Pheromonverteilung: Neben der lokalen Information gibt es auch die globale Information, die in Form der Pheromonmenge (t) der Kante (i,j) in der Tour t dargestellt wird. Im Gegensatz zur lokalen Information ist die globale Information dynamisch, da sie sich im Laufe der Iterationen verändert. Sie repräsentiert die Erfahrungen der Ameisen. Die Pheromonverteilung wird beeinflusst von der bisherigen Wegwahl der Ameisen, gleichzeitig beeinflusst sie die zukünftige Wahl der Wege.

In Abbildung 4 ist eine Ameise an dem Knoten i angekommen und wählt den nächsten Knoten mittels der Funktion aus dem Pheromonwert auf der Kanteund dem heuristischen Wertfür den Knoten j. Dies gilt analog für die Knoten g und k.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Wahrscheinlichkeit zur Auswahl des nächsten Knotens (Quelle: Eigene Darstellung, in Anlehnung an Dorigo, M.; Stützle, T. (2004), S.67)

Mittels der Übergangswahrscheinlichkeit kann errechnet werden, mit welcher Wahrscheinlichkeit die Ameise k von dem Knoten i zum Knoten j in der t -ten Tour wandert:

Formel 1:Übergangswahrscheinlichkeit von Knoten i zu Knoten j, Ant System (Quelle: Dorigo, M.; Stützle, T. (2004)), S.70)

Diese Formel kann nur angewendet werden, wenn j in der Tabu-Listeenthalten ist und somit der Knoten j noch nicht besucht wurde. Die Variablenundstellen die Einflussgröße von lokaler sowie globaler Information dar, und können im Algorithmus frei gewählt werden.stellt die globale Information dar. Ist= 0 bedeutet dies, dass keine Erfahrungswerte, in Form von Pheromonen, vorliegen. Ist hingegen die lokale Information = 0, entscheiden ausschließlich Erfahrungswerte die Wahl des nächsten Knotens, die lokale Information hingegen wird vollständig außer Acht gelassen.

Daraus würde resultieren, dass die Tour als Lösung betrachtet wird, welche am häufigsten benutzt wurde, was aber nicht in jedem Fall heißt, dass diese Tour auch gleichzeitig die optimale Lösung darstellt. Wurden Touren anfangs nicht genutzt, würden diese bei der Wahl endgültig vernachlässigt und die Lösungen könnten sehr schnell zu einer nicht optimalen Lösung konvergieren; die Exploration neuer Wege wird verhindert. Mit der Wahl des Verhältnisses vonundsoll dem beschriebenen Problem entgegengewirkt werden.

Mit der Übergangsregel wird nicht immer der Knoten gewählt, der bezüglich lokaler und globaler Information als der beste erscheint, die Ameisen können aufgrund der Wahrscheinlichkeitsverteilung auch Knoten mit auf dem ersten Blick niedriger Qualität wählen. Dadurch wird es möglich neue, auf die gesamte Tour bezogene sowie, kürzere Wege zu finden.

Ant System: Pheromon- Update-Regel

Neben dem Verhältnis vonundist auch die Pheromon-Update-Regel für den Algorithmus von Bedeutung.

Eine Ameise hinterlässt auf der beschrittenen Kante (i,j) eine gewisse Menge an Pheromonen (t). Die Menge an Pheromonen hängt von der Qualität der Lösung ab. gibt die Länge der Tour t der Ameise k an. Q bezeichnet ein Parameter, dessen Wert möglichst nahe an der optimalen Länge der Tour liegen soll. Q wird daher vorab mittels einer heuristischen Methode ermittelt. Ist eine Kante (i,j) nicht in einer Tour t der Ameise k enthalten, so gilt (t) = 0.

Die Pheromon – Update – Regel lautet:^[22]

t ij (t) ¬(1- p) ×t ij (t) + Dt ij (t)

Formel 2 : Pheromon-Update-Regel, Ant System

gibt einen Faktor von 0 bis 1 für die Verflüchtigung der Pheromone^[23] nach jeder Iteration an. Ein unbegrenztes Wachstum von Pheromonen auf einem Pfad wird so entgegengewirkt. Damit wird das Erforschen neuer Wege gefördert, und die Wahrscheinlichkeit, dass die Lösung in einer nicht optimalen Route stagniert, verringert.

Die Pheromon – Update – Regel besagt zum Einen durch den Verdunstungsfaktor, wie lange das Pheromon wirken soll, zum anderen wird die Intensität der Qualität der Lösung bestimmt. Initialisiert werden die einzelnen Kanten mit einem kleinen, positiven Wert To, was impliziert, dass zum Zeitpunkt t = 0 eine homogene Verteilung der Pheromone vorliegt.

Ant System (AS-TSP) – Der Algorithmus

Abbildung in dieser Leseprobe nicht enthaltenAbbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Ant System Algorithmus zur Lösung des TSP (Quelle: Focke, A. (2006), S.164, in Anlehnung an: Bonabeau, Dorigo und Theraulaz (1999), S. 45)

[...]

---

^[1] Formel: (n-1)! /2

^[2] D.h. durch Ausprobieren aller Elemente des Suchraums.

^[3] Vgl. Rückel B. (2014), S.3

^[4] Vgl. Kruse et al. (2015), S.259

^[5] Vgl. Nöllke M. (2008), S.283

^[6] Goss, S.; Aron, S.; Deneubourg, J. L.; Pasteels, J. M. (1989), S.579-581

^[7] Bonabeau, E.; Dorigo, M.; Theraulaz, G. (1999), S.26

^[8] Vgl. Kruse et al. (2015), S.229

^[9] Goss, S.; Aron, S.; Deneubourg, J. L.; Pasteels, J. M. (1989)

^[10] Die verschiedenen Ameisenarten sind sehr unterschiedlich mit Sehorganen ausgestattet. Der Großteil besitzt sehr zurückgebildete Sehorgane, die lediglich zur Wahrnehmung von Helligkeitsunterschieden oder Bewegung in der Natur genutzt werden. Einige Arten kommen ohne jegliche Sehorgane aus. Die Futtersuche funktioniert aber bei allen nach demselben Muster. Vgl. Sinnesorgane (Überblick) – Ameisenwiki 2015

^[11] Vgl. Kruse et al. (2011), S.260

^[12] Vgl. Gerdes et al. (2004), S.29

^[13] Goss, S.; Aron, S.; Deneubourg, J. L.; Pasteels, J. M. (1989)

^[14] Vgl. Büsing, C. (2010), S.78

^[15] Vgl. Zülch, G. (2010), S.231

^[16] Vgl. com (2017)

^[17] Focke, A. (2006), S.176

^[18] D.h. auch hier wird der kürzeste Weg gesucht

^[19] Bonabeau, E.; Dorigo, M.; Theraulaz, G (1999)., S.40

^[20] Bonabeau, E.; Dorigo, M.; Theraulaz, G.(1999), S.44

^[21] Bonabeau, E.; Dorigo, M.; Theraulaz (1999), S.42

^[22] Bonabeau, E.; Dorigo, M.; Theraulaz, G. (1999), S.43

^[23] Analog zum Begriff „Evaporation“ aus der Natur