Lade Inhalt...

Ant Colony Optimization - Ameisenkolonie-Optimierung

Seminararbeit 2008 34 Seiten

Informatik - Wirtschaftsinformatik

Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Vorstellung des Ant Colony Optimization Ansatzes
2.1 Historische Entwicklung
2.2 Anwendungsbereiche
2.3 Biologisches Vorbild der Ameise
2.3.1 Beobachtung der Futtersuche von Ameisen
2.3.2 Das Phänomen der Pheromonspuren
2.4 Einführung in das Konzept der „Künstlichen Ameise“

3 Teilalgorithmen und Komponenten der Ant Colony Optimization
3.1 Ameisen-Generierung und -Aktivitäten
3.2 Pheromon-Verdunstung
3.3 Optionale Dämon-Aktionen

4 Lösung eines Network Routing Problem
4.1 Darstellung des zu lösenden Problems
4.2 Vorstellung des Verfahrens
4.2.1 Ameisen-Generierung und -Aktivitäten
4.2.2 Pheromon-Verdunstung
4.2.3 Optionale Dämon-Aktionen
4.2.4 Lösungsgüte im Vergleich zu alternativen Verfahren

5 Einordnung des Ansatzes in das Konzept der Swarm Intelligence
5.1 Grundlagen der Swarm Intelligence
5.2 Bedeutung des Ant Colony Optimization Ansatzes

6 Zusammenfassung

Literaturverzeichnis

Anhang

Abbildungsverzeichnis

Abb. 1 Schematischer Versuchsaufbau „Double Bridge Experiment“

Abb. 2 Pseudo-Algorithmus ACO-Metaheuristik, Teil

Abb.3 Darstellung eines sehr einfachen Travelling Salesman Problem

Abb. 4 Pseudo-Algorithmus ACO-Metaheuristik, Teil

Abb. 5 Pseudo-Algorithmus ACO-Metaheuristik, Teil

Abb. 6 Monte-Carlo-Auswahl in Zyklus

Abb. 7 Berechnung der Weglänge

Abb. 8 Ant System Berechnung für das TSP in Zyklus

Abb. 9 Pseudo-Algorithmus AntNet 19/

Abb. 10 lokales Traffic-Modell Μi und Pheromonmatrix Γ i in Knoten i

Abb. 11 NSFnet: Vergleich der Algorithmen unter RP-Datenverkehr

Tabellenverzeichnis

Tab. 1 Überblick über die mit Ameisenalgorithmen gelösten Problemstellungen

Tab. 2 Ant-Routing Tabelle Ai zu Beginn des Zyklus

Tab. 3 Berechnung neue Markierungsmengen tij nach Zyklus

Tab. 4 Berechnung neue Markierungsmengen t ij nach der Pheromonverdunstung

Tab. 5 Berechnung neue Ant-Routing Tabelle Ai nach der Pheromonverdunstung

1 Einleitung

Die Lösung NP-harter[1] kombinatorischer Optimierungsprobleme - nicht nur im betriebs-wirtschaftlichen Bereich - ist mit einer gravierenden Schwierigkeit, nämlich dem mehr als polynomiell, das heißt zum Beispiel exponentiell ansteigenden Bearbeitungsaufwand verbunden. Dies rührt daher, dass die Zahl der benötigten Rechenoperationen für eine exakte algorithmische Lösung stärker als polynomiell mit der Komplexität der Problemstellung anwächst, so dass schon mittlere Probleme eine Rechenzeit benötigen, die auch bei Verwendung aller Supercomputer der Welt nicht bis zum Ende der Lebensdauer des Sonnensystems abgearbeitet wäre. Ungeachtet dessen treten solche Probleme überaus häufig in der Praxis auf. Zu finden sind diese vor allem bei vielen Planungsaufgaben und es ist von großer ökonomischer Bedeutung, diese Probleme doch zu lösen, zumindest näherungsweise oder umgangssprachlich "so gut wie es geht".

Geeignete Verfahren können vor allem im Bereich von Heuristiken gesucht werden. Heuristiken stellen Algorithmen dar, die häufig, d.h. für viele praktisch wichtige Eingaben, gute, wenn auch nicht exakte, so doch annähernd optimale Lösungen hervorbringen. Im Verlauf der beiden letzten Jahrzehnte zeigte sich ein starkes Interesse an Verfahren, die von natürlichen Vorgängen inspiriert sind. Eines der jüngsten dieser Verfahren ist die „Ant Colony Optimization“ (ACO, deutsch etwa: Ameisenkolonie-Optimierung), d.h. die Optimierung in Anlehnung an reale Ameisenkolonien und deren Verhalten bei der Futtersuche. Das Verfahren stellt wie allgemein bei den genetischen Algorithmen den Versuch dar, Optimierungsprobleme durch Adaption natürlichen Verhaltens heuristisch zu lösen. In dieser Seminararbeit wird dieses Verfahren beschrieben, die Anwendung an Beispielen illustriert und in das übergreifende Feld der Swarm Intelligence eingeordnet.

2 Vorstellung des Ant Colony Optimization Ansatzes

2.1 Historische Entwicklung

Der italienische Informatiker Marco Dorigo hat 1991 in seiner Doktorarbeit, welche er an der Universität Mailand ablegte, die Grundlagen eines Algorithmus unter Anwendung von Theorien über Ameisenkolonien vorgestellt. Er stützte sich dabei auf Forschungen von Jean-Louis Deneubourg und Kollegen (Deneubourg u.a., 1990; S. 159-168; Goss u.a., 1989, S. 579-589). Die genannten haben in kontrollierten Experimenten gezeigt, dass futtersuchende Ameisen den kürzesten Weg zwischen ihrem Nest und einer Futterquelle finden können. Daraus ergab sich der „Simple ACO“ (S-ACO), die einfachste Form des Ansatzes, der anhand der Suche in einem Graph nach einem Pfad mit minimalen Kosten vor allem didaktischen Zwecken genügt, um die grundsätzlichen Mechanismen des Konzeptes zu erklären. Eine Weiterentwicklung ist das Ant System (AS), das anhand des „Travelling Salesman Problem“ (TSP), des bekannten NP-schweren Problem aus der Logistik, die Anwendung der Ameisen-theorie weiterentwickelte (Dorigo, Colorni, und Maniezzo, 1991). In den folgenden Jahren beschäftigten sich immer mehr Wissenschaftler wie z.B. Stützle und Hoos (Max-Min Ant System, 1998) oder Bullnheimer u. a. (AS rank,1997), mit dem Thema, da das AS bei vielen Anwendungen nicht mit den besten bekannten Algorithmen mithalten konnte. Es entstanden zahlreiche abgeänderte und verbesserte Algorithmen, die sich nicht nur mit dem ursprünglichen TS-Problem sondern auch mit anderen Problembereichen auseinandersetzen. 1999 bemühte sich Marco Dorigo, mittlerweile an der Freien Universität von Brüssel als Wissenschaftler tätig, zusammen mit seinem Kollegen Gianni Di Caro diese neuen Richtungen zusammenzufassen, um einen gemeinsamen Rahmen für die weiteren Forschungsarbeiten zu finden. Heraus kam der Ant Colony Optimization Meta Heuristic Ansatz (Dorigo, Di Caro & Gambardella, 1999, S. 137-172). Die ACO-Metaheuristik ist so generell gehalten, dass sich darauf aufbauend, mit z.T. nur geringen Änderungen, spezielle Ameisenalgorithmen entwickelt haben und sich auch in Zukunft entwickeln werden, die sich jeweils für die Lösung bestimmter Anwendungsprobleme eignen.

2.2 Anwendungsbereiche

Die Anwendungsbereiche des ACO sind sehr vielfältig. Grundsätzlich kann er für alle diskreten Optimierungsprobleme verwendet werden, für die man einen Mechanismus entwickeln kann, der auf Teillösungen aufbauend Schritt für Schritt zur vollständigen Lösung führt (vgl. Dorigo und Stützle, 2003, S. 6). Aktuelle Anwendungen lassen sich in die zwei Teilklassen der statischen und dynamischen Optimierungsprobleme einordnen. Typische Beispiele für statische Probleme sind das TSP, das gleichzeitig ein Reihenfolgeproblem darstellt oder auch das Quadratic Assignment Problem (QAP), das in die Klasse der Zuordnungsprobleme gehört. Ein Beispiel für ein dynamisches Problem ist das Network Routing Problem, das vor allem in der Telekommunikation eine große Rolle spielt und im weiteren Verlauf dieser Arbeit vorgestellt wird. Bei dynamischen Problemen kann sich die Struktur während des Lösungsprozesses verändern. Beispiele hierfür sind das Wegfallen, die Addition oder die Änderung der Anordnung der Komponenten oder Änderungen der lokalen Informationen, wie z.B. die Änderung der Kosten der zur Verfügung stehenden Wege. Das Network Routing Problem fällt gleichzeitig in die Kategorie der verteilten Probleme. Diese liegen dann vor, wenn das Problem innerhalb eines verteilten Systems auftritt und nur innerhalb dieses Systems gelöst werden kann. Der Prozess der Lösungsfindung ist dadurch auf mehrere Rechner aufgeteilt.

Die folgende Tab. 1 zeigt einen Überblick – ohne Anspruch auf Vollständigkeit - über die mit Ameisenalgorithmen (engl. Ant Algorithms) gelösten Problemstellungen. Zusammengestellt wurde diese Übersicht von Dr. Nils Boysen[2] an der Universität in Hamburg.

Tab. 1 Überblick über die mit Ameisenalgorithmen gelösten Problemstellungen

(Quelle: Boysen, 2004, S. 10)

Abbildung in dieser Leseprobe nicht enthalten

2.3 Biologisches Vorbild der Ameise

Man weiß nicht genau, warum die Ameisen ökologisch so erfolgreich sind. Seit 140 Millionen Jahren hat diese Spezies kaum Änderungen in der Evolution erfahren. Der Schlüssel könnte die Schwarmintelligenz[3] sein, wie sie auch bei anderen Insektenstaaten zu

finden ist (vgl. Bonabeau, Dorigo, Theraulaz, 1999a, S. 9 ff.). Weltweit kennt man rund 12.000 Ameisenarten mit jeweils besonderen Fähigkeiten. Bei vielen Arten sind die visuellen Fähig-keiten kaum ausgebildet und einige Arten sind sogar komplett blind. Die einzelnen Ameisen verfügen nur über einfachste Fähigkeiten, sind jedoch durch die Zusammenarbeit in einer Kolonie und ganz ohne zentrale Rolle eines Befehlgebers in der Lage, erfolgreich ihre täglichen Herausforderungen wie z.B. den gemeinsamen Transport von Gütern oder die flexible Arbeitsteilung zu meistern. Eines der erstaunlichsten Phänomene zeigt sich während der Futtersuche. So ist es den Ameisenkolonien möglich, kürzeste Wege zwischen zwei Punkten - z.B. dem Nest und einer Futterquelle - zu finden, wie folgender Abschnitt zeigt.

2.3.1 Beobachtung der Futtersuche von Ameisen

Ende der 80er Jahre wurde das Verhalten der Ameisen während der Futtersuche von Deneubourg u.a. (1990), sowie von Goss u.a. (1989) experimentell untersucht. Zusammen- gefasst und beschrieben wurden diese Versuche auch in Dorigo und Stützle (2004,

S. 2-5), worauf dieser und der folgende Abschnitt basieren. Das Double Bridge Experiment war grundlegend für die Entwicklung der Ameisenkolonie-Optimierung. Für das Experiment wurde das Volk der argentinischen Ameise Iridomyrmex humilis (I.h.)[4] beobachtet, wie es einen Versuchsaufbau mit zwei variierenden Pfadlängen durchläuft. In der folgenden Abbildung wird der Versuchsaufbau mit dem Nest als Ausgangspunkt und der Futterquelle als Endpunkt dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1 Schematischer Versuchsaufbau „Double Bridge Experiment“,

nach Goss et al. (1989), vereinfachte Darstellung

Zunächst waren beide Pfade, die zur Futterquelle führten gleich lang, siehe Versuchsaufbau a). Die eingesetzten Ameisen konnten frei entscheiden, welchen Weg sie vom Nest aus zur Futterquelle einschlagen wollten. Es wurde in mehreren Durchläufen beobachtet, wieviel Prozent der Ameisen welche Abzweigung nahm. Das überraschende Ergebnis war, dass nach einer gewissen Zeit sich jeweils fast alle Ameisen auf den selben Pfad konzentrierten. Zeitweilig nahmen zwar einzelne Ameisen den zweiten Pfad, dies ebbte jedoch nach gewisser Zeit fast vollständig ab.

Der Versuchsaufbau von a) wurde nun dahingehend abgeändert, dass ein Pfad länger war als der andere, so dass der Versuchsaufbau dem von b) entsprach. Auch dieser Versuchsaufbau wurde in mehreren Durchläufen getestet und es stellte sich heraus, dass die Ameisen sich in den meisten Fällen jeweils auf den kürzesten Pfad konzentrierten. Man hätte nun in Analogie zum Aufbau in a) annehmen können, dass die Ameisen sich zwar in jedem Versuch auf einen Pfad einigen, dies aber zu etwa gleichen Prozentsätzen jeweils der kürzere oder der längere Pfad sein könnte. Was also hat die Ameisen dazu bewegt sich 1. auf nur einen Pfad und 2. sogar (meistens) auf den kürzeren zu beschränken? Diese Frage soll im nächsten Abschnitt geklärt werden.

2.3.2 Das Phänomen der Pheromonspuren

Viele Ameisenarten – so auch die Iridomyrmex humilis - sind fast blind und auch der akustische Sinn kann als nicht sehr ausgeprägt bezeichnet werden[5]. Der Informations-austausch zwischen den einzelnen Individuen geschieht hingegen durch indirekte Kommuni-kation d.h. durch die Veränderung (= Adaption) der lokalen Umwelt. Hierfür hat sich der Begriff Stigmergy[6] eingebürgert. Die Ameisen produzieren chemische Duftstoffe, sogenannte Pheromone[7]. Manche Ameisenvölker wie z.B. die Lasius niger (Bonabeau u.a., 1997) oder auch die argentinische Ameise I.h. produzieren ein spezielles „Pfad-Pheromon“ (engl. trail pheromone), das sie während ihrer Fortbewegung ständig aus einer Drüse am hinteren Teil ihres Körpers auf den Boden absondern. Damit werden Wege auf dem Boden markiert z.B. von den Futterquellen zum Nest und umgekehrt (vgl. Goss u.a.. 1989, S. 579-581). Die Ameisen können diese Duftstoffe als Geruch wahrnehmen und daher dem entdeckten Pfad ebenfalls folgen.

Dies erklärt auch die beschriebene Beobachtung von Ameisen bei der Futtersuche. Zu Beginn des vorher beschriebenen Experiments existierte noch kein Pheromon auf den beiden Pfaden. Die Ameisen wählen zunächst bei a) und b) mit derselben Wahrscheinlichkeit den einen oder anderen Pfad aus. Da jedoch zufällige Häufungen in der Wahl eines Pfades zu einem bestimmten Zeitpunkt auftreten können, wird jeweils ein Pfad stärker markiert als der andere. Dies geschieht bei a) rein zufällig und führt dazu, dass weitere Ameisen diesen Pfad ebenfalls wieder auswählen und schließlich die Masse der Ameisen zu einem Pfad hin tendieren. Im Fall von b) ist die Tendenz hin zum kürzeren Pfad nicht mehr rein zufällig. Es wird zunächst mit gleich hoher Wahrscheinlichkeit der kürzere oder der längere Pfad von den ersten Ameisen ausgewählt, da beide Pfade den Ameisen anfänglich als identisch erscheinen. Da nun jedoch tatsächlich ein Pfad kürzer als der andere ist, erreichen die Ameisen, die sich für diesen Pfad entscheiden, schneller die Futterquelle und finden sich somit auch schneller wieder im Nest ein. Durch die dadurch schon höhere Ablagerung von Pheromon auf dem kürzeren Pfad, wählen auch die nachfolgenden Ameisen mit höherer Wahrscheinlichkeit diesen Pfad aus. Dieses Phänomen ist unter dem Namen „Differential Path Length Effect“ bekannt. Verglichen mit dem Versuchsaufbau unter a) haben bei b) die zufälligen Auswahlentscheidungen weniger Einfluss. Bei beiden Versuchen spielt die Autokatalyse eine große Rolle. Autokatalyse bedeutet, dass eine Entscheidung die im Zeitpunkt t getroffen wurde, die Wahrscheinlichkeit erhöht, dass die selbe Entscheidung zum Zeitpunkt T>t wieder getroffen wird, wodurch erst die Selbstorganisation ermöglicht wird. Durch kleine Entscheidungen und Aktionen, die sich ständig selbst verstärken, werden große „Entscheidungen“ getroffen. Man spricht hierbei von emergentem Verhalten: Das Wirken einzelner Individuen auf der Mikroebene zeigt seine Resultate erst auf der Makroebene.

Interessanterweise kann beobachtet werden, dass trotz der Längenunterschiede im Verlauf des Versuchs immer mal wieder bestimmte Ameisen den längeren Pfad auswählen. Man kann dies als eine Art von „Pfaderforschung“ ansehen, das adaptives Verhalten ermöglicht und das Gefangensein in lokalen Optimas weitgehend verhindert. Ein nicht ganz so positives Ergebnis, das jedoch zur Entwicklung von ACO beitrug, brachte folgende Abänderung des Experiments. Zu Beginn wurde den Ameisen nur der längere Pfad zur Verfügung gestellt und nach 30 Minuten wurde der kürzere Pfad hinzugefügt. In diesem Fall wählten die Ameisen den kürzeren Pfad nur sehr selten und nach einer gewissen Zeit war die Ameisenkolonie im längeren Pfad „gefangen“. Hier war offensichtlich die Pheromonverdunstung, die naturgemäß auftritt, nicht groß genug, um das suboptimale Ergebnis vergessen zu lassen und adaptives Verhalten zu ermöglichen. Dieses hier beschriebene kollektive, selbstorganisierende Verhalten der Ameisen ist die inspirierende Quelle für die Entwicklung der Ameisenalgorithmen (vgl. Dorigo und Stützle, 2004, S. 2). Wie sagte schon in Walt Disney’s Film „A Bug’s Life – Das große Krabbeln“ Flik, die Ameise, so schön, nachdem ein Blatt als Hindernis mitten in eine Ameisenstraße fiel: „I am lost! Where is the line?!”

2.4 Einführung in das Konzept der „Künstlichen Ameise“

Es wurde bisher gezeigt, dass echte Ameisenkolonien eine „eingebaute Optimierungsfähigkeit“ (vgl. Dorigo und Stützle, 2004, S. 7) besitzen. Man kann sich nun vorstellen, dass man, um die Vorlage der Natur in mathematische Algorithmen umzusetzen, „einfach“ die doppelte Brücke aus dem Experiment durch einen Graph und die Pheromonspuren durch „Künstliche Pheromonspuren“, d.h. Gleichungen, die einen Akkumulationsprozess simulieren, ersetzen kann.

Um darüber hinaus in der Lage zu sein, kompliziertere Probleme als die der echten Ameisen zu lösen, vergibt man den „Künstlichen Ameisen“ veränderte bzw. zusätzliche Fähigkeiten. Eine Veränderung besteht z.B. darin, keine Ablage von Pheromonen auf dem „Hinweg“, d.h. während des wahrscheinlichkeitsgestützten schrittweisen Aufbaus einer Lösung, zuzulassen. Dadurch wird verhindert, dass die Lösung im Kreis verläuft und im schlimmsten Fall die Ameise in dieser Wiederholungsschleife gefangen bleibt. Erst auf dem Rückweg, nachdem eine ausführbare Lösung gefunden wurde und eventuelle Schleifen eliminiert wurden, kann damit Pheromon abgelegt werden. Man kann jedoch die Ablage auf dem Hinweg nicht ohne eine Gegenmaßnahme verhindern, da sichergestellt sein muss, dass die künstliche Ameise ihren Weg vom Ausgangspunkt zum Endpunkt nach der Lösungsfindung kennt. Die Lösung stellt die Einführung eines „Gedächtnis“ dar, das den künstlichen Ameisen die Möglichkeit gibt, den gleichen Hin- und Rückweg zu wählen. Die Pheromonablage der künstlichen Ameisen auf dem Rückweg geschieht im Unterschied zu den echten somit deterministisch und nicht wahrscheinlichkeitsgestützt (vgl. Dorigo und Stützle, 2004, S. 9-11). Ein weiterer Vorteil des „Gedächtnis“ ist die Möglichkeit, weitere Beschränkungen (= Nebenbedingungen) in die Problemrepräsentation einzufügen. Die zusätzliche Fähigkeit der „Künstlichen Ameisen“ die sie in die Lage versetzt, eine Menge an Pheromon proportional zur Güte der gefundenen Lösung abzulegen, ist durchaus auch auf die Inspiration durch einige echte Ameisenarten zurückzuführen. Zum Beispiel legt die Lasius niger auf dem Rückweg zum Nest eine Menge Pheromon ab, das proportional gesehen der Qualität der Futterquelle entspricht (Beckers u.a.., 1993, S. 751-759).

Für die Entwicklung der Algorithmen auf der Grundlage des Verhaltens echter Ameisen-kolonien sind zusammenfassend die Mechanismen der Stigmergy und der Autokatalyse, der Differential Path Length Effect, die Pfaderfor4chung und die Pheromonverdunstung immens wichtig (vgl. Dorigo und Stützle, 2004, S. 2).

Die Kernidee besteht darin, ein „Volk“ von künstlichen Ameisen, zukünftig auch Agenten genannt, Simulationen durchführen zu lassen in denen die Lösungssuche mehrfach und jeweils gleichzeitig von vielen Agenten durchlaufen wird. Dies geschieht oft mit Hilfe des Verfahrens der lokalen Suche[8], um die gefundenen Lösungen schrittweise zu verbessern (vgl. Dorigo und Stützle, 2003, S. 27). Nicht nur hierzu, sondern auch für die Wegsuche selbst, orientieren sich die Agenten zusätzlich an einer heuristischen Information, einer Prioritätsregel, die - übertragen auf die Wegsuche im TSP - bei der nächstgelegenen Weggabelung die Kanten je nach Länge unterschiedlich betont.

Charakteristisch ist ebenfalls, dass die künstliche Ameise nach ihrer Pfadsuche und ggfs. Pfadverstärkung „stirbt“ und alle gebundenen Ressourcen frei gibt.

Im nun folgenden Abschnitt geht es schließlich um die Umsetzung des biologischen Vorbilds in einen metaheuristischen Ansatz, der als Modellrahmen für die Lösung vielfältigster diskreter Optimierungsprobleme herangezogen werden kann.

3 Teilalgorithmen und Komponenten der „Ant Colony Optimization“

Zur Repräsentation eines diskreten Optimierungsproblems gehört eine endliche Menge von Knoten und eine endliche Menge von gewichteten Kanten, die in einem Graph dargestellt werden können. Die Gewichtung bzw. Prioritätsfestlegung einer Kante entsteht durch eine Kostenfunktion, die als heuristische Information beispielsweise zeit- oder entfernungs-abhängig a priori hergeleitet werden kann. Die Kostenfunktion kann sich bei dynamischen Problemen auch im Zeitablauf ändern. Eventuell können auch mehrere Gewichtungen auf einer Kante existieren. Die Kanten können gerichtet oder ungerichtet sein. Bei ungerichteten Kanten sind die Kosten nicht von der Bewegungsrichtung abhängig. Dies ist z.B. in Abb. 1 beim Beispiel der Futtersuche der Fall. Wenn die Kanten gerichtet sind, können sich die Kosten von Knoten A zu Knoten B gegenüber den Kosten von Knoten B zu Knoten A unterscheiden. Dies kommt u.a. beim Network Routing Problem häufig vor. Desweiteren können Beschränkungen, beispielsweise bezüglich der Start- und Zielknoten oder der Existenz von Kanten, definiert werden. Eine weitere charakteristische Eigenschaft von Optimierungsproblemen ist, dass das Problem mehrere Zustände aufweist. Diese werden als Sequenzen von Knoten ausgedrückt, wobei die Menge aller gültigen Sequenzen alle Beschränkungen erfüllen muss. Die Lösung eines diskreten Optimierungsproblems ist eine gültige Sequenz, die alle Anforderungen des Problems erfüllt. Die Aufgabe besteht darin, den Pfad (= Sequenz) im Graphen zu finden, der die Gesamtkostenfunktion unter Beachtung der Nebenbedingungen minimiert. Die Gesamtkosten der Lösung ergeben sich aus einer bestimmten Funktion, die von den Kosten aller Kanten, die in der Lösung enthalten sind, abhängig ist. Des Weiteren existiert eine geregelte Nachbarschaftsstruktur[9], die besagt, welche Sequenzen miteinander benachbart sind (vgl. Dorigo und Di Caro, 1999, S. 1470).

Der Pseudo-Rahmencode für den ACO Metaheuristik Algorithmus ist sehr einfach und wird in Abb. 2 vorgestellt.

[...]


[1] richtiger: NP-schwer, NP = nicht deterministisch polynomielle Zeit

[2] Dr. Boysen ist seit dem Beginn des SS08 an der Universität Jena als Lehrstuhlinhaber „ABWL und Operations Management“ tätig.

[3] siehe auch Kapitel 5

[4] jetzt Linepithema humile (vgl. Goss u.a.., 1989 und Deneubourg u.a., 1990).

[5] Die Ameisen sind nahezu taub für Schallwellen, die durch Luft übertragen werden. Sie sind aber sehr empfind-lich gegenüber Klangvibrationen, die durch Objekte übertragen werden. Dies ist für manche Ameisenarten ein sehr wirkungsvolles Warnsignal (Hölldobler und Wilson, 1990, S. 255-258), kann jedoch für die Effizienz bei der Futtersuche nicht als Erklärung herangezogen werden.

[6] Dieser Begriff wurde 1959 durch den französischen Biologen Pierre-Paul Grasse für die Beschreibung des Verhaltens von Termiten eingeführt (vgl. Wikipedia: Stigmergy) und durch Eric Bonabeau (1999) geprägt.

[7] Das Wort „Pheromon“ setzt sich aus den Wörtern "Pher" für „Tragen“ und "Hormon" zusammen und bedeutet somit soviel wie "Hormonträger".

[8] vgl. hierzu auch die beschriebenen Dämon-Aktionen in Abschnitt 3.3

[9] Eine Nachbarsequenz s2 von s1 muss immer in einem logischen Schritt von s1 zu s2 erreicht werden können. Ein logischer Schritt kann darin bestehen, dass man sich bei der letzten Weggabelung nicht für die Kante, die bei s1 ausgewählt wurde, entscheidet, sondern für eine andere von der Weggabelung aus erreichbare Kante. Es müssen somit alle Elemente der Sequenz von s2 bis auf ein Element gleich wie die Elemente von s1 sein

Details

Seiten
34
Jahr
2008
ISBN (eBook)
9783640399635
ISBN (Buch)
9783640399468
Dateigröße
576 KB
Sprache
Deutsch
Katalognummer
v133300
Institution / Hochschule
FernUniversität Hagen
Note
2
Schlagworte
Travelling Salesman Problem Ameisenkolonieoptimierung Netrouting-Problem Heuristik Metaheuristik Genetischer Algorithmus Swarm Intelligence Schwarmintelligenz

Autor

Teilen

Zurück

Titel: Ant Colony Optimization - Ameisenkolonie-Optimierung