\documentstyle[twocolumn]{article}
\pagestyle{empty}
\setlength{\textwidth}{6.9in}
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.5pc}
\setlength{\topmargin}{-0.3in}
\setlength{\oddsidemargin}{-.3in}
\setlength{\parindent}{1pc}

\makeatletter
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip
 \abovedisplayskip \abovedisplayshortskip \z@
 plus3pt\belowdisplayshortskip 6pt plus3pt
 minus3pt\let\@listi\@listI}

\def\subsize{\@setsize\subsize{12pt}\xipt\xipt}

\def\section{\@startsection{section}{1}{\z@}{24pt plus 2 pt
 minus 2 pt} {12pt plus 2pt minus 2pt}{\large\bf}}

\def\subsection{\@startsection {subsection}{2}{\z@}{12pt
 plus 2pt minus 2pt}{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}
\bibliographystyle{plain}

% Macros for PostScript Figures:
\input psfig
\date{}

\title
{A Genetic Algorithm for the Steiner Minimal Tree Problem}


\author{\begin{tabular}[t]{c@{\extracolsep{8em}}c}
Joseph Jones & Frederick C. Harris, Jr. \\
Department of Computer Science & Department of Computer Science\\
University of Nevada & University of Nevada \\
Reno, NV~~ 89557  & Reno, NV~~ 89557 \\
jones@cs.unr.edu & fredh@cs.unr.edu
\end{tabular}}

\maketitle

\thispagestyle{empty}

\subsection*{\centering Abstract}
\vspace*{-3mm}


	We present a Genetic Algorithm to solve the Steiner Minimal
	Tree Problem. The Steiner Minimal Tree Problem is a network
	optimization problem in which we are able to add points to the
	network in order to minimize its length. The Genetic Algorithm
	searches for the number and location of  these new points.
	Preliminary results are promising.

{\bf keywords:} Genetic Algorithms, Steiner Minimal Tree

\section{Introduction.}

        Minimizing a network's length is one of the oldest
        optimization problems in mathematics and, consequently, it has
        been worked on by many of the leading mathematicians in
        history.  In the mid-seventeenth century a simple problem was
        posed:  Find the point $P$ that minimizes the sum of the
        distances from $P$ to each of three given points in the plane.
        Solutions to this problem were derived independently by Fermat,
        Torricelli and Cavalieri.  They all deduced that either $P$ is
        inside the triangle formed by the given points and that the
        angles at $P$ formed by the lines joining $P$ to the three
        points are all $120^{\circ}$, or $P$ is one of the three
        vertices and the angle at $P$ formed by the lines joining $P$
        to the other two points is greater than or equal to
        $120^{\circ}$.

        The method proposed by the mathematicians of the
        mid-seventeenth century for the three point problem is
        illustrated in Figure~\ref{fig:melzak}.  This method stated
        that in order to calculate the point $P$ given points A, B,
        and C, you first construct an equilateral triangle $(ACX)$
        using the longest edge between two of the points $(AC)$ such
        that the third $(B)$ lies outside the triangle.  A circle is
        circumscribed around the triangle, and a line is constructed
        from the third point $(B)$ to the far vertex of the triangle
        $(X)$.  The location of the point $(P)$ is the
        intersection of this line $(BX)$ with the circle.

        \begin{figure}
        \centerline{\psfig{figure=fig-melzak.ps,height=2in}}
                \caption{\label{fig:melzak}AP + CP = PX.}
        \end{figure}


        In the nineteenth century a mathematician at the University of
        Berlin, named Jakob Steiner, studied this problem and
        generalized it to include an arbitrarily large set of points in
        the plane.  This generalization created a star when $P$ was
        connected to all the given points in the plane, and is a
        geometric approach to the 2-dimensional center of mass
        problem.

        In 1934 K\"{o}ssler and Jarn\'{i}k generalized the network
        minimization problem even further~\cite{jk34:omgodb}:  Given
        $n$ points in the plane find the shortest possible connected
        network containing these points.  This generalized problem,
        however, did not become popular until the book, {\it What is
        Mathematics}, by Courant and Robbins~\cite{cr41:wim}, appeared
        in 1941. Courant and Robbins linked the name Steiner with this
        form of the problem proposed by K\"{o}ssler and Jarn\'{i}k, and
        it became known as the Steiner Minimal Tree problem.  The
        general solution to this problem allows multiple points to be
        added, each of which is called a Steiner Point, creating a tree
        instead of a star.

        Much is known about the exact solution to the Steiner Minimal
        Tree problem.  Those who wish to learn about some of the
        spin-off problems are invited to read the introductory article
        by Bern and Graham~\cite{bg89:tsnp}, the excellent survey paper
        on this problem by Hwang and Richards~\cite{hr92:survey}, or
        the recent volume in The Annals of Discrete Mathematics devoted
        completely to Steiner Tree problems~\cite{hrw:annals}.  Some of
        the basic pieces of information about the Steiner Minimal Tree
        problem that can be gleaned from these articles are: (i) the
        fact that all of the original $n$ points will be of degree 1,
        2, or 3, (ii) the Steiner Points are all of degree 3, (iii) any
        two edges meet at an angle of at least $120^{\circ}$ in the
        Steiner Minimal Tree, and (iv) at most $n-2$ Steiner Points
        will be added to the network.

	While the Steiner Minimal Tree (SMT) problem is itself quite 
	interesting, it also has a number of application areas. Some 
	of these include: Laying telephone cable between a number of 
	cities; laying pipe between points; connecting a number of 
	computers together using the least amount of cable necessary.

	The current algorithms in use for solving the SMT problem take
	a large amount of time to compute a non-trivial
	solution~\cite{harris:dissertation,harris:asoafsmt}. It is 
	for this reason that
	we have developed a Genetic Algorithm (GA) to solve the problem.
	The GA we developed has provided a great improvement in the
	time it takes for computation of SMTs, dropping the time from
	many hours to under 20 minutes.  We are able to produce an
	acceptable answer for the 100 point problem, where acceptable
	means a SMT of shorter length than the Minimal Spanning Tree
	over the same points.  For those readers interested in GAs,
	Goldberg \cite{GOLD89} and Davis \cite{DAVI91} are the important
	works in this field to read, while previous work in applying 
	GAs to different aspects of the Steiner Tree Problem are 
	presented in Hesser \cite{hms:oostuga} and Julstrom 
	\cite{Julstrom:agaftrsp}.

	In Section 2 we go into depth on the Genetic Algorithm we
	developed.  In Section 3 Results are presented.  Conclusions
	and Future Work are presented in Section 4.

\section{The Genetic Algorithm}

	A Genetic Algorithm is an algorithm based upon the process of
	natural selection and genetics. It combines survival of the
	fittest with random, but structured,
	information exchange among members of the population. There are
	four distinct points in which GAs differ from more traditional
	search techniques. These are:
	\begin{enumerate}
	\item They work with an encoding of the problem parameters, 
		not the parameters themselves.
	\item They search through a population of points, not a 
		single point.
	\item They use objective function information (payoff), not 
		derivatives or other secondary information.
	\item They use probabilistic transition rules, not deterministic.
	\end{enumerate}

	When using a GA, the parameters are usually encoded as a bit
	string. A GA begins with an instantiated population of
	individuals, in which each individual's encoded string is
	generated at random. The members of the population then undergo
	Reproduction, Crossover, and Mutation. It is these three
	processes that provide the strength of the GA as a search
	technique.

	Reproduction selects members of the current generation and
	mates them.  Selection is based on fitness of an individual,
	where fitness is a measure of how close each member of this
	population is to the correct solution. This provides the next
	generation with members that incorporate a better solution then
	the previous generation and is modeled after survival of the
	fittest. The members selected in this manner are called
	parents, and the new members of the next generation are called
	children

	Crossover mates the encodings of the parents to generate
	children. A traditional GA uses one-point crossover, where a
	point on the chromosome (the bit string representing the
	encoding) is selected at random and the parents swap their
	strings from the selected point to the end of the chromosome.
	This swapping of material models chromosome crossover in the
	nucleus of cells.


	Mutation provides for the generation of new information or the
	regeneration of possibly lost information due to selection.
	This process is modeled after radiation mutation of chromosomes
	in the cells nucleus~\cite{GOLD89}.

	In developing the GA for this problem, we made many design
	changes to the traditional GA. Specifically we changed the
	style of the encoding, altered the way crossover and mutation
	work and provided for population regeneration due to
	sub-optimal convergence.

    \paragraph{Encoding:}
	Our encoding consisted of an array of x and y coordinates
	representing the location of the Steiner Points and some extra
	flags used in Steiner Point generation and tree validity
	testing. Instead of crossing over at random bit positions, we
	decided to crossover the chromosomes at point boundaries. This
	provided us with the means of keeping known Steiner Points, as
	opposed to creating random non-Steiner points.

	Roulette wheel selection proved to be too random, causing the
	GA to not converge to any specific solution. For this reason we
	chose to use CHC selection with a probability of crossover (Pc)
	= 0.95 and a probability of mutation (Pm) = 0.05. These
	settings provided us with the best results.

    \paragraph{Crossover:}
	Simple one-point crossover proved to be a little too
	inefficient, so we decided to move to two-point crossover. The
	idea behind two-point crossover is that we select two points on
	the chromosome randomly and then swap the information between
	the two points. We selected this method to provide us with some
	control over locality problems concerning the Steiner Points.

    \paragraph{Mutation:}
	Mutation was another area in which modification was necessary.
	Since our encoding did not allow us to just mutate simple
	on/off bits, it was necessary to alter it. In our GA, mutation
	does two things:  1. If the chromosome is full, select a point
	at random and remove it.  2.  Generate a new point and add it
	to the chromosome.


    \paragraph{Population Regeneration:}
	Our first tests with the GA showed that we were unable to
	generate an exact solution. We realized that not as many
	different possible Steiner Points as we needed were being 
	generated. As an attempt to fix this problem, we implemented 
	two different population regeneration schemes, both based on 
	the length of population convergence. The two types of 
	regeneration are (1) Random regeneration and (2) Cataclysmic 
	regeneration. Random regeneration is when the bottom 80\% of 
	the population regenerates their encoded strings at random. 
	Cataclysmic regeneration is when the bottom 95\% of the population
	regenerates their encoded strings as mutations of the top 5\%.
	While random regeneration proved useful and will be kept as a
	viable tool, cataclysmic regeneration provided little or no
	help in generating an exact solution.

\section{Results}

	The parameters that we found to work the best are given in
	Table~\ref{tab:params}.  
	\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}
	We found these population size 
	settings by comparing the information provided by evaluating 
	the maximum performance while running this on a 4 x 4 Grid.
	The input and spanning tree for the 4 x 4 Grid are presented in
	Figure~\ref{fig:4x4span}, 
        \begin{figure}
        \centerline{\psfig{figure=4x4span.ps,height=3in}}
                \caption{\label{fig:4x4span}4 x 4 Spanning Tree}
        \end{figure}
	and the GA output is given in Figure~\ref{fig:4x4ga}.
        \begin{figure}
        \centerline{\psfig{figure=4x4ga.ps,height=3in}}
                \caption{\label{fig:4x4ga}4 x 4 Genetic Algorithm}
        \end{figure}
	We then used these settings to generate our solution to a
	100-point problem.  Our results are presented in
	Table~\ref{tab:solution}.  
	It is important to note that our GA results were computed from
	non-relaxed trees (the steienr points are not in the exact
	position, but the tree is structured properly).  This is due to
	the fact that in the crossover operations trees are combined
	and placement of points is not re-calculated.  Relaxation of
	the trees would provide an even larger decrease in length.
	\begin{table}[h]
	\begin{center}
	{\footnotesize
	\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}


	Figure~\ref{fig:100data} presents the 100 point input set 
	for the problem while Figures~\ref{fig:100ga} and 
	\ref{fig:100exact} show the output of the Genetic Algorithm
	for 100 points and the exact solution 
	for this 100 point problem.

        \begin{figure}
        \centerline{\psfig{figure=100data.ps,height=3in}}
                \caption{\label{fig:100data}100 point Input}
        \end{figure}
        \begin{figure}
        \centerline{\psfig{figure=100ga.ps,height=3in}}
                \caption{\label{fig:100ga}100 point Genetic Algorithm}
        \end{figure}
        \begin{figure}
        \centerline{\psfig{figure=100exact.ps,height=3in}}
                \caption{\label{fig:100exact}100 point exact solution}
        \end{figure}

	While looking at the information from the GA, we began to
	realize that it was usually generating sub-optimal solutions.
	We believe this is because we are not generating as many
	different Steiner Points as are necessary to find an exact
	solution. This is why we chose two-point crossover and
	population regeneration. Unfortunately these techniques
	provided only marginal performance improvement. We believe that
	the problem lies in how we generate Steiner Points, not in how
	the GA operators work. If this is true, we can gain
	considerably in run time by the elimination, or at least
	scaling back of, population regeneration.


\section{Conclusions and Future Work}

	While the solutions provided from our GA for the test data sets
	are not exact, We believe that our GA holds much
	promise for finding good solutions to the SMT problem. With
	more work and an improvement in the Steiner Point generation
	algorithm, we hope we can produce near exact solutions in the
	future.

	The future work for this problem extends in many areas.  First
	we want to try to fix the problems that we are having with our
	Steiner Point generation.  This could be done through a few
	different ways.  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.
	This would take care of the relaxation problem discussed
	earlier.  The second item of future work would be to extend the
	GA to a parallel environment, as was described
	in~\cite{zh96:codiopoga}, so that we can attack larger problems.
	The third direction for future work, which is probably the
	hardest, is to extend the SMT problem to 3 dimensions.  This 
	attack, while being the hardest, will probably yield some
	interresting communication networks for building construction,
	and other 3 dimensional spaces.


\baselineskip=12pt
\bibliography{/staff/fredh/papers/bibdir/xing,/staff/fredh/papers/bibdir/steiner,/staff/fredh/papers/bibdir/fredh}
\end{document}
