Ob Ameisen, Bienen, Wespen oder Termiten: Insekten, die in Kolonien leben, haben seit jeher Forscher wie Künstler inspiriert. Der belgische Dichter Maurice Maeterlinck schrieb 1926 in seinem Buch „Das Leben der Termiten“: „Was regiert hier? Was gibt die Befehle, sieht die Zukunft voraus, schmiedet Pläne und bewahrt das Gleichgewicht?“ Auch über siebzig Jahre später sind dies immer noch große Rätsel.

Jedes Insekt einer Kolonie scheint selbstständig zu handeln, und doch wirkt der Staat als Ganzes hoch organisiert. Offenbar erfordert die nahtlose Zusammenfügung aller individuellen Aktivitäten zu einem Ganzen keinerlei spezielle Oberaufsicht. Wissenschaftler entdeckten, dass die Zusammenarbeit innerhalb einer Kolonie größtenteils selbstorganisiert ist; das heißt, sie entsteht in zahllosen Situationen aus Interaktionen unter Individuen. Jede einzelne von ihnen mag einfach sein – eine Ameise folgt etwa einem Pfad, den eine andere vorher markiert hat. Im Zusammenspiel können sie jedoch die Lösung schwieriger Probleme liefern, etwa unter unzähligen Wegen zu einer Nahrungsquelle den kürzesten zu finden. Diese kollektive Leistung nennen die Wissenschaftler auch „Schwarmintelligenz“.

In den letzten Jahren stießen Forscher und Ingenieure auf immer mehr Möglichkeiten und Ansätze, Schwarmintelligenz für technische Probleme einzusetzen:

- Die Futtersuche von Ameisen inspirierte sie zu einer neuartigen Methode für die Verbindungssteuerung in überlasteten Telekommunikationsnetzen.

- Die Kooperation von Ameisen beim Transport eines großen Futterstückes führt vielleicht zu effizienteren Algorithmen zur Robotersteuerung.

- Die Art, wie Insekten ihre Toten beiseite schaffen oder ihre Larven sortieren, kann die Analyse von Bankdaten verbessern.

- Die Arbeitsteilung bei Honigbienen hilft möglicherweise, die Fertigung am Fließband in Fabriken besser zu organisieren.

Virtuelle Futtersuche

Eine der frühen Studien über Schwarmintelligenz untersuchte das Verhalten von Ameisen bei der Futtersuche. Jean-Louis Deneubourg von der Freien Universität Brüssel und seine Mitarbeiter zeigten, dass die „Ameisenstraßen“, die man oft in der Natur (und in der Küche) sehen kann, dadurch entstehen, dass einzelne Ameisen ein Pheromon ausscheiden, einen Duftstoff, der andere Ameisen anzieht. Deneubourg, ein Vorreiter auf diesem Gebiet, zeigte auch, dass die Kennzeichnung eines Pfades durch Duftstoffe, dem andere Ameisen folgen können, zugleich eine gute Strategie ist, um den kürzesten Weg zwischen Nest und Futterquelle zu finden.

In Untersuchungen mit argentinischen Ameisen (Linepithema humile) baute Deneubourg zwischen Nest und Futterquelle eine Brücke mit zwei Wegen, der eine doppelt so lang wie der andere. Innerhalb weniger Minuten wählte die Kolonie gewöhnlich den kürzeren Weg. Der Belgier fand heraus, dass die Ameisen bei der Futtersuche Pheromonpfade markieren und ihnen folgen. Die Ameisen, die als Erste von der Futterquelle zum Nest zurückkehren, sind diejenigen, die in beiden Richtungen den kürzeren Weg genommen haben, hin zur Futterquelle und zurück zum Nest. Da diese Route die erste ist, die doppelt mit dem Pheromon markiert wird, ist sie es, der dann auch die anderen Ameisen folgen.

Wenn man allerdings den Ameisen den kürzeren Weg erst nach einer Weile anbietet, benutzen die Ameisen ihn nicht, weil ja der längere bereits mit Pheromon markiert ist. (Das Pheromon der Ameise L. humile verflüchtigt sich zwar mit der Zeit, aber nur sehr langsam.) Aber in einem künstlichen System können die Programmierer dieses Problem dadurch umgehen, dass sie das Pheromon schneller verdunsten lassen. In dieser Situation können längere Wege kaum stabile Pheromonpfade bleiben. Vielmehr wählen die Software-Ameisen einen kürzeren Weg, selbst wenn er verspätet angeboten wird. Durch diesen Kunstgriff wird verhindert, dass das System gegen eine schlechte Lösung konvergiert.

In einer Computersimulation solcher Pheromonverdunstung boten die Forscher einer virtuellen Ameisenkolonie in unterschiedlichen Abständen vom Nest gleiche Futterquellen an (siehe Grafik Seite 73 oben). Zuerst untersuchten die Software-Ameisen das Terrain per Zufall. Dann legten sie zwischen jeder Futterquelle und dem Nest Pfade an. „Aktiv“, das heißt mit hohen Konzentrationen virtuellen Pheromons ausgestattet, blieben jedoch nur die Pfade zu den Quellen, die dem Nest am nächsten lagen. Erst als diese zur Neige gingen, begannen die künstlichen Ameisen auch die entfernteren Quellen zu nutzen.

Marco Dorigo, Informatiker an der Freien Universität Brüssel, und seine Kollegen erweiterten dieses Ameisenmodell und wandten es auf das berühmte „Problem des Handlungsreisenden“ (travelling salesman problem, TSP) an. Bei diesem Problem ist der kürzeste Rundreiseweg durch eine Reihe von Städten gesucht (vergleiche Spektrum der Wissenschaft, 4/1999, S. 76). Dieser Test war besonders spannend: Das Problem ist leicht zu formulieren, aber nur sehr schwer zu lösen.

Bei solchen Problemen versucht man in der Praxis, anstelle der exakten Lösung eine hinreichend gute Näherung zu finden – eine Wegstrecke, die hinreichend kurz ist, aber nicht unbedingt die kürzestmögliche. Dorigo konnte zeigen, dass er solche fast optimalen Wege mit künstlichen Ameisen finden kann, die je nach Länge des durchlaufenen Weges mehr oder weniger Pheromon ausscheiden (Kasten Seite 74).

Ähnliche Verfahren haben sich auch bei anderen Optimierungsproblemen als erfolgreich erwiesen. Beispielsweise liefern künstliche Ameisen die beste Lösung für eine Art des Maschinenbelegungsproblems: Die Herstellung eines Produkts ist so unter verschiedenen räumlich entfernten Produktionsstätten aufzuteilen, dass Zwischenprodukte möglichst wenig hin- und hertransportiert werden müssen.

Von ähnlichen Anwendungen berichten David Gregg von der Firma Unilever in England und Vincent Darley von der Bios-Gruppe in Santa Fe (New Mexico). Sie entwickelten ein Ameisenverfahren, um gewisse Ar-beitsprozesse in einer großen Unilever-Fabrik zu optimieren. Das Programm muss dabei den Einsatz diverser Lagertanks, chemischer Mischmaschinen, Verpackungsbänder und anderer Gerätschaften planen.

Neben solchen, im Wesentlichen „statischen“ Optimierungsproblemen kommen ameisenartige Agenten aber auch mit dynamischen, also schnell veränderlichen Umgebungen zurecht, beispielsweise wenn in einer Firma eine Maschine plötzlich ausfällt. Weil die virtuellen Ameisen ständig Pheromonspuren legen und neue Wege ausprobieren, haben sie stets auch Informationen über Alternativpläne verfügbar. So können sie auf plötzliche Veränderungen in ihrer Umgebung rasch reagieren. Diese Eigenschaft, die vielleicht auch den ökologischen Erfolg der echten Ameisen erklärt, ist für viele Anwendungen außerordentlich bedeutsam.

Beispiel Telefonnetzwerk: Das Problem in solchen Netzen ist die dynamische Unvorhersagbarkeit der Telefonverbindungen, mit der Folge von Staus und langsameren Verbindungen. Schlechtes Wetter auf einem Flugplatz zum Beispiel oder eine TED-Telefon-Aktion einer Fernsehanstalt können in einem Netz lokal Engpässe erzeugen, die sofortige Umverteilung sogar bereits bestehender Verbindungen auf weniger belastete Teile des Gesamtnetzes erfordern.

Ein Anruf von A nach B wird gewöhnlich über einige Schaltstationen weitergeleitet. An jeder Station entscheidet ein Programm für jeden Anruf, an welche Schaltstation es ihn weiterreicht, bis die komplette Verbindung von A nach B steht. Natürlich sollte der Algorithmus überlastete Strecken tunlichst umgehen und geeignete Ausweichrouten so schnell parat haben, wie sich die Bedingungen verändern.

Um mit solchen Situationen zurechtzukommen, entwickelten Ruud Schoonderwoerd und Janet Bruten von der Hewlett-Packard-Forschung in England sowie Owen Holland von der Universität von West-England ein Weiterleitungsverfahren, bei dem ameisenartige Agenten in den Netzwerkknoten bestimmte Informationsbits, „virtuelle Pheromone“, hinterlegen – je geringer die Auslastung einer Strecke, desto mehr. Ein „Verdunstungsalgorithmus“ sorgt dafür, dass veraltete Information das Verhalten des Netzes nicht beeinflusst.

Genauer: Jeder Knoten führt eine Tabelle, in der für jeden Zielort und für jede Verbindung eingetragen ist, wie geeignet zur Zeit diese Verbindung für diesen Zielort ist. Ein Gespräch wird dann bevorzugt auf eine Verbindung gelegt, die für diesen Zielort in der Tabelle eine hohe Punktzahl hat. Ameisenartige Agenten aktualisieren diese Tabellen ständig, sodass sie die momentane Netzwerksituation widerspiegeln. Die Tabelleneinträge entsprechen dabei Pheromonkonzentrationen. Registriert ein Agent eine längere Verzögerung, etwa weil er sich gerade durch einen überlasteten Netzabschnitt bewegt, fügt er dem zugehörigen Tabelleneintrag nur sehr wenig Digital-Pheromon hinzu. Gelangt der Agent dagegen schnell von einem Knoten zum nächsten, wird er diesen Weg weiterempfehlen, indem er den entsprechenden Tabelleneinträgen mehr „Pheromon“, also viele Bewertungspunkte hinzufügt. Diese Regelung führt zu einem dynamischen Lastenausgleich: Sie ist so ausbalanciert, dass selbst viele Agenten auf einem überfüllten Weg insgesamt weniger „Pheromon“ hinterlegen als die wenigen, die sich einer freien Bahn erfreuen.

Alle Punktzahlen der Tabellen werden regelmäßig um einen kleinen Betrag reduziert („Verdunstung“). Dieses Verfahren sowie die Erhöhung der Tabellenwerte durch die Ameisen-Agenten wirken zusammen. Resultat: Auf Staustrecken überwiegt die Pheromon-Verdunstung, auf weniger belasteten Strecken die Verstärkung.

Wenn dieses Gleichgewicht von Verdunstung und Verstärkung plötzlich gestört wird, etwa weil auf einer bislang freien Strecke die Anrufe sich häufen, kommen die Agenten dort langsamer voran, die Verdunstung wird durch die Verstärkung nicht mehr aufgewogen, und bald wird diese Route gänzlich aufgegeben; Alternativrouten werden entdeckt (oder wiederentdeckt) und genutzt. Der Nutzen ist doppelt: Sobald Telefonverbindungen in weniger belastete Netzteile umgeleitet werden, kommen sie schneller zu Stande, und die überlasteten Teile können sich vom Stau erholen.

Mehrere Telefongesellschaften arbeiten derzeit an Anwendungen dieses Prinzips. So haben France Télécom und British Telecommunications solche Methoden schon vor Jahren in ihren Netzen eingesetzt. In den USA benutzt MCI Worldcom künstliche Ameisen nicht nur zur Steuerung seiner Telefonnetze, sondern auch für andere Aufgaben, etwa zur Rechnungsstellung. Als echte Bewährungsprobe dieser Verfahren gilt allerdings das Internet, auf dem der Verkehr besonders chaotisch abläuft.

Für diesen Zweck haben Dorigo und sein Kollege Gianni Di Caro die Agenten weiterentwickelt. Sie berücksichtigen weitere Faktoren, darunter die Gesamtzeit, die eine Information von der Quelle bis zum Ziel unterwegs ist. (Bei Telefonnetzen wird sonst nur die Laufzeit zwischen zwei benachbarten Knoten berücksichtigt.) In Simulationen optimierte das Verfahren der belgischen Forscher sowohl den Durchsatz als auch die Verzögerungszeiten besser als jedes andere Routingverfahren. Darüber hinaus zeigen umfangreiche Tests, dass die Ameisenmethode besser ist als das zur Zeit praktizierte Übertragungsprotokoll „kürzester freier Weg zuerst“ (Open Shortest Path First). Denn im Internet müssen sich die Knoten einander ständig über den Zustand ihrer Verbindungen informieren, was zusätzliche Zeit verbraucht.

Kisten schieben, Bankkunden sortieren, Autos lackieren: ein Schwarm von Anwendungen

In diversen Forschungsprojekten analysierten Informatiker weitere Verhaltensmuster von Insekten, die in sozialen Gemeinschaften leben:

- Aus dem Verhalten von Insektenschwärmen versuchen sie, neue Methoden zur Steuerung von Robotergruppen abzuleiten. Eine Anwendung betrifft den „kooperativen Transport“ (Kasten unten). Mit solchen Methoden gelang Ingenieuren bereits der Entwurf relativ einfacher und billiger Roboter, die miteinander kooperieren und dabei zunehmend komplexere Aufgaben bewältigen sollen.

- Ein Modell, das erklärt, wie Ameisen ihre Toten sammeln und ihre Lar-ven sortieren, nutzten sie als Grundlage zur Analyse von Finanzdaten (Kasten Seite 75).

- Die flexible Verteilung der Arbeiten bei Honigbienen untersuchen sie mit dem Ziel, die Effizienz gängiger Verfahren zur Arbeitsverteilung in Fabriken zu steigern (Kasten rechts).

- Nach dem Vorbild der Wespen beim Nestbau konzipierte Dan Petrovich von der Technischen Hochschule der US-Luftwaffe in Dayton (Ohio) einen Schwarm winziger, sich autonom steuernder Satelliten, die sich in der Erdumlaufbahn zu größeren Strukturen zusammenfügen können.

- H. Van Dyke Parunak vom Umwelt-Forschungsinstitut von Michigan in Ann Arbor entwickelt insektenartige Software-Agenten, um damit Fabrikationsprobleme zu lösen – beispielsweise bei der Rohmaterialversorgung.

- Paul B. Kantor von der Rutgers-Universität in New Brunswick (New Jersey) entwickelte nach Prinzipien der Schwarmintelligenz ein Computerprogramm, um im World Wide Web und anderen großen Netzwerken Informationen aufzuspüren. Insofern sie einer bestimmten „Kolonie“ von Benutzern angehören, können damit Websurfer auf der Suche nach interessanten Seiten von Informationen in Form digitaler Pheromone (Punktebewertungen) profitieren, die andere Benutzer bei vorangehenden Suchaktionen hinterlassen haben.

Schwarmintelligenz hat zahlreiche Einsatzgebiete. Sie bietet eine Möglichkeit zum Entwurf von Systemen, die ansonsten einer zentralen Steuerung sowie aufwendiger Programmierung bedurft hätten. Nun stehen Autonomie und Einfachheit an erster Stelle; einzig die direkten oder indirekten Wechselwirkungen zwischen einfachen, individuellen Agenten halten das System zusammen und machen es in besonderem Maße anpassungsfähig.

Aber noch steckt das ganze Gebiet in den Kinderschuhen. Weil Biologen und Verhaltensforscher selbst noch nicht genau verstehen, wie Insektenschwärme eigentlich funktionieren, ist im Detail noch weniger klar, wie die Individuen innerhalb solcher Schwärme miteinander wechselwirken. Ohne derartige Kenntnisse lässt sich auch entsprechende Software kaum entwickeln.

Gelegentlich wird kritisiert, dass der Einsatz autonomer, insektenartiger Agenten zu unvorhersagbarem Verhalten bei den Computern führe, in denen diese Kreaturen virtuell existieren. Der vermeintliche Nachteil könnte sich jedoch als eine Stärke erweisen: Vielleicht sind solche Systeme weitaus besser als herkömmliche Software fähig, sich neuen, überraschenden Problemen anzupassen.

Manche Visionäre sagen vorher, dass Chips bald in Tausenden alltäglicher Gegenstände zu finden sein werden – von Briefumschlägen bis hin zu Mülleimern oder Salatköpfen. Damit all diese miteinander kommunizieren können, müssen ganz neue Wege gefunden werden. Oder, wie es der Technik-Autor Kevin Kelly formulierte: "Dumme Komponenten, richtig miteinander in einem Schwarm verbunden, liefern kluge Ergebnisse."

Glossar


- Software-Agenten: Programme, die im Auftrag ihrer Nutzer relativ autonom gewisse Aufgaben erledigen.

- Problem des Handlungsreisenden: das Prototyp-Problem der kombinatorischen Optimierung. Die kürzeste Rundreise durch eine gegebene Menge von Städten ist gesucht. Bei n Städten gibt es (n-1)! mögliche Rundreisen – bereits für mäßig große n eine astronomische Zahl.

- Schwarmintelligenz: kollektive Leistung einer großen Zahl jeweils wenig intelligenter Einzelakteure.

Literaturhinweis

Swarm Intelligence: From Natural to Artificial Systems.Von Eric Bonabeau, Marco Dorigo und Guy Théraulaz. Oxford University Press, 1999.


Aus: Spektrum der Wissenschaft 5 / 2000, Seite 72
© Spektrum der Wissenschaft Verlagsgesellschaft mbH