Information Technology Reference
In-Depth Information
auch hier finden die Ausreißer immer noch neue Wege. Somit liefert der Ameisenalgo-
rithmus, modelliert auf die Problematik des Handlungsreisenden eine optimierte Lösung,
sprich: eine optimale Wege- bzw. Routenplanung. Das Problem ist abstrakt, einfach zu
verstehen und wurde als klassisches Shortest-Path-Problem in den vorangegangenen Ab-
schnitten bereits behandelt. Bei dieser Behandlung zeigte sich, dass mathematisch be-
trachtet, n! mögliche Touren für den Reisenden existieren. Das Problem lässt sich ebenfalls
darstellen als Graph (N, E) mit der Menge der Städte N und deren Verbindungen E. Der
Graph muss nicht symmetrisch sein und schon bei einer kleinen Anzahl von Städten lassen
sich nicht alle Touren und deren Längen berechnen. Leider erweist sich die Lösung dieses
Problems als außerordentlich schwierig. Es handelt sich nämlich um ein sogenanntes NP-
adäquates Problem. Nach heutigem Wissensstand existiert kein Lösungsalgorithmus, der
eine Optimallösung für ein NP-adäquates Problem in vernünftiger Zeit bestimmen kann.
In diesem Abschnitt wird ein System entwickelt, das auf der oben beschriebenen Fut-
tersuche von Ameisen beruht. Gibt es zwischen Nest und Futterquelle mehrere mögliche
Wege, so wird sich mit der Zeit auf dem kürzesten Pfad die höchste Pheromonkonzentra-
tion einstellen, so dass dieser Weg von den Ameisen bevorzugt wird. Der zu entwickelnde
Ameisenalgorithmus simuliert das Verhalten solcher Ameisen auf der Suche nach Futter
um das Optimierungsproblem zu lösen. Dabei werden Ameisen simuliert, die durch den
Graphen reisen, wobei die Zeit diskretisiert wird. Am Ende der Reise liefert das System
eine Heuristik für die Lösung des Problems.
Das Ergebnis eines Systemlaufes kann dabei grafisch dargstellt werden. Die Dicke der
Linien weist auf die Verteilung des Pheromons hin. Neben sehr stark markierten Kanten
gibt es solche, die etwas weniger Konzentration vorweisen und solche, die kaum mit Duft-
stoffen behaftet wurden. Das Bild zeigt außerdem die im weiteren Verlauf gefundene beste
Lösung (rechts). Die Pfade, die eine geringere Pheromonkonzentration aufweisen, können
als alternative Routen angesehen werden. Diese werden vor allem dann relevant, wenn
man von einem statischen Problem zu einem eher dynamischen Problem übergeht. Fügt
man nämlich weitere Knoten in den Graphen ein oder nimmt man welche heraus, so ist das
System in der Lage, schnell auf diese Gebenheiten zu reagieren und eine neue optimale
Lösung zu finden.
Literatur
Bauer, F.L., Wirsing, M.: Elementare Aussagenlogik. Springer, Berlin (1991)
Beck K.: Test Driven Development. Addison-Wesley, Reading (2003)
Bunke, H.: Künstliche Intelligenz und Expertensysteme: Grundlegende Begriffe, Anwendungen
und zukünftige Perspektiven, in: Bunke, H.; Mey, H. (Hrsg.): Künstliche Intelligenz und Ex-
perten Beiträge zur Mathematik, Informatik und Nachrichtentechnik Bd. 8, S. 11-24, Bern
( 1987)
Haun, M.: Cognitive Organisation. Springer, Berlin (2015)
Hitz, M., Kappel, G.: Von der Analyse zur Realisierung, 2. Aufl. dpunkt, Heidelberg (2003)
Jobst, F.: Einführung in Java, 2. Aufl. Fachbuchverlag, Leipzig (2001)
