% für präsentation:
% \documentclass[utf8x]{beamer}
% für handout:
\documentclass[utf8x,handout]{beamer}

\usepackage[utf8x]{inputenc}
\usepackage[german]{babel}
\usepackage{pgfpages}
\usepackage{natbib}
\usepackage{textcomp}
\usepackage{multimedia}
\usepackage{default}

\usetheme{Warsaw}
% \usecolortheme{seahorse}
\setbeamercovered{transparent}
\setbeamertemplate{footline}[frame number]
\beamertemplatenavigationsymbolsempty

\def\newblock{\hskip .11em plus .33em minus .07em}

% für handout:
\pgfpagesuselayout{4 on 1}[a4paper,border shrink=5mm,landscape]

\title[Wabenbau]{Entwicklung hierarchischer Klassifikatoren beim Wabenbau sozialer Insekten}
\subtitle{Vortrag zur Diplomarbeit}
\author{Marius Zirngibl\\ \texttt{0zirngib@informatik.uni-hamburg.de}}
\institute{Betreuung: Prof. A. Fleischer / AB Biokybernetik\\ Prof. B. Page / Dept. Informatik\\ Universität Hamburg}
\date[20.06.09]{20. Juni 2009 / Seminar Umweltinformatik\\ SoSe 2009 / Veranstalter Prof. B. Page}

\begin{document}
\pgfdeclareimage[interpolate=true,height=170pt]{wespennest_gras}{./vortrag/wespennest}
\pgfdeclareimage[interpolate=true,height=120pt]{wespe_mit_wabe}{./vortrag/174663274_9d8e5d2459_o}
\pgfdeclareimage[interpolate=true,height=120pt]{wabe_mit_wespen}{./vortrag/nido_di_vespe}
\pgfdeclareimage[interpolate=true,height=50pt]{rekombination}{./vortrag/nissen_crossover}
\pgfdeclareimage[interpolate=true,height=150pt]{sechserwabe}{./vortrag/sechs_waben_klein}

\pgfdeclareimage[interpolate=true,height=200pt]{wespennest}{./vortrag/Wespennest-leer}
\pgfdeclareimage[interpolate=true,height=200pt]{wespennest_3d}{./vortrag/wespennest_3d}
\pgfdeclareimage[interpolate=true,height=200pt]{stigmergie_wabenbau}{./vortrag/camazine_wabenbau_1}
\pgfdeclareimage[interpolate=true,height=175pt]{LCS_schema}{./vortrag/weicker_LCS}
\pgfdeclareimage[interpolate=true,height=100pt]{wabenschema}{./vortrag/camazine_wabenbau_2}
\pgfdeclareimage[interpolate=true,height=100pt]{bauwahrscheinlichkeit}{./vortrag/camazine_wahrscheinlichkeit}
\pgfdeclareimage[interpolate=true,height=30pt]{classifier_1}{./vortrag/wabe_2d_1}
\pgfdeclareimage[interpolate=true,height=30pt]{classifier_2}{./vortrag/wabe_2d_2}
\pgfdeclareimage[interpolate=true,height=30pt]{classifier_3}{./vortrag/wabe_2d_3}

\pgfdeclareimage[interpolate=true,height=180pt]{simulationsbeispiel_1}{./vortrag/beispiel_4ag_500step}

\begin{frame}
 \titlepage
\end{frame}

\begin{frame}
 \frametitle{Übersicht}
 \tableofcontents[pausesections]
\end{frame}
\section{Einleitung}
 % Worüber geht meine Arbeit? Was ist die prinzipielle Idee?
\subsection{Idee der Arbeit}

\begin{frame}
 \frametitle{Idee der Arbeit}

\begin{columns}
  \column{.6\textwidth}
    \begin{itemize}
   \item<1->
    Betrachtung sozialer Insekten und ihres Nestbaus als natürliches Beispiel für ein komplexes
    adaptives System
    \note{CAS kurz erklären: viele stark vernetzte Elemente, Verhalten nicht vorhersagbar, Fähigkeit zur Anpassung an Umwelt}
  \item<2->
    Modellierung des Wabenbaus sozialer Wespen als Simulation mit einem Schwarm adaptiver Agenten
  \item<3->
    Ziel: Besseres Verständnis komplexer adaptiver Systeme
 \end{itemize}
 \column{.4\textwidth}
   \pgfuseimage{wespennest_gras}
 \end{columns}
 
\end{frame}

\subsection{Biologischer Hintergrund}
% \subsection{Soziale Insekten}
\begin{frame}
 \frametitle{Soziale Insekten}
 
 \begin{itemize}
  \item 
    Ameisen, Termiten, Honigbienen und bestimmte Wespenarten bilden Staaten.
  \item
    Fähigkeit zu hochkomplexen und nur durch Kooperation möglichen Vorgängen,
    z.B. Futtersuche, Verteidigung und Nestbau
  \item
    \textit{Selbstorganisation} - keine erkennbare zentrale Kontrollinstanz 
  \item
    \textit{Emergenz} - kollektive Fähigkeit des Insektenstaates übersteigt Summe der Fähigkeiten der einzelnen
    Individuen
  % vll. ein paar Bilder von Ameisenbauten, Termitenhügeln etc.
 \end{itemize}

\end{frame}

% \subsection{Nestbau von Wespen}
\begin{frame}
 \frametitle[Nestbau]{Nestbau sozialer Wespen}
 

 \begin{columns}
  \column{.3\textwidth}
   \pgfuseimage{wespe_mit_wabe}
  \column{.4\textwidth}
   \begin{itemize}
     \item
        Lokale Regeln $\leftrightarrow $ Globale Struktur
        \begin{itemize}
          \item
            Handeln der Individuen nach einfachen lokalen Regeln
          \item
             Entstehung einer komplexen globalen Struktur durch Kooperation
        \end{itemize}
   \end{itemize}
  \column{.3\textwidth}
    \pgfuseimage{wabe_mit_wespen}
 \end{columns}

\end{frame}

\begin{frame}
 \frametitle{Komplexe Strukturen im Wespennest}

 \pgfuseimage{wespennest}
\end{frame}

% \subsection{Stigmergie}
\begin{frame}
 \frametitle[Stigmergie]{\textit{Stigmergie} als Kommunikationsprinzip}
 
 \begin{columns}
  \column{.6\textwidth}
    \begin{itemize}
  \item
    Indirekte Kommunikation als zentrales Prinzip der Selbstorganisation
  \item
    Begriff \textit{Stigmergie} abgeleitet vom griechischen \textit{stigma} (Zeichen, Markierung)
    und \textit{ergon} (Arbeit, Aktion)
  \item
    Individuen setzen Markierungen (\textit{stigmata}) in der Umgebung und beeinflussen dadurch das
    Verhalten (\textit{ergon}) des Individuums $\Rightarrow $ Indirekter Informationsaustausch
 \end{itemize}
 
 \column{.4\textwidth}
   \pgfdeclareimage[interpolate=true,height=150pt]{termiten}{./vortrag/bonabeau_termiten_pheromone}
   \pgfuseimage{termiten}
 \end{columns}
\end{frame}

\begin{frame}
 \frametitle{Stigmergie beim Nestbau sozialer Wespen}
 
 \begin{columns}
  \column{.5\textwidth}
    \pgfuseimage{stigmergie_wabenbau}
  \column{.5\textwidth}
    \pgfuseimage{wabenschema} \\
    \pgfuseimage{bauwahrscheinlichkeit}
 \end{columns}

\end{frame}

% \subsection{Evolution}
% \begin{frame}
% \frametitle{Die Grundzüge der Evolutionstheorie}
% 
% \end{frame}

\section{Theoretische Grundlagen}

\subsection{Learning Classifier Systeme}
\begin{frame}
 \frametitle[LCS]{\textit{Learning Classifier System}}
 
 \begin{itemize}
  \item
    LCS: 
    Regelbasiertes Verfahren für \textit{Maschinelles Lernen},
    vor allem in Zusammenhang mit adaptiven Agentensystemen
  \item
    Agenten handeln aufgrund lokaler Regeln (\textit{Klassifikatoren})
  \item
    Klassifikator bestehend aus 
    \begin{itemize}
     \item
       \textit{Detektor} - vergleicht Input aus Umgebung mit Bedingung der Regel
     \item
       \textit{Effektor} - definiert die Aktion des Agenten bei Aktivierung
     \item
       \textit{Fitnesswert} - Wahrscheinlichkeit für Aktivierung des Klassifikators
    \end{itemize}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{\textit{Reinforcement Learning} in LCS}
 \begin{itemize}
  \item
    Anpassung der Regeln durch Feedback von außen \textrightarrow \quad Adaption des Systems an die Umgebung
  \item{Reinforcement Learning}
    \begin{enumerate}
     \item 
       Bewertung der \textit{Overall Performance} des Systems durch globale Fitnessfunktion
     \item
       Anpassung der Fitnesswerte beteiligter Klassifikatoren aufgrund globaler Bewertung
       \textrightarrow \quad \textit{positives / negatives Feedback} % bzw. Belohnung / Bestrafung
    \end{enumerate}
 
 \end{itemize}
 
\end{frame}

\begin{frame}
 \frametitle{Schema eines \textit{Learning Classifier System}}
 \pgfuseimage{LCS_schema}
\end{frame}

\subsection{Genetische Algorithmen}
\begin{frame}
 \frametitle[GA]{\textit{Genetischer Algorithmus (GA)}}
 
 \begin{itemize}
  \item
    Heuristisches Optimierungsverfahren nach Vorbild biologischer Evolution
  \item
    Betrachtung von Lösungsvorschlägen als Individuen einer Population (\textit{Genotyp} vs. \textit{Phänotyp}),
    die durch Kombination neue (bessere) Lösungsvorschläge hervorbringen
  \item
    Bei LCS: Individuum $\Longleftrightarrow $ Regelsatz
  \item 
    Wichtigste Grundprinzipien:
       \begin{enumerate}
        \item
	  Selektion: Auswahl geeigneter Ausgangsindividuen
        \item
          Rekombination: Erzeugen neuer Individuen aus vorhandenen
        \item
	  Mutation: Zufällige Veränderung einzelner Elemente (Regeln) des Individuums
       \end{enumerate}
 % im großen und ganzen gesehen ist der Effekt des GA beim LCS, dass 
  \end{itemize}
  
  \qquad \qquad \qquad \pgfuseimage{rekombination}
\end{frame} 
    
\section{Simulationsmodell}

\begin{frame}
 \frametitle{Modellierung und graphische Darstellung der Simulation}
  % hier ein praktisches Beispiel mit Bildern, wie sehen die Waben aus, wie ist der Klassifikator implementiert,
  % was bedeutet [001**10], wie ist die Fitness implementiert (Kompaktheit)...
 
  \begin{itemize}
   \item
     Implementation in \texttt{MATLAB}
  \item 
     Variable Anzahl adaptiver Agenten - Insektenpopulation als LCS
  \item
    Stochastische Bewegung der Agenten auf hexagonalem Gitternetz variabler Größe
  \item
    Satz von Klassifikatoren zur Steuerung der Agentenaktionen (Stigmergieprinzip)
  \item
    Mögliche Aktionen: Bau verschiedener Typen von Zellbausteinen
  \item
    Globale Fitnessfunktion zur Zuweisung eines Fitnesswertes zur entstandenen Struktur -
    Beurteilung z.B. nach Kompaktheit (aktuell) oder Symmetrie
   \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Beispiele für Klassifikatoren}
   \begin{tabular}{|c|c|c|}
    \hline
     Detektor-/Effektor-String & Fitness & Graphische Darstellung \\
    \hline
    \hline
     [***B**1] & 37 & \pgfuseimage{classifier_1} \\
    \hline
     [*BBB**2] & 65 & \pgfuseimage{classifier_2} \\
    \hline
     [*111**1] & 97 & \pgfuseimage{classifier_3} \\
    \hline
   \end{tabular}
 \end{frame}

\begin{frame}
 \frametitle{Beispiel für einen Simulationslauf}
 % hier soll das Video vom Wabenbau hin
 \movie{\pgfuseimage{simulationsbeispiel_1}}{./vortrag/sim_demo.avi}
\end{frame}

\begin{frame}
 \frametitle{Parameter der Beispielsimulation}
 
 \begin{itemize}
  \item 
    Schwarm aus 10 Individuen
  \item
    Verwendeter Regelsatz:
    \begin{enumerate}
      \item
       'BBB***3'
      \item
       '*BBB**3'
      \item
       '**BBB*3'
      \item
       '***BBB3'
      \item
       '*BB***2'
      \item
       '****BB2'
      \item
       '***B**1'
      \item
       'B*****1'
    \end{enumerate}
  \item
   Stochastische Verteilung der einzelnen Fitnesswerte - höhere Auswahlwahrscheinlichkeit für spezifischere Klassifikatoren
  \item
   Globales Fitnesskriterium: Kompaktheit der Struktur (Verhältnis Umfang zu Gesamtfläche minimal) 
 \end{itemize}

\end{frame}

\section{Thematische Zielsetzung}
\subsection{Ungelöste Fragen}
\begin{frame}
 \frametitle{Ungelöste Fragen}
 
 \begin{itemize}
  \item 
    Inwieweit kann sich die globale Struktur tatsächlich auf die lokalen Regeln auswirken,
    wenn das Individuum nur seine unmittelbare Umgebung wahrnimmt?
  \item
    Können tatsächlich komplexe Strukturen wie reale Wespennester entstehen, wenn jedes
    Individuum nach immer den gleichen unveränderlichen Regeln baut?
  \item
    Bisher: Abbruch der Simulation nach bestimmter Anzahl von Schritten. Aber woher weiß das Individuum,
    wann das Nest fertiggestellt ist?
   
 \end{itemize}

\end{frame}


\subsection{Hierarchische Klassifikatoren}
\begin{frame}
 \frametitle{Mögliche Lösung: Einführung von \textit{Hierarchien}}
 
 \begin{itemize}
  \item 
    Idee: Einführung hierarchischer Klassifikatoren
  \item
    Statt nur einem Regelsatz werden mehrere eingesetzt, zwischen denen
    durch globale Ereignisse umgeschaltet wird.
  \item
    Beispiel: Erreichen einer bestimmten Größe \textrightarrow
    \quad Umschalten auf anderen Regelsatz, der anderen Zelltyp baut
    \textrightarrow \quad Entstehen einer Ringstruktur
 \end{itemize}
 
 \pgfdeclareimage[interpolate=true,height=100pt]{bienenwabe}{./vortrag/bonabeau_bienenwabe}
 \qquad \qquad \qquad \pgfuseimage{bienenwabe}
\end{frame}

\begin{frame}
 \frametitle[Ausblick]{Ausblick in die Zukunft}
 
 \begin{columns}
  \column{.5\textwidth}
    \begin{itemize}
      \item 
        Erweiterung des Modells in die dritte Dimension - Möglichkeiten
        für komplexere und realitätsnähere Strukturen
    \end{itemize}
  \column{.5\textwidth}
    
    \pgfuseimage{wespennest_3d}
 \end{columns}

\end{frame}

% \subsection{Ausblick}
% \begin{frame}
%  \frametitle{Ausblick}
% 
% \end{frame}

\section*{Zusammenfassung}

\begin{frame}
  \frametitle{Zusammenfassung}
  
  \begin{itemize}
   \item 
     Komplexe adaptive Systeme in der Natur - Beispiel: Nestbau sozialer Wespen
   \item
     \textit{Stigmergie} - wichtiges Prinzip für indirekte Kommunikation
   \item
     Theoretische Grundlagen des Modells:
     \begin{enumerate}
      \item Learning Classifier Systeme
      \item Reinforcement Learning
      \item Genetische Algorithmen
     \end{enumerate}
   \item
     Zur Verbesserung des Modells: Einführung hierarchischer Strukturen in das Regelsystem

  \end{itemize}

\end{frame}

\nocite{bonabeau:99,camazine:01}
\nocite{holland:92,sutton:98,goldberg:89}

\begin{frame}
 \bibliographystyle{dinatneu}
 \bibliography{literatur}
\end{frame}

\end{document}
