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

\begin{document}
\bibliographystyle{plain}

% Macros for PostScript Figures:
\input psfig

\begin{center}

{\Huge\bf Solving \\

\vspace{0.05in}

	Quadratic Assignment Problems \\

\vspace{0.15in}

	With Parallel Genetic Algorithms}

\vspace{0.2in}

{\LARGE
	Jerri Hines \\ 
	John T. Thorpe
		\footnote{Current Address: Common Development Team, 
		AT\&T Global Information Solutions, 
		Greenville, SC  29615, \newline
		John.Thorpe@ClemsonSC.ATTGIS.COM} \\
	Department of Computer Science \\
	Clemson University 	\\
	Clemson, South Carolina 29634 \\

\vspace{0.2in}

	Kenneth B. Winiecki, Jr. 
		\footnote{Current Address: Loral Aerosys,
		NASA Goddard Space Flight Center
		Greenbelt, MD  20771
		kwiniec@vlsi9.gsfc.nasa.gov} \\
	Department of Electrical Engineering \\
	Clemson University \\
	Clemson, South Carolina 29634\\
	
\vspace{0.2in}

	Frederick C. Harris, Jr.\\
	Department of Computer Science\\
	University of Nevada\\
	Reno, Nevada 89557\\
	fredh@cs.unr.edu
}
\end{center}


\newpage

\huge
1. Quadratic Assignment Problem (QAP)


	\begin{itemize}
	\item General Description
		\begin{itemize}
		\item Given:
			\begin{itemize}
			\item $m$ plants.
			\item $n$ possible sites.
			\end{itemize}

		\vspace{0.2in}

		\item Place the plants at the sites.

		\vspace{0.2in}

		\item Goal: minimize the total cost of
			transporting materials from one site to 
			another 

		\vspace{0.2in}

		\item Restrictions:
			\begin{itemize} 
			\item Each plant must be placed.  
			\item At most one plant per site.
			\end{itemize} 

		\end{itemize}

\newpage
	\item Specific Information

		\begin{itemize}
		\item Other info:
			\begin{itemize}
			\item $d_{i,j}$ = the number of items to be 
				transported from site $i$ to site $j$,
			\item $c_{i,j}$ = the cost of transporting a 
				single item from site $i$ to site $j$
			\end{itemize}

		\vspace{0.2in}

		\item Produce
			\begin{itemize}
			\item  $A=(\pi(1),\pi(2),\ldots,\pi(m))$ 
				 -- a mapping of plants to sites where 
				$1 \leq \pi(i) \leq n$ is the site at 
				which plant $i$ is located.  
			\end{itemize}

		\vspace{0.2in}

		\item The objective is to find a mapping $A$ such 
		that the cost 
		\[ F(A) =
		\sum_{i=1}^{m} \sum_{j=1}^{m}(d_{i,j}c_{\pi(i),\pi(j)})
		\] is minimized.

		\end{itemize}


\newpage
	\item Example:~\cite{Horowitz}.  

		\begin{itemize}
		\item Two plants ($m=2$) 
		\item Three possible sites ($n=3$).  
		\item Number of Items Transported 
			\[ \left(
			\begin{array}{cc}
			d_{1,1} & d_{1,2} \\
			d_{2,1} & d_{2,2}
			\end{array}
			\right)
			= 
			\left(
			\begin{array}{rr}
			0	& 	4 \\
			10	& 	0
			\end{array}
			\right)
			\]

		\item Cost to transport 
			\[ \left(
			\begin{array}{ccc}
			c_{1,1} & c_{1,2} & c_{1,3} \\
			c_{2,1} & c_{2,2} & c_{2,3}\\
			c_{3,1} & c_{3,2} & c_{3,3}
			\end{array}
			\right)
			= 
			\left(
			\begin{array}{rrr}
			0	& 	9 	& 3\\
			5	& 	0 	& 10\\
			2	& 	6	& 0
			\end{array}
			\right)
			\]
		\end{itemize}
		Sample placement of the plants at sites and their
		corresponding costs are shown in the table below.
		The third row represents the optimal solution.
		\[
		\begin{array}{|c|c|c|}\hline
		\pi(1)	& \pi(2)	& F \\\hline \hline
		1 & 2	& 9\times 4 + 5 \times 10 = 86\\
		3 & 1	& 2\times 4 + 3 \times 10 = 38\\
		1 & 3	& 3\times 4 + 2 \times 10 = 32 \\\hline
		\end{array}
		\]

		\vspace{0.2in}

	\item {\bf Note:}  This problem is NP-Complete~\cite{GARE82}.
	\end{itemize}

\newpage
2. Genetic Algorithms
	\begin{itemize}
	\item History
		\begin{itemize}
		\item Developed by John Holland in the early 1970's 
			at the University of Michigan.
		\item His Goals:
			\begin{itemize}
			\item Explain the adaptive process of natural
				systems.
			\item Design artificial systems software which
				would retain the important mechanisms
				of natural selection~\cite{GOLD89}.
			\end{itemize}
		\end{itemize}

		\vspace{0.2in}

	\item Overview:
		\begin{itemize}
		\item Genetic Algorithms are heuristic search algorithms.
		\item Random choice is used as to guide a Genetic
			Algorithm as it searches.
		\item As a genetic algorithm iterates, better solutions 
			may be discovered.
		\end{itemize}
\newpage
	\item Structure:
		\begin{itemize}
		\item First, an initial population of feasible 
			solutions is randomly generated.  
		\vspace{0.2in}
		\item {\bf Selection} takes place between members of 
			the population, and a {\bf child} is formed 
			from a combination of the {\bf parent} 
			chromosomes.  
		\vspace{0.2in}
		\item An evaluation function is used to determine the
			{\bf fitness} of that child.  
		\vspace{0.2in}
		\item Each new child chromosome is compared against 
			the worst member of the population, and the
			better one is kept.
		\vspace{0.2in}
		\item Mutation can take place by randomly
			generating a child chromosome or by randomly
			changing part of the encoding of a child
			chromosome.  
		%	As in nature, mutation generally
		%	occurs only a small portion of the time.

		\end{itemize}

		\vspace{0.2in}

		By iterating in this manner, the population improves and
		the best member of the final population is the solution
		returned by the algorithm.

	\end{itemize}
\newpage
3. Parallel Genetic Algorithms.
	\begin{itemize}
	\item {\bf Why:}  \\
		If a single Genetic Algorithm produces good results,
		multiple versions operating in parallel in some {\it
		cooperative fashion} should produce better results

	\vspace{0.2in}

	\item {\bf How:}
		\begin{itemize}
		\item A parallel machine 
			\begin{itemize}
			\item iPSC/2.
			\item Host -- Node communication architecture.
			\end{itemize}

		\vspace{0.2in}

		\item {\bf Cross-Pollination}
			\begin{itemize}
			\item Each $P$ iterations every processor 
				sends the host its best solution.
			\item The best of those is broadcast to all
				processors.
			\item That solution is placed into the
				population.
			\end{itemize}

		\vspace{0.2in}

		\item {\bf Second-Chance Restart}
			\begin{itemize}
			\item {\bf When:} If one processor converges 
				before the time limit or generations 
				limit.
			\item {\bf How:} A Completely New population 
				is generated and the top 10 members 
				of the previous population are inserted
				into it.
			\end{itemize}

		\end{itemize}
	\end{itemize}
\newpage
4. Results.

	\begin{itemize}
	\item We have Data Tables for problems of size 15, 20, and 30.

	\vspace{0.2in}

	\item The results wer on average ``good'', but not perfect.
		This is consistent with a heuristic algorithm.

	\vspace{0.2in}

	\item This produced {\bf Consistently} better results than the
		non-parallel version.

	\vspace{0.2in}

	\item Therefore, we must say it was a success.

	\newpage
	\item Problem Size 15
		\begin{table}[h]
		\Large
		\begin{center}
		\input{table15}
		\end{center}
		\normalsize
		\caption{Problem Size 15}
			\label{table15}
		\end{table}

	\newpage
	\item Problem Size 20
		\begin{table}[h]
		\Large
		\begin{center}
		\input{table20}
		\end{center}
		\normalsize
		\caption{Problem Size 20}
			\label{table20}
		\end{table}

	\newpage
	\item Problem Size 30
		\begin{table}[h]
		\Large
		\begin{center}
		\input{table30}
		\end{center}
		\normalsize
		\caption{Problem Size 30}
			\label{table30}
		\end{table}

	\end{itemize}
\newpage
5. Future Work.
	
	\vspace{0.2in}

	\begin{itemize}
	\item What is the best Cross-Pollination rate?

	\vspace{0.2in}

	\item Should only the best member be cross-pollinated, or should
		some other criteria be used (random, \ldots)?

	\vspace{0.2in}

	\item Should Cross-Pollination from one Gene Pool go to all Gene
		Pools or just to ``neighbors''?

	\vspace{0.2in}

	\item How good is {\bf Second-Chance Restart}?
	\end{itemize}

\newpage
%\quad
\baselineskip=12pt
\parindent=0pt
\bibliography{/staff/fredh/papers/bibdir/xing}
\end{document}