\documentstyle[a4,german,umlaut]{article}
\usepackage{/usr/lib/teTex/texmf/tex/latex/graphics}
\begin{document}

\title{Javaprogramm zur Visualisierung verschiedener Operatoren in einem Genetischen Algorithmus (GA) anhand des Traveling Salesman Problems (TSP)}
\author{Diplomarbeit\\
Johannes Sarg}
\maketitle

Einerseits soll die Möglichkeit bestehen Parameter für einen GA einstellen zu können und diesen dann ablaufen zu lassen. Hierbei sind besonders wichtige Informationen welche sich im Laufe des GA entwickeln darzustellen. Andererseits soll nach der Auswahl spezieller Operatoren der genaue Ablauf und die Auswirkungen auf den GA dargestellt werden.

\section{Der GA:}
Parameter des GA:
\begin{tabular}[t]{l}
Populationsgrösse\\Rekombinationswahrscheinlichkeit\\
Mutationswahrscheinlichkeit\\k-Faktor vom Tournamentselektion\\Elitismus\\
\end{tabular}
\\
\\
Als Selektionsmethode wird Tournamentselektion (zufällige Auswahl von k vielen Individuen, das beste kommt in den matingpool) verwendet. Die Operatoren können in zwei Gruppen eingeteilt werden und unabhängig voneinander eingestellt werden. Um das Wirken der Operatoren beurteilen zu können, ist es auch sinnvoll die Möglichkeit zu haben, keinen Operator auswählen zu können. Die Generationenzahl ist insofern vom Benutzer einstellbar, als er entscheiden kann wann er den Algorithmus abbricht.
\\
\\
Rekombinationsmethoden: 
\begin{tabular}[t]{l}
Partially Matched Crossover (PMX)\\Order Crossover (OX)\\Cycle Crossover (CX)\\
Uniform Order Based Crossover (UOBX)\\Edge Recombination Crossover (ERX)\\
Hybrides Verfahren mit Heuristik (nach Grefenstette)\\none\\
\end{tabular}
\\
\\
Mutationsmethoden:
\begin{tabular}[t]{l}
Inversion\\Insertion\\Displacement\\Reciprocal\\Exchange (Swap)\\none\\
\end{tabular}
\\
\\
Als wesentliche Entwicklungsmerkmale des GA sollen die Population, die selektierten Individuen und deren Rekombination und die Mutation dieser neu entstandenen Individuen in eigenen Fenstern dargestellt werden. Der Anwender hat hierbei die Möglichkeit Schritt für Schritt diese Entwicklung zu beobachten oder gleich eine Generation weiter zu gehen. Durch Doppelklicken eines Individuums kann er sich eine Darstellung der von diesem Individuum repräsentierten Rundreise anschauen.
Der beste Weg und der Mittelwert aller Wege der Population werden in Abhängigkeit zur momentanen Generation graphisch dargestellt um so den genauen Verlauf des GA zu visualisieren. Der Algorithmus kann jederzeit vom Anwender gestartet und abgebrochen werden.

\section{Die Darstellungsweise der Individuen und der Statistik:}
Die interne Darstellung des TSP in einem GA ist eine Kette von Zahlen. Jede Zahl entspricht hierbei einer Stadt und der Übergang zur nächsten Zahl einer Reise zu dieser nächsten Stadt. Zur graphischen Darstellung von Individuen bietet sich diese interne Repräsentation in leicht abgewandelter Form an. Die Kette von Zahlen wird durch eine Kette von Großbuchstaben ersetzt. Die einzelnen Schritte des GA werden ab einer Reise über 26 Städte nicht mehr angezeigt sondern nur mehr das statistische Verhalten und der beste Weg. Wegen der Übersichtlichkeit wird aus zwei Eltern beim Crossover immer nur ein Kind erzeugt.

\section{Genaue Darstellung der Funktion der Rekombinationsmethode:}
Hierbei soll möglichst im Detail gezeigt werden wie die einzelnen Rekombinationsmethoden arbeiten. Wiederum soll es möglich sein Schritt für Schritt dieses Verhalten beobachten zu können. Es wird die Möglichkeit geben entweder Schritt für Schritt die Funktionalität der Rekombinationsmethode zu beobachten.
\\
\\
z.B.:
\begin{tabular}[t]{l}
Auswahl des Crossoverbereichs (farbig)\\Übertragung des Crossoverbereichs\\
Auswahl der restlichen Individuen (welche Kriterien)\\
\end{tabular}
\\
\\
Die Rundreisen der Eltern können nach einer vollendeten Rekombination mit der Rundreise des entstandenen Kindes angeschaut und verglichen werden.

\section{Verwendete Probleme:}

\subsection{Allgemein:}
Verschiedene Punkte werden aus einem Rechteck gewählt, wobei jeder Punkt der Lage einer Stadt entspricht. Von jeder Stadt aus sind alle anderen Städte erreichbar. Der euklidische Abstand der Städte zueinander ist hierbei als Preis zu verstehen. Eine Rundreise durch alle Städte ist also um so besser, je kleiner die Summe der Preise über alle Teilstrecken ist. Da die Rundreisen auch dargestellt werden sollen, dürfen zwei benachbarte Städte nicht beliebig nahe beieinander liegen. Dies wird durch eine Rasterung des Rechtecks gewährleistet.

\subsection{Zufällige Probleme:}
Die Anzahl der Städte kann eingestellt werden und muß mindestens drei betragen. Danach werden Punkte per Zufall aus einem gerasterten Rechteck genommen.

\subsection{Selbst erzeugte Probleme:}
In einem eigenen Fenster werden die Städte des Problems mittels Maus ausgewählt.
Werden hierbei mindestens 3 Städte ausgewählt, so wird dieses selbst erzeugte Problem genommen, ansonsten wird wiederum ein zufällig generiertes Problem verwendet.

\fbox{includegraphics{start.ps}}

\end{document}

