\documentclass[10pt, fleqn, a4paper]{report}
\usepackage{times}
\usepackage[austrian]{babel}
\usepackage{german}
\usepackage{graphicx}
%\usepackage{isolatin1}

\textheight     680pt
\textwidth      460pt
\topmargin      -40pt
\oddsidemargin    5pt
\evensidemargin   5pt
\parindent        0pt
\parskip      5pt



\date{}

\begin{document}

\begin{titlepage}

\begin{center}
% universit"at
\vfill
{\Large Universit"at~Salzburg, Institut~f"ur Computerwissenschaften }

% lehrveranstaltung
\vfill
{\Large PS Programmierpraktikum \\ SS 2000}

% titel
\vfill
{\Huge Optimierte Objektpositionierung}

% autoren
\vfill
{\large \begin{tabular}{rl}
Manfred Bernhard Mayr & \underline{mmayr@cosy.sbg.ac.at}\\
Florian Angulanza & \underline{fangulan@cosy.sbg.ac.at}\\
Christian Osterrieder & \underline{coster@cosy.sbg.ac.at}\\
Markus Spitzlinger & \underline{mspitzl@cosy.sbg.ac.at}\\
& \\
Projektbetreuer: \\ Dipl.Ing.~Mag.~Roland Schwaiger & \underline{rschwaiger@cosy.sbg.ac.at}
\end{tabular} }

% projektbetreuer
%\vfill
%{\large }

\vfill
{\Large Version vom \today }

\end{center}

\vfill
\end{titlepage}

%
%Abstract
%

\begin{abstract}

\end{abstract}


\tableofcontents

\chapter{Einf"uhrung}
\section{Genetischer Algorithmus}

Nach \cite{Meyers-95} ist ein Genetischer Alogrithmus ein Algorithmus, der Strategien aus der Evolutionstheorie verwendet, um zu einem Problem eine m"oglichst gute L"osung zu finden. Bei dieser Heuristik mu"s man die L"osungen eines Problems als Chromosomen, aufgebaut aus einer Folge oder Menge von elementaren Bausteinen (Gene), formulieren; eine Menge solcher Chromosomen, eventuell erweitert um zus"atzliche Attribute, hei"st Population. Ausgehend von irgendeiner Anfangspopulation erzeugt man durch biologische Vererbungsmechanismen neue Chromosomen, bewertet diese mit Hilfe einer vorgegebenen Bewertungsfunktion (Fitnessfunktion) m und l"a"st gewisse Chromosomen "uberleben. Durch Wiederholung entsteht dann eine Folge von Populationen, in denen man hofft, eine besonders gute L"osung f"ur das vorgegebene Problem zu entdecken. Als Vererbungsmechanismen verwendet man zumeist Kombinationen folgender Strategien:
\begin{itemize}
        \item {\bf Reproduktion:} Ein Chromosom wird unver"andert an die n"achste
Population vererbt.
        \item {\bf Mutation:} Ein oder mehrere Gene eines Chromosoms werden bei der Vererbung zuf"allig abge"andert.
        \item {\bf Inversion:} Umdrehen eines Teilst"ucks eines Chromosoms und Vererbung des so modifizierten Chromosoms an die n"achste Population.
        \item {\bf Crossover:} Teilen zweier Chromosomen und Vererbung des "uber Kreuz zusammengesetzten Chromosoms. Hierbei mu"s man darauf achten, da"s die Ergebnisse der Neukombination wieder g"ultige Chromosomen sind.
        \item {\bf Blockung:} Zusammenfassen bestimmter Gene zu einer Einheit, deren Teile bei der weiteren Vererbung bei einer Inversion oder einem Crossover nicht mehr getrennt werden d"urfen.
        \item {\bf Entblockung:} Aufhebung einer Blockung.
        \item {\bf Selektion:} Die bzgl. der Bewertungsfunktion besten Chromosomen "uberleben.
\end{itemize}

%
% Projektbeschreibung
%

\chapter{Projektbeschreibung}

\section{Einleitung}

Es wird ein GA (Genetischer Algorithmus) ben"utzt um
Objektgruppierungen $o_{1},...,o_{n}$, in einer 2-dimensionalen
Umgebung, mit Hilfe einer gegebenen Fitness-Funktion zu optimieren.
Die verschiedenen Objekte $o_{i}$ erhalten in einem vordefinierten
Intervall $[l_{i},u_{i}]$ Werte, gemessen in einem diskreten
Zeitintervall, z. B. in einem Tag. Die 2-dimensionale Fl"ache ist
in Teilfl"achen unterteilt, die einzelnen Teilfl"achen k"onnen

\begin{enumerate}
\item verboten sein,
\item zu einer vordefinierten Gruppe geh"oren,
\item besetzt sein, oder nicht bei einem Objekt $o_{i}$ sein.
\end{enumerate}

Ziel des Projektes ist, das Problem theoretisch zu untersuchen (ist
es m"oglich dieses Problem zu klassifizieren?), eine GUI (grafische
Benutzeroberfl"ache) und einen GA zu implementieren. Ein Ergebnis
wird sein, Vorschl"age f"ur die Gruppierung in der Fl"ache zu machen
(basierend auf einer allgemeing"ultigen Fitness-Funktion), z. B.
maximal zuweisbare Werte der Objekte mit R"ucksicht auf ein
zugrundeliegendes Modell der verschiedenen Aufgaben.
\linebreak %zeilenwechsel mit randausgleich

Optimierte Objektpositionierung (OOP) ist ein Multiagentensystem,
welches im wesentlichen aus zwei Komponenten besteht:
\begin{enumerate}
\item Agentenwelt
\item Objektwelt
\end{enumerate}

Das Projekt unterteilt sich hierbei in nat"urlicher Weise in zwei
Teilaufgaben:
\begin{enumerate}
\item Initialisierungsphase, welche die Agenten in der Welt
simuliert und somit Daten f"ur die zweite Phase generiert.
\item Optimierungsphase, wo mit Hilfe der Daten aus der
Initialisierungsphase versucht wird die Objekte m"oglichst gut zu
positionieren.
\end{enumerate}


\subsection{Agentenwelt}
In der Initialisierungsphase werden die Agenten in der Welt $W$,
mit den Dimensionen $w_{x} \in 1,...,n$ und $w_{y} \in 1,...,m$, in
denen die Agenten und Objekte existieren, simuliert. Die Welt ist
begrenzt durch Mauern, in denen Markierungen f"ur Eing"ange und
Ausg"ange enthalten sind. Agent $a_{i} \in A$ kann die Welt nach
einer zugrundeliegenden Verteilung betreten und verlassen. Die
Anzahl der Agenten in der Welt besitzt eine Obergrenze. Jeder Agent
$a_{i}$ besetzt ein gewisses Feld in der Welt welches

\begin{enumerate}
\item nicht besetzt von einem anderen Agenten ist,
\item nicht verboten ist,
\item nicht von einem Objekt besetzt ist.
\end{enumerate}

Jeder Agent bekommt eine bestimmtes Guthaben $v^{a}_{i}$ zugewiesen,
welches erniedrigt wird sobald dieser vor einem Objekt anh"alt. Die
Verminderung des Guthaben h"angt dabei vom Objekt ab, welches der
Agent gerade besucht und wird mit $c^{o}_{i}$ festgehalten. Der
Agent $\mathcal{A}$ kann dabei in der Welt zuf"allig herumwandern,
folgt einem vordefinierten, oder evolvierten Schema. Das Ziel dabei
ist alle Objekte mit einem $v^{a}_{i} > 0$ zu besuchen.

Die Agenten k"onnen dabei $T$ Zeiteinheiten umherwandern und
Objekte besuchen. Wir werden dies eine dynamische auf Generationen
basierende Population nennen. Dynamisch deswegen, weil die Agenten
die Welt jederzeit verlassen oder betreten k"onnen und auf
Generationen basierend, weil nach $\mathcal{T}$ Zeiteinheiten eine
andere Generation von Agenten die Welt bev"olkert. Aktualisiert
sollte die Simulation dabei synchron werden, z.B wenn eine
Generation zum Zeitpunkt $t$ gegeben ist h"angt die Aktualiesierung
f"uer den Zeitpunkt $t+1$ nur vom Zeitunkt $t$ ab. Alle Kollisionen
mit anderen Agenten usw. werden basierend auf der jeweiligen
Zeitstufe berechnet.

\begin{figure}[hbtp]
\begin{center}
\includegraphics[width=10cm]{pic/obj_a_w.eps}
\end{center}
\caption{Objekt- und Agentenwelt} \label{objektpos1}
\end{figure}


\underline{Beschreibung der Abbildung \ref{objektpos1}}:

Links ist das Schema der Objektwelt dargestellt. Es wird ein Raster
"uber die Objektwelt gelegt. Schwarze Rasterfelder bedeuten, dass
kein Objekt (=Entity) hier positioniert werden darf. Ein  wei\ss
es  Rasterfeld bedeutet, dass dieses Feld leer ist. Objekte
k\"onnen nur auf wei\ss e Felder gestellt werden. Objekte k\"onnen
nur vom Agenten einen Wert bekommen,wenn dieser genau vor der
\"Offnung des Objektes steht. Rechts ist das Schema der Agentenwelt
abgebildet. Agenten sind f\"ur uns Klassen. Die Umsetzung der
Bewegungen der Agenten erfolgt am Anfang ganz einfach mit Hilfe
eines Zufallsgenerators. Die Anzahl der Agenten wird immer konstant
gehalten, d.h. wenn ein Agent die Agentenwelt verl\"a\ss t wird ein
anderer nachgeschickt.
\newline

Um genug Daten f"ur den Optimierungsphase sammeln zu k"onnen, wird
die Grundeinstellung der Objekte nach einem Durchlauf ver"andert.


\subsection{Objektwelt}

Im Grunde hat die Objektwelt die gleiche Gr"o"se wie die
Agentenwelt, aber sie ist viel ungenauer. Das ist deshalb so, weil
die Agenten in der Regel nicht soviel Raum wie unsere Objekte
ben"otigen. Objekte besetzen eine Einheit in der Welt. Objekte
werden einem bestimmten Typen zugeordnet und folglich werden ihnen
bestimmte Kosten $c^{o}_{i}$ zugewiesen, die dem Agenten von seinem
Wert abgezogen werden, falls das Objekt vom Agenten besucht wurde.
Das Objekt sammelt die reduzierten Werte des Agenten und nach einem
Durchlauf hat das Objekt den Wert $v^{o}_{i}$. Nach jedem Durchlauf
wird die Grundeinstellung der Objekte solange ver"andert, bis genug
Daten f"ur den Optimierungsphase gesammelt wurden. Einige der
Objekte k"onnen durch andere Objekte aus dem Objektvorrat ersetzt
werden.



\section{Initialisierungsphase}
Diese Phase dient dazu, die f"ur den Optimierungslauf notwendigen
Daten zu ermitteln und zu sammeln. Hier werden "uber einen Zeitraum
von $p*\mathcal{T}$ Datens"atze angelegt, wobei $p$ z.B. 30\,(Tage)
und $\mathcal{T}$ z.B. 24\,Stunden $*$ 60\,Minuten sind. Es finden
also insgesamt $p$ Durchl"aufe statt, wobei vor jedem Durchlauf die
Grundeinstellungen (Objekte, deren Verteilung, $\ldots$) ver"andert
werden. Nach jedem Durchlauf wird festgehalten welches Guthaben die
einzelnen Objekte an der bestimmten Postion haben. Durch die
Ver"anderung der Grundeinstellungen vor jedem Experiment
(=Durchlauf) entstehen gen"ugend Vergleichsdaten f"ur die
Optimierungsphase.

Hierbei stellt sich jetzt die Frage, wie die einzelnen Agenten
positioniert werden und nach welchem Schema sie sich bewegen. In
unserem Fall wird dies zuerst ganz einfach mit Hilfe eines
Zufallsgenerators realisert. Die Bewegung und die Postionierung
sind Methoden, soda"s sie zu einem sp"ateren Zeitpunkt einfach durch
m"oglicherweise bessere ersetzt werden k"onnen.

Wichtig dabei ist auch, da"s die Anzahl der Agenten konstant
gehalten wird, d.h. da"s wenn ein Agent die Welt betritt ein
anderer sie verl"a"st und umgekehrt.

Eine weitere Frage ist, ob "uberwacht werden mu"s, da"s die Objekte
durch ihre Aufstellung die Agenten nicht behindern. Ein Beispiel
w"are, da"s etwa alle Objekte in einer Reihe stehen und kein Agent
mehr zu einem Objekt kann, oder der Ein- oder Ausgang blockiert
ist. Diese Problem m"u"ste jedoch der GA l"osen, da sich diese
Aufstellung der Objekte als nicht sehr vorteilhaft klassifizieren
m"u"ste.

Wie ermittelt man welchen Fitnisswert ein Objekt hat wenn es
 zwei Eintr"age in der Liste gibt?
 z.B.: Objekt 1 hat am Platz 1 zuerst 50 Punkte und beim n"achsten
 Mal 100 Punkte bekommen.
 \begin{itemize}
  \item Ermittelt man dies durch Zufall?
  \begin{itemize}
   \item Dies ist sehr schlecht, da der GA zuerst einen Fitnisswert
   bekommt und beim n"achsten Mal einen anderen. Welcher gilt?
  \end{itemize}
  \item Maximum?
  \item Durchschnitt?
 \end{itemize}
 Dies ist noch zu kl"aren.\\

Am Ende der Initialisierungsphase werden die gesammelten Daten zu
einem Datensatz zusammengef"ugt und stehen anschliessend dem
Optimierungsalgorithmus als Ausgangsbasis zur Verf"ugung.\\

\begin{center}
\begin{tabular}{l|c|r} Datum & Objekt & Wert\\
\hline
02.03.2000 & 1 & 1000\\
02.03.2000 & 2 & 3000\\
\dots & \dots & \dots\\
\end{tabular}
\end{center}



%
%Optimierungsphase
%

\section{Optimierungsphase}
In dieser Phase wird versucht, aus den Daten, welche aus der
Initialisierungsphase gewonnen wurden (k"onnen auch empirische
Daten sein) eine optimale Postitionierung der Objekte zu finden.
Ziel dabei ist es eine Aufstellung zu finden, bei welcher die Summe
der Werte aller Objekte m"oglichst hoch ist. Realisiert wird diese
Optimierung mit Hilfe eines GA's.

\subsection{Motivation warum ein GA verwendet wird}
\begin{itemize}
  \item Wahrscheinlich ist dieses Problem ein Assigment-Problem.
  \item Ein Assigment-Problem ist jedoch NP-Vollst"andig!
  \item Herk"omlicher L"osungsansatz:
  \begin{itemize}
   \item Gegeben ist die Liste der Objekte, ihre Postion und ihrer
   Wertigkeit:
   \item z.B.:

    \begin{tabular}{l|c|r}
    Objekt & Positon & Wert\\
    \hline
    1 & 1 & 1000\\
    1 & 2 & 300\\
    2 & 1 & 900\\
    2 & 2 & 100\\
    \dots & \dots & \dots\\
   \end{tabular}\medskip
   \item Nun sucht man einfach aus der Liste den Besten heraus (in
   unserem Fall Objekt 1 auf Postion 1) und positioniert ihn dort. Das
   Ergebnis ist in diesem Beispiel folgendes:

   \begin{tabular}{l|c|r}
    Objekt & Positon\\
    \hline
    1 & 1 & 1000\\
    2 & 2 & 100\\
    \dots & \dots & \dots\\
   \end{tabular}\medskip
   Dies ergibt ein Gesamtergebnis von 1100.

   Besser w"are jedoch folgendes:

   \begin{tabular}{l|c|r}
    Objekt & Positon\\
    \hline
    1 & 2 & 300\\
    2 & 1 & 900\\
    \dots & \dots & \dots\\
   \end{tabular}\medskip
   Da das Gesamtergebnis hier 1200 ist!
   \end{itemize}
 \end{itemize}


\subsection{Evolution"arer Zyklus}

Wir bilden unser System anhand der Generationsbasierten Methode,
d.h. es werden Populationen von Individuen gebildet, indem am Ende
einer Generation Fitness-Werte bestimmt werden, und zwar in Bezug
auf eine zuvor bestimmte Fitness-Funktion. In unserem Fall wird
jedem Individuum (= Codierung einer Objektposition) die Summe aller
Werte zugeschrieben, die von den Agenten dem Individuum zugewiesen
werden.

Als n"achstes stellt sich die wichtige Frage: Wie soll man die
Objektposition in einen bit string codieren? In unserer Simulation
wollen wir eine Objektposition durch zwei Chromosome codieren.
Chromosom 1 ($C_1$) repr"asentiert die verschiedenen m"oglichen
Positionen von Objekten in der Objektwelt. All diese Positionen
sind grunds"atzlich nichtgesperrte Felder. Da Objekt- und
Agentenwelt in Matrix-Form organisiert sind, k"onnen wir die
Objektwelt Zeile f"ur Zeile auslesen und pro nichtgesperrtem Feld
ein Bit vorsehen. In diesem Fall repr"asentiert 1 das Vorhandensein
und 0 das Nicht-Vorhandensein eines Objektes auf diesem bestimmten
Feld. Das zweite Chromosom ($C_2$) codiert den Index der Objekte.
$C_2$ kann gr"osser, gleich gross oder kleiner sein als $C_1$. Da
wir den Index der Objekte codieren, m"ussen wir mehr als ein Bit
f"ur den Index verwenden, n"amlich $\lceil \log_2 (\#
objects)\rceil$. Weiters m"ussen wir aufpassen, dass im Falle einer
Mutation ein Objekt genau einmal in $C_2$ aufscheint. Daher m"ussen
wir den Mutations-Operator auf folgende Weise ab"andern:

\begin{enumerate}
\item Bestimme in Bezug auf die Mutationswahrscheinlichkeit $p_m$ einen
Mutationsort auf $C_2$.
\item W"ahle zuf"allig einen zweiten Ort auf $C_2$.
\item Tausche die beiden Elemente gegeneinander aus.
\end{enumerate}

Die Verwendung des obigen Algorithmus garantiert, dass ein Objekt
genau einmal in $C_2$ vorkommt. Bei $C_1$ k"onnen wir den Operator
der Standard-Bit-Mutation verwenden.

\begin{figure}[hbtp]
\begin{center}
\includegraphics[width=7cm]{pic/reproduction_optimizing.xfig.eps}
\end{center}
\caption{Crossing over zwischen Chromosom $C_1$ der Individuen
$i_i$ und $i_j$.} \label{cd}
\end{figure}

In Abbildung~\ref{cd} zeigen wir das crossing over f"ur zwei
verschiedene Individuen. F"ur Chromosom $C_2$ k"onnten wir den
gleichen Mechanismus anwenden, aber wir m"ussen garantieren, dass
ein Objekt genau einmal vorkommt. Diese Erfordernis impliziert
deutlich die Modifikation des crossover-Operator auf nicht-triviale
Weise. Daher beabsichtigen wir, das original $C_2$ der Individuen
$i_i$ und $i_j$ zu kopieren und behalten einen urspr"unglichen
Satz. Somit bekommen wir wieder vier Chromosome.

Wie m"ussen wir die relevanten Objekte f"ur Orte mit Wert = 1 in
$C_1$ bestimmen? $C_1$ wird von links nach rechts ausgelesen. Wann
immer eine 1 im bit string auftaucht, lesen wir den passenden
Objektindex $C_2$ und erh"ohen
den Z"ahler f"ur $C_2$.



\section{Anwenderf"alle}
\begin{figure}[hbtp]
\begin{center}
\includegraphics[width=7cm]{pic/usecase.eps}
\end{center}
\caption{use-case-diagram} \label{usecase}
\end{figure}


\begin{enumerate}
% beginn betriebsart grunddaten -


\item \textbf{Betriebsart Grunddaten anlegen}

Unter Grunddaten wird verstanden, dass der Benutzer diese Daten auf alle
F"alle eingeben mu\ss.\\Grunddaten sind:
\begin{enumerate}
\item Die Dimension und die Rasterung der Superklasse Welt:\\
Die Form der Welt mu\ss  \ immer die Form eines Rechtecks haben.
Es m"ussen folgende Daten eingegeben werden:

\begin{enumerate}
\item Die Werte m und n.\\ Der Wert m gibt an wieviele Objekte in Y-Richtung
- siehe Abbildung 2.1 - maximal nebeneinander aufgestellt werden k"onnen.
Der Wert n
gibt an wieviele Objekte in X-Richtung maximal nebeneinander
aufgestellt werden
k"onnen.
Es wird angenommen, dass die Objektabmessung quadratisch ist.


\item Eingabe von Wert k.\\ Der Wert k gibt das Verh"altnis Agentenaktionsradius
zu Objektabmessung an. Die Fl"ache die ein Agent in der Agentenwelt f"ur
sich alleine beansprucht, ist der Agentenaktionsradius.
\end{enumerate}
\item Festlegung der Sperrfl"achen.\\ Die Definition, wo eine Sperrfl"ache ist, erfolgt "uber die
Rasterfl"achen in  der Agentenwelt. Das hei\ss t, es wird f"ur jedes Feld festgelegt, ob es sich um eine
Sperrfl"ache handelt oder nicht.


\item Festlegung der Ein- und Ausg"ange.\\Die Definition der Ein- und Ausg"ange erfolgt "uber zwei Punkte.
\item Eingabe der Objekte. \\ Ein Objekt hat einen Namen und
Kosten $c^0_i$.
\end{enumerate}

Der Benutzer, der die Grunddaten eingibt, hat die M"oglichkeit die
Richtigkeit seiner Eingaben anhand einer graphischen Darstellung oder in Form
einer Tabelle zu kontrollieren.\\



\item \textbf{Betriebsart Simulation}

  Der Benutzer kann zwischen einer automatischen Generierung der Daten und einer benutzerdefinierten Eingabe der Daten w\"ahlen.
  Diese Auswahl beeinflusst die weitere Bedienung des Programmes:

% 2 spalten f�r automatische generierung und benutzerdefiniert:


\begin{minipage}[t]{7cm}
  \textbf{benutzerdefinierte Eingabe:} \\
  Der Benutzer muss die Objekte in der Objektwelt positionieren. Diese Positionierung kann entweder mit einer grafischen Benutzeroberfl\"ache
  oder mit einer Eingabeaufforderung mittels der Koordinaten der Objektwelt (m,n) erfolgen. Weiters muss vom Anwender die Ausrichtung der Objekte
  angegeben werden. Diese Ausrichtung orientiert sich nach den Himmelsrichtungen (N - oben, S - unten, W - links, O - rechts) und bezieht sich
  auf die Darstellung am Bildschirm. \\
  Weiters wird vom Anwender die Agentenanzahl und ein Mittelwert des Budgets der Agenten angelegt.
\end{minipage}
\hfill
\begin{minipage}[t]{7cm}
  \textbf{automatische Generierung:} \\
  Das Programm nimmt die Positionierung der Objekte und deren Ausrichtung zuf\"allig vor. Die Anzahl und das Budget der Agenten wird vom Programm
  angelegt. Das Programm generiert eine feste Anzahl von Experimentenlisten (30 Tabellen).
\end{minipage}

\vspace{0,5 cm}

Das Experiment kann mittels einer grafischen Anzeige der Welt (inkl. aller sich darin befindlichen Sperrfl\"achen, Objekte, Ein- und
Ausg\"ange und Agentenbewegungen), am Bildschirm verfolgt werden. Diese grafische
Anzeige erfolgt in vom Benutzer bestimmten Zeitintervallen (0 - 100 \% der Experimentendauer). \\
Durch eine einfache Anzeige soll der Benutzer den Fortschritt der Simulation verfolgen k\"onnen.\\
Die Simulation kann vom Benutzer gestartet, unter- und abgebrochen werden. \\
Das Experimentenergebnis wird in einer Tabelle angelegt und kann als solches vom Benutzer ver\"andert, gespeichert, neu geladen und ausgegeben werden.
Falls das System gen\"ugend Experimente zur Verf\"ugung hat (30 Experimentenergebnisse) kann vom Benutzer eine Tabelle erzeugt werden,
die das Simulationsergebnis darstellt. Um diese Datengenerierung vorzunehmen, k\"onnen Experimentenergebnisse geladen werden. Falls zuvor
die automatische Generierung der Daten ausgew\"alt wurde, werden die Daten aus der automatischen Generierung verwendet, der Anwender kann
in diesem Fall keine anderen Experimentenergebnisse laden.
Das Simulationsergebnis kann gespeichert, gel\"oscht und angezeigt werden.


% ende betriebsart simulation



% beginn betriebsart optimierung der objektaufstellung

\item \textbf{Betriebsart Optimierung der Objektaufstellung}

Als Basisdaten f"ur die Optimierung der Objektaufstellung dienen die Grunddaten, d.h. die Dimensionierung der Objekt- und Agentenwelt und
deren Raster, definierte Sperrfl"achen und Ein-/Ausg"ange sowie die angegebenen Objekte $o_{i}$ mit ihren Parametern (Name, Kosten).

Dem Benutzer soll es m"oglich sein, einen Optimierungsalgorithmus zu laden. Grunds"atzlich steht als "`default�"{}-Wert ein
Basisalgorithmus zur Verf"ugung. Der Benutzer kann nun den Optimierungsvorgang starten, in dem der gew"ahlte Algorithmus eine m"oglichst
gute Objektaufstellung berechnet. Nach Abschluss dieses Vorgangs kann sich der Benutzer die berechnete Objektaufstellung grafisch oder
tabellarisch anzeigen lassen.\\

% ende betriebsart optimierung der objektaufstellung


% beginn betriebsart optimierung des algorithmus, Florian Angulanza

\item \textbf{Betriebsart Optimierung des Algorithmus}

Es m"ussen mehrere Simulationsergebnisse bereitstehen, die dazu dienen, den Optimierungsalgorithmus zu verbessern
und/oder fu"r gewisse Problemstellungen zu optimieren.

Dem Benutzer soll es nun m"oglich sein, einen vorhandenen Optimierungsalgorithmus zu laden oder den Basisalgorithmus als Voreinstellung
auszuw"ahlen. Ausserdem kann der Benutzer Simulationsergebnisse, die in der Betriebsart Simulation errechnet worden sind, laden, um den
Algorithmus f"ur die Optimierung zu verbessern. Dabei soll eine History "uber bereits verwendete Simulationsergebnisse Auskunft geben.
Diese History enth"alt Namen der Simulationsergebnisse sowie die zeitlichen Daten ihrer Verwendung f"ur die Optimierung.

Nach Vornahme dieser Einstellungen kann der Benutzer nun den Start der Algorithmus-Optimierung veranlassen. Das erfolgreiche Ende der
Optimierung wird dem Benutzer mitgeteilt, dieser kann den neuen Algorithmus nun speichern.\\

% ende betriebsart optimierung des algorithmus

\end{enumerate}

\section{Klassendiagramm}

\begin{figure}[hbtb]
\begin{center}
\includegraphics[width=15cm]{pic/classdig.eps}
\end{center}
\caption{Klassendiagramm} \label{classdiagram}
\end{figure}


% snapshots des hauptfensters

\section{Snapshots der Benutzeroberfl\"achen:}

\begin{enumerate}
  \item Darstellung des Hauptfensters:\\ In diesem Hauptfenster wird die grafische Anzeige der Welt dargestellt. Links davon befindet sich eine Liste mit den bereits angelegten Objekten. Diese Objektliste wird in 4 Spalten unterteilt. Die erste Spalte zeigt die automatisch vergebene Nummerierung des Objektes. Die zweite Spalte zeigt den vom Benutzer eingegeben Namen des Objektes. Die dritte und vierte Spalte zeigt die Position und die Ausrichtung des Objektes an. Position und Ausrichtung der Objekte wird standardm\"a"sig vom Programm definiert. Indem der Benutzer die Schaltfl\"ache Auto abschaltet, kann die Position und Ausrichtung vom Benutzer ver\"andert werden. \\ Unter den Anzeigen f\"ur Objektliste und Welt befinden sich ein Schalter zur\"uck und vor. Mit Hilfe dieser Schalter k\"onnen die verschiedenen Simulationen betrachtet werden. Die Zahl zwischen den beiden Schaltern zeigt die Nummer der Simulation. \\ Der Schalter optimiert zeigt die Objektliste und Welt der optimierten Aufstellung.

  \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=17cm]{pic/hauptfenster.ps}
    \end{center}
    \caption{Hauptfenster} \label{hauptfenster}
  \end{figure}

  \item Darstellung der Auswahl Datei, aus der Men\"uleiste des Hauptfensters:\\ Hier kann ein neues Projekt gestartet, ein Projekt geladen, gespeichert und das Programm beendet werden.

  \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=10cm]{pic/datei.ps}
    \end{center}
    \caption{Men\"u: Datei} \label{datei}
  \end{figure}

  \item Darstellung der Auswahl Grunddaten - Welt, aus der Men\"uleiste des Hauptfensters:\\ Mit dieser Auswahl kein eine neue Welt angelegt werden, eine bereits bestehende Welt bearbeitet und geladen werden.

  \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=10cm]{pic/grunddaten_welt.ps}
    \end{center}
    \caption{Men\"u: Grunddaten - Welt} \label{grunddaten_welt}
  \end{figure}

  \item Darstellung der Auswahl Grunddaten - Objekte, aus der Men\"uleiste des Hauptfensters:\\ Hier kann die Objektliste geladen und bearbeitet werden.

  \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=10cm]{pic/grunddaten_objekte.ps}
    \end{center}
    \caption{Men\"u: Grunddaten - Objekte} \label{grunddaten_objekte}
  \end{figure}

  \item Darstellung der Auswahl Grunddaten - Agenten, aus der Men\"uleiste des Hauptfensters:\\  Hier kann die Agentenliste geladen und bearbeitet werden.

  \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=10cm]{pic/grunddaten_agenten.ps}
    \end{center}
    \caption{Men\"u: Grunddaten - Agenten} \label{grunddaten_agenten}
  \end{figure}

  \item Darstellung der Auswahl Start, aus der Men\"uleiste des Hauptfensters:\\ Mit dieser Auswahl kann eine Simulation und die Optimierung gestartet werden.

  \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=10cm]{pic/start.ps}
    \end{center}
    \caption{Men\"u: Start} \label{start}
  \end{figure}

 \item Darstellung der Auswahl Optionen, aus der Men\"uleiste des Hauptfensters:\\ Unter Optionen kann ein Algorithmus geladen und optimiert werden. Weiters k\"onnen hier diverse Einstellungen getroffen werden.

 \begin{figure}[hbtb]
    \begin{center}
      \includegraphics[width=10cm]{pic/optionen_algorithmus.ps}
    \end{center}
    \caption{Men\"u: Optionen} \label{optionen}
  \end{figure}


\item Eingabefenster f\"ur Daten der Welt:

\begin{figure}[!h]

    \begin{center}
    \includegraphics[width=15cm]{pic/weltb.eps}
    \end{center}
\caption{Eingabefenster f"ur Daten der Welt} \label{eingabe_welt}
  \end{figure}

\item Eingabefenster f\"ur Daten der Objektliste:

\begin{figure}[!h]

    \begin{center}
    \includegraphics[width=15cm]{pic/objekte.eps}
    \end{center}
\caption{Eingabe der Objekte} \label{eingabe_objekt}
  \end{figure}

\item Eingabefenster f\"ur Daten der Agentenliste:

\begin{figure}[!h]

    \begin{center}
    \includegraphics[width=15cm]{pic/agenten.eps}
    \end{center}
\caption{Eingabe der Agenten} \label{eingabe_agenten}
  \end{figure}

\item Eingabefenster f\"ur Einstellungen:

\begin{figure}[!h]

    \begin{center}
    \includegraphics[width=15cm]{pic/einstel.eps}
    \end{center}
\caption {Einstellungen} \label{einstellungen}
  \end{figure}


\item Eingabefenster f\"ur Algorithmusoptimierung:

\begin{figure}[!h]

    \begin{center}
    \includegraphics[width=13cm]{pic/opt_al.eps}
    \end{center}
\caption{Fenster f"ur Algorithmusoptimierung} \label{opt_algor}
  \end{figure}

\end{enumerate}




%
% Anhang
%

%
% Protokoll vom 15. Maerz 2000
%

\appendix
\chapter{Protokolle}

\section{Protokoll vom 15.\,M"arz\,2000}

\begin{tabbing}
 \textbf{Protokollf"uhrer: } \= Name                       \kill
 \textbf{Leiter:}            \> DI~Mag.~Roland~Schwaiger\\
 \textbf{Protokollf"uhrer: } \> Florian~Angulanza\\
 \textbf{Teilnehmer:}        \> Manfred~Bernhard~Mayr\\
                             \> Christian~Osterrieder\\
                             \> Markus~Spitzlinger\\
 \textbf{Ort:}               \> Salzburg\\
 \textbf{Zeit:}              \> $17^{30}$ \\
\end{tabbing}

\begin{itemize}
\item Treffen w"ochentlich, sp"ater weniger oft
\item Was ist zu tun im Laufe des Praktikums:
 \begin{itemize}
  \item Paper erstellen (in \LaTeX )
  \item Objektbeschreibung in UML (Unified Modelling Language)
  \item Beherrschung von HTML
  \item Programmieren in Java
 \end{itemize}
\item Beschreibung als \LaTeX -file bis Mi $17^{30}$ als .\TeX -Source

\item Beschreibung der Grafik im Paper:\\      %Vielleicht spaeter ref
      Grafik besteht aus folgenden Elementen:
 \begin{itemize}
  \item Objekten (Entities)
   \begin{itemize}
    \item bewegen sich
    \item Werte werden gesammelt
   \end{itemize}
  \item Agenten
   \begin{itemize}
    \item bewegen sich anders als Objekte
    \item kann nicht auf Objektfelder
   \end{itemize}
  \item Schwarzen Flecken
   \begin{itemize}
    \item sind verbotene Zonen
   \end{itemize}
  \item Ein- und Ausg"angen
 \end{itemize}

\item OOP ist ein Multiagentensystem

\newpage

\item Beschreibung des Diagramms im Paper:      %Vielleicht spaeter ref

 \begin{enumerate}
  \item \textbf{Initialphase:}\\
   z.B.: System 24 Stunden laufen lassen / mit einer Aufl"osung von 1 Minute
   Daten aufzeichnen $\rightarrow$ Tagesergebnis $\mathcal{T}$ ergibt sich aus
   $24*60$\,Minuten.\\
   Dies wird wiederholt, z.B. 30\,mal $\rightarrow$ 1\,Monat
   $\rightarrow$ 30\,Experimente. Immer zwischendurch an den Objekten
   "Anderungen machen $\rightarrow$ \emph{Vergleichsdaten}.\medskip

   \begin{tabular}{l|c|r}
    Datum & Objekt & Value\\
    \hline
    02.03.2000 & 1 & 1000\\
    02.03.2000 & 2 & 3000\\
    $\ldots$ & $\ldots$ & $\ldots$\\
   \end{tabular}\medskip

  \item \textbf{Hauptphase:}

   Gleiche Laufzeit (z.B. 1\,Tag), Optimierung aufgrund von Daten aus der
   Initialphase $\rightarrow$ \emph{Genetischer Algorithmus} f"ur Optimierung,
   dann Agenten wieder laufen lassen.

 \end{enumerate}

\item 1.\,Aufgabe:
 \begin{itemize}
  \item \LaTeX -file aus \quad \underline{\textasciitilde
   rschwaig/out-dir/ppktII2000/gruppe2} \quad holen und in eigenes Dokument
   kopieren
   \item Dokument erg"anzen
   \item Fragen einbinden
  \end{itemize}

\item N"achster Termin: Mi, 22.\,M"arz\,2000

\end{itemize}

%
% Protokoll vom 22. Maerz 2000
%

\section{Protokoll vom 22.\,M"arz\,2000}

\begin{tabbing}
 \textbf{Protokollf"uhrer: } \= Name                       \kill
 \textbf{Leiter:}            \> DI~Mag.~Roland~Schwaiger\\
 \textbf{Protokollf"uhrer: } \> Markus~Spitzlinger\\
 \textbf{Teilnehmer:}        \> Manfred~Bernhard~Mayr\\
                             \> Christian~Osterrieder\\
                             \> Florian~Angulanza\\
 \textbf{Ort:}               \> Salzburg\\
 \textbf{Zeit:}              \> $17^{30}$ \\
\end{tabbing}

\begin{itemize}
\item Was ist UML und wozu wird es verwendet?
 \begin{itemize}
  \item UML ist die Abk"urzung f"ur Unified Modelling Language.
  \item UML dient dazu die Entwicklung von Software zu dokumentieren und ist
  prinzipiell eine graphische Beschreibungssprache.
\end{itemize}

\item UML in unserem Projekt:
 \begin{itemize}
  \item Ein Tool um Dokumentationen in UML zu erstellen ist ARGO-UML (auf
  der Hompage von DI~Mag.~Roland~Schwaiger zu finden (XML-Parser von IBM ist
  notwendig!).
  \item Klassendiagramme und Benutzerf"alle sollen mit UML-dargestellt werden.
 \end{itemize}

\item Wie werden die Agenten positioniert?
\begin{itemize}
  \item Ein Agent ist in diesem Fall eine Klasse.
  \item Die Bewegung des Agenten wird zuerst ganz einfach mittels
  Zufallsgenerator realisiert (einfache Methode).
  \item Die Anzahl der Agenten wird immer konstant gehalten, d.h. wenn ein
  Agent die Agentenwelt verl"a"st wird ein anderer nachgeschickt.
 \end{itemize}

\item Motivation warum ein GA verwendet wird:
 \begin{itemize}
  \item Wahrscheinlich ist dieses Problem ein Assigment-Problem.
  \item Ein Assigment-Problem ist jedoch NP-Vollst"andig!
  \item Herk"omlicher L"osungsansatz:
  \begin{itemize}
   \item Gegeben ist die Liste der Objekte, ihre Postion und ihrer
   Wertigkeit:
   \item z.B.:

    \begin{tabular}{l|c|r}
    Objekt & Positon & Wert\\
    \hline
    1 & 1 & 1000\\
    1 & 2 & 300\\
    2 & 1 & 900\\
    2 & 2 & 100\\
    \dots & \dots & \dots\\
   \end{tabular}\medskip
   \item Nun sucht man einfach aus der Liste den Besten heraus (in
   unserem Fall Objekt 1 auf Postion 1) und positioniert ihn dort. Das
   Ergebnis ist in diesem Beispiel folgendes:

   \begin{tabular}{l|c|r}
    Objekt & Positon\\
    \hline
    1 & 1 & 1000\\
    2 & 2 & 100\\
    \dots & \dots & \dots\\
   \end{tabular}\medskip
   Dies ergibt ein Gesamtergebnis von 1100.

   Besser w"are jedoch folgendes:

   \begin{tabular}{l|c|r}
    Objekt & Positon\\
    \hline
    1 & 2 & 300\\
    2 & 1 & 900\\
    \dots & \dots & \dots\\
   \end{tabular}\medskip
   Da das Gesamtergebnis hier 1200 ist!
   \end{itemize}
 \end{itemize}

 \item Wie wird "uberwacht, da"s die Objekte die Agenten
 durch ihre Aufstellung nicht behindern, z.B. alle in einer Reihe
 wodurch es m"oglich w"are, da"s kein Agent mehr zu einem Objekt kann?
 \begin{itemize}
  \item Dies m"u"ste der GA l"osen, da die Objekte keine Punkte
  bekommen und somit als gute L"osung ausscheiden.
 \end{itemize}

 \item Wie ermittelt man welchen Fitnisswert ein Objekt hat wenn es
 zwei Eintr"age in der Liste gibt?
 z.B.: Objekt 1 hat am Platz 1 zuerst 50 Punkte und beim n"achsten
 Mal 100 Punkte bekommen.
 \begin{itemize}
  \item Ermittelt man dies durch Zufall?
  \begin{itemize}
   \item Dies ist sehr schlecht, da der GA zuerst einen Fitnisswert
   bekommt und beim n"achsten Mal einen anderen. Welcher gilt?
  \end{itemize}
  \item Maximum?
  \item Durchschnitt?
 \end{itemize}
 Dies ist noch zu kl"aren.

 \item Aufgabenstellung bis n"achste Woche:
 \begin{itemize}
  \item Welche Datenstrukur wird verwendet?
  \item Welche Felder hat die Tabelle bzw. Datenbank?
  \item Motivation GA ins Dokument einbinden.
  \item Mit UML vertraut machen.
  \item Dokument erweitern.
 \end{itemize}

\end{itemize}

%
% Protokoll vom 29. Maerz 2000
%

\section{Protokoll vom 29.\,M"arz\,2000}

\begin{tabbing}
  \textbf{Protokollf"uhrer: } \= Name                       \kill
  \textbf{Leiter:}            \> DI~Mag.~Roland~Schwaiger\\
  \textbf{Protokollf"uhrer: } \> Christian Osterrieder\\
  \textbf{Teilnehmer:}        \> Manfred~Bernhard~Mayr\\
                             \> Markus~Spitzlinger\\
                             \> Florian~Angulanza\\

  \textbf{Ort:}               \> Salzburg\\
  \textbf{Zeit:}              \> $17^{30}$ \\
\end{tabbing}

\begin{itemize}
\item Datenstruktur, welche Klassen werden vorerst ben"otigt?
  \begin{itemize}
  \item Agentenklasse
  \item Objektklasse
  \item Klasse Tagesliste
  \item Klasse Monatsliste
  \end{itemize}

  Vorschlag f\"ur Tagesliste:

  \begin{tabular}{|c|c|c|}
  \hline
  Objektbezeichner & Position    & Wert    \\ \hline\hline
  1                & $(x,y)_{1}$ & $w_{1}$ \\ \hline
  2                & $(x,y)_{2}$ & $w_{2}$ \\ \hline
  .                & .           & .       \\ \hline
  .                & .           & .       \\ \hline
  .                & .           & .       \\ \hline
  n                & $(x,y)_{n}$ & $w_{n}$ \\ \hline
\end{tabular}

Um eventuell sp\"ater Daten weiterzuverarbeiten, sollten die einzelnen Zwischenwerte zum Zeitpunkt $t$ gespeichert werden:

\begin{tabular}{|c|c|c|c|c|c|c|}
  \hline
  Objektbezeichner & Position    & \multicolumn{4}{|c|}{Wert}             \\ \hline\hline
  1                & $(x,y)_{1}$ & $w_{t}$ & $w_{t+1}$ & ... & $w_{t+m}$  \\ \hline
  2                & $(x,y)_{2}$ & $w_{t}$ & $w_{t+1}$ & ... & $w_{t+m}$  \\ \hline
  .                & .           & .       & $w_{t+1}$ & ... & $w_{t+m}$  \\ \hline
  .                & .           & .       & $w_{t+1}$ & ... & $w_{t+m}$  \\ \hline
  .                & .           & .       & $w_{t+1}$ & ... & $w_{t+m}$  \\ \hline
  n                & $(x,y)_{n}$ & $w_{t}$ & $w_{t+1}$ & ... & $w_{t+m}$  \\ \hline
\end{tabular}

\item Objekte und Agenten haben eine Orientierung:

% darstellung der grafik richtung.eps aus dem verzeichnis \pic
  \begin{figure}[h]
    \begin{center}
      \includegraphics[width=4cm]{pic/richtung.eps}
    \end{center}
  \end{figure}

\item weiters sollen folgende Daten mitprotokolliert werden:
  \begin{itemize}
  \item Orientierung von Objekten
  \item Orientierung von Agenten
  \item von welchem Agenten kommt das Guthaben
  \item Querverbindung: welcher Agent war an welchem Objekt
  \item zu welchem Zeitpunkt kommt das Guthaben von einem Agenten
  \end{itemize}

  d. h. eine Simulation sollte wiederholbar sein -- Zufallsgenerator mit seed verwenden

\item Klasse Monatsliste: Warum Orientierung an Stellpl\"atzen und nicht an Objekten?



  Angenommen man hat mehr Objekte ($n$) als Stellpl\"atze ($m$): $n > m$, Ziel ist es, aus einem Stellplatz das Maximum "'herauszuholen"'
  -- Assignementproblem!
  \\

% darstellung der grafik stellplatz.eps aus dem verzeichnis \pic
  \begin{figure}[!h]
    \begin{center}
      \includegraphics[width=4cm]{pic/stellpl.eps}
    \end{center}
  \end{figure}


\item Warum wird eine Monatsliste erstellt? Kann der GA nicht die Tageslisten verwenden?

  Falls ein Objekt mehrmals am gleichen Stellplatz war, wird z. B. das Maximum verwendet.
  Die Tagessicht wird dadurch eleminiert. Der GA ben\"utzt die Werte mehrerer Monatslisten nach folgendem Schema:
  \\ Periode $\rightarrow$ Datensammlung $\rightarrow$ Optimierung  $\rightarrow$ Periode  $\rightarrow$ Datensammlung $\rightarrow$ Optimierung  $\rightarrow$ usw.

\item Datenstruktur der Welten:

  Agentenwelt und Objektwelt werden von einer "'Welt"' vererbt.

% darstellung der grafik welt.eps aus dem verzeichnis \pic
  \begin{figure}[!h]
    \begin{center}
    \includegraphics[width=4cm]{pic/welt.eps}
    \end{center}
  \end{figure}

\item Eine grafische Darstellung soll eingebaut werden:
  \begin{itemize}
  \item wie bewegen sich die Agenten
  \item wie ist die Welt aufgebaut
  \item diese Darstellung sollte abschaltbar sein, da es die Rechenleistung mindert
  \item die Schritte zwischen Darstellung und Berechnung sollten festgelegt werden k\"onnen
  \end{itemize}

\item Aufgabenstellung bis zum n\"achsten Treffen:
  \begin{itemize}
  \item \"Uberlegung wie die Daten abgelegt werden (ASCII oder XML) -- Java parsing!
  \item mit UML vertraut machen (Powerpoint-Einf\"uhrung)
  \item Use-Cases entwickeln und zus\"atzliche Informationen erfragen
  \end{itemize}

\item Weitere Bemerkungen:
  \begin{itemize}
  \item n\"achste Woche entf\"allt (5. April 2000)
  \item GA steht noch nicht fest, wird bis zum n\"achsten Treffen erledigt.
  \end{itemize}

\end{itemize}

%
% Protokoll vom 12. April 2000
%



\section{Protokoll vom 12.\,April\,2000}

\begin{tabbing}
  \textbf{Protokollf"uhrer: } \= Name                       \kill
  \textbf{Leiter:}            \> DI~Mag.~Roland~Schwaiger\\
  \textbf{Protokollf"uhrer: } \> Manfred Mayr\\
  \textbf{Teilnehmer:}        \> Markus Spitzlinger\\
                             \> Christian~Osterrieder\\
                             \> Florian~Angulanza\\
  \textbf{Ort:}               \> Salzburg\\
  \textbf{Zeit:}              \> $17^{30}$ \\


\end{tabbing}


\begin{itemize}
\item Besprechung des Klassendiagramms
  \begin{itemize}
  \item Klasse \texttt{Welt}\\
Wir sollen unsere Welt so konstruieren, so dass sie 3 Dimensionen hat.\\
Die Welt kann mehrere Ein- und Ausg"ange haben. Diese Tatsache muss im Klassendiagramm
ber"ucksichtigt werden. Das hei\ss t "Anderung des Typs bei den Attributen \texttt{eingang}  und \texttt{ausgang}.
Es wird festgelegt, dass es nur Ein- und Ausg"ange am "au\ss eren Rand der Welt geben kann. Diese "Offnugen werden jeweils "uber zwei Punkte definiert. Die Welt soll Au\ss enw"ande haben, die auch graphisch dargestellt werden. Durchbr"uche in diesen W"anden entsprechen Ein- oder Ausg"angen. Ein Eingang kann aber mu\ss  \ nicht auch Ausgang sein und umgekehrt. Sperrfl"achen werden "uber X- und Y-Koordinaten bestimmt. Ist es vielleicht doch besser ein Metaobjekt einzuf"uhren?\\
Es soll ein Methode hinzugef"ugt werden, die es m"oglich macht Sperrfl"achen zu "andern. Diese "Anderungen sollen auch intern dokumentiert werden.


% darstellung der aussenwaende und ein- und ausgaengegrafik
  \begin{figure}[!h]
    \begin{center}
      \includegraphics[width=8cm]{pic/dig.eps}
    \end{center}
\caption{Aussenw"ande und "Offnungen} \label{aussenwaende}
  \end{figure}




\item Klasse \texttt{Agent}\\
Es soll m"oglich sein den Agenten einen Namen zu geben.\\
Dies stellt einen Beitrag zur Erh"ohung der Flexibilit"at des Programmes dar.

\item Klasse \texttt{Objekt}\\
Es soll ein besserer Name f"ur das Attribut \texttt{kosten} gefunden werden. Es soll m"oglich sein die Kosten eines Objektes zu "andern.

\item Typ \texttt{Status} \\
Die Ausrichtung des Objekts wird im Sourcecode mit den Bezeichnungen \texttt{N}, \texttt{S}, \texttt{O}, \texttt{W} definiert.

\item Klasse \texttt{ObjektGuthaben}\\
Die Bezeichnung \texttt{Guthaben} ist schlecht gew"ahlt, besser \texttt{ Detaileintrag}.
Es soll die Zeit mit protokolliert werden. Daher soll ein Attribut \texttt{Zeitschritt} in der Klasse \texttt{ObjektGuthaben} eingef"ugt werden.\\

\vspace{0.5cm}

\begin{tabular}{l|c|r}
    Zeitschritt & Agent & Objekt\\
    \hline
    1  & $a_1$ & $o_5$ \\
    1& $a_{10}$ & $o_3$\\
    2& $a_{12}$ & $o_7$\\
    2& $a_{17}$ & $o_3$\\
    2& $a_{33}$ & $o_{45}$\\
    2& $a_{52}$ & $o_{17}$\\
    $\ldots$ & $\ldots$ & $\ldots$\\
   \end{tabular}\medskip

Motivation:\\
Da in unserer Tabelle nur ein Eintrag erfolgt, wenn ein Objekt das Guthaben eines Agenten reduziert, kann ohne das Attribut \texttt{Zeitschritt} nicht festgestellt werden, wenn der "Ubergang vom Zeitschritt $i$ auf Zeitschritt $i+1$ erfolgte.

\item Klasse \texttt{SimulationErgebnis}\\
Begr"undung warum es keine Verweise auf die Experimentenergebnisliste gibt: Es gibt in der Klasse \texttt{SimulationErgebnis} eine Methode \texttt{experiment\_hinzufuegen}, die alle notwendigen Daten, die in der Experimentenergebnisliste existieren, in die Simulationsergebnisliste einf"ugt. Daher werden keine Verweise mehr auf die Experimentenergebnisliste mehr ben"otigt. Der Algorithmus kann dann direkt auf der Simulationsergebnisliste arbeiten. Die Folge ist Performancesteigerung w"ahrend der Laufzeit.

\end{itemize}


\item Genetischer Algorithmus

Was haben wir?
\begin{itemize}
\item Eine Liste von Objekten $m$
\item Eine Liste von Objektpositionen $n$

Wie schaut die Beziehung zwischen $m$ und $n$ aus?\\
Schwer zu sagen, da die Relation $m$ zu $n$ wie folgt sein kann: $m > n$, $m < n$ oder $m = n$.
\item Mutation (siehe Zusammenfassung)
\item Crossover (siehe Zusammenfassung)\\

\end{itemize}


\item Aufgabenstellung bis zum n"achsten Treffen

\begin{itemize}
\item Prototypen von GUI entwicklen
\begin{itemize}
\item Was mu\ss \ man sehen?
\item Was f"ur Fenster gibt es?
\item Wie wird die Welt dargestellt?
\item usw.
\end{itemize}
\item Erg"anzung der Zusammenfassung
\end{itemize}
\item Sonstige Bemerkungen
\begin{itemize}
\item Vielleicht ist es m"oglich das Projekt zu publzieren.
\item Erweiterung im Dokument \glqq Project Ideas \grqq \ werden wieder ins Netz gesetellt.
\item N"achstes Treffen: 12.Mai 2000, 18.00 - 18.30.
\end{itemize}
\end{itemize}











%
% Glossar
%

\chapter{Glossar}

\begin{description}

% Blockung
\item [Blockung:]
Zusammenfassen bestimmter Gene zu einer Einheit, deren Teile bei der weiteren Vererbung bei einer Inversion oder einem Crossover nicht mehr getrennt werden d"urfen.
% Crossover
\item [Crossover:]
Teilen zweier Chromosomen und Vererbung des "uber Kreuz zusammengesetzten Chromosoms. Hierbei mu"s man darauf achten, da"s die Ergebnisse der Neukombination wieder g"ultige Chromosomen sind.
% Entblockung
\item [Entblockung:]
Aufhebung einer Blockung.
% GA
\item [GA:] Genetischer Algorithmus
Algorithmus, der Strategien aus der Evolutionstheorie verwendet, um zu einem Problem eine m"oglichst gute L"osung zu finden.
% Inversion
\item [Inversion:]
Umdrehen eines Teilst"ucks eines Chromosoms und Vererbung des so modifizierten Chromosoms an die n"achste Population.
% Mutation
\item [Mutation:]
Ein oder mehrere Gene eines Chromosoms werden bei der Vererbung zuf"allig abge"andert.
% NP-Problem
\item [NP:]
Menge aller Sprachen, die von einer nichtdeterministischen
Turingmaschine in polynomialer Laufzeit erkannt werden k"onnen
(Determinismus). Hinter dem K"urzel NP verbirgt sich eines der
schwierigsten und f"ur die Praxis bedeutsamsten Probleme der
Informatik, n"amlich die Frage, ob gewisse Aufgabenstellungen
schnelle L"osungsverfahren besitzen oder nicht.
% Reproduktion
\item [Reproduktion:]
Ein Chromosom wird unver"andert an die n"achste
Population vererbt.
% Selektion
\item [Selektion:]
Die bzgl. der Bewertungsfunktion besten Chromosomen "uberleben.


\end{description}


%
% bibliography
%

\bibliographystyle{alpha}
\bibliography{ppkt3}
\addcontentsline{toc}{chapter}{Bibliography}

\end{document}
