Inhaltsverzeichnis

1  Einleitung  1

2  Vorstellung des Ant Colony Optimization Ansatzes  1

2.1  Historische Entwicklung  1

2.2  Anwendungsbereiche  2

2.3  Biologisches Vorbild der Ameise.  3

2.3.1  Beobachtung der Futtersuche von Ameisen  4

2.3.2  Das Phänomen der Pheromonspuren  5

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

3  Teilalgorithmen und Komponenten der Ant Colony Optimization  8

3.1  Ameisen-Generierung und -Aktivitäten  10

3.2  Pheromon-Verdunstung.  15

3.3  Optionale Dämon-Aktionen  17

4  Lösung eines Network Routing Problem  18

4.1  Darstellung des zu lösenden Problems  18

4.2  Vorstellung des Verfahrens  19

4.2.1  Ameisen-Generierung und -Aktivitäten  20

4.2.2  Pheromon-Verdunstung.  23

4.2.3  Optionale Dämon-Aktionen.  23

4.2.4  Lösungsgüte im Vergleich zu alternativen Verfahren  24

5  Einordnung des Ansatzes in das Konzept der Swarm Intelligence.  25

5.1  Grundlagen der Swarm Intelligence.  25

5.2  Bedeutung des Ant Colony Optimization Ansatzes  26

6  Zusammenfassung  27

Literaturverzeichnis.   28

Anhang   31

Abbildungsverzeichnis   

Abb.  1 Schematischer Versuchsaufbau „Double Bridge Experiment“  4

Abb.  2 Pseudo-Algorithmus ACO-Metaheuristik, Teil 1  9

Abb.3  Darstellung eines sehr einfachen Travelling Salesman Problem  10

Abb.  4 Pseudo-Algorithmus ACO-Metaheuristik, Teil 2  10

Abb.  5 Pseudo-Algorithmus ACO-Metaheuristik, Teil 3  10

Abb.  6 Monte-Carlo-Auswahl in Zyklus 1  13

Abb.  7 Berechnung der Weglänge  15

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

Abb.  9 Pseudo-Algorithmus AntNet  19/20

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

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

Tabellenverzeichnis   

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

Tab.  2 Ant-Routing Tabelle A i zu Beginn des Zyklus 1  13

Berechnung  neue Markierungsmengen W ij nach Zyklus 1  15

Tab.   3

Berechnung  neue Markierungsmengen W ij nach der Pheromonverdunstung.  16

Tab.   4

Tab  5 Berechnung neue Ant-Routing Tabelle A i nach der Pheromonverdunstung  16