\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<1-> 
    Ameisen, Termiten, Honigbienen und bestimmte Wespenarten bilden Staaten.
  \item<2->
    Fähigkeit zu hochkomplexen und nur durch Kooperation möglichen Vorgängen,
    z.B. Futtersuche, Verteidigung und Nestbau
  \item<3->
    \textit{Selbstorganisation} - keine erkennbare zentrale Kontrollinstanz 
  \item<4->
    \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<1->
    Indirekte Kommunikation als zentrales Prinzip der Selbstorganisation
  \item<2->
    Begriff \textit{Stigmergie} abgeleitet vom griechischen \textit{stigma} (Zeichen, Markierung)
    und \textit{ergon} (Arbeit, Aktion)
  \item<3->
    Individuen setzen Markierungen (\textit{stigmata}) in der Umgebung und beeinflussen dadurch das
    Verhalten (\textit{ergon}) des Individuums $\Rightarrow $ Indirekter Informationsaustausch
 \end{itemize}
 \pause
 \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<1->
    Heuristisches Optimierungsverfahren nach Vorbild biologischer Evolution
  \item<2->
    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<3->
    Bei LCS: Individuum $\Longleftrightarrow $ Regelsatz
  \item<4->
    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<1-> 
    Inwieweit kann sich die globale Struktur tatsächlich auf die lokalen Regeln auswirken,
    wenn das Individuum nur seine unmittelbare Umgebung wahrnimmt?
  \item<2->
    Können tatsächlich komplexe Strukturen wie reale Wespennester entstehen, wenn jedes
    Individuum nach immer den gleichen unveränderlichen Regeln baut?
  \item<3->
    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}
