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.
Inhaltsverzeichnis
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
Zielsetzung & Themen
Das Hauptziel dieser Arbeit ist die Erstellung einer Konzeption sowie die praktische Umsetzung eines didaktischen Beispiels für den Einsatz eines schwarmbasierten Algorithmus in der Tourenplanung. Dabei wird untersucht, wie sich das natürliche Verhalten von Ameisen bei der Futtersuche als heuristisches Verfahren auf das "Travelling Salesman Problem" (TSP) übertragen lässt, um in einem nachvollziehbaren Modell die Auswirkungen der Algorithmus-Parameter zu veranschaulichen.
- Analyse des biologischen Phänomens der Pheromonspur bei Ameisen.
- Übertragung der natürlichen Lösungsstrategien auf das mathematische Travelling Salesman Problem.
- Detaillierte Modellierung und Parametrisierung eines Ameisenalgorithmus für ein konkretes Beispiel.
- Implementierung und Evaluation der Performance mittels der Software MATLAB.
- Gegenüberstellung der Algorithmen Ant System (AS) und Ant Colony System (ACS).
Auszug aus dem Buch
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“ 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).
Nacheinander verlassen die Ameisen nun das Nest. Da die Ameisen praktisch blind 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.
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. 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.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Tourenplanung und das Travelling Salesman Problem als NP-hartes Optimierungsproblem sowie die Motivation für den Einsatz naturinspirierter Heuristiken.
2 Futtersuche bei natürlichen Ameisen: Erläuterung des biologischen Konzepts der Stigmergie und der Pheromonkommunikation am Beispiel des Doppelbrücken-Experiments.
3 Travelling Salesman Problem: Mathematische Definition des TSP und Begründung, warum sich dieses Problem für den Einsatz von Ameisenalgorithmen eignet.
4 Ameisenalgorithmen: Detaillierte Darstellung der Funktionsweise des Ant System (AS) und des weiterentwickelten Ant Colony System (ACS) sowie deren mathematische Grundlagen.
5 Konzeption und Umsetzung eines didaktischen Beispiels: Anwendung des Algorithmus auf ein selbst definiertes Szenario, Modellierung in MATLAB und Vergleich der Ergebnisse bei unterschiedlichen Parametern.
6 Resümee: Zusammenfassende Betrachtung der Erkenntnisse über die Wirksamkeit von Ameisenalgorithmen und Ausblick auf deren aktuelle Relevanz für spezifische Problemstellungen.
Schlüsselwörter
Schwarmintelligenz, Ameisenalgorithmus, Tourenplanung, Travelling Salesman Problem, TSP, Pheromone, Stigmergie, Optimierungsproblem, Ant System, Ant Colony System, MATLAB, Heuristik, Autokatalyse, Evaporation, Kombinatorische Optimierung.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit dem Einsatz schwarmbasierter Optimierungsverfahren in der Tourenplanung, speziell unter Verwendung von Ameisenalgorithmen zur Lösung des Travelling Salesman Problems.
Was sind die zentralen Themenfelder?
Die Schwerpunkte liegen auf der Übertragung biologischer Verhaltensweisen von Ameisen (Futtersuche) auf mathematische Algorithmen, der Parametrisierung dieser Verfahren und deren praktischer Anwendung zur Lösungsfindung.
Was ist das primäre Ziel der Arbeit?
Ziel ist die Konzeption und Umsetzung eines didaktischen Beispiels, das nachvollziehbar macht, wie ein Ameisenalgorithmus funktioniert und wie sich verschiedene Parameter auf die Güte der gefundenen Touren auswirken.
Welche wissenschaftliche Methode wird verwendet?
Die Autorin nutzt eine methodische Herangehensweise, bei der zunächst das theoretische Modell erläutert und anschließend eine manuelle bzw. softwaregestützte Implementierung (MATLAB) zur Evaluation der Performance durchgeführt wird.
Was wird im Hauptteil behandelt?
Der Hauptteil umfasst die theoretischen Grundlagen des Ant Systems und des Ant Colony Systems sowie die schrittweise Modellierung und Berechnung eines TSP-Beispiels mit vier Städten sowie eines erweiterten Szenarios mit elf Städten.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wesentliche Begriffe sind Schwarmintelligenz, Ameisenalgorithmus, Travelling Salesman Problem (TSP), Pheromone, Stigmergie, Heuristik und kombinatorische Optimierung.
Welche Bedeutung hat der Parameter q0 im Ant Colony System?
Der Parameter q0 steuert die Entscheidungsfindung der Ameisen und legt die Häufigkeitsverteilung zwischen der Wahl des vielversprechendsten Pfades und der Exploration neuer Wege fest.
Warum wird im didaktischen Beispiel ein symmetrisches TSP verwendet?
Ein symmetrisches TSP vereinfacht die Darstellung, da die Distanz zwischen zwei Städten in beide Richtungen identisch ist, was die manuelle Berechnung und die Verständlichkeit des Algorithmus erhöht.
Welche Rolle spielt die Evaporation bei der Lösungsfindung?
Die Verdunstung der Pheromone (Evaporation) verhindert, dass der Algorithmus in lokalen Optima stagniert, indem sie veraltete Pfadinformationen reduziert und so die Exploration neuer, potenziell kürzerer Wege fördert.
Wann erreicht das Ant System seine Leistungsgrenzen?
Ab einer Größenordnung von etwa 70 Städten verschlechtert sich die Performance des einfachen Ant Systems merklich, da die Suche nicht zielgerichtet genug auf die optimale Lösung zusteuert.
- Citation du texte
- Nathalie Serban (Auteur), 2017, Schwarmintelligenz in der Tourenplanung, Munich, GRIN Verlag, https://www.grin.com/document/384873
