\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{\Large\bf Solving Quadratic Assignment Problems \\ With Parallel Genetic Algorithms} %\author{I. M. Author \\ %My Department\\ %My Institute \\ %My City, ST, Zip} %for two authors (type the following) %\author{\begin{tabular}[t]{c@{\extracolsep{8em}}c} %I. M. Author & U. R. Coauthor \\ %My Department & Coauthor Department\\ %My Institute & Coauthor Institute \\ %City, St ~~Zip & City, ST~~Zip %\end{tabular}} %\author{ \begin{tabular}[t]{c@{\extracolsep{8em}}c} % Jerri Hines & \\ % John T. Thorpe % \thanks{Current Address: Common Development Team, % AT\&T Global Information Solutions, % Greenville, SC 29615, \newline % John.Thorpe@ClemsonSC.ATTGIS.COM} % & Kenneth B. Winiecki, Jr. % \thanks{Current Address: Loral Aerosys, % NASA Goddard Space Flight Center % Greenbelt, MD 20771 % kwiniec@vlsi9.gsfc.nasa.gov} \\ % Department of Computer Science & % Department of Electrical Engineering \\ % Clemson University & Clemson University \\ % Clemson, South Carolina 29634 & Clemson, South Carolina 29634\\ % \\ % \multicolumn{2}{c}{Frederick C. Harris, Jr.}\\ % \multicolumn{2}{c}{Department of Computer Science}\\ % \multicolumn{2}{c}{University of Nevada}\\ % \multicolumn{2}{c}{Reno, Nevada 89557}\\ % \multicolumn{2}{c}{fredh@cs.unr.edu} %\end{tabular} %} \author{ \begin{tabular}[t]{c@{\extracolsep{8em}}c} Jerri Hines \\ John T. Thorpe \thanks{Current Address: Common Development Team, AT\&T Global Information Solutions, Greenville, SC 29615, \newline John.Thorpe@ClemsonSC.ATTGIS.COM} & Frederick C. Harris, Jr.\\ Department of Computer Science & Department of Computer Science\\ & University of Nevada\\ Kenneth B. Winiecki, Jr. \thanks{Current Address: Loral Aerosys, NASA Goddard Space Flight Center Greenbelt, MD 20771 kwiniec@vlsi9.gsfc.nasa.gov} & Reno, Nevada 89557 \\ Department of Electrical Engineering & fredh@cs.unr.edu \\ Clemson University \\ Clemson, South Carolina 29634 \\ \end{tabular} } \maketitle \thispagestyle{empty} \subsection*{\centering Abstract} \vspace*{-3mm} Parallel processing has been valuable for improving the performance of many algorithms and is attractive for solving intractable problems. Traditionally, exhaustive search techniques have been used to find solutions to NP-complete problems; however, parallelization of exhaustive search algorithms can provide only linear speedup, which is typically of little use since problem complexity increases exponentially with problem size. Genetic algorithms can help to provide satisfactory results to such problems. This paper presents a genetic algorithm that uses parallel processing to solve the quadratic assignment problem. {\bf keywords:} Quadratic Assignment Problem, Parallel Genetic Algorithms %\parindent=1em %\baselineskip=24pt \section{Introduction} \label{intro} Parallel processing has proven to be valuable for increasing the performance of various algorithms. Intractable problems traditionally solved by exhaustive search techniques seem to resist the speedup typically produced by parallelization. Algorithms for these problems, when run in parallel, typically give a speedup only directly proportional to the number of processors working in concert on the problem. This paper presents an alternative to traditional exhaustive search methods using a variation on genetic algorithms~\cite{DAVI91,GOLD89}. In the early 1970's John Holland at the University of Michigan developed a heuristic search technique he termed a {\it genetic} {\it algorithm}~\cite{GOLD89}. Because they are heuristic techniques, genetic algorithms are not guaranteed to find optimal solutions to complex systems, but rather to find ``satisfactory'' ones. A satisfactory result is defined by the problem and by how close to the optimal solution the user deems acceptable. It is hoped that using genetic algorithms in parallel can produce acceptable results in a ``reasonable'' amount of time, as good as or better than exhaustive search techniques can in that same time. NP-complete problems are a class of decision problems that are considered intractable; i.e., solutions to these problems probably will not be found with a polynomial time algorithm. Although it has not been proven whether or not NP-complete problems are truly intractable, it appears that a major breakthrough is necessary to solve them in polynomial time. The quadratic assignment problem has been classified as an NP-complete problem that is a transformation of the HAMILTONIAN CIRCUIT problem~\cite{GARE82}. For a more complete overview of NP-completeness and for a list of known NP-completeness problems see~\cite{GARE82}. For more work on NP-Complete problems see Johnson's series of {\it NP-Completeness Columns}~\cite{JOHN82}. The purpose of this paper is to demonstrate the effectiveness of using genetic algorithms along with parallel processing to obtain good solutions for large or intractable problems. The problem chosen to demonstrate this effectiveness is the quadratic assignment problem. Simply stated this problem involves the placement of $m$ production plants at $n$ sites so as to minimize transportation costs between them. In Section \ref{background} the backgrounds of the quadratic assignment problem and genetic algorithms are presented. Section~\ref{method} explains the heuristic used to solve the problem. Results and conclusions are presented in Section~\ref{results}, and future work is presented in Section~\ref{future}. \section{Background} \label{background} \subsection*{Quadratic Assignment Problem} The problem chosen is known as the Quadratic Assignment Problem (QAP). Consider the problem of placing each of $m$ plants at one of $n$ possible sites such that the total cost of transporting materials from one site to another is minimized. Each plant must be placed at some site, and at most one plant may be placed at a single site. Let $d_{i,j}$ be the number of items to be transported from site $i$ to site $j$, let $c_{i,j}$ be the cost of transporting a single item from site $i$ to site $j$, and let \[ A=(\pi(1),\pi(2),\ldots,\pi(m)) \] be a mapping of plants to sites where $1 \leq \pi(i) \leq n$ is the site at which plant $i$ is located. 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. The following example is taken from Horowitz and Sahni~\cite{Horowitz}. Assume two plants ($m=2$) and three possible sites ($n=3$). Also assume: \[ \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) \] and \[ \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) \] 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} \] \subsection*{Genetic Algorithms} Genetic algorithms were first developed by John Holland at the University of Michigan in the early 1970's. Holland was interested in how an algorithm could simulate natural selection. The goals of Holland's research included explaining the adaptive processes of natural systems and then designing artificial systems software which would retain the important mechanisms of natural selection~\cite{GOLD89}. Thus, the power of genetic algorithms should lie in their robustness, or ability to adapt, just as in natural systems. Genetic algorithms are heuristic search algorithms. Thus, the goal of a genetic algorithm is not necessarily to find the optimal solution to a complex system, but to produce a ``satisfactory'' one. Random choice is used to guide a genetic algorithm as it searches. As a genetic algorithm iterates, better solutions may be discovered. The structure of a genetic algorithm is based on natural selection. First, an initial population of feasible solutions is randomly generated. The initial population consists of ``chromosomes,'' encoded representations of solutions. ``Selection'' takes place between members of the population, and a ``child'' is formed from a combination of the ``parent'' chromosomes. For each new child an evaluation function is used to determine the ``fitness'' of that child. Whether or not the child becomes a member of the population depends on its fitness value. Each new child chromosome is compared against the worst member of the population, and the better one is kept in the population. By producing new generations in this manner, the population improves and the best member of the final population is the solution returned by the algorithm. A chromosome is traditionally a binary string. According to Goldberg~\cite{GOLD89}, genetic algorithms should be blind to the application; that is, the genetic algorithm should have no information as to what the bit string represents. Davis~\cite{DAVI91}, on the other hand, suggests that close inspection of the encoding can give clues as to what makes a good solution ``good'' and what makes a bad solution ``bad'' and can improve the quality of the search by including this information in the genetic algorithm. Since they are based on genetics, major elements of genetic algorithms include selection, recombination and mutation. Selection is the process of choosing parent chromosomes which will be recombined to form the next generation. The choice of parent chromosomes can be completely random but is usually biased in some manner so that better chromosomes are more likely to be used as parents. Two popular biased random number generators used with genetic algorithms are linear bias and roulette wheel. Recombination is the process of taking the parent chromosomes and forming a child chromosome. Simple methods for recombination include one-point crossover and two-point crossover. In these methods a random number is generated to correspond with one (or two) positions in the encoded parent solutions, and then the portions of the parent chromosomes around these positions are switched to form a child chromosome. The one- and two-point crossover methods of recombination require no knowledge as to what makes a solution good or bad. %Mutation is necessary in a genetic algorithm to prevent %the non-use of some potentially useful genetic %material and can guide the search in new directions. Mutation is necessary in a genetic algorithm to prevent the some potentially useful genetic material from being ignored and can guide the search in new directions. Mutation occurs in a genetic algorithm at the time of recombination. 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. Another feature of natural selection which is simulated in a genetic algorithm is survival of the fittest, achieved through the use of an evaluation function. When a child chromosome is evaluated for fitness, its survival, in essence, is being determined. If the child's fitness is not good enough for it to be inserted into the population, then the child does not ``survive''. The evaluation function used depends upon the particular problem to which the genetic algorithm is being applied. A genetic algorithm stops when it reaches convergence or when it has run for a predetermined number of iterations. Some definitions of convergence could involve having all identical solutions in the population, having all fitness values equal in the population, or having all fitness values within a certain range of each other. When convergence has occurred or when the predetermined number of iterations has been reached, the best solution is returned from the final population. \section{Method} \label{method} Why use genetic algorithms implemented in parallel to find solutions to the quadratic assignment problem? An initial attempt might be to use an exhaustive search method to place plants at various cities and then evaluate the resulting configuration. For large problem sizes (10 or more plants), this approach is obviously time consuming and is not guaranteed to produce a satisfactory result within a reasonable amount of time. An alternative to the exhaustive search is a heuristic such as a genetic algorithm. The premise of the genetic algorithm is that by generating a large number of solutions, or population, and continually recombining the solutions, a satisfactory result will eventually be produced through ``survival of the fittest'' as ``better'' results replace ``worse'' results. A genetic algorithm working on a single processor may produce good results, but if multiple versions of the algorithm were to operate in parallel in some {\it cooperative fashion}, it is likely that the concurrent version would produce even better results than the single processor implementation. The algorithm used for the quadratic assignment problem is basically a genetic algorithm with some modifications that enhance its use on a parallel processing system. For this experiment four nodes of a parallel processing machine (in this case an iPSC/2) are allocated to run the genetic algorithms. Each node generates its own initial population and begins executing the genetic algorithm. Each iteration of the genetic algorithm produces six children to evaluate and possibly insert into the node's population. A ``mutant'' is generated periodically and inserted into the population. Mutation is a technique to help prevent stagnation of the population. Once the genetic algorithm meets one of its convergence criteria (time limit, number of iterations, difference in the cost between the best and the worst solutions), the algorithm halts and broadcasts its results to the host program. If all nodes have converged to the same cost, the host stops and reports the results. As previously noted, the algorithm used does not follow the traditional approach described by Goldberg~\cite{GOLD89} in which the {\it entire} population is replaced at each iteration. Instead, a combination of Davis' and Goldberg's approaches was used in which each genetic algorithm uses a Davis-like approach to insert a few new members into the population~\cite{DAVI91}. There is no strategy involved in creating initial populations. The plants are randomly placed at the sites and the cost of each configuration is determined. After the initial population is generated, the genetic algorithm selects three sets of parent ``chromosomes'' to recombine. Two set are chosen via a simple linear bias, and the other is chosen from a normal distribution of the best ten percent (10\%) of the population. The reason for this selection method is that using the ``best'' parent for every generation was found to cause the population to converge to local ``best'' solutions rather than generating better solutions. In other words, the population tended to be dominated by variations on the best parent. Genetic algorithms were originally designed for use on single-processor machines. To take advantage of parallel processing, a variation on traditional genetic algorithms is in order. By allowing some sort of ``cross-pollination'' of chromosomes between genetic algorithms operating in parallel, information can be shared, and it is hoped that the interaction will improve performance of the genetic algorithms. This modification is logically consistent and exists in ``real-world'' genetics. A pollination rate $P$ is set as a parameter to the program, and each genetic algorithm sends a solution to the host program once every $P$ iterations. The host then chooses the best solution and broadcasts it back to all the nodes to use in their recombination. This method of cross-pollination has provided exceptionally better results then simply running four genetic algorithms independently, an observation made by the authors in preliminary work. One additional note: when cross-pollination occurs too frequently, the populations tend to converge very quickly, and rarely do they produce a satisfactory result. The recombination technique used in this work is based on uniform order-based crossover presented by Davis~\cite{DAVI91}. According to this recombination, a chromosome is a bit string that represents the contribution of the parents to a child. A one in the bit string indicates that the vertex corresponding to that bit index will contribute to the construction of child 1, and a zero indicates that the vertex will contribute to child 2. This bit string is generated randomly for each generation with parent 1 receiving the bit string and parent 2 receiving its complement. Hence, child 1 is composed of vertices marked with ones and child 2 is made of vertices marked with zeroes. This type of chromosome recombination is illustrated in Figure \ref{recom}. This bit string is then used to determine the six children (two from each pairing of the three parents). These children are then evaluated by the cost function (our fitness criteria) and inserted into the population if the value returned is better than %that of the worst member. \begin{figure} \begin{center} \input{recom} \end{center} \caption{Recombination of Chromosomes} \label{recom} \end{figure} In prior versions of this program, convergence was based upon three criteria: a 15 minute time limit, a maximum number of generations, and the difference between the best and the worst solutions in the population. The major change that was made to the parallel version of this algorithm (beside cross-pollination) was the addition of a ``second chance.'' Based upon the performance of previous versions we decided that better results could be produced if we took the top ten members of a converged population and used them as members of a completely new population. This new population was then allowed to converge under the same criteria as the original population. This second-chance scheme is then repeated until one of the original convergence criteria is met. \section{Results and Conclusions} \label{results} The results shown in the following tables represent the first time the convergent cost was produced. The actual running time was, on average, about 10\% longer than when the best result was first produced. The best result produced by the algorithm is indicated by a \verb+<=+ in the right margin. Three %different problem sizes were tried: 15, 20 and 30 points; their %results are presented in Table~\ref{table15}, %Table~\ref{table20}, and Table~\ref{table30} respectively. different problem sizes were tried: 15, 20 and 30 points. The results for the two larger problems are presented in Table~\ref{table20} and Table~\ref{table30} respectively. The genetic algorithm implemented to address the quadratic assignment problem produced results that were on average good, but not perfect. This finding is consistent with the processes that genetic algorithms attempt to model, i.e. ``success begets success'' but not necessarily perfection. Therefore, the implementation itself is a success. The implementation exploited the parallelism offered by the MIMD distributed-memory message-passing machine (iPSC/2 Hypercube) in the forms of cross-pollination, second-chance, and concurrent effort (as previously described). It produced consistently better results than the earlier non-parallel implementation. Also, the value of cross-pollination in achieving better results was not conclusive (too much was bad, but what amount is too little?). %\begin{table}[t] %%\scriptsize %\footnotesize %\begin{center} %\input{table15} %\end{center} %\normalsize %\caption{Problem Size 15} % \label{table15} %\end{table} \begin{table}[t] %\scriptsize \footnotesize \begin{center} \input{table20} \end{center} \normalsize \caption{Problem Size 20} \label{table20} \end{table} \begin{table} %\scriptsize \footnotesize \begin{center} \input{table30} \end{center} \normalsize \caption{Problem Size 30} \label{table30} \end{table} The marriage of parallel processing and genetic algorithms seems to be reasonably effective for obtaining results for intractable problems. The method presented is somewhat crude; however, with refinement it appears to have the potential of becoming an even more valuable problem-solving heuristic. As there was no comparison between the presented algorithm and an equivalent exhaustive search technique, few, if any, conclusions can be made about the superiority of one method over the other. The performance of a traditional exhaustive search for an optimal solution is known to have a speedup linearly proportional to the number of processors working in concert on the problem. Genetic algorithms do not guarantee optimal solution and so do not provide speedup (in the technical sense of the word); however, they can provide satisfactory solutions in a short period of time, so the results generated by this implementation indicate that the genetic algorithm can be a valuable search tool. % It is essential to remember the nature of genetic algorithms % when considering their application. If a strictly optimum % solution to a problem is required, genetic algorithms should % not be used; they are not exhaustive, and thus can not % guarantee such a solution. Also, if the representation of a % solution contains too little information about its relative % fitness, the concept of ``begetting success' has no relevance, % so genetic algorithms can not perform better than pure random % chance. If, however, a ``reasonably good'' solution is all % that is desired, and the form of the solution carries with it % indications of its fitness, then the use of genetic algorithms % is appropriate. For such applications, genetic algorithms have % the potential to produce significantly better results in % significantly less time than either exhaustive or random % methods. Indeed, those potentials were realized with the % genetic algorithm implementation as compared to the % previously-implemented ``brute-force' exhaustive search. \section{Future Work} \label{future} As with any project, extensions and modifications can be made to increase utility and/or performance, yet a further, and perhaps more significant, experiment would be to investigate and make use of the general characteristics of ``good'' solutions. For instance, the results produced by the program might have distinct characteristics which could be exploited in generating the initial population(s). Research into the representation of the solution should also be performed. A genetic algorithm is only as good as its solution representation, and it is not clear that the one chosen for this implementation carried as much fitness information as feasible. On the other hand, a representation with more fitness information may be unwieldy in some way. It is thus likely that a compromise should be investigated, and it is possible that the one used herein is the best one available. %\quad \baselineskip=12pt \parindent=0pt \bibliography{/users2/staff/fredh/papers/bibdir/xing} \end{document}