Ant Colony Optimization - Ameisenkolonie-Optimierung - Ameisenkolonie-Optimierung (German, Electronic book text)

Die Losung NP-harter kombinatorischer Optimierungsprobleme - nicht nur im betriebswirtschaftlichen Bereich - ist mit einer gravierenden Schwierigkeit, namlich dem mehr als polynomiell, das heisst zum Beispiel exponentiell ansteigenden Bearbeitungsaufwand verbunden. Dies ruhrt daher, dass die Zahl der benotigten Rechenoperationen fur eine exakte algorithmische Losung starker als polynomiell mit der Komplexitat der Problemstellung anwachst, so dass schon mittlere Probleme eine Rechenzeit benotigen, die auch bei Verwendung aller Supercomputer der Welt nicht bis zum Ende der Lebensdauer des Sonnensystems abgearbeitet ware. Ungeachtet dessen treten solche Probleme uberaus haufig in der Praxis auf. Zu finden sind diese vor allem bei vielen Planungsaufgaben und es ist von grosser okonomischer Bedeutung, diese Probleme doch zu losen, zumindest naherungsweise oder umgangssprachlich 'so gut wie es geht'. Geeignete Verfahren konnen vor allem im Bereich von Heuristiken gesucht werden. Heuristiken stellen Algorithmen dar, die haufig, d.h. fur viele praktisch wichtige Eingaben, gute, wenn auch nicht exakte, so doch annahernd optimale Losungen hervorbringen.Im Verlauf der beiden letzten Jahrzehnte zeigte sich ein starkes Interesse an Verfahren, die von naturlichen Vorgangen inspiriert sind. Eines der jungsten 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 naturlichen Verhaltens heuristisch zu losen. In dieser Seminararbeit wird dieses Verfahren beschrieben, die Anwendung an Beispielen illustriert und in das ubergreifende Feld der Swarm Intelligence eingeordne