Grin logo
en de es fr
Shop
GRIN Website
Texte veröffentlichen, Rundum-Service genießen
Zur Shop-Startseite › Informatik - Künstliche Intelligenz

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

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

Bachelorarbeit , 2010 , 79 Seiten , Note: 1,0

Autor:in: Matthias Herreiner (Autor:in)

Informatik - Künstliche Intelligenz
Leseprobe & Details   Blick ins Buch
Zusammenfassung Leseprobe Details

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.

Leseprobe


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.

Ende der Leseprobe aus 79 Seiten  - nach oben

Details

Titel
Ant Colony Optimization. Optimierung von Wegestrecken am Beispiel des Travelling Salesman Problem
Hochschule
Hochschule Deggendorf
Note
1,0
Autor
Matthias Herreiner (Autor:in)
Erscheinungsjahr
2010
Seiten
79
Katalognummer
V1348043
ISBN (PDF)
9783346866110
ISBN (Buch)
9783346866127
Sprache
Deutsch
Schlagworte
KI Künstliche Intelligenz Ant Colony Optimization Travelling Salesman Problem Wegestreckenproblem Optimierungsverfahren
Produktsicherheit
GRIN Publishing GmbH
Arbeit zitieren
Matthias Herreiner (Autor:in), 2010, Ant Colony Optimization. Optimierung von Wegestrecken am Beispiel des Travelling Salesman Problem, München, GRIN Verlag, https://www.grin.com/document/1348043
Blick ins Buch
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
  • Wenn Sie diese Meldung sehen, konnt das Bild nicht geladen und dargestellt werden.
Leseprobe aus  79  Seiten
Grin logo
  • Grin.com
  • Zahlung & Versand
  • Impressum
  • Datenschutz
  • AGB
  • Impressum