\documentstyle[11pt]{article}
\textwidth=6in
\textheight=9in
\evensidemargin=0.5in
\oddsidemargin=0.5in
\topmargin=-0.375in
\topskip=0pt
\parindent=3em
\baselineskip=24pt

\input{psfig}
\begin{document}
\bibliographystyle{plain}

\Huge 

%
% Title Page
%

\vspace*{\fill}
\begin{center}
A Genetic Algorithm\\ for the\\ Steiner Minimal Tree Problem\\
\quad \\
\quad \\
Joseph Jones\\
jones@cs.unr.edu\\
\quad \\
Frederick C. Harris, Jr.\\
fredh@cs.unr.edu\\
\quad \\
Department of Computer Science\\
University of Nevada\\
Reno, Nevada 89557\\
\end{center}
\vspace*{\fill}

\newpage
\noindent
I.  Introduction
        \begin{itemize}
        \item Original Problem

                \vspace{0.25in}
                \begin{itemize}
                \item Given: 3 points, (A,B,C).
                \vspace{0.25in}
                \item Find: Point X that minimizes\\
                 $dist(A, X)+dist(B,X) + dist(C,X)$
                \vspace{0.25in}
                \item Solved independently by Fermat, \\
                Torrichelli, and Cavalieri.
                \end{itemize}

                \begin{figure}[h]
                \vspace*{22pt}
                \centerline{\psfig{figure=fig-melzak.ps,height=3.1in}}
                \caption{\label{fig:melzak}}
                \vspace*{22pt}
                \end{figure}

        \newpage
        \item First Expansion --
                \begin{itemize}
                \item 4 point problem.
                \item Proposed by Gauss
                \item Four Cities and Railroad lines
                \end{itemize}

        \vspace{1in}

        \item Jacob Steiner --
                \begin{itemize}
                \item 19th Century Professor
                \item University of Berlin
                \item 1 point to many
                \item Actually the 2-D center of Mass
                \end{itemize}

        \vspace{1in}

        \item General Form of the Problem
                \begin{itemize}
                \item Paper by K\"{o}ssler and Jarn\'{i}k ('34)
                \item What is Mathematics? ('41)
                \end{itemize}

        \newpage
        \item First Algorithm
                \begin{itemize}
                \item Melzak ('61)
                \vspace{0.35in}
                \item Replace two points with a third.
                \vspace{0.35in}
                \item $T(n)=2*\left( \begin{array}{c}n\\2\end{array}
                        \right)*T(n-1).$
                \vspace{0.35in}
                \item Given $n$ points and $s$ Steiner Points,
                        Sample Space is of size:

                        \vspace{0.35in}

			$2^{-n}\left(\begin{array}{c}n\\s+2\end{array}\right)
                        \frac{(n-s-2)!}{s!} $
                \end{itemize}
        \end{itemize}

\newpage
\noindent
II. The Genetic Algorithm

	\begin{itemize}
	\item Encoding
		\vfill
		\begin{itemize}
		\item an array of x and y coordinates representing 
			the location of the Steiner Points
		\vfill
		\item Instead of crossing over at random bit positions,
			we decided to crossover the chromosomes 
			at point boundaries.
		\end{itemize}
		\vfill
	\item Selection
		\vfill
		\begin{itemize}
		\item Roulette wheel selection proved to be too random,
			causing the GA to not converge to any specific solution.
		\vfill
		\item For this reason we chose to use CHC selection
		\end{itemize}
		\vfill
\newpage
	\item Crossover
		\vfill
		\begin{itemize}
		\item Simple one-point crossover proved to be a little
			too inefficient
		\vfill
		\item So we decided to move to two-point crossover.
		\end{itemize}
		\vfill
	\item Mutation
		\vfill

		Since our encoding did not allow us to just mutate
		simple on/off bits, it was necessary to alter it to 
		do two things:
		\vfill
		\begin{itemize}
		\item If the chromosome is full, select a point at 
			random and remove it.
		\vfill
		\item Generate a new point and add it to the chromosome.
		\end{itemize}
		\vfill
\newpage
	\item Population Regeneration
		\vfill
		\begin{itemize}
		\item Random regeneration -- the bottom 80\% of the 
			population regenerates their encoded strings at random.
		\vfill
		\item Cataclysmic regeneration -- the bottom 95\% of the
			population regenerates their encoded strings 
			as mutations of the top 5\%.
		\end{itemize}
		\vfill
		\vfill
		\vfill
	\end{itemize}
\newpage
\noindent
III. Results

        \begin{figure}[h]
        \centerline{\psfig{figure=4x4span.ps,height=3in}}
                \caption{\label{fig:4x4span}4 x 4 Spanning Tree}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=4x4ga.ps,height=3in}}
                \caption{\label{fig:4x4ga}4 x 4 Genetic Algorithm}
        \end{figure}
\newpage 
        \begin{figure}[h]
        \centerline{\psfig{figure=100ga.ps,height=6in}}
                \caption{\label{fig:100ga}100 point Genetic Algorithm}
        \end{figure}
\newpage
        \begin{figure}[h]
        \centerline{\psfig{figure=100exact.ps,height=6in}}
                \caption{\label{fig:100exact}100 point exact solution}
        \end{figure}
\newpage


        \begin{table}
        \begin{center}
        \begin{tabular}{|l|r|} \hline
        Probability of Crossover        & 0.95 \\ \hline
        Probability of Mutation         & 0.05 \\ \hline
        Population Size                 &  75 \\ \hline
        Generations                     &  100-200 \\ \hline
        \end{tabular}
        \end{center}
        \caption{Best Parameter Settings}
        {\label{tab:params}}
        \end{table}


        \begin{table}
        \begin{center}
        {\huge
        \begin{tabular}{|l|rr|rr|} \hline
        \multicolumn{5}{|c|}{GA solutions for test data sets.} \\
        \multicolumn{5}{|c|}{(Given as Tree length, \% of MST Length)}
\\
        \hline
        & \multicolumn{2}{c|}{16 point}
        & \multicolumn{2}{c|}{100 point} \\
        & \multicolumn{2}{c|}{Grid problem}
        & \multicolumn{2}{c|}{Random problem} \\ \hline
        MST Solution    & 3.00000 &  100\%  & 6.44869 &  100\% \\ \hline
       SMT Solution    & 2.73205 &  91\%   & 6.25546 &  97\% \\ \hline
        GA Solution     & 2.85757 &  95\%   & 6.37021 &  98.8\% \\
\hline
        \end{tabular}
        }
        \end{center}
        \caption{GA Solution Comparisons}
        {\label{tab:solution}}
        \end{table}


\clearpage
%\newpage
\noindent
IV. Conclusions and Future Work
	\begin{itemize}
	\vfill
	\item Fix the problems that we are having with our
        	Steiner Point generation
	\vfill
		\begin{itemize}
		\item The best (and probably the hardest) would be to
		treat the points as logical points in a tree structure,
		where they logically connect other vertices, but do not
		have a coordinate location until the length of the tree
		is calculated.
		\end{itemize}

	\vfill
	\item  Extend the GA to a parallel environment

	\vfill
	\item Extend the SMT problem to 3 dimensions
	\end{itemize}
\end{document}
