\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 einen bestimmen Wert $v^{a}_{i}$ zugewiesen,
welcher erniedrigt wird sobald dieser vor einem Objekt anh"alt. Die
Verminderung des Wertes 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/object_agent_world.xfig.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 welchen Wertevorrat
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}


\subsection{Datenstrukutr}

%
%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}


%
% 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}


%
% 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}
