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

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

Informatik - Künstliche Intelligenz

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

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungs- und Symbolverzeichnis

1 Einleitung

2 Travelling Salesman Problem
2.1 Problemstellung
2.2 Lösungsverfahren
2.2.1 Exakte Verfahren
2.2.2 Heuristische Verfahren
2.3 Standardisiertes Testwesen
2.3.1 Testbibliothek TSPLIB
2.3.2 Entfernungsbetrachtung

3 Ant Colony Optimization
3.1 Die reale Ameise
3.2 Nachschub rollt
3.3 Ameisenalgorithmen
3.3.1 Grundlegende Aspekte
3.3.2 Ant System
3.3.2.1 Konstruktion von Touren
3.3.2.2 Monte-Carlo-Auswahl
3.3.2.3 Aktualisierung der Pheromone
3.3.3 Ant Colony System
3.3.3.1 Konstruktion von Touren
3.3.3.2 Aktualisierung der Pheromone
3.3.3.3 Beispiel Optimierungslauf
3.4 Ameisen im Vergleich
3.5 Zwischenfazit

4 Implementierung
4.1 Anforderungsprofil
4.2 Design Patterns
4.2.1 Callback Pattern
4.2.2 Singleton Pattern
4.3 Fütterung der Ameisen
4.3.1 Datenformat JSON
4.3.2 JSON-Datenstrukturen
4.3.2.1 Ein einfaches JSON-Objekt
4.3.2.2 Das JSON-Array
4.3.3 Tourenbeschreibung mit JSON
4.3.4 Die Klasse TourProblem
4.3.5 Touren Unmarshalling und Marshalling
4.3.6 Die Klasse TSPMarshaller
4.4 Algorithmen
4.4.1 Zentrales Koloniewissen
4.4.2 Die Künstliche Ameise
4.4.3 Eine Tour der Ameise
4.4.4 Der virtuelle Ameisenstaat

5 Test
5.1 Testclient
5.2 Evaluierung
5.2.1 Anzahl der Ameisen
5.2.2 Einfluss des ^-Parameter
5.2.3 Einfluss des «-Parameter
5.2.4 Einfluss der Pheromonverteilungsstrategie
5.3 Testfazit

6 Ausblick
6.1 Problemstellung der Stundenplanung
6.2 Stundenplanbewertung
6.3 Stundenplanerstellung
6.4 Unterschiede zur Streckenoptimierung

7 Resümee

A Anhang
A.1 Screenshots Testclient
A.2 Evaluierungsdaten
A.3 Programmcode Klasse TSPMarshaller

Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 2.1: Kosteninformation einer Kante zwischen zwei Städten

Abbildung 2.2: Gewichteter symmetrischer Graph mit vier Städteknoten

Abbildung 2.3: Städteverbindung mit gleichen Kosten bei Hin-und Rückreise

Abbildung 2.4: Städteverbindung mit ungleichen Kosten bei Hin-und Rückreise

Abbildung 2.5: Testinstanz „bays29“ aus der TSPLIB

Abbildung 2.6: Lösungsinstanz „bays29“ aus der TSPLIB mit optimaler Tour

Abbildung 2.7: Koordinatenauszug der Testinstanz „bays29“

Abbildung 3.1: Ameisenstraße zwischen Nest und Futterquelle

Abbildung 3.2: Ameisenexperiment mit Hindernis

Abbildung 3.3: Ameisenexperiment, Entwicklung der Pheromonkonzentration

Abbildung 3.4: Etablierte Ameisenstraße mit optimaler Verbindung

Abbildung 3.5: Kosteninformation und Pheromonwert einer Kante

Abbildung 3.6: Städtewahl anhand des Prioritätswerts der Kanten

Abbildung 3.7: Monte-Carlo-Auswahl mit drei Städten

Abbildung 3.8: Beispiel Rundreiseproblem mit Entfernungsangaben

Abbildung 4.1: Klassendiagramm des ACS-Algorithmus

Abbildung 4.2: Callback Implementierung im ACS-Algorithmus

Abbildung 4.3: Generische Klasse des Singleton Pattern

Abbildung 4.4: Singleton Implementierung in ACS

Abbildung 4.5: Klassenrepräsentation eines Tourenproblems

Abbildung 4.6: Datenaustausch zwischen Client und ACS

Abbildung 4.7: Technische Hilfsklasse zur Serialisierung und Deserialsierung

Abbildung 4.8: Klassendiagramm des Koloniewissens

Abbildung 4.9: Klassendiagramm künstliche Ameise

Abbildung 4.10: Klassendiagramm der künstlichen Ameisenkolonie

Abbildung 4.11: Sequenzdiagramm ACS-Optimierungslauf

Abbildung 5.1: Screenshot des ACS-Testclient

Abbildung 5.2: Einfluss Anzahl der Ameisen auf Lösungsgüte

Abbildung 5.3: Einfluss Entfernungsgewichtung auf Lösungsgüte

Abbildung 5.4: Einfluss Pheromongewichtung auf Lösungsgüte

Abbildung 5.5: Einfluss Strategie Pheromonverteilung

Abbildung 6.1: Die fünf Dimensionen der Stundenplanung

Tabellenverzeichnis

Tabelle 2.1: Übersicht kombinatorische Explosion bei Rundreiseproblemen

Tabelle 3.1: Parameterwerte für ACS-Beispiellauf

Tabelle 3.2: Ameisen- und Alternativalgorithmen im Vergleich

Tabelle 4.1: Import- und Exportparameter des ACS-Algorithmus

Tabelle 5.1: Vergleich Optima Gleitkommaarithmetik und Integer

Tabelle 6.1: Constraintsübersicht mit Schadenspunkten (Gewichtung)

Tabelle 6.2: Leerer Stundenplan zu Beginn des Erstellungslaufs

Abkürzungs- und Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Gerade in Zeiten von Rezessionen oder der globalen Finanz- und Wirtschaftskrise ist es für Unternehmen wichtig Ressourcen effizient und optimal einzusetzen. Stagnierende Märkte und Umsatzeinbrüche verschärfen die heikle Situation vieler Unternehmen. Um den Fortbestand der Unternehmen zu sichern, werden an vielen Stellen Kosteneinsparungen getroffen. Ergebnis sind oft knappe Budgets und Kosten-Nutzen-Analysen die Unternehmensentscheidungen prägen. Vorgegebene Ziele müssen mit möglichst geringem Aufwand oder Kosten erreicht werden. Klassische Prinzipien, wie z.B. das ökonomische Prinzip, spielen dabei eine entscheidende Rolle. Sie rücken verstärkt in den Mittelpunkt des unternehmerischen Handelns und prägen nachhaltig den Unternehmensalltag. 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 wettbewerbs­entscheidend sein.

Naturanaloge Verfahren bieten ein breites Spektrum an Optimierungsansätzen. Die Natur hat über die Jahrtausende der Evolution Verfahren entwickelt, die in ihrer Effizienz ihres gleichen 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.

Ein Ansatz sind Verfahren der Schwarmintelligenz [BDT99]. Dabei weist ein Individuum eine geringe Intelligenz auf und ist seiner komplexen Umgebung fast chancenlos ausgeliefert. Die Natur bietet hierfür eine leistungsfähige Lösung. Viele Individuen werden in einem Schwarm zusammengefasst, um durch Kommunikation innerhalb des Schwarms zu einem intelligenten Verhalten aller Mitglieder zu kommen. Komplexe Probleme können somit effektiv bewältigt werden. 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 [GP99]. Motivation dieser Arbeit ist, dass Verhalten der natürlichen Ameisen in einem Algorithmus zu adaptieren sowie die Anwendung des Algorithmus auf das Standardproblem des Handlungsreisenden zu übertragen.

2 Travelling Salesman Problem

2.1 Problemstellung

Das Travelling Salesman Problem, kurz TSP, oder auch als Problem des Handlungsreisenden bekannt, blickt auf eine interessante Historie zurück. Schon zu Beginn des 20 Jahrhunderts beschäftigten sich Kaufleute mit dem Problem der Rundreise. Karl Menger erwähnte das Problem als solches als Erster in einem mathematischen Kolloquium in Wien [Men32]. Ausgehend von einem Startpunkt, ist eine Reihe von Städten so zu bereisen, dass nach Rückkehr zum Ausgangspunkt die gesamte Wegestrecke möglichst kurz ist. Dabei darf jede Stadt nur einmal besucht werden. Geschäftsleute behalfen sich damals mit dokumentierten Beispieltouren die für ein bestimmtes Land als Vorschlag galten. Auf den ersten Blick, scheint das Rundreiseproblem simpel zu sein, da es leicht zu verstehen ist. Beschäftigt man sich jedoch näher mit dem Problem erkennt man, dass es relativ einfach ist eine gute Lösung zu finden, es aber umso schwerer fällt, eine optimale Lösung zu produzieren. Dies machte den Reiz für viele Wissenschaftler aus sich mit diesem Problem zu beschäftigen.

2.2 Lösungsverfahren

Zur Vereinfachung komplexer Problemstellungen werden Probleme oft abstrahiert und in einem Modell widergegeben. Formal wird ein Rundreiseproblem als Graph G = (N,Ä) mit N als Menge der zu bereisenden Städte und A der Menge der Kanten dargestellt. Eine Kante stellt dabei die Kosten zwischen zwei Städten dar. Die Kosten entstehen, wenn der Handlungsreisende sich entscheidet die Strecke zwischen der Stadt i und j zurückzulegen. Der entsprechende Kostenwert d0· wird an der Kante als Information abgelegt. Abbildung 2.1 zeigt die Kosteninformation die zwischen der Stadt A und B gespeichert wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Kosteninformation einer Kante zwischen zwei Städten

Ein Rundreiseproblem wird durch eine gültige Tour gelöst, die unter allen möglichen Touren, die mit den geringsten Gesamtkosten ist. Gültig bedeutet in diesem Zusammenhang: Eine Lösungstour muss einen geschlossenen Kreis bilden, auch Hamiltonkreis genannt, der jede Stadt einmal enthält und im Ausgangspunkt wieder endet [Wei10]. Die Gesamtkosten einer Tour ergeben sich aus der Summe Σ der in der Tour enthaltenen Kanten. Je geringer die
Gesamtkosten sind, desto besser ist die Tour für einen Handlungsreisenden geeignet. Als Kosten können zum Beispiel Entfernungs- oder Zeiteinheiten angesetzt werden. Durch Angabe der Einheit Zeit, erhält man die Lösungstour, mit der geringsten Reisedauer. Wird die Einheit Entfernung gewählt, wird die kürzeste Tour als Lösung geliefert. Zwangsläufig muss die kürzeste Tour nicht die schnellste sein.

Zur Tourenfindung wird angenommen, dass in einem Graphen immer gültige Touren existieren. Das wird durch die Vollständigkeit des Graphen erreicht. Vollständig bedeutet, dass zwischen zwei Städten immer eine Verbindung besteht. Liegt diese nicht vor, so wird eine fiktive Kante in den Graphen aufgenommen. Die Kante erhält eine Länge, die bei der Konstruktion einer optimalen Tour nicht berücksichtigt wird, außer es gäbe sonst keine Lösung [DS04]. Der folgende Beispielgraph (Abbildung 2.2) beinhaltet vier Städteknoten N = {A,B,C,D} und sechs Kanten mit den jeweiligen Kosten dtJ. Die Städtefolge A-B-C-D-A zeigt in rot den Hamiltonkreis mit minimalen Kosten von 9 Einheiten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Gewichteter symmetrischer Graph mit vier Städteknoten

Da eine gültige Rundreise einen Hamiltonkreis bildet, endet eine Rundreise immer wieder im Ausgangspunkt. Bei einem einfachen Problem mit zwei Städten gibt es dadurch zwei Möglichkeiten um zum Ausgangspunkt zurückzukehren. Erste Möglichkeit: Die Kante, die zur Hinreise verwendet wurde, wird auch wieder für die Rückreise gewählt. Dadurch entstehen für Hin- und Rückreise die gleichen Kosten mitd¿J- = άμ (siehe Abbildung 2.3).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Städteverbindung mit gleichen Kosten bei Hin-und Rückreise

Zweite Möglichkeit: Die ursprüngliche Kante kann nicht gewählt werden, da sie nur in eine Richtung passierbar ist (z.B. Einbahnstraße). Das bedeutet, zur Rückreise muss eine andere Kante gewählt werden. Es entstehen unterschiedliche Kosten mit d0· ψ dji (siehe Abbildung 2.4).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Städteverbindung mit ungleichen Kosten bei Hin-und Rückreise

Rundreiseprobleme lassen sich dadurch generell in zwei Klassen einteilen. Symmetrische und asymmetrische Probleme. Entstehen bei der Hin- und Rückreise die gleichen Kosten so spricht man von symmetrischen Problemen (d¿J- = άμ). Bei ungleichen Kosten werden die Probleme als asymmetrische klassifiziert (d¿J- ψ djt). In dieser Arbeit werden ausschließlich symmetrische Probleme behandelt.

Mittlerweile gibt es eine Vielzahl von Methoden um Rundreiseprobleme zu lösen. Meist führen sie aber nicht zu optimalen Ergebnissen. In Summe können Lösungsverfahren in zwei Klassen eingeteilt werden. Exakte und heuristische Verfahren [Sch01].

2.2.1 Exakte Verfahren

Eine exakte Lösungsvariante könnte der Versuch der vollständigen Enumeration sein. Ausgehend von einem Startpunkt werden alle möglichen Touren konstruiert und anhand ihrer Kosten verglichen. Die Tour mit den geringsten Gesamtkosten wird als optimale Tour gewählt. Bei Rundreiseproblemen mit einer geringen Anzahl von Städten, klingt dieser Ansatz vielversprechend. Betrachtet man aber komplexe Probleme mit einer großen Anzahl von Städten, so kommt es zu einer kombinatorischen Explosion. Nennen wir die Anzahl der Orten. Ausgehend von einem beliebigen Startpunkt gibt es für die Wahl des zweiten Ortes (n - 1) Möglichkeiten, da der Ausgangsort ausgeschlossen wird. Für den Dritten gibt es (n - 2) Möglichkeiten, da bereits besuchte Orte nicht erneut angefahren werden können usw. Es ergeben sich somit (n-1)! Möglichkeiten bei asymmetrischen Problemen, bei symmetrischen Problemen ergeben sich (n-l)!/2 Möglichkeiten, da die Hin- und Rückreise identisch ist. Die Anzahl der Touren können somit halbiert werden, da sie als eine Lösungsmöglichkeit gelten. Daraus folgt: Die Tour A-B-C-D-A ist gleichwertig mit der Tour A- D-C-B-A. Um der Problematik der kombinatorischen Explosion einen zeitlichen Aspekt zu verleihen, werden die Anzahl der Lösungsmöglichkeiten und der zur vollständigen Enumeration entstehende Rechenaufwand gegenübergestellt. Angenommen ein Rechner leistet die Konstruktion von 100.000 Touren in einer Sekunde. Bei 10 Städten ergeben sich 9! = 362.880 Möglichkeiten. Daraus folgt ein Rechenaufwand von ~ 3,63 Sekunden für eine vollständige Enumeration der Touren. Tabelle 2.1 zeigt exemplarisch die entstehenden Rechenaufwände, bei einer steigenden Anzahl von Städten.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Übersicht kombinatorische Explosion bei Rundreiseproblemen

Betrachtet man die entstehenden Rechenaufwände so ist der naive Ansatz der vollständigen Enumeration wenig zielführend.

2.2.2 Heuristische Verfahren

Um Näherungslösungen zu konstruieren, die in kürzerer Laufzeit annähernd an das Optimum heranreichen, wurden heuristische Verfahren entwickelt. Der Unterschied zu den exakten Verfahren, liegt im Faktor Zeit und der Güte der gefundenen Touren. Heuristische Verfahren können keine Garantie über die Qualität der gefundenen Lösungen abgeben. Sie bieten aber den Vorteil, dass sie mit beschränktem Rechenaufwand auskommen. Nachteilig ist allerdings die Tatsache, dass nicht ohne weiteres zu erkennen ist, wie gut die jeweils gefundene Lösung ist, also um welchen Betrag sie vom Optimum abweicht [VM07, S.49].

Heuristische Verfahren können in Eröffnungsverfahren und Verbesserungsverfahren unterteilt werden [VM07]. Bei Eröffnungsverfahren wird eine erste gültige Tour konstruiert, die dann in einem zweiten Schritt durch ein Verbesserungsverfahren optimiert wird. In Abschnitt 3.3.2 wird dazu ein Eröffnungsverfahren, die Nearest-Neighbor-Heuristik, näher erläutert. In der Praxis ist es meist ausreichend eine suboptimale Lösung und nicht zwingend das Optimum zu finden. Um einen Standard für die Bewertung gefundener Lösungen zu implementieren, werden Testbibliotheken eingesetzt.

2.3 Standardisiertes Testwesen

2.3.1 Testbibliothek TSPLIB

Gerhard Reinelt, Professor an der Universität Heidelberg, stellte 1991 eine Sammlung von Testinstanzen zur Wegeoptimierung zur Verfügung [Rei10]. Die Testbibliothek „TSPLIB“ umfasst ungefähr 111 heterogene Testinstanzen in unterschiedlichen Schwierigkeits­kategorien (Stand: 31.05.2010). Die kleinste Instanz verfügt über 14 Städte, die größte über 85.900. Die Bibliothek hilft damit, die Leistungsfähigkeit des eigenen Algorithmus mit anderen Algorithmen zu vergleichen. Eine vorschnelle Bewertung, oder eine Entwicklung die zu sehr vom Problem getrieben wird, kann durch die etablierte Testbibliothek vermieden werden. Ein weiterer Vorteil der Bibliothek ist, dass Lösungsinstanzen mit globalen Optima enthalten sind. Die „TSPLIB“ kann aus diesem Grund von Beginn an als Testinstrument eingesetzt werden. Zur Veranschaulichung des Inhalts der „TSPLIB“, wird exemplarisch eine Testinstanz mit Namen „bays29“ in Abbildung 2.5 visualisiert. Die Testinstanz gehört zur Klasse der symmetrischen Probleme, mit der Schwierigkeit 29 bayerische Städte zu bereisen. Die passende Lösungsinstanz zeigt die optimale Tour für die Testinstanz „bays29“ in Abbildung 2.6.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Testinstanz „bays29“ aus der TSPLIB

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: Lösungsinstanz „bays29“ aus der TSPLIB mit optimaler Tour

2.3.2 Entfernungsbetrachtung

Bei einigen Testinstanzen werden die Kosten der Kanten als Entfernungseinheiten in der Eingabe mitgeliefert. Dies hat den Vorteil, dass die Entfernungen zwischen den Städten nicht berechnet werden müssen. Die Testinstanzen die in dieser Arbeit verwendet werden sind, neben der Symmetriebedingung, euklidischer Art. Das bedeutet, dass die Entfernungen zwischen den Städten durch Punktkoordinaten im zweidimensionalen Raum gegeben sind. Dadurch ist eine direkte Verwendung der Entfernungen nicht möglich, diese müssen erst berechnet werden. Abbildung 2.7 zeigt einen Auszug aus der Eingabe der Testinstanz „bays29“. Unter dem Bereich NODE_COORD_SECTION sind die Koordinatenpaare der Städte angegeben die über EDGE_WEIGHT_TYPE im zweidimensionalen euklidischen Raum definiert sind.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.7: Koordinatenauszug der Testinstanz „bays29 Zur Berechnung der Entfernung zwischen zwei Punktkoordinaten kann folgende auf dem Satz des Pythagoras basierende Gleichung

Abbildung in dieser Leseprobe nicht enthalten

angewendet werden. Als Ergebnis erhält man die Entfernung zweier Städte, die anschließend als Kosteninformation der Kante verwendet werden kann. x¿ und y¿ stellen dabei die Koordinaten der Stadt i dar.

Nun kann man einwenden, dass der berechnete Abstand nur die Luftlinie zwischen den Städten darstellt. In der Realität wird eine Route aber in den seltensten Fällen der Luftlinie entsprechen. Diese Tatsache ist für den Test und der Bewertung eines Algorithmus aber vernachlässigbar. Für den Algorithmus ist es unerheblich, ob die Entfernung der tatsächlichen Strecke, oder nur der Luftlinie entspricht. Es ist ein Kostenwert, der die Gewichtung bzw. Attraktivität einer Kante darstellt.

Interessanter ist die Frage, welcher Datentyp verwendet werden soll, um die Kosten einer Kante in einer Matrix abzulegen. Die TSPLIB definiert die Entfernungen als Integer-Werte, die zum nächstliegenden Integer Wert gerundet werden. Vorteil ist die höhere Performance, da Ganzzahloperationen im Vergleich zur Gleitkommaarithmetik mit geringerem Rechneraufwand zu realisieren sind. Nachteil ist, dass es zu einer Verfälschung der optimalen Tour kommen kann. Grund hierfür ist das Radizieren, bei dem es zu irrationalen Zahlen und zu späteren Rundungsdifferenzen kommt. Angenommen Stadt A hat die Koordinaten (2;2) und Stadt B (1;1). Durch Anwendung der Gleichung 2-1 kann eine Entfernung von ~ 1,414 ermittelt werden. Eine Rundung dieses Ergebnis ergibt einen Wert von 1 der auch in eine ganzzahlige Matrix eingeht und fortan für alle Tourenberechnungen dienen würde [Wen95]. Aus diesem Grund werden in dieser Arbeit folgende Rundreiseprobleme konsequenterweise mit Gleitkommazahlen berücksichtigt.

3 Ant Colony Optimization

Die Natur übt auf den Menschen eine gewisse Faszination aus. Sie stellt ihn immer wieder vor Rätsel und lässt den Menschen oft staunend zurück. Was die Natur im Laufe der Evolution an komplexen Umgebungen und einzigartigen Geschöpfen geschaffen hat, gilt für den Menschen oft zu Recht als Natürliches Vorbild. Eine der leistungsfähigsten und erfolgreichsten Geschöpfe der Evolution ist die Ameise. Über zehn Billionen Individuen haben sich in ungefähr 9.500 Arten aufgespalten. Außerdem gibt es Biotope, speziell im Regenwald, in denen Ameisen zehn Prozent der lebenden Biomasse ausmachen [Boy05]. Einer der ersten, der sich von den Ameisen inspirieren ließ, war der italienische Mathematiker Marco Dorigo in seiner Dissertation „Optimization, Learning and Natural Algorithms“ [Dor92]. Er übertrug das Verhalten der Ameisen auf einen Algorithmus und imitierte ihre selbstorganisierende Fähigkeit zur Lösung von Optimierungsproblemen. In diesem Kapitel wird der Ansatz der Schwarmintelligenz am Beispiel der Ameisenalgorithmen dargestellt. Dabei wird das natürliche Verhalten der Ameisen analysiert und durch virtuelle Ameisen adaptiert. Mittels einer Ameisenkolonie werden dann Lösungsmöglichkeiten aufgezeigt, um das unter Abschnitt 2.1 behandelte Optimierungsproblem des TSP zu lösen.

3.1 Die reale Ameise

Aus Sicht einer Ameise ist die Welt, in der sie sich bewegt, sehr komplex. Selbst ein kleiner Halm kann für die Ameise schon ein unüberschaubares Hindernis darstellen. Erschwerend kommt hinzu, dass ihre visuellen Fähigkeiten stark eingeschränkt sind. Eine Ameise kann gewöhnlich keine Schärfeeinstellungen treffen und entfernte Gegenstände fokussieren. Sie nimmt ihre Umgebung meist nur sehr verschwommen und rasterartig wahr [Kir07]. Einige Ameisenarten haben so gut wie keine Sehfähigkeit und sind nahezu blind. Erstaunlicherweise gelingt es Ihnen dennoch, sich in hoch strukturierten sozialen Kolonien zu organisieren um komplexen Problemen im Kollektiv entgegenzutreten.

Eine Schlüsselrolle spielt dabei die indirekte Kommunikation über die Umgebung. Die Ameisen hinterlassen auf ihren Touren einen chemischen Duftstoff, das Pheromone. Pheromone werden über eine Drüse am Hinterleib produziert und von der Ameise abgesondert. Die Kommunikation zwischen den Ameisen, oder zwischen der Umgebung und den Ameisen, findet im Austausch über die Pheromone statt. Das abgelegte Pheromon bildet dazu eine unsichtbare Duftmarke am Boden, an der sich nachfolgende Ameisen orientieren. Eine Ameisenstraße entsteht, wenn vielen Ameisen das gleiche Wegestück wählen und dadurch die Konzentration der Pheromone am Boden erhöht wird. Siehe dazu die Abbildung 3.1.

3.2 Nachschub rollt

Jeder der eine Ameisenstraße näher betrachtet, wird feststellen, dass die Straße oft die kürzeste Verbindung zwischen dem Ameisennest und der Futterquelle ist. Entscheidend für diese Tatsache ist das Verhalten der Ameisen in zwei wesentlichen Punkten. Zum einen markieren die Ameisen ihre zurückgelegten Touren durch Abgabe von Pheromonen. Zum anderen werden Strecken mit höherer Pheromonkonzentration bevorzugt. Durch diese Verhaltensweisen gelingt es Ameisen effektiv, kurze Strecken aufzuspüren und zu etablieren. Goss et al. führten dazu 1989 ein Experiment durch, in dem Ameisen der direkte Weg zwischen Nest und Futterquelle durch ein Hindernis versperrte wurde [GADP89]. Die Ameisen hatten zwei Möglichkeiten das Futterziel zu erreichen. Das Hindernis konnte entweder über einen oberen, oder einen unteren Weg umgangen werden. Im Experiment war dabei der obere Weg kürzer als der untere. Siehe dazu Abbildung 3.2.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Ameisenexperiment mit Hindernis

Im Fortgang des Experiments wurde beobachtet, wie viele Ameisen den oberen respektive den unteren Weg wählen. Bei jeder Ameise besteht am Anfang die Wahrscheinlichkeit, dass sie mit p-! = 0,5 den oberen, p2 = 0,5 den unteren Weg wählen. Angenommen die erste Ameise wählt den oberen, die zweite den unteren Weg. Die erste Ameise erreicht ihr Ziel schneller als die zweite, da ihr Weg kürzer ist. Während die zweite Ameise sich noch auf dem Hinweg befindet, tritt die erste Ameise schon wieder ihren Rückweg an. Das hat zur Folge, dass auf dem oberen Weg eine höhere Pheromonkonzentration entsteht als auf dem unteren, da am Rückweg auch Pheromone durch die Ameise abgelegt werden. Durch die kürzere Strecke, haben innerhalb des gleichen Zeitraums mehr Ameisen die Möglichkeit am oberen Weg ihre Pheromone abzulegen, als auf dem unteren. Siehe dazu Abbildung 3.3.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Ameisenexperiment, Entwicklung der Pheromonkonzentration

Die höhere Frequentierung drückt sich in einer stetig wachsenden Pheromonkonzentration der oberen Strecke aus. Am Anfang wird die Auswahlwahrscheinlichkeit der Ameisen durch die etwas höhere Konzentration nicht wesentlich beeinflusst. Das heißt, die untere Strecke stellt für die Ameisen immer noch eine attraktive Verbindung dar. Erst nach einer gewissen Zeit, wenn viele Ameisen die Strecke markiert haben, kristallisiert sich die kürzere Strecke auch als optimalere Verbindung heraus, da sie mit immer höherer Wahrscheinlichkeit von immer mehr Ameisen gewählt wird. Es kommt zu einem Konvergenzverhalten, dass mit der Selbstorganisation der Kolonie oder auch als Stigmergie bezeichnet wird [DS04]. In Abbildung 3.4 ist die entstandene optimale Verbindung zwischen Nest und Futterquelle illustriert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Etablierte Ameisenstraße mit optimaler Verbindung

Da eine Ameise selbst nur über begrenztes Wissen verfügt, können die Pheromonablagerungen am Boden auch als gesammeltes Wissen der Kolonie betrachtet werden. Die Erfahrungen der Kolonie werden als Wissensschatz in Form von Pheromonen in der Umgebung abgelegt. Ein natürlicher Verwitterungsprozess lässt die Kolonie aber auch wieder kollektiv vergessen. Die Pheromonspur verdampft mit der Zeit, wenn sie nicht regelmäßig passiert wird. Sie wird verwaschen und verliert dadurch an Duftintensität.

Interessant ist die Frage, was passiert, wenn sich die Umgebung verändert, d.h. wenn ein Hindernis hinzukommt bzw. wegfällt. Es ist nicht der Fall, dass Ameisen immer blindlings der stärksten Spur folgen. Die Pheromonkonzentration stellt lediglich eine Auswahlwahrscheinlichkeit dar. Je höher die Konzentration, desto wahrscheinlicher fällt die Wahl auf den stärker duftenden Weg. Entscheiden sich Ameisen gegen eine stark duftende Pheromonspur, nehmen sie die Rolle einer Entdeckerameise ein. Sie erkunden ihre Umgebung und können dadurch auf neue und kürzere Strecken stoßen. Durch das neugierige Verhalten verhindern die Entdeckerameisen das Konvergieren der Kolonie gegen ein lokales Optimum. Auf Entdeckertour legen die Ameisen wieder Pheromone ab, was wiederum nachfolgende Ameisen veranlasst die neuere Route zu wählen. Es entsteht eine neue Ameisenstraße. Um das Verhalten der natürlichen Ameisen zu imitieren, wurden Ameisenalgorithmen konzipiert, die mit Hilfe virtueller Ameisen das natürliche Verhalten nachbilden.

3.3 Ameisenalgorithmen

Virtuelle Ameisen, oder auch künstliche Ameisen, werden in Algorithmen zum Konzept der Metaheuristiken gezählt [DS04]. Metaheuristiken werden in heuristischen Verfahren eingesetzt (siehe Abschnitt 2.2.2) um eine Reihe von kombinatorischen Optimierungsproblemen zu lösen. Sie sind generischer Art und können mit wenigen Einstellungen auf spezielle Probleme adaptiert werden. Als Vorbild der Ameisenalgorithmen diente das Verhalten natürlicher Ameisen. Künstliche Abbilder stellen mit ihren Artgenossen eine virtuelle Ameisenkolonie dar, die im Schwarm kollektiv Lösungen für spezielle Probleme suchen. Grundlegender Ansatz ist die Kooperation zwischen den virtuellen Ameisen. Sie kommunizieren und stimmen sich im indirekten Austausch über die Umgebung ab. Zum Austausch der Informationen dient eine zweidimensionale Matrix. Die Matrix besteht aus mehreren Kanten, an denen neben der Kosteninformation d0· auch die Pheromoninformation Tij abgelegt wird (siehe Abbildung 3.5).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5: Kosteninformation und Pheromonwert einer Kante

Die virtuellen Ameisen können während der Optimierung ihre Erfahrungen mit Hilfe der Pheromone in der Matrix codieren. Schritt für Schritt entsteht dadurch ein globaler Informationsspeicher der durch die gesamte Kolonie aufgebaut und genutzt wird. Der Informationsspeicher ist für die Kolonie wichtig, da das Wissen einer einzelnen Ameise lokal begrenzt ist (siehe Abschnitt 3.1). Auf der Suche nach Lösungen agieren die Ameisen autonom und begeben sich pro aktiv auf die Suche nach optimalen Lösungen. Durch diese Eigenschaften kann man auch von einem Multiagentensystem sprechen. Typische Anwendungsfälle für Ameisenalgorithmen sind:

- Optimierung von Reihenfolgenproblemen (z.B. das in dieser Arbeit behandelte TSP)
- Leiterplattenplanung
- Routing in Netzwerken
- Automatisches Hochregallager (Ein- und Auslagerroutine)
- Stundenplanungssysteme

3.3.1 Grundlegende Aspekte

Ameisenalgorithmen bieten eine Folge von Parametern, mit denen Einfluss auf das Verhalten der Ameisen genommen werden kann. Dorigo definierte dazu folgende Parameter [DS04]:

- «-Parameter: Gewichtungswert der den Einfluss der Pheromoninformationen (globale Information) auf die Auswahlentscheidung der Ameisen vorgibt.
- ^-Parameter: Gewichtungswert der den Einfluss der Kosteninformation (lokale Information) auf die Auswahlentscheidung der Ameisen vorgibt.
- Verwitterungsgrad p: Konstanter Faktor der die simulierte Regenwahrscheinlichkeit zum verwaschen der Pheromonspuren im System ausdrückt.

Um flexibel auf verschiedene Problemstellungen reagieren zu können, kann es sinnvoll sein, folgende zusätzliche Parameter für einen Ameisenalgorithmus zu deklarieren.

- m-künstliche Ameisen: m Ameisen agieren im System und bearbeiten ein Optimierungsproblem auf der Suche nach Lösungen.
- tmax-Iterationen: Anzahl an Iterationen die maximal für den Optimierungslauf durchgeführt werden.
- Flag Asynchrone Ausführung der Ameisen: Boolesches Flag mit dem eine parallele Ausführung der einzelnen Ameisen vorgegeben wird. Auf modernen Mehrkernprozessoren kann dadurch ein Performancegewinn erzielt werden.

Ameisenalgorithmen weisen neben den Parametern prinzipiell auch ein ähnliches Grundschema auf, welches nachfolgend skizziert wird (siehe Listing 3.1).

Abbildung in dieser Leseprobe nicht enthalten

Listing 3.1: Pseudocode Ameisenalgorithmus

Nach einer Initialisierungsphase, werden m virtuelle Ameisen in mehreren Iterationen n mal durch einen problembeschreibenden Graphen geschickt, um Lösungen zu konstruieren. Eine Übergangsregel entscheidet dabei, welche Kante benutzt wird, um den nächsten noch nicht besuchten Knoten zu erreichen. Nachdem eine Iteration t beendet wurde, werden die gefundenen Lösungen evaluiert und mit dem bisher bekannten Optimum verglichen. Ist eine gefundene Tour besser, als das bisherige globale Optimum, wird die Tour übernommen und als neues Optimum gespeichert. Nach der Evaluierung der Touren, werden die Pheromonwerte der Umgebung angepasst. Damit die Pheromonspur nicht ins Unermessliche wächst setzt eine künstliche Verwitterung, der virtuelle Regen, ein. Der Regen verwischt die Pheromonspur, um eine frühzeitige Konvergenz der Kolonie in eine suboptimale Region zu vermeiden. Zur Realisierung von Ameisenalgorithmen gibt es zwei wesentliche Ansätze. Ant System und Ant Colony System.

3.3.2 Ant System

Ant System, kurz AS, wurde 1992 von Marco Dorigo auf Basis virtueller Ameisen vorgestellt [Dor92]. Prinzipiell gibt es in AS zwei Phasen. Als Erstes werden gültige Touren durch die Ameisen konstruiert, danach wird der neue Pheromonwert bestimmt und in der Matrix abgelegt. In Ant System wird zum Beginn der Optimierung zunächst die Matrix mit einem initialen Pheromonwert τ0 belegt. Der initiale Pheromonwert wird dazu auf jeder Kante in der
Matrix verteilt. Dieser Schritt ist notwendig, damit der erste Iterationsschritt nicht als Sonderfall behandelt werden muss, da noch keine Pheromonwerte im Ant System existieren. In der Praxis wird meistens ein sehr kleiner Wert gewählt, der sich aus der Anzahl m eingesetzter Ameisen dividiert durch die Tourlänge Cnn der Nearest-Neighbor-Heuristik ergibt.

Abbildung in dieser Leseprobe nicht enthalten

Bei der Nearest-Neighbor-Heuristik, handelt es sich um eine Eröffnungsheuristik, die ausgehend von einem zufällig gewählten Knoten, die benachbarte Kante mit minimalen Kosten sucht [WPA1]. Nach Ermittlung der Kante wird der damit verbundene Knoten als nächster Ausgangspunkt gewählt. Nun wird erneut die Kante mit den geringsten Kosten gesucht usw. Das Verfahren endet, wenn alle Knoten besucht wurden. Diese Eröffnungsheuristik klingt vielversprechend, hat aber ihren Nachteil in der Rückkehr zum Startpunkt. Meist stellt hier die letzte Kante eine überdurchschnittlich schlechte Wegestrecke dar. Zur Erstellung des initialen Pheromonspiegels ist diese Eröffnungsheuristik aber ausreichend.

3.3.2.1 Konstruktion von Touren

Touren werden im AS durch m künstliche Ameisen konstruiert. Ausgehend von einem zufälligen Startpunkt i wird anhand einer Übergangsregel (siehe Gleichung 3-3) die nächste Stadt; gewählt. Nach Ermittlung der nächsten Stadt, wird diese durch die Ameise besucht. Dieser Vorgang wird solange wiederholt bis alle Städte bereist wurden. Jede Stadt darf dabei nur einmal angefahren werden. Nachdem die letzte Stadt besucht wurde, wird zum Ausgangspunkt zurückgekehrt. Die Ameise führt dazu eine lokale Tabuliste in der sie bereits besuchte Städte vermerkt. Am Ende eines Iterationsschritts, wird die Tabuliste durch die Ameise wieder verworfen. Die virtuellen Ameisen favorisieren genau wie ihre natürlichen Vorbilder Städte, die weniger weit entfernt sind und Verbindungen mit hohem Pheromongehalt. Zur Bewertung der offenen Städte fließen deshalb zwei Betrachtungswerte in die Entscheidungsfindung der Ameisen ein:

- Heuristischer Wert: Die Kosteninformation zwischen zwei Städten ist in einer Matrix an der Kante (t,;) abgelegt. Der heuristische Wert wird durch die Gleichung

Abbildung in dieser Leseprobe nicht enthalten

berechnet, wobei die Kosten an der Kante zwischen Stadt i und j sind. Der entstehende Kehrwert zeigt, wie attraktiv die Kante anhand ihres Kostenwerts ist. Je höher die Kosten, desto kleiner ist der heuristische Wert. Ein großer heuristischer
Wert, stellt in Folge eine attraktivere Verbindung dar. Der heuristische Wert ist eine konstante Größe die während des Optimierungslaufs unverändert bleibt.

- Aktueller Pheromonspiegel: Neben dem heuristischen Wert wird zusätzlich die abgelegte Pheromonmenge τί7· der Kante betrachtet. Die Menge spiegelt den Erfahrungsschatz der Kolonie wider. Sie drückt die Attraktivität einer Kante anhand des bisher erworbenen Wissens im Optimierungslauf aus. Der Wert ändert sich während der Optimierung und ist nicht statisch.

Die Wahrscheinlichkeit mit der sich letztendlich eine Ameise k von Stadt i zu Stadt j bewegt, wird im AS mit der Übergangsregel

Abbildung in dieser Leseprobe nicht enthalten

ausgedrückt, wobei j in der Tabuliste der Ameise nicht Vorkommen darf. Durch die Multiplikation des Pheromonwerts mit dem heuristischen Wert, ergibt sich ein Prioritätswert der Kante (siehe Zähler, Gleichung 3-3). Wird der Prioritätswert einer Stadt durch die Summe aller Prioritätswerte der noch nicht besuchten Städte (siehe Nenner, Gleichung 3-3) dividiert, wird der Prioritätswert zu der Auswahlwahrscheinlichkeit p¡j normiert. Die Summe der Auswahlwahrscheinlichkeiten aller noch nicht besuchten Städte ergibt dadurch einen Wert von 1. Die Auswahlwahrscheinlichkeit einer Stadt bewegt sich in Folge immer zwischen 0 Pij 1.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6: Städtewahl anhand des Prioritätswerts der Kanten

Eine wichtige Rolle bei der Ermittlung der Auswahlwahrscheinlichkeit spielen die Gewichtungsexponenten a undß (siehe Abschnitt 3.3.1). Sie sind Stellschrauben mit denen die Feinjustierung der Ameisen im AS vorgenommen wird. Durch die beiden Exponenten kann der Einfluss der heuristischen- und der Pheromonwerte bei der Bewertung der noch nicht besuchten Städte gesteuert werden. Das bedeutet, je höher der Exponent ß angegeben wird, desto mehr Beachtung finden die heuristischen Informationen bei der Bewertung der Ameise. Dieses gilt ebenso für den Exponent a. Je höher der a Wert ist, desto mehr werden die Pheromoninformationen berücksichtigt. Setzt man einen der Exponenten auf den Wert 0, so wird der entsprechende Wert deaktiviert. Gibt man beispielsweise ß = 0 als Exponent vor finden die heuristischen Informationen keine Berücksichtigung. Es wird nur der aktuelle Pheromonwert begutachtet. Gleiches gilt für den Exponent a = 0. Hier werden die Pheromoninformationen deaktiviert und nur die heuristischen Informationen finden Anwendung. Gute Einstellungen für einen Ameisenalgorithmus finden sich bei Dorigo [DS04, S. 71].

3.3.2.2 Monte-Carlo-Auswahl

Nach der Berechnung der Auswahlwahrscheinlichkeiten erfolgt die endgültige Auswahl der nächsten Zielstadt. Dabei wird eine gleichverteilte Zufallszahl r erzeugt, die im Bereich [0,1.0] liegt. Es werden die Auswahlwahrscheinlichkeiten p¡j der offenen Städte nacheinander summiert, bis die Zufallszahl r überschritten wird. Die Stadt, deren Auswahlwahrscheinlichkeit zuletzt addiert wurde, wird als nächste Zielstadt der Ameise gewählt. Diese Auswahlregel wird als Monte-Carlo-Auswahl bezeichnet [BoyoJ].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.7: Monte-Carlo-Auswahl mit drei Städten

Abbildung 3.7 illustriert die Monte-Carlo-Auswahl mit drei noch nicht besuchten Städten {j,g,k }. Alternative k stellt dabei die attraktivste Stadt mit der höchsten Auswahlwahrscheinlichkeit dar (blaues Ringsegment).

[...]

• 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