Diese Arbeit beschäftigt sich mit der Optimierung von Wegstrecken am Beispiel des Travelling Salesman Problem und der Ant Colony Optimization. Gerade in Zeiten von Rezessionen oder der globalen Finanz- und Wirtschaftskrise ist es für Unternehmen wichtig, Ressourcen effizient und optimal einzusetzen. Dabei werden Unternehmen vor neue Herausforderungen gestellt. Kenntnisse über Methoden und Verfahren zur Optimierung von Prozessen sowie die ökonomische Nutzung von Ressourcen werden in Zukunft verstärkt an Bedeutung gewinnen und letztendlich wettbewerbsentscheidend sein.
Naturanaloge Verfahren bieten ein breites Spektrum an Optimierungsansätzen. Die Natur hat über die Jahrtausende der Evolution Verfahren entwickelt, die in ihrer Effizienz ihresgleichen suchen. Der Mensch versucht, diese Verfahrens- und Verhaltensweisen zu imitieren und zu adaptieren. Meist ist es sehr aufwändig und zeitintensiv, solche Verhaltensweisen zu erforschen und in der Technik des Menschen umzusetzen. Dennoch gelingt es naturanaloge Verfahren, die in ihrer Effizienz sehr gut zur Lösung von praktischen Problemstellungen geeignet sind, zu entwickeln.
Eine beeindruckende Leistung der Natur ist eine Ameisenkolonie. Sie führen ihre Futtersuche selbstorganisierend im Schwarm durch. Die Welt der natürlichen Ameisen kann noch so komplex sein, sie finden stets den kürzesten Weg zwischen dem Nest und der Futterquelle. Das Problem des Handlungsreisenden ist ein Standardproblem der Optimierung, bei dem es um die Suche nach der kürzesten Route geht. Diese Arbeit soll einen Beitrag zur Optimierung dieser Herausforderungen leisten.
Inhaltsverzeichnis
- Einleitung
- Travelling Salesman Problem
- Problemstellung
- Lösungsverfahren
- Exakte Verfahren
- Heuristische Verfahren
- Standardisiertes Testwesen
- Testbibliothek TSPLIB
- Entfernungsbetrachtung
- Ant Colony Optimization
- Die Ameise
- Die reale Ameise
- Nachschub rollt
- Ameisenalgorithmen
- Grundlegende Aspekte
- Ant System
- Konstruktion von Touren
- Monte-Carlo-Auswahl
- Aktualisierung der Pheromone
- Ant Colony System
- Konstruktion von Touren
- Aktualisierung der Pheromone
- Beispiel Optimierungslauf
- Ameisen im Vergleich
- Zwischenfazit
- Implementierung
- Anforderungsprofil
- Design Patterns
- Callback Pattern
- Singleton Pattern
- Fütterung der Ameisen
- Datenformat JSON
- JSON-Datenstrukturen
- Ein einfaches JSON-Objekt
- Das JSON-Array
- Tourenbeschreibung mit JSON
- Die Klasse TourProblem
- Touren Unmarshalling und Marshalling
- Die Klasse TSPMarshaller
- Algorithmen
- Zentrales Koloniewissen
- Die Künstliche Ameise
- Eine Tour der Ameise
- Der virtuelle Ameisenstaat
- Testclient
- Test
- Evaluierung
- Anzahl der Ameisen
- Einfluss des ẞ-Parameter
- Einfluss des α-Parameter
- Einfluss der Pheromonverteilungsstrategie
- Testfazit
- Ausblick
- Problemstellung der Stundenplanung
- Stundenplanbewertung
- Stundenplanerstellung
- Unterschiede zur Streckenoptimierung
- Resümee
Zielsetzung und Themenschwerpunkte
Diese Bachelorarbeit untersucht die Anwendung von Ant Colony Optimization (ACO) zur Optimierung von Wegestrecken am Beispiel des Travelling Salesman Problem (TSP). Das Ziel ist es, die Effizienz und Leistungsfähigkeit von ACO-Algorithmen im Vergleich zu anderen Verfahren aufzuzeigen. Dabei werden die Funktionsweise, die Implementierung und die Evaluation des ACO-Algorithmus im Detail beleuchtet. Die Arbeit konzentriert sich auf den Vergleich des Ant System (AS) und des Ant Colony System (ACS).
- Die Anwendung von Ant Colony Optimization (ACO) zur Lösung des Travelling Salesman Problem (TSP)
- Die Funktionsweise, die Implementierung und die Evaluation von ACO-Algorithmen
- Der Vergleich des Ant System (AS) und des Ant Colony System (ACS)
- Die Analyse des Einflusses verschiedener Parameter auf die Lösungsgüte
- Die Potentiale der ACO-Methode für weitere Optimierungsprobleme
Zusammenfassung der Kapitel
- Einleitung: Dieses Kapitel führt in das Thema der Bachelorarbeit ein und stellt die Problemstellung sowie die Zielsetzung vor.
- Travelling Salesman Problem: Dieses Kapitel beschreibt das Travelling Salesman Problem (TSP) als ein klassisches Optimierungsproblem, das in vielen Bereichen Anwendung findet. Es werden verschiedene Lösungsansätze, darunter exakte Verfahren und heuristische Verfahren, vorgestellt.
- Die Ameise: Dieses Kapitel erläutert die Funktionsweise von Ameisenalgorithmen. Es werden die Prinzipien der natürlichen Ameisen, die Inspiration für die Algorithmen, sowie die verschiedenen Arten von Ameisenalgorithmen wie das Ant System (AS) und das Ant Colony System (ACS) behandelt.
- Implementierung: Dieses Kapitel beschreibt die Implementierung des ACO-Algorithmus, einschließlich der verwendeten Design Patterns, Datenstrukturen und Algorithmen.
- Testclient: Dieses Kapitel präsentiert den entwickelten Testclient, der zur Evaluation des ACO-Algorithmus verwendet wird.
- Test: Dieses Kapitel beschreibt die Durchführung von Tests mit dem entwickelten Testclient, um die Effizienz und Leistungsfähigkeit des ACO-Algorithmus zu evaluieren.
- Ausblick: Dieses Kapitel diskutiert die Möglichkeiten der Anwendung von ACO-Algorithmen in anderen Optimierungsproblemen, wie z. B. der Stundenplanung.
Schlüsselwörter
Diese Bachelorarbeit befasst sich mit den Themen Ant Colony Optimization (ACO), Travelling Salesman Problem (TSP), Ant System (AS), Ant Colony System (ACS), Optimierung, Heuristische Verfahren, Implementierung, Evaluation, Testclient, Datenstrukturen, Design Patterns, JSON, Stundenplanung.
- Quote paper
- Matthias Herreiner (Author), 2010, Ant Colony Optimization. Optimierung von Wegestrecken am Beispiel des Travelling Salesman Problem, Munich, GRIN Verlag, https://www.grin.com/document/1348043
