Schwarmalgorithmen

Aus ProgrammingWiki

Die Schwarmintelligenz ist ein Forschungsfeld der künstlichen Intelligent und hat nahe Bindungen an die Agententechnologie. Als Agent meinen wir hier ein Computerprogramm, welches zu einem gewissen eigenständigem Verhalten fähig ist. Auch die Begriffe verteilte künstliche Intelligenz sowie kollektive Intelligenz im Allgemeinen sind für Schwarmintelligent i.w.S. gebräuchlich. Dabei wird versucht, in einem Computerprogramm das Verhalten von intelligenten Schwärmen zu simulieren. Besonders geeignet sind Schwarmalgorithmen, um für sehr komplexe Probleme schnell gute (keine optimalen) Lösungen zu finden.

Schwärme in der Natur

Die Schwarmalgorithmen sind, wie neuronale Netze, genetische Algorithmen und vieles andere auch, aus der Natur abgeguckt. Etwa bei Ameisen, Termiten, Vögeln, Fischen, Binen und anderen Tieren kann man beobachten, dass sie in einem Schwarm Aufgaben lösen, zu denen ein Individuum allein nicht fähig wäre.

So schaffen es Termiten z. B. extrem komblexe Bauten zu errichten, obwohl keine Termite weiß, wie der gesamte Bau aussehen und es keine "Super-Termite" gibt, welche den anderen Anweisungen gibt.

Wenn wir uns überlegen, was passieren würde, wenn man ein paar Hundert Menschen hinsetzt, und sie unkoordiniert versuchen lässt, ein Haus zu bauen, erkennt man schnell, dass bei einem Schwarm diesen Tieren eine Art Intelligenz vorliegt.

Futtersuche von Ameisen

Die Suche nach Futter gehört für jedes Lebewesen zu einer existentiellen Aufgabe. Ameisen sind dabei bei der Bewältigung dieser Aufgabe besonders effizient. Dabei markieren die Ameisen beim Ausschwärmen aus dem Nest ihren Weg mit Pheromonen, die ihre Artgenossen als Wegweiser wahrnehmen. Sobald eine Ameise Futter gefunden hat, kehrt sie damit zum Nest zurück. Der Rückweg ist dabei der Weg, mit der größten Intensität an Pheromonen. Wenn die Ameise als erste an ihrem Futter war, kehrt sie auf ihrem eigenen Weg wieder zurück, und hinterlässt auf dem Weg wieder Pheromone. Da alle Ameisen etwa die gleiche Geschwindigkeit haben, wird automatisch der kürzeste Weg zum Futter der, mit der höchsten Intensität an Pheromonen, da die anderen Ameisen noch nicht wieder am Nest angekommen sind. Dabei ist aber zu beachten, dass jede Ameise nur mit einer bestimmten Wahrscheinlichkeit dem Weg mit der stärksten Ausprägung an Pheromonen folgt, so können Abkürzungen gefunden werden und neue Wege zu neuen Futterquellen erschlossen werden. Außerdem verliert das Pheromon mit der Zeit an Intensität.

Die Ameiste schafft es also automatisch, den kürzesten Weg zu ihrem Ziel zu finden. Dieses Problem erinnert uns, leicht abgewandelt, an das altbekannte Problem des Travelling Salesman. Mit Hilfe von sogenannten Ameisenalgorithmus kann man hierfür in wenigen Iterationen eine gute Lösung bekommen.

Java-Applet für TSP-Simulation mit Ameisen

http://www.ameisenalgorithmus.de/appletantstour.htm

TSP - Manuell

http://www.ameisenalgorithmus.de/appletmanuelletour.htm

http://www.m-boehmer.de/pdf/Schwarmintelligenz_Artikel.pdf