\documentclass[a4paper,12pt]{report}
\usepackage{german,umlaut,graphicx,alltt}
\begin{document}
\addtolength{\oddsidemargin}{0.5cm}
%\pagestyle{headings}
\tableofcontents

\chapter{Einleitung}
{\em Evolutionäre Algorithmen} (EAs) versuchen nach stark vereinfachten Prinzipien der natürlichen Evolution Optimierungsaufgaben zu lösen. Besonders sind sie für Probleme mit sehr großen, komplexen Suchräumen geeignet, wo eine Optimumsuche durch exakte Verfahren nicht mehr möglich ist. {\em Genetische Algorithmen} (GAs) sind ein spezieller Typ dieser Evolutionären Algorithmen.\\
Das {\em Traveling Salesman Problem} (TSP) ist ein Musterbeispiel für NP-vollstän\-di\-ge Probleme. Der Berechnungsaufwand mit allgemeinen Methoden steigt bei diesem Problem mit grösserwerdendem Umfang sehr stark an.\\
Dieses Problem kann in einem Genetischen Algorithmus unter besonderen Gesichtspunkten betrachtet werden, da nur die Reihenfolge, in der die Städte besucht werden, von Interesse ist. Solche Probleme werden auch als Reihenfolgeprobleme bezeichnet. Hiefür kommen spezielle Operatoren im GA zum Einsatz. Von diesen Operatoren hängt einerseits die Effizienz und andererseits die Konvergenz zu einem Optimum ab.\\
Im Rahmen dieser Diplomarbeit wurde ein Visualisierungsprogramm für Genetische Algorithmen anhand des Traveling Salesman Problems implementiert, in dem diese unterschiedlichen Operatoren für Reihenfolgeprobleme getestet und visualisiert werden können. Abgesehen von den Operatoren kann auch ganz genau die Funktionsweise eines GAs beobachtet werden. Verschiedenste TSPs können vom Benutzer selbst erzeugt und unterschiedlichste Parameter für den GA eingestellt werden. Besonders die Einstellung dieser Parameter wirkt sich auf den GA aus. Es muß versucht werden, die Parameter an das gestellte Problem so anzupassen, daß ein möglichst gutes Verhalten des GAs erreicht werden kann.\\
Zum Einsatz wird dieses Programm insbesondere für die Vorlesung ``Evolutionäre Algorithmen'' an der TU Wien kommen.

\chapter{Das Traveling Salesman Problem (TSP)}
Gegeben sei ein gerichteter Graph mit $n$ Knoten. Für jede Kante von Knoten $i$ zu Knoten $j$ $(i,j \in \{1,...,n\})$ ist eine Bewertung $d_{i,j}$ gegeben. Die Knoten können als Städte und die Kanten als Wege zwischen den Städten interpretiert werden, ihre Bewertungen als Wegkosten.\\
Die Kostenmatrix $D = [d_{i,j}]$ wird auch als {\em Adjazenzmatrix} bezeichnet. Wenn es keine Kante von einem Knoten $i$ zu einem Knoten $j$ gibt ist $d_{i,j} =  \infty$.\\
Es ist die kürzeste Rundreise gesucht, bei der jede Stadt genau einmal besucht wird:\\[20pt]
\begin{tabular}{ll}
minimiere & $ \sum_{j=1}^{n-1} d_{t_{j},t_{j+1}} + d_{t_{n},t_{1}}, $  \\ \\
wobei & $({t_{1}, ... , t_{n}})$ eine Permutation der Knoten von $1$ bis $n$ ist.
\end{tabular}
\\[20pt]
Dieses Problem ist NP-vollständig und wird auch in \cite{Sed91} beschrieben.\\
Der primitivste Algorithmus für dieses Problem ist, alle möglichen Permutationen der Knoten zu erzeugen und zu berechnen. Da nur die Reihenfolge der Städte und nicht ihre absoluten Positionen von Interesse sind, könnte eine beliebige Ausgangsstadt der Rundreise fixiert werden. Die Lösung ist daher rotationsinvariant. So einfach dieser Algorithmus auch ist, sein Aufwand steigt mit der Anzahl der Städte faktoriell.\\
Durch begrenzte Enumeration und Reduktion der Kostenmatrix kann der Aufwand stark verringert werden, das Problem bleibt jedoch im allgemeinen trotzdem NP-vollständig.\\
Konkrete Verfahren zur Lösung des TSP sind: {\em Backtracking}, {\em Branch and Bound} und {\em Dynamic Programming}, diese sind genauer in \cite{Sed91} und \cite{algodat} beschrieben.\\
Im weiteren Verlauf wird für das TSP festgelegt, daß von jedem Knoten zu jedem anderen Knoten eine Kante existiert, wobei die Bewertung dieser Kante der Euklidischen Distanz der beiden Knoten zueinander entspricht. Die Bewertung ist somit reflexiv. Ein Beispiel hierzu ist in Abb.~\ref{tspbsp} zu sehen.\\
\begin{figure}[htbp]
\begin{center}
\fbox{\includegraphics[scale=0.7]{./data/reise1.eps}}
\caption{Rundreise durch 6 Städte} \label{tspbsp}
\end{center}
\end{figure}
 
\include{gadoc01}
\include{doc02}
\include{tree}

\chapter{Zusammenfassung}
Für die näherungsweise Lösung großer Traveling Salesman Probleme sind Genetische Algorithmen gut geeignet. Ein Gen repräsentiert hierbei eine Stadt und ein Individuum eine Rundreise. Da für die optimale Lösung nur die Reihenfolge, in der die Städte besucht werden, von Interesse ist, werden spezielle Umordnungsoperatoren verwendet. Diese stellen sicher, daß ausschließlich gültige Individuen bei Rekombination und Mutation entstehen. Diese Operatoren lassen sich sehr gut graphisch visualisieren, und dadurch ist ihre Wirkungsweise und Funktionalität leichter zu erkennen und zu vergleichen.\\
Es soll hier aber auch erwähnt werden, daß durch speziell an ein Problem angepaßte Initialisierungen, Fitneßfunktionen und Operatoren (wie zum Beispiel der ERX mit Heuristik) ein GA im allgemeinen noch verbessert werden kann.\\
Erst das Testen, verschiedener Parametereinstellungen und Operatoren für den GA auf verschiedenen konkreten Instanzen des TSP, vermittelt wie unterschiedlich ein GA funktionieren kann.\\
Das implementierte Programm TSPGA stellt eine sehr flexible Grundlage zu diesem Experimentieren dar und erlaubt eine detailierte Visualisierung der inneren Vorgänge, die das Verständnis besonders im Unterricht wesentlich erleichtern.

\begin{thebibliography}{99}
\bibitem{Mic92}
Z. Michalewicz \textit{Genetic Algorithms $+$ Data Structures $=$ Evolution Programs}, Springer, NewYork, 1992

\bibitem{Gol89}
D. E. Goldberg \textit{Genetic Algorithms in Search, Optimization and Machine Learning}, Addison-Wesley, MA, 1989

\bibitem{Chu97}
P. C.H. Chu \textit{A Genetic Algorithm Approach for Combinatorial Optimisation Problems}, Jänner 1997

\bibitem{Sed91}
R. Sedgewick \textit{Algorithms}, Addison-Wesley, 1991

\bibitem{evol}
G. Raidl \textit{Vorlesungsskriptum für Evolutionäre Algorithmen}, Institut für Computergraphik TU Wien, 1996

\bibitem{algodat}
H. Müller-Merbach \textit{Optimale Reihenfolge}, Springer, 1970

\bibitem{javabook}
G. Cornell, C. S. Horstmann \textit{Core Java}, SunSoft, 1996

\bibitem{javasoft}
Sun Microsystems \textit{Java Development Kit Version 1.1.3}, http://java.sun.com/products/jdk/1.1/, 1998

\end{thebibliography}

\end{document}
