Ant Colony Optimization. Optimierung von Wegestrecken am Beispiel des Travelling Salesman Problem

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.