Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Entwicklung hierarchischer Klassifikatoren beim

Wabenbau sozialer Insekten

Vortrag zur Diplomarbeit

Marius Zirngibl

      0zirngib@informatik.uni-hamburg.de

Betreuung: Prof. A. Fleischer / AB Biokybernetik Prof. B. Page / Dept. Informatik Universität Hamburg

20. Juni 2009 / Seminar Umweltinformatik SoSe 2009 / Veranstalter Prof. B. Page

1 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Übersicht

1 Einleitung

Idee der Arbeit Biologischer Hintergrund

2 Theoretische Grundlagen

Learning Classifier System Genetische Algorithmen

3 Simulationsmodell
4 Weitere Zielsetzung

Aufgetretene Fragen Hierarchien

2 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Idee der Arbeit Biologischer Hintergrund

Idee der Arbeit

Betrachtung sozialer Insekten und ihres Nestbaus als Beispiel für ein natürliches adaptives System Modellierung des Wabenbaus sozialer Wespen als Simulation mit einem Schwarm adaptiver Agenten Ziel: Besseres Verständnis komplexer adaptiver Systeme

3 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Idee der Arbeit Biologischer Hintergrund

Soziale Insekten

Ameisen, Termiten, Honigbienen und bestimmte Wespenarten bilden Staaten. Viele Aktivitäten dieser Insektenarten sind hochkomplex und nur durch Kooperation möglich (z.B. Futtersuche, Verteidigung und Nestbau). Keine zentrale Kontrollinstanz zu erkennen � Selbstorganisation Kollektive Fähigkeit des Insektenstaates übersteigt die Summe der Fähigkeiten der einzelnen Individuen � Emergenz

4 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Idee der Arbeit Biologischer Hintergrund

Nestbau sozialer Wespen

Lokale Regeln ↔ Globale Struktur

Handeln der Individuen nach einfachen lokalen Regeln Entstehung einer komplexen globalen Struktur durch Kooperation

wespe_{m}it_{w}abe

5 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Idee der Arbeit Biologischer Hintergrund

Komplexe Strukturen im Wespennest

wespennest 6 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Idee der Arbeit Biologischer Hintergrund

Stigmergie als Kommunikationsprinzip

Stigmergie Indirekte Kommunikation als zentrales Prinzip der Selbstorganisation Begriff abgeleitet vom griechischen στιγμα (stigma: Zeichen, Markierung) und ϵργoν (ergon: Arbeit, Aktion) Individuen setzen Markierungen (stigmata) in der Umgebung und beeinflussen dadurch das Verhalten (ergon) des Individuums ⇒ Indirekter Informationsaustausch

termiten

7 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Idee der Arbeit Biologischer Hintergrund

Stigmergie beim Nestbau sozialer Wespen

stigmergie_{w}abenbau wabenschema

8 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Learning Classifier System Genetische Algorithmen

Learning Classifier System

LCS Regelbasiertes Verfahren für Maschinelles Lernen, vor allem in Zusammenhang mit adaptiven Agentensystemen Agenten handeln aufgrund lokaler Regeln (Klassifikatoren) Klassifikator bestehend aus

Detektor - Bedingung für Zustand der Umgebung

Effektor - definiert die Aktion des Agenten bei Aktivierung des Klassifikators Fitnesswert - Wahrscheinlichkeit für Aktivierung des Klassifikators

Regeln werden durch Feedback aus der Umgebung verändert �Adaption des Systems an die Umgebung Reinforcement Learning

1 Bewertung der Overall Performance des Systems durch globale

Fitnessfunktion 2 Anpassung der Fitnesswerte beteiligter Klassifikatoren

aufgrund globaler Bewertung �positives / negatives Feedback _{9 / 20}

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Learning Classifier System Genetische Algorithmen

Schema eines Learning Classifier System

LCS_{s}chema

10 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Learning Classifier System Genetische Algorithmen

Genetischer Algorithmus (GA)

Heuristisches Optimierungsverfahren nach Vorbild biologischer Evolution Betrachtung von Lösungsvorschlägen als Individuen einer Population (Genotyp vs. Phänotyp), die durch Kombination neue (bessere) Lösungsvorschläge hervorbringen Bei LCS: Individuum ⟺ Regelsatz Wichtigste Grundprinzipien:

1 Selektion Auswahl geeigneter Ausgangsindividuen

2 Rekombination Erzeugen neuer Individuen aus vorhandenen

rekombination

3 Mutation Zufällige Veränderung einzelner Elemente (Regeln)

des Individuums

11 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Modellierung und graphische Darstellung der Simulation

Implementation in MATLAB Variable Anzahl adaptiver Agenten - Insektenpopulation als LCS Stochastische Bewegung der Agenten auf hexagonalem Gitternetz variabler Größe Satz von Klassifikatoren zur Steuerung der Agentenaktionen (Stigmergieprinzip) Mögliche Aktionen: Bau verschiedener Typen von Zellbausteinen Globale Fitnessfunktion zur Zuweisung eines Fitnesswertes zur entstandenen Struktur - Beurteilung z.B. nach Kompaktheit (aktuell) oder Symmetrie

12 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Beispiele für Klassifikatoren

Detektor-/Effektor-String Fitness Graphische Darstellung

[***B**1]  37  classifier_{1}

[*BBB**2]  65  classifier_{2}

[*111**1]  97  classifier_{3}

13 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Beispiel für einen Simulationslauf

sechserwabe

14 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Parameter der Beispielsimulation

Schwarm aus 10 Individuen Verwendeter Regelsatz

’BBB***3’ ’*BBB**3’ ’**BBB*3’ ’***BBB3’ ’*BB***2’ ’****BB2’ ’***B**1’ ’B*****1’

Verteilung der einzelnen Fitnesswerte stochastisch - höhere Auswahlwahrscheinlichkeit für spezifischere Klassifikatoren Globales Fitnesskriterium: Kompaktheit der Struktur (Verhältnis Umfang zu Gesamtfläche minimal)

15 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Aufgetretene Fragen Hierarchien

Aufgetretene Fragen

Inwieweit kann sich die globale Struktur tatsächlich auf die lokalen Regeln auswirken, wenn das Individuum nur seine unmittelbare Umgebung wahrnimmt? Können tatsächlich komplexe Strukturen wie reale Wespennester entstehen, wenn jedes Individuum nach immer den gleichen unveränderlichen Regeln baut? Bisher: Abbruch der Simulation nach bestimmter Anzahl von Schritten. Woher weiß das Individuum, wann das Nest fertiggestellt ist?

16 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Aufgetretene Fragen Hierarchien

Mögliche Lösung: Einführung von Hierarchien

Idee: Einführung hierarchischer Klassifikatoren

Statt nur einem Regelsatz werden mehrere eingesetzt, zwischen denen durch globale Ereignisse umgeschaltet wird. Beispiel: Erreichen einer bestimmten Größe �Umschalten auf anderen Regelsatz, der anderen Zelltyp baut �Entstehen einer Ringstruktur

bienenwabe 17 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur Aufgetretene Fragen Hierarchien

Ausblick in die Zukunft

Erweiterung des Modells in die dritte Dimension - Möglichkeiten für sehr viel komplexere und realitätsnähere Strukturen

wespennest_{3}d

18 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

Zusammenfassung

Wabenbau sozialer Insekten als Beispiel für adaptives System Simulationsmodell als künstliches adaptives System

19 / 20

Einleitung

Theoretische Grundlagen Simulationsmodell Weitere Zielsetzung Zusammenfassung

Literatur

[Bonabeau et al. 1999] Bonabeau, Eric ; Dorigo, Marco ; Theraulaz, Guy: Swarm Intelligence: From Natural to Artificial Systems. 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 University Press, 2001

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

[Holland 1992] Holland, John H.: Adaptation in Natural and

Artificial Systems. MIT Press, 1992 [Sutton und Barto 1998] Sutton, Richard S. ; Barto,

Andrew G.: Reinforcement learning : an introduction. MIT Press, 1998

20 / 20