Genetische Entwicklung hierarchischer Klassifikatoren beim

Wabenbau sozialer Insekten

Marius Zirngibl - Matrikel 5299377 eMail 0zirngib@informatik.uni-hamburg.de

23. März 2009

Der Nestbau sozialer Insekten ist ein anschauliches Beispiel für in der Natur auftretende emergente Phänomene. Ameisen, Wespen oder Bienen bringen in kollektiver Arbeit Nestbauten zustande, deren Größe und Komplexität den menschlichen Beobachter bei oberflächlicher Betrachtung zu der Annahme verleiten könnten, dass eine derartige Struktur nicht ohne einen Bauplan oder einen übergeordneten „Architekten“ entstehen kann (e.g. Matsuura und Yamane, 1990; Winston, 1991; Camazine et al., 2001). Da ein einzelnes Insekt nicht die Fähigkeiten besitzt, um eine globale Struktur wie die eines komplexen Nestes zu erfassen, wird im Allgemeinen davon ausgegangen, dass soziale Insekten ihre Nester nach Prinzipien der Selbstorganisation bauen. Das einzelne Individuum arbeitet nach einfachen, genetisch evolvierten lokalen Regeln, die in ihrer Gesamtheit eine Struktur entstehen lassen, die trotz fehlender zentraler Koordination den Anforderungen von Brutpflege, Vorratshaltung und Schutz gegen Feinde bei veränderlichen Umweltbedingungen entsprechen. Es ist davon auszugehen, dass hier Selbstorganisation in Form von Stigmergie ein zentrales Prinzip darstellt (Bonabeau et al., 1999; Karsai, 1999). Der Begriff Stigmergie wurde von Grassé (1959) geprägt und ist von den griechischen Wörtern στιγμα (stigma: Zeichen, Markierung) und ϵργoν (ergon: Arbeit, Aktion) abgeleitet. Als Stigmergie wird eine Form der indirekten Kommunikation verstanden, die sich dadurch auszeichnet, dass Individuen durch Manipulation ihrer Umgebung Informationen austauschen. Die gesetzten Zeichen oder Markierungen (stigma), auch Stimuli genannt, beeinflussen also das Verhalten bzw. die Aktionen (ergon) des Individuums. Bonabeau et al. (1999) unterscheiden hier zwei Arten der Stigmergie: zum einen die quantitative Stigmergie, bei der die Stärke der relevanten Stimuli über das Verhalten des Individuums entscheidet, zum anderen die qualitative oder diskrete Stigmergie, bei der qualitativ verschiedene Stimuli unterschiedliches Verhalten hervorrufen. Die Wegmarkierung mittels Pheromonen, welche von Ameisen zur Anzeige einer Futterquelle genutzt werden, wäre ein Beispiel für quantitative Stigmergie, da die Intensität der Pheromonspur dafür verantwortlich ist, wie stark deren Anziehungskraft auf die einzelne Ameise ist. Ein Beispiel für qualitative Stigmergie hingegen stellt der Nestbau verschiedener Wespenarten dar, wobei das Individuum aufgrund unterschiedlicher Wabenstrukturen entscheidet, an welcher Stelle eine zusätzliche Wabe angebaut wird (Karsai, 1999).

Ein zentrales Ziel der geplanten Arbeit ist es, ein vom realen Nestbau abstrahiertes Modell zu entwickeln, welches in Anlehnung an die beschriebenen Mechanismen mit einem Schwarm adaptiver Agenten eine Struktur aus hexagonalen Einzelbausteinen (Waben) zusammensetzen kann. Die Agenten sollen sich zufällig auf einem dreidimensionalen Gitternetz bewegen und an jedem Punkt des Gitters jeweils entscheiden, ob dort ein Baustein gesetzt wird oder nicht. Die Gesamtheit aller möglichen Zustände des Gitters stellt den Zustandsraum des betrachteten Problems dar. Dabei wird als Zustand eines Punktes die Art der dort gebauten Wabe definiert. Geht man von einem Gitternetz mit W Punkten und n möglichen Zuständen eines einzelnen Punktes aus, arbeitet man in einem Zustandsraum der Größe n^{W}, was schon im einfachsten Fall (nur ein Wabentyp, also n = 2) zu einem exponentiell zu W wachsenden Zustandsraum führt. Die Entscheidung des Agenten über den Bau einer Wabe erfolgt nach dem Prinzip der diskreten Stigmergie, das heißt die lokale Umgebung des Agenten an seiner Position gibt den Ausschlag für die Entscheidung, ob an dieser Position gebaut wird oder nicht. Hierbei soll explizit kein konkretes Zielmuster vorgegeben, sondern die entstehenden Strukturen anhand verschiedener Kriterien wie z.B. Kompaktheit oder Symmetrie bewertet und die Verhaltensregeln der Agenten aufgrund dieser Bewertungen angepasst werden.

„ […] a few simple behavioural rules lead to coordinated building and the production of amazingly complex architectures without needing to develop a strategy.“ (Theraulaz et al., 1999, S.327)

Die adaptiven Agenten sollen über einen Satz von Regeln verfügen, mit dessen Hilfe sie über ihr konkretes Verhalten in einer bestimmten Situation entscheiden können. Regeln sollen hierbei im Wettbewerb zueinander stehen, wobei der Agent mittels eines internen Bewertungssystems entscheidet, welche der passenden Regeln angewandt werden soll. Die Bewertung der Regeln erfolgt zum einen durch eine spezifische Gewichtung, welche die Bedeutung der Regel für das gesamte System repräsentieren soll, zum anderen durch die Unterscheidung aufgrund des in einer Regel enthaltenen Informationsgehalts. Eine Regel mit vielen signifikanten Bits hat einen höheren Informationsgehalt als eine Regel mit wenigen signifikanten Bits und soll daher vorgezogen werden. Konkret bedeutet das für den Wabenbau, dass eine Regel, die den Zustand vieler benachbarter Waben berücksichtigt, mit größerer Wahrscheinlichkeit zur Anwendung kommt als eine Regel, die nur von einer Nachbarwabe abhängt. Dieser Mechanismus wurde sehr anschaulich von Holland (1995) beschrieben. Regeln mit wenig Informationsgehalt werden als default rules betrachtet, auf die der Agent zurückgreift, wenn keine spezifischeren Regeln vorhanden sind. Um verschiedene Abschnitte im Nestbau von Insekten zu berücksichtigen, soll es mehrere hierarchisch geordnete Regelsätze geben, und an definierten Triggerzuständen von übergeordneten zu untergeordneten Regelsätzen umgeschaltet werden. Die Agenten sollen also zu unterschiedlichen Zeitpunkten der Simulation nach verschiedenen Regeln funktionieren, was besonders bei einer komplexeren Neststruktur wichtig ist.

Die Gewichtung der einzelnen Regeln soll nach dem Prinzip des reinforcement learning angepasst werden. Vereinfacht ausgedrückt wird hierbei die Gewichtung von Regeln erhöht oder verringert, abhängig davon, ob ihre wiederholte Anwendung zu einem als gut oder als schlecht bewerteten Endergebnis geführt hat (Mitchell, 1997). Zusätzlich sollen die Regelsätze durch einen Genetischen Algorithmus (Goldberg, 1989; Nissen, 1997) verändert werden, um diejenigen Regeln zu finden, die zu sinnvollen Ergebnissen führen. Jeweils nach einem Simulationsdurchlauf mit einem bestimmten Satz von Regeln wird der Genetische Algorithmus (GA) angewendet, wobei der komplette Regelsatz als Genotyp eines Individuums betrachtet wird. Der GA arbeitet auf einer Population von Individuen, d.h. es werden unterschiedliche Regelsätze in der Simulation angewendet und die jeweils entstandenen Strukturen durch den GA bewertet. Je nach Bewertung der entstandenen Struktur ändert sich die Chance des verwendeten Regelsatzes, in der nächsten Generation des GA berücksichtigt zu werden. Näheres zu dieser Anwendung Genetischer Algorithmen findet sich bei Bonabeau et al. (1999). Diese Variante selbstorganisierten Lernens orientiert sich auch am Konzept der ebenfalls auf Holland zurückgehenden Learning Classifier Systems oder kurz LCS (Sigaud und Wilson, 2007; Holland, 1992).

Eine grobe Gliederung der geplanten Arbeit:

1. Einleitung und theoretisches Konzept a) Definition des Zustandsraumes (Gitternetz mit Belegung durch Waben)

b) Bedeutung von Regeln und Klassifikatoren bei stochastischer Entscheidung zwischen einzelnen Aktionen

c) Hierarchische Ordnung der Regeln

d) Definition der Population von Regelsätzen

e) Bewertung der Aktionen mittels Reinforcement Learning

f) Modifikation der Regelsätze durch einen Genetischen Algorithmus

g) Entwicklung von Populationsstrukturen

2. Simulationsumgebung a) Sechseckige Waben in der Ebene

b) Erweiterung in den Raum

c) Räumliche Umgebung mit Begrenzung

3. Ergebnisse der Simulation a) in der begrenzten Ebene

b) in der unbegrenzten Ebene

c) im dreidimensionalen Raum

d) nach weiteren Kriterien i. Brutpflege ii. Vorrat iii. Schutzbegrenzung

e) Konvergenzprobleme

4. Diskussion

Es soll eine Testumgebung entwickelt werden, in der die Regelsätze praktisch angewendet werden können. Aufgrund der heuristischen Natur des Verfahrens können mehrere Testläufe mit gleichen Ausgangsparametern sehr unterschiedliche Ergebnisse liefern, außerdem muss in diesem Zusammenhang untersucht werden, unter welchen Bedingungen das Modell konvergiert. Die relevanten Ergebnisse sollen grafisch und textuell dargestellt werden.

Zum Ende der Arbeit sollen die erzielten Ergebnisse bewertet und diskutiert werden. Neben dem Verständnis und der Analyse selbstorganisierender Prozesse in komplexen natürlichen Systemen ist ein weiterer Fokus der Arbeit auch, inwieweit deren charakteristische Eigenschaften wie Selbstorganisation, Stigmergie und Emergenz auf künstlich geschaffene komplexe Systeme übertragbar sind.

Literatur

[Bonabeau et al. 1999] Bonabeau, Eric ; Dorigo, Marco ; Theraulaz, Guy: Swarm Intelligence: From Natural to Artificial Systems. Oxford; New York : Oxford University Press, 1999

[Camazine et al. 2001] Camazine, Scott ; Deneubourg, Jean-Louis ; Franks, Nigel R. ; Sneyd, James ; Theraulaz, Guy ; Bonabeau, Eric: Self-Organization in Biological Systems. Princeton; Oxford : Princeton University Press, 2001

[Goldberg 1989] Goldberg, David E.: Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley Longman, 1989

[Grassé 1959] Grassé, P.-P.: La reconstruction du nid et le coordinations interindividuelles chez Bellicositermes natalensis et Cubitermes sp. La theorie de la stigmergie: Essai d’interpretation du comportement des termites constructeurs. In: Insectes Sociaux 6 (1959), S. 41–81

[Holland 1992] Holland, John H.: Adaptation in Natural and Artificial Systems. Cambridge; London : MIT Press, 1992

[Holland 1995] Holland, John H.: Hidden Order : How Adaptation Builds Complexity. New York : Helix Books, 1995

[Karsai 1999] Karsai, István: Decentralized control of construction behavior in paper wasps: an overview of the stigmergy approach. In: Artif. Life 5 (1999), Nr. 2, S. 117– 136. – ISSN 1064-5462

[Matsuura und Yamane 1990] Matsuura, Makoto ; Yamane, Seiki: Biology of the Vespine Wasps. Berlin; Heidelberg : Springer, 1990

[Mitchell 1997] Mitchell, Tom M.: Machine learning. Boston, Mass. : McGraw-Hill, 1997

[Nissen 1997] Nissen, Volker: Einführung in Evolutionäre Algorithmen. Braunschweig; Wiesbaden : Vieweg, 1997

[Sigaud und Wilson 2007] Sigaud, Olivier ; Wilson, Stewart W.: Learning Classifier Systems: A Survey. In: Soft Comput. 11 (2007), Nr. 11, S. 1065–1078 [Theraulaz et al. 1999] Theraulaz, Guy ; Bonabeau, Eric ; Deneubourg, Jean-

Louis: The mechanisms and rules of coordinated building in social insects. In: Detrain, Claire (Hrsg.) ; Deneubourg, Jean-Louis (Hrsg.) ; Pasteels, Jacques M. (Hrsg.): Information Processing in Social Insects. Basel : Birkhäuser, 1999, S. 309–330

[Winston 1991] Winston, Mark L.: The Biology of the Honey Bee. Cambridge; London : Harvard University Press, 1991