%\documentstyle[11pt,titlepage]{article}
%\documentstyle[psfig,verbatim,sty/tpage,sty/here]{report} 
\documentstyle[psfig,epsf,verbatim,/home/bsmith/petsc/docs/tex/sty/tpage]{report} 
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-.6in}

% \textwidth=6.0in
% \textheight=9.0in
% \hoffset=-0.5in
% \voffset=-1.0in
% \parskip=.1in
% \pagestyle{empty}

\newcommand{\pga}{PGAPack}
% \newcommand{\v}{1.0}
\newcommand{\findex}[1]{\index{FUNCTION #1}}
\newcommand{\sindex}[1]{\index{#1}}
% \newcommand{\a}{\findex{#1}{\tt #1}}
\makeindex

% Defines the environment where design issues are discussed. In the manual
% version of this report, these regions are ignored.
\def\design{\medskip \noindent Design Issue:\begin{em}}
\def\enddesign{\end{em} \medskip}
% Manual version:
% \def\design{\comment}
% \def\enddesign{\endcomment}

% Print DRAFT in large letters across every page
% \special{!userdict begin /bop-hook{gsave 200 70 translate
% 65 rotate /Times-Roman findfont 216 scalefont setfont
% 0 0 moveto 0.95 setgray (DRAFT) show grestore}def end}

\begin{document}

\ANLTitle{Users Guide to the PGAPack Parallel \\Genetic Algorithm
Library}
{\em David Levine\vspace{.1in}
\\Mathematics and Computer Science Division}{-95/18}{January 31, 1996}


\date{\today}

\newpage

\noindent {\bf Acknowledgments}

Much of the code in \pga\ was originally developed as part of the author's
Ph.D. thesis.  Significant contributions to the development of
\pga\ were made by Philip Hallstrom, David Noelle, Greg Reeder, and Brian
Walenz, participants in Argonne's Science and Engineering Research Semester
program.

Many aspects of \pga---including the user interface, choice of some data
structures, and design of Fortran wrappers---were strongly influenced by the
design of the {\tt PETSc} (Portable and Extensible Tools for Scientific
Computing) library.
% \cite{GrSm94}
I thank Bill Gropp, Lois Curfman McInnes, and Barry Smith
for many helpful discussions.  The code in \pga\ for parsing command line
arguments is a modified version of that used in the {\tt p4} system
developed by Ralph Butler and  Rusty Lusk.

\newpage

% \begin{center}
% \large{\bf COPYRIGHT}
% \end{center}
% 
% \begin{verbatim}
% ************************************************************************
% 			COPYRIGHT NOTIFICATION
% ************************************************************************
%                (C) COPYRIGHT 1995 UNIVERSITY OF CHICAGO
% ************************************************************************
% 
% This program contains material protectable under copyright laws of the
% United States.  Permission is hereby granted to use, reproduce, prepare 
% derivative works, and to redistribute to others, so long as this original
% copyright notice is retained.  This software was authored by
% 
% D. Levine
% Mathematics and Computer Science Division
% Argonne National Laboratory
% Argonne IL 60439
% levine@mcs.anl.gov
% (708) 252-6735
% (708) 252-5986 (FAX)
% 
% with programming assistance of participants in the Laboratory's SERS program.
% 
% ************************************************************************
% 			      DISCLAIMER
% ************************************************************************
% THIS PROGRAM WAS PREPARED, IN PART, AS AN ACCOUNT OF WORK SPONSORED
% BY AN AGENCY OF THE UNITED STATES GOVERNMENT.  NEITHER THE UNITED STATES
% GOVERNMENT, NOR THE UNIVERSITY OF CHICAGO, NOR ANY OF THEIR EMPLOYEES OR
% OFFICERS, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
% LIABILITY OR RESPONSIBILITY FOR THE ACCURACY, COMPLETENESS, OR USEFULNESS
% OF ANY INFORMATION, APPARATUS, PRODUCT, OR PROCESS DISCLOSED, OR REPRESENTS
% THAT ITS USE WOULD NOT INFRINGE PRIVATELY OWNED RIGHTS.
% \end{verbatim}



\pagenumbering{roman}
\setcounter{page}{3}
\tableofcontents
\clearpage
\pagenumbering{arabic}

% \begin{document}
% 
% \def\code#1{{\tt \\ #1}\null}
% 
% \vspace*{-.5in}
% 
% \thispagestyle{empty}
% \parindent=3.5in
% \parskip=.002in
% 
% Distribution Category:
% 
% Mathematics and
% 
% \parindent=3.7in
% 
% Computer Science (UC-405)
% 
% \begin{center}
% 
% \vspace{.1in}
% {\large
% ARGONNE NATIONAL LABORATORY\\
% }
% 9700 South Cass Avenue \\
% Argonne, IL 60439
% \end{center}
% 
% \vspace{.06in}
% \begin{center}
% {\bf
% -----------------\\
% ANL-95/DRAFT \\
% -----------------\\
% }
% \end{center}
% \vskip .75 in
% \begin{center}
% {\large\bf
% User's Guide to the PGAPack \\ [1ex]
% Parallel Genetic Algorithm Library}
% \end{center}
% \vskip .1 in
% \begin{center}
% by
% \end{center}
% \vskip .1in
% \begin{center}
% {\large\em David Levine}
% 
% \vspace{.6in}
% {\large Mathematics and Computer Science Division}
% \vskip 1.2 in
% May 1994
% \end{center}
% \vfill
% {\small 
% This work was supported by the Mathematical, Information, and Computational
% Sciences Division subprogram of the Office of Computational and Technology
% Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.}
% 
% \parindent=.25in
% \parskip=8pt
% 
% \clearpage
% \pagestyle{headings}
% \pagenumbering{roman}
% \tableofcontents
% 
% \newpage
% 
% 
% \pagenumbering{arabic}
% \clearpage

\setcounter{chapter}{0}
\addtocounter{chapter}{-1}
%*****************************************************************************
\chapter{Quick Start}\label{chp:quick-start}
%*****************************************************************************

If you wish to get started by just typing a few lines and running an example,
this section is for you.  We assume you have {\tt ftp}ed the compressed tar
file {\tt pgapack.tar.Z} containing the distribution into {\tt
/home/username}.  To build a sequential version of \pga\ for a Sun
SparcStation in {\tt /usr/local/pga} and run a test example, type
\begin{enumerate}
\item {\tt uncompress /home/username/pgapack.tar.Z}
\item {\tt mkdir /usr/local/pga}
\item {\tt cd /usr/local/pga}
\item {\tt tar xvf /home/username/pgapack.tar}
\item {\tt configure -arch sun4}
\item {\tt make install}
\item {\tt /usr/local/pga/examples/c/maxbit}
\end{enumerate}

To build an optimized (no built-in debugging capabilities), parallel
version of \pga\ for an IBM SP parallel computer, using an MPI implementation
with include files in {\tt /usr/local/mpi/include} and library in {\tt
/usr/local/mpi/lib}, and run a test example using four processes, type
\begin{enumerate}
\item {\tt uncompress /home/username/pgapack.tar.Z}
\item {\tt mkdir /usr/local/pga}
\item {\tt cd /usr/local/pga}
\item {\tt tar xvf /home/username/pgapack.tar}
\item {\tt configure -arch rs6000 \verb+\+ } \\
\hspace{.5in}
{\tt -mpiinc /usr/local/mpi/include -mpilib /usr/local/mpi/lib/libmpi.a}
\item {\tt make install}
\item {\tt mpirun -np 4 /usr/local/pga/examples/c/maxbit}
\end{enumerate}

Step 7, the execution step, is completely dependent on the MPI
implementation.  This  example uses the {\tt mpirun} script that is
distributed with the {\tt MPICH} implementation \cite{mpich-web-page}.
Other MPI implementations may have other ways to specify the number of
processes to use.  

More details on the installation process and various options are given in
Chapter~\ref{chp:install}.  Chapter~\ref{chp:examples} (example problems) and
Sections~\ref{sec:big-picture} (required functions) and~\ref{sec:evaluation}
(string evaluation and fitness) should be read next.



%*****************************************************************************
%*****************************************************************************
\part{Getting Started}\label{part:started}
%*****************************************************************************
%*****************************************************************************


%*****************************************************************************
\chapter{Introduction}\label{chp:intro}
%*****************************************************************************

\pga\ is a parallel genetic algorithm library that is intended to provide most
capabilities desired in a genetic algorithm package, in an integrated,
seamless, and portable manner.  Key features of \pga\ are as follows:
\begin{itemize}
\item Ability to be called from Fortran or C.
\item Executable on uniprocessors, multiprocessors, multicomputers, and workstation
networks.
\item Binary-, integer-, real-, and character-valued native data types.
\item Object-oriented data structure neutral design. 
\item Parameterized population replacement.
\item Multiple choices for selection, crossover, and mutation operators.
\item Easy integration of hill-climbing heuristics. 
\item Easy-to-use  interface for novice and application users.
\item Multiple levels of access for expert users.
\item Full extensibility to support custom operators and new data types.
\item Extensive debugging facilities.
\item Large set of example problems.
\end{itemize}

% This users guide is organized as follows.
% Chapter~\ref{chp:install} discusses the installation process, and
% Chapter~\ref{chp:examples} presents some simple examples that can be
% mimicked for a quick start.
% Part~\ref{part:userguide} contains the bulk of the material.  
% Chapter~\ref{chp:structure} discusses the  structure of \pga.
% Chapter~\ref{chp:functionality} describes basic usage of \pga,
% Chapter~\ref{chp:explicit} explicit usage,
% Chapter~\ref{chp:custom1} custom usage with a native data type, and
% Chapter~\ref{chp:new-data} custom usage with new data types.
% Chapter~\ref{chp:hill-climbing} discusses hybridizing a hill-climbing
% heuristic with the genetic algorithm.
% Chapter~\ref{chp:parallel} discusses parallel aspects of \pga.
% Chapter~\ref{chp:fortran} discusses  the Fortran interface to
% \pga. 
% %Chapter~\ref{chp:specific-machines} contains specific comments about running
% % \pga\ on specific machines.
% Chapter~\ref{chp:debug} discusses debugging tools in \pga.
% Chapter~\ref{chp:problems} discusses some common problems.

%*****************************************************************************
\chapter{Installation}\label{chp:install}
%*****************************************************************************

%*****************************************************************************
\section{Obtaining \pga}\label{sec:obtain}
%*****************************************************************************

The complete distribution of \pga\ is available by anonymous ftp from {\tt
ftp.mcs.anl.gov} in the file {\tt pub/pgapack/pgapack.tar.Z}. The distribution
contains all source code, installation instructions, this users guide, and a
collection of examples in C and Fortran.  The current release of \pga\ is 1.0.
You can check which version of \pga\ you have by running any C language \pga\
program with the command-line option {\tt -pgaversion}.


%*****************************************************************************
\section{Requirements}\label{sec:require}
%*****************************************************************************

To compile \pga, you {\em must} have an ANSI C compiler that includes a full
implementation of the Standard C library and related header files.  
If you wish only to build a {\em sequential} version of \pga\ this is all that
is required.

To build a {\em parallel} version, you {\em must} have an implementation of the
Message Passing Interface (MPI) \cite{MPI-final,GrLuSk94} for the parallel
computer or workstation network you are running on.  If you do not have a
native version of MPI for your computer, several machine-independent
implementations are available.  Most of the testing and development of \pga\ was
done by using the {\tt MPICH} implementation of MPI which is freely available
\cite{mpich-web-page}.


%%*****************************************************************************
%\section{Computers Supported}\label{sec:computers-supported}
%%*****************************************************************************
%
%This version of \pga\ (1.0) has been tested on Sun Sparc, Next, IBM RS6000,
%and SGI workstations, PC`s running freebsd, and the SGI Powerchallenge, IBM
%SP, and Intel Paragon parallel computers
%Since  \pga\ is written in ANSI C, it should be possible to compile it on
%other systems as well.

%*****************************************************************************
\section{Structure of the Distribution Directory}\label{sec:dirstruc}
%*****************************************************************************

The \pga\ distribution contains the following files and
subdirectories:
\begin{itemize}
\item {\bf CHANGES:} Changes new to this release of \pga.
\item {\bf COPYRIGHT:} The usage terms.
\item {\bf README:} General instructions, including how to build and install
\pga.
\item {\bf configure.in:} The ``source code'' for the {\tt configure}
script.
\item {\bf configure:} A Unix shell script that 
configures {\tt Makefile.in} for a specific architecture.
\item {\bf Makefile.in:} Prototype makefile that is configured into the
file {\tt Makefile} for a specific architecture by {\bf configure}.
\item {\bf docs:}  The users guide and any other supporting files.
\item {\bf examples:}  A directory containing C and Fortran examples.
\item {\bf include:} The \pga\ include directory.
\item {\bf lib:} The top-level directory where \pga\ will be installed.
\item {\bf man:} The directory containing the \pga\ man pages.
\item {\bf source:} The source code for \pga.
\end{itemize}
In the rest of this guide we use ``{\tt .}'' as the top-level directory, 
e.g., {\tt ./source}, {\tt ./examples/c/maxbit.c}.


%*****************************************************************************
\section{Installation Instructions}\label{sec:install}
%*****************************************************************************

When installing \pga\ you make two choices: whether to build a sequential (the
default) or parallel version (see the flags {\tt-mpiinc} and {\tt
-mpilib} below) and whether to build an optimized (the default) or debug
version (the {\tt -debug} flag).  In broad outline, the installation steps
are as follows.
\begin{enumerate}
\item Make a directory to install \pga\ in ({\tt mkdir /usr/local/pga}).
\item Change directories to the directory created in the last step
({\tt cd /usr/local/pga}).
\item Obtain the compressed tar file {\tt pgapack.tar.Z} by anonymous ftp from
{\tt ftp.mcs.anl.gov} in the directory {\tt pub/pgapack}.
\item Uncompress the tar file ({\tt uncompress pgapack.tar.Z}).
\item Untar the uncompressed \pga\ tar file
({\tt tar xvf pgapack.tar}).
\item Use {\tt configure} to configure the makefiles
({\tt configure -arch ARCH\_TYPE})

where {\tt ARCH\_TYPE} is one of
{\tt sun4} for Sun SparcStations workstations,
{\tt next} for NeXT workstations,
{\tt rs6000} for IBM RS/6000 workstations,
{\tt irix} for Silicon Graphics workstations,
{\tt hpux} for Hewlett Packard workstations,
{\tt alpha} for DEC Alpha workstations,
{\tt linux} for machines running Linux,
{\tt freebsd} for machines running FreeBSD,
{\tt generic} for generic 32-bit machines, 
{\tt powerchallenge} for the Silicon Graphics Power Challenge Array,
{\tt challenge} for the Silicon Graphics Challenge,
{\tt t3d} for the Cray T3D,
{\tt sp2} for the IBM SP2,
{\tt paragon} for the Intel Paragon,
or
{\tt exemplar} for the Convex  Exemplar.

The full {\tt configure} options are {\tt configure -arch ARCH\_TYPE [-cc CC] 
[-cflags CFLAGS] [-f77 FC] [-fflags FFLAGS] [-debug]
[-mpiinc MPI\_INCLUDE\_DIRECTORY] [-mpilib MPI\_LIBRARY]  [-help]}
where all parameters except {\tt -arch} are
optional and do the following:
\begin{itemize}
\item {\tt -cc}: The name of the ANSI C compiler, {\tt cc} by
default.
\item {\tt -cflags}: Options passed to the C compiler.
\item {\tt -f77}:  The name of the Fortran 77 compiler, {\tt f77} by
default. (The Fortran compiler is used only to compile the Fortran
examples in the {\tt ./examples/fortran} directory.)
\item {\tt -fflags}: Options passed to the Fortran compiler.
\item {\tt -debug}: If specified, enables the debugging features (see
Chapter~\ref{chp:debug}) and compiles the source code with the {\tt -g} flag.
If this flag is not specified the debugging features are disabled, and
the library is compiled with the {\tt -O} flag
\item {\tt -mpiinc}: The {\em directory} where MPI include files are located.
\item {\tt -mpilib}: The {\em full path} to the MPI library.
\end{itemize}
If {\tt -mpiinc} and  {\tt -mpilib} are specified, {\em a parallel version} of
\pga\ will be built.  If these flags are not specified, a {\em sequential
version} of \pga\ will be built.
\item Execute the makefile ({\tt make install}).
\item Add \pga's man pages to your man page path.
({\tt setenv MANPATH "\$MANPATH"":/home/pgapack/man"})
\item Execute a test problem
\begin{itemize}
\item {\tt /usr/local/pga/examples/c/maxbit} in C
\item {\tt /usr/local/pga/examples/fortran/maxbit} in Fortran.
\end{itemize}
\end{enumerate}

If a parallel version of \pga\ was used, the actual commands to execute a
parallel program in Step 9 will depend on the particular MPI implementation
and parallel computer used.  See Appendix~\ref{chp:start-up} for some
examples.

%*****************************************************************************
\section{Installation Examples}\label{sec:install-examples}
%*****************************************************************************

These installation examples assume you have {\tt ftp}ed the compressed tar
file {\tt pgapack.tar.Z} containing the distribution into {\tt
/home/username}.

%*****************************************************************************
\subsection{Sequential Installation}\label{subsec:seq-install}
%*****************************************************************************

To build a sequential version of \pga\ for a Sun SparcStation in {\tt
/usr/local/pga} and run a test example, type:
\begin{enumerate}
\item {\tt uncompress /home/username/pgapack.tar.Z}
\item {\tt mkdir /usr/local/pga}
\item {\tt cd /usr/local/pga}
\item {\tt tar xvf /home/username/pgapack.tar}
\item {\tt configure -arch sun4}
\item {\tt make install}
\item {\tt /usr/local/pga/examples/c/maxbit}
\end{enumerate}

%*****************************************************************************
\subsection{Parallel Installation}\label{subsec:par-install}
%*****************************************************************************

To build an optimized (no built-in debugging capabilities), parallel
version of \pga\ for an IBM SP parallel computer using an MPI implementation
with include files in {\tt /usr/local/mpi/include} and library in {\tt
/usr/local/mpi/lib}, and run a test example using four processes, type:
\begin{enumerate}
\item {\tt uncompress /home/username/pgapack.tar.Z}
\item {\tt mkdir /usr/local/pga}
\item {\tt cd /usr/local/pga}
\item {\tt tar xvf /home/username/pgapack.tar}
\item {\tt configure -arch rs6000  \verb+\+} \\
\hspace{.5in}
{\tt -mpiinc /usr/local/mpi/include -mpilib /usr/local/mpi/lib/libmpi.a}
\item {\tt make install}
\item {\tt mpirun -np 4 /usr/local/pga/examples/c/maxbit}
\end{enumerate}

Step 7, the execution step, is completely dependent on the MPI implementation.
This example uses the {\tt mpirun} script that is distributed with the {\tt
MPICH} implementation \cite{mpich-web-page}.  Other MPI implementations may
have other ways to specify the number of processes to use.



%*****************************************************************************
\section{Mailing Lists, Web Page, and Bug Reporting}\label{sec:support}
%*****************************************************************************

To join the \pga\ mailing list to receive announcements of new versions,
enhancements, and bug fixes, send electronic mail to {\tt
pgapack@mcs.anl.gov}.  Bug reports should be sent to {\tt
pgapack-bugs@mcs.anl.gov}.  The World Wide Web page for \pga\ is {\tt
http://www.mcs.anl.gov/pgapack.html} and contains 
up-to-date news and a list of bug reports.


When reporting a bug, please include as much information and documentation as
possible.  Helpful information would include \pga\ version number ({\tt
-pgaversion}), MPI implementation and version used, configuration options,
type of computer system, problem description, and error message output.  It is
helpful if you put a {\tt PGAPrintContextVariable} call before and after the
{\tt PGASetUp} call.  Additionally, if possible, build a debug version of
\pga\ and send ``high-level'' output from running your program with the trace
facility enabled (Chapter~\ref{chp:debug}).

%*****************************************************************************
\chapter{Examples}\label{chp:examples}
%*****************************************************************************

This chapter presents some simple \pga\ programs.  The problem chosen is the
Maxbit problem.  The objective is to maximize the number of 1-bits in a
string.  

Section~\ref{sec:simple-example} presents a simple \pga\ program in C
whose structure is sufficient to solve many problems.
Section~\ref{sec:simple-example-fortran} presents this same program in Fortran.
Section~\ref{sec:default-values} shows how to change default values in \pga.
Section~\ref{sec:parallel-simple-example} contains an example that shows how
keyboard input may be read in an MPI environment.  Finally,
Section~\ref{sec:execute} shows how to compile, link, and execute a
\pga\ program.  These and other examples may be found in the {\tt
./examples/c} and {\tt ./examples/fortran} directories.



%*****************************************************************************
\section{Maxbit Problem in C}\label{sec:simple-example}
%*****************************************************************************

\begin{figure}
\begin{verbatim}
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop);

int main(int argc, char **argv)
{
    PGAContext *ctx; 
    ctx = PGACreate (&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
    PGASetUp        (ctx                                                );
    PGARun          (ctx, evaluate                                      );
    PGADestroy      (ctx                                                );
    return;
}

double evaluate (PGAContext *ctx, int p, int pop)
{
    int i, nbits, stringlen;

    stringlen = PGAGetStringLength(ctx);
    nbits     = 0;
    for (i=0; i<stringlen; i++)
        if (PGAGetBinaryAllele(ctx, p, pop, i))
            nbits++;
    return((double) nbits);
}
\end{verbatim}
\caption{\pga\ C Program for the Maxbit Example}\label{example:simple-main}
\end{figure}

Figure~\ref{example:simple-main} shows a minimal program and evaluation
function in C for the Maxbit problem.  All \pga\ C programs {\em must} include
the header file {\tt pgapack.h}. The {\tt PGACreate} call is always the first
function called in a \pga\ program.  It initializes the context variable, {\tt
ctx}.  The parameters to {\tt PGACreate} are the arguments to the program
(given by {\tt argc} and {\tt argv}), the data type selected ({\tt
PGA\_DATATYPE\_BINARY}), the string length ({\tt 100}), and the direction of
optimization ({\tt PGA\_MAXIMIZE}).  The {\tt PGASetUp} call initializes all
parameters and function pointers not explicitly set by the user to default
values.

{\tt PGARun} executes the genetic algorithm.  Its second argument is the name
of a user-defined function ({\tt evaluate}) that will be called to evaluate
the strings.  {\tt PGADestroy} releases all memory allocated by \pga.  Note
that all \pga\ functions take the context variable as an argument (except {\tt
PGACreate}, which creates the context variable).

The {\tt evaluate} function must be written by the user, must return a {\tt
double}, and must follow the exact calling sequence shown.  {\tt
PGAGetStringLength} returns the string length.  {\tt PGAGetBinaryAllele}
returns the value of the {\tt i}th bit of string {\tt p} in population {\tt
pop}.

%*****************************************************************************
\section{Maxbit Problem in Fortran}
\label{sec:simple-example-fortran} 
%*****************************************************************************

\begin{figure}
\begin{verbatim}
      include "pgapackf.h"
      external evaluate
      integer ctx
      ctx = PGACreate (PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE)
      call  PGASetUp  (ctx                                   )
      call  PGARun    (ctx, evaluate                         )
      call  PGADestroy(ctx                                   )
      stop
      end

      double precision function evaluate (ctx, p, pop)
      include "pgapackf.h"
      integer ctx, p, pop, i, bit, nbits, stringlen
      stringlen = PGAGetStringLength(ctx)
      nbits     = 0
      do i=1, stringlen
         bit = PGAGetBinaryAllele(ctx, p, pop, i)
         if (bit .eq. 1) then 
            nbits = nbits + 1
         endif
      enddo
      evaluate = dble(nbits)
      return
      end
\end{verbatim}
\caption{\pga\ Fortran Program for the Maxbit Example}
\label{example:maxbit-fortran}
\end{figure}

The Fortran Maxbit problem in Figure~\ref{example:maxbit-fortran} is similar
to the C version in Figure~\ref{sec:simple-example}.  The Fortran include file
is {\tt pgapackf.h} and should be included in every Fortran function or
subroutine that makes \pga\ calls\footnote{Since not all Fortran compilers
support the -I mechanism for specifying the include file search path,
you will need to copy or set up a symbolic link to {\tt pgapackf.h} from
the directory you are compiling a Fortran program in.}.  Since Fortran
provides no standard mechanism for specifying command line arguments, these
are omitted from the {\tt PGACreate} function call.  The context variable,
{\tt ctx}, is declared {\tt integer} in Fortran.

The evaluation function {\tt evaluate} must contain exactly the calling
sequence shown and must return a {\tt double precision} value.  Note that {\tt
evaluate} is declared in an {\tt external} statement in the program unit in
which it is used as an actual argument.  This is a requirement of the Fortran
language.  In Fortran, the range of allele values is {\tt 1:stringlen}, rather
than {\tt 0:stringlen-1} as in C.

%*****************************************************************************
\section{Specifying Nondefault Values}\label{sec:default-values}
%*****************************************************************************

\begin{figure}
\begin{verbatim}
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop);

int main(int argc, char **argv)
{
    PGAContext *ctx; 
    ctx = PGACreate        (&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
    PGASetPopSize          (ctx, 500                   );
    PGASetFitnessType      (ctx, PGA_FITNESS_RANKING   );
    PGASetCrossoverType    (ctx, PGA_CROSSOVER_UNIFORM );
    PGASetUp               (ctx                        );
    PGARun                 (ctx, evaluate              );
    PGADestroy             (ctx                        );
    return;
}
\end{verbatim}
\caption{Specifying Nondefault Values}
\label{example:soph-main}
\end{figure}

\pga\ offers a wide range of choices for parameter values, operators,
and algorithmic choices.  These will be set to default values in {\tt
PGASetUp} if the user does not explicitly set a value for them.  A nondefault
value may be set by using the {\tt PGASet} family of calls {\em after} {\tt
PGACreate} has been called, but {\em before} {\tt PGASetUp} has been called.

In Figure~\ref{example:soph-main} the {\tt PGASet} calls change the default
values for population size, fitness calculation, and crossover type.  {\tt
PGASetPopSize} changes the population size to 500.  {\tt PGASetFitnessType}
specifies that the fitness values be determined by using a ranking procedure
rather than by direct use of the evaluation function values.  {\tt
PGASetCrossoverType} specifies that uniform crossover, rather than the default
of two-point crossover is to be used.  Most {\tt PGASet} calls are discussed
in Chapter~\ref{chp:functionality}.

%*****************************************************************************
\section{Parallel I/O}\label{sec:parallel-simple-example}
%*****************************************************************************

\begin{figure}
\begin{verbatim}
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop);

int main( int argc, char **argv )
{
     PGAContext *ctx;
     int myid, len, maxiter;

     MPI_Init(&argc, &argv);
     MPI_Comm_rank(MPI_COMM_WORLD, &myid);
     if (myid == 0) {                        /* Process 0 has a dialog */
         printf("String length? ");          /* with the user and      */
         scanf("%d", &len);                  /* broadcasts the user's  */
         printf("Max iterations? ");         /* parameters to all      */
         scanf("%d", &maxiter);              /* other processes        */
     }
     MPI_Bcast(&len,     1, MPI_INT, 0, MPI_COMM_WORLD);
     MPI_Bcast(&maxiter, 1, MPI_INT, 0, MPI_COMM_WORLD);

     ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, len, PGA_MAXIMIZE);
     PGASetMaxGAIterValue(ctx, maxiter);
     PGASetUp(ctx);
     PGARun(ctx, evaluate);
     PGADestroy(ctx);

     MPI_Finalize();
     return(0);
}
\end{verbatim}
\caption{\pga\ Maxbit Example in C with I/O}
\label{example:parallel-simple-main}
\end{figure}


The examples in Figures~\ref{example:parallel-simple-main} (C) and
\ref{example:parallel-simple-main-f77} (Fortran)
read values for the two parameters {\tt len} (string length) and {\tt maxiter}
(maximum number of GA iterations) from standard input.  These examples will
work correctly with either a sequential or parallel version of \pga.  However,
the explicit use of MPI calls for I/O is necessary {\em only} if a parallel
version of \pga\ is used, and parameter values are read from standard input.
The purpose is to be sure that each process receives a copy of the input
values.  See Appendix~\ref{app:par-background} for further details.

{\tt MPI\_Init(\&argc, \&argv)} is always the first function called in any MPI
program.  Each process executes {\tt MPI\_Comm\_rank(MPI\_COMM\_WORLD,
\&myid)} to determine its unique rank in the communicator\footnote{See
Appendix~\ref{app:par-background}} {\tt MPI\_COMM\_WORLD}.  The logic used in
this program is to have process {\tt 0} read and write from/to standard
input/output and broadcast (using {\tt MPI\_Bcast}) the parameters to the
other processes.  The \pga\ function calls are similar to those in the
previous examples.  If the user called {\tt MPI\_Init}, the user must also
call {\tt MPI\_Finalize} before exiting.

We elaborate here on the {\tt MPI\_Bcast} function because of its practical
value in the model of parallel I/O shown. For more detailed discussion of MPI
concepts and functions, the user should consult \cite{MPI-final,GrLuSk94}.

The C binding for {\tt MPI\_Bcast} is
\begin{verbatim}
int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int root, MPI_Comm comm)
\end{verbatim}
and the Fortran binding
\begin{verbatim}
MPI_BCAST(buffer, count, datatype, root, comm, ierror)
<type> buffer(*)
integer count, datatype, root, comm, ierror
\end{verbatim}
{\tt MPI\_Bcast} will result in every process in communicator {\tt comm}
receiving a copy of the contents of {\tt *buf}/{\tt buffer}.  The other
parameters are the number of items ({\tt count}), the datatype ({\tt
datatype}), which may be one of 
{\tt MPI\_DOUBLE},
{\tt MPI\_INT},
{\tt MPI\_CHAR},
{\tt MPI\_UNSIGNED},
or {\tt MPI\_LONG};
the rank of the process with the original copy ({\tt root}); the MPI
communicator ({\tt comm}); and, for Fortran, a variable to handle an error
return code ({\tt ierror}).


\begin{figure}
\begin{verbatim}
      include 'pgapackf.h'
      include 'mpif.h'

      double precision evaluate
      external         evaluate

      integer ctx, myid, len, maxiter, ierror

      call MPI_Init(ierror)
      call MPI_Comm_rank(MPI_COMM_WORLD, myid, ierror)

c     Process 0 has a dialog with the user and broadcasts the user's 
c     parameters to all other processes
      if (myid .eq. 0) then
         print *, 'String length?'
         read  *, len
         print *, 'Max iterations?'
         read  *, maxiter
      endif
      call MPI_Bcast(len,     1, MPI_INT, 0, MPI_COMM_WORLD, ierror)
      call MPI_Bcast(maxiter, 1, MPI_INT, 0, MPI_COMM_WORLD, ierror)

      ctx = PGACreate(PGA_DATATYPE_BINARY, len, PGA_MAXIMIZE)
      call PGASetMaxGAIterValue(ctx, maxiter)
      call PGASetUp(ctx)
      call PGARun(ctx, evaluate)
      call PGADestroy(ctx)

      call MPI_Finalize(ierror)

      stop
      end
\end{verbatim}
\caption{\pga\ Maxbit Example in Fortran with I/O}
\label{example:parallel-simple-main-f77}
\end{figure}

%*****************************************************************************
\section{Compiling, Linking, and Execution}\label{sec:execute}
%*****************************************************************************

When \pga\ was installed, the makefiles in the {\tt ./examples/c} and {\tt
./examples/fortran} directories were correctly configured for the machine
\pga\ was installed on using the version of MPI specified (if any).  To run
your own programs, it is best to copy the appropriate makefile (C or Fortran)
to your directory and modify it to use your source code files.  The makefile
will compile your source code files, link in the \pga\ library (and MPI
library if a parallel version of \pga\ was built), and build your executable.

How you execute your program will depend on whether a sequential or parallel
version of \pga\ was built, the MPI implementation used and the machine you
are running on.  If a sequential version of \pga\ was built (i.e., one where
the user did not supply a version of MPI), the executable {\tt maxbit} can be
executed on a uniprocessor Unix system by typing {\tt maxbit}.  If the {\tt
MPICH} implementation of MPI was used, it may be executed (using four
processes) by {\tt mpirun maxbit -np 4}. Appendix~\ref{chp:start-up} contains
some examples.


%*****************************************************************************
%*****************************************************************************
\part{Users Guide}\label{part:userguide}
%*****************************************************************************
%*****************************************************************************


%*****************************************************************************
\chapter{The Structure of \pga}\label{chp:structure}
%*****************************************************************************

This chapter provides a general overview of the structure of
\pga.

%*****************************************************************************
\section{Native Data Types}\label{sec:data-structure}
%*****************************************************************************

\pga\ is a data-structure-neutral library.  By this we mean that a data-hiding
capability provides the full functionality of the library to the user, in a
transparent manner, irrespective of the data type used.  \pga\ supports four
native data types: binary-valued, integer-valued, real-valued, and
character-valued strings.  In addition, \pga\ is designed to be easily
extended to support other data types (see Chapter~\ref{chp:custom1}).

The binary (or bit) data type (i.e., {\tt |1|0|1|1|}) is the traditional GA
coding.  The bits may either be interpreted literally or decoded into integer
or real values by using either binary coded decimal or binary-reflected Gray
codes.  In \pga\ the binary data type is implemented by using each distinct
bit in a computer word as a gene, making the software very memory-efficient.
The integer-valued data type (i.e., {\tt |3|9|2|4|}) is often used in routing
and scheduling problems.  The real-valued data type (i.e., {\tt
|4.2|7.1|-6.3|0.8|}) is useful in numerical optimization applications.  The
character-valued data type (i.e., {\tt |h|e|l|l|o|w|o|r|l|d|}is useful for
symbolic applications.

%*****************************************************************************
\section{Context Variable}\label{sec:context}
%*****************************************************************************

In \pga\ the {\em context variable} is the data structure that provides the
data hiding capability.  The context variable is a pointer to a C language
structure, which is itself a collection of other structures.  These
(sub)structures contain all the information necessary to run the genetic
algorithm, including data type specified, parameter values, which functions to
call, operating system parameters, debugging flags, initialization choices,
and internal scratch arrays.  By hiding the actual data type selected and
specific functions that operate on that data type in the context variable,
user-level functions in \pga\ can be called independent of the data type.

Almost all fields in the context variable have default values.  However, the
user can set values in the context variable by using the {\tt PGASet} family
of function calls.  The values of fields in the context variable may be read
with the {\tt PGAGet} family of function calls.

%*****************************************************************************
\section{Levels of Usage Available}\label{sec:usage}
%*****************************************************************************

\pga\ provides multiple levels of control to support the requirements of
different users.  At the simplest level, the genetic algorithm ``machinery''
is encapsulated within the {\tt PGARun} function, and the user need specify
only three parameters: the data type, the string length, and the direction of
optimization. All other parameters have default values.  At the next level,
the user calls the data-structure-neutral functions explicitly (e.g., {\tt
PGASelect, PGACrossover, PGAMutation}).  This mode is useful when the
user wishes more explicit control over the steps of the genetic algorithm or
wishes to hybridize the genetic algorithm with a hill-climbing heuristic.  At
the third level, the user can customize the genetic algorithm by supplying his
or her own function(s) to provide a particular operator(s) while still using
one of the native data types.  Finally, the user can define his or her own
datatype, write the data-structure-specific low-level GA functions for the
datatype (i.e., crossover, mutation, etc.), and have the
data-structure-specific functions executed by the high-level
data-structure-neutral \pga\ functions.

%*****************************************************************************
\section{Function Call--Based Library}\label{sec:function}
%*****************************************************************************

All the access to, and functionality of, the \pga\ library is provided
through function calls.

\begin{itemize}

\item
The {\tt PGASet} family of functions sets parameter values, allele values, and
specifies which GA operators to use.  For example, {\tt PGASetPopSize(ctx,500)}
sets the GA population size to 500.

\item
The {\tt PGAGet} family of functions returns the values of fields in the
context variable and allele values in the string.  For example, {\tt bit =
PGAGetBinaryAllele(ctx,p,pop,i)} returns the value of the {\tt
i}th bit in string {\tt p} in population {\tt pop} into {\tt bit}.

\item
The simplest level of usage is provided by the {\tt PGARun} function.  This
function will run the genetic algorithm by using any nondefault values specified
by the user and default values for everything else.

\item
The next level of usage is provided by the data-structure-neutral functions,
which the user can call to have more control over the specific steps of the
genetic algorithm.  Some of these functions are {\tt PGASelect, PGACrossover,
PGAMutate, PGAEvaluate}, and {\tt PGAFitness}.

\item
The data-structure-specific functions deal directly with native
data types.  In general, the user never calls these functions directly.

\item 
System calls in \pga\ provide miscellaneous functionality, including debugging,
random number generation, output control, and error reporting.

\end{itemize}

%*****************************************************************************
\section{Header File and Symbolic Constants}\label{sec:header}
%*****************************************************************************

The \pga\ header file contains symbolic constants and type definitions for all
functions and should be included in any file (or function or subroutine in
Fortran) that calls a \pga\ function.  For example, {\tt
PGA\_CROSSOVER\_UNIFORM} is a symbolic constant that is used as an argument
to the function {\tt PGASetCrossoverType} to specify uniform crossover.  In C
the header file is {\tt pgapack.h}.  In Fortran it is {\tt pgapackf.h}

%*****************************************************************************
\section{Evaluation Function}\label{sec:evalfunc}
%*****************************************************************************

\pga\ requires that the user supply a function that returns an evaluation of a
string that it will map to a fitness value.  This function is called whenever
a string evaluation is required.  The calling sequence and return value of the
function must follow the format discussed in Section~\ref{sec:evaluation}.

%*****************************************************************************
\section{Parallelism}\label{sec:parallel}
%*****************************************************************************

\pga\ can be run on both sequential computers (uniprocessors) and parallel 
computers (multiprocessors, multicomputers, and workstation networks).  The
parallel programming model used is message passing, in particular the single
program, single data (SPMD) model.  \pga\ version 1.0 supports sequential and
parallel implementations of the global population model (see
Chapter~\ref{chp:parallel}).

%*****************************************************************************
\section{Implementation}\label{sec:implement}
%*****************************************************************************

\pga\ is written in ANSI C. A set of interface functions allows most user-level
\pga\ functions to be called from Fortran.  
All message-passing calls follow the
Message Passing Interface (MPI) standard
\cite{MPI-final,GrLuSk94}.  
Nonoperative versions of the basic MPI functions used in the examples are
supplied if the user does not provide an MPI implementation for their machine.
These routines simply return and provide {\em no} parallel functionality.
Their purpose is to allow the \pga\ library to be built in the absence of an
MPI implementation.

Most  low-level internal functions in \pga\ are
data-structure {\em specific} and use addresses and/or offsets of the
population data structures.  The user-level routines, however, provide the
abstractions of data-structure {\em neutrality} and an integer indexing scheme
for access to population data structures.



%*****************************************************************************
\chapter{Basic Usage}\label{chp:functionality}
%*****************************************************************************

As the examples in Chapter~\ref{chp:examples} show, a \pga\ program can be
written with just four function calls and a string evaluation function.  This
basic usage is discussed further in Section~\ref{sec:big-picture}.
Sections~\ref{sec:stopping-criteria}--\ref{sec:utility} explain options
available in \pga.  Section~\ref{sec:cla} discusses \pga\ command line
arguments.

%*****************************************************************************
\section{Required Functions}\label{sec:big-picture}
%*****************************************************************************

Any file (or function or subroutine in Fortran) that uses a \pga\ function must
include the \pga\ header file.  In C this file is {\tt pgapack.h}.  In Fortran
this file is {\tt pgapackf.h}.  The first \pga\ call made is {\em always} to
{\tt PGACreate}.  In C this call looks like
\begin{verbatim}
PGAContext *ctx;
ctx = PGACreate (&argc, argv, datatype, len, maxormin);
\end{verbatim}
{\tt PGACreate} allocates space for the context variable, {\tt ctx}
(Section~\ref{sec:context}), and returns its address. {\tt argc} and {\tt
argv} are the standard list of arguments to a C program.  {\tt datatype} must
be one of {\tt PGA\_DATATYPE\_BINARY}, {\tt PGA\_DATATYPE\_INTEGER}, {\tt
PGA\_DATATYPE\_REAL}, or {\tt PGA\_DATATYPE\_CHARACTER} to specify strings
consisting of binary-valued, integer-valued, real-valued, or character-valued
strings, respectively.  {\tt len} is the length of the string (i.e., the
number of genes).  {\tt maxormin} must be {\tt PGA\_MAXIMIZE} or {\tt
PGA\_MINIMIZE} to indicate whether the user's problem is maximization or
minimization, respectively.

In Fortran the call to {\tt PGACreate} is
\begin{verbatim}
integer ctx
ctx = PGACreate (datatype, len, maxormin)
\end{verbatim}
where  {\tt datatype}, {\tt len}, and {\tt maxormin} are the same as for C
programs.
After the {\tt PGACreate} call, the user may {\em optionally} set nondefault
values.  These are then followed by a call to {\tt PGASetUp} to initialize to
default values all options, parameters, and operators not explicitly specified
by the user. For example,
\begin{verbatim}
ctx = PGACreate(&argc, argv, datatype, len, maxormin);
PGASetPopSize              (ctx, 500);
PGASetFitnessType          (ctx, PGA_FITNESS_RANKING);
PGASetCrossoverType        (ctx, PGA_CROSSOVER_UNIFORM);
PGASetUniformCrossoverProb (ctx, 0.6);
PGASetUp                   (ctx);
\end{verbatim}
will change the default values for the population size, the mapping
of the user's
evaluation to a fitness value, and the crossover type.  All {\tt
PGASet} calls should be made {\em after} {\tt PGACreate} has been called, but
{\em before} {\tt PGASetUp} has been called; all such calls are {\em
optional}.  Note also that {\em all} \pga\ functions other than {\tt
PGACreate} take the context variable as their first argument.

The {\tt PGARun} function executes the genetic algorithm.  Its second argument
is the name of a user-supplied evaluation function that returns a {\tt double}
({\tt double precision} in Fortran) value that is the user's evaluation of an
individual string.  In C the prototype for this function looks like
\begin{verbatim}
double evaluate (PGAContext *ctx, int p, int pop);
\end{verbatim}
and in Fortran
\begin{verbatim}
double precision function evaluate (ctx, p, pop)
integer ctx, p, pop
\end{verbatim}
The user {\em must} write the evaluation function, and it {\em must} have the
calling sequence shown above and discussed further in
Section~\ref{sec:evaluation}.  After {\tt PGARun} terminates, {\tt PGADestroy}
is called to release all memory allocated by \pga.
\footnote{{\tt PGADestroy} will also call {\tt MPI\_finalize}, if MPI was
started by {\tt PGACreate}.}

Except for writing an evaluation function (Section~\ref{sec:evaluation}) the
information contained in rest of this chapter is optional---defaults will be
set for all other GA parameters.  We do note, however, that the defaults used
are the result of informal testing and results reported in the GA literature.
{\em They are by no means optimal}, and additional experimentation
with other values may well yield better performance on any given problem.


%*****************************************************************************
\section{Population Replacement}\label{sec:population-replacement}
%*****************************************************************************
Two population replacement schemes are common in the literature.  The first,
the {\em generational replacement} genetic algorithm (GRGA), replaces the
entire population each generation and is the traditional genetic algorithm
\cite{Ho92}.  The second, the {\em steady-state} genetic algorithm (SSGA),
typically replaces only a few strings each generation and is a more recent
development
\cite{Sy89,Wh89,WhKa88}.
\pga\ supports both GRGA and SSGA and variants in between via {\em
parameterized} population replacement.  For example, the {\tt PGASet} calls
\begin{verbatim}
PGASetPopSize           (ctx,200);
PGASetNumReplaceValue   (ctx,10);
PGASetPopReplacementType(ctx, PGA_POPREPL_BEST);
\end{verbatim}
specify that each generation a new population is created consisting of ten
strings created via recombination, and the 190 most fit strings from the old
population.  The 190 strings can also be selected
randomly, with or without replacement, by setting the second argument of {\tt
PGASetPopReplacementType} to {\tt PGA\_POPREPL\_RANDOM\_REP} or {\tt
PGA\_POPREPL\_RANDOM\_NOREP}, respectively.

By default, the number of new strings created each generation is 10 percent
of the population size (an SSGA population replacement strategy).  A GRGA can
be implemented by setting {\tt PGASetNumReplaceValue} to the population size
(the default population size is 100).  Setting {\tt PGASetNumReplaceValue} to
one less than the population size will result in an elitist GRGA, where the
most fit string is always copied to the new population (since {\tt
PGA\_POPREPL\_BEST} is the default population replacement strategy).

Traditionally, strings created through recombination first undergo crossover
and then mutation.  Some practitioners \cite{Da91} have argued that these two
operators should be separate.  By default, \pga\ applies mutation only to
strings that did {\em not} undergo crossover.  This is equivalent to setting
{\tt PGASetMutationOrCrossoverFlag} {\tt (ctx,PGA\_TRUE)}.  To have strings
undergo {\em both} crossover and mutation, on should use {\tt
PGASetMutationAndCrossoverFlag} {\tt (ctx,PGA\_TRUE)}.

By default, \pga\ allows duplicate strings in the population.  Some
practitioners advocate not allowing duplicate strings in the population in
order to maintain diversity.  The function call {\tt PGASetNoDuplicatesFlag}
{\tt (ctx,PGA\_TRUE)} will not allow duplicate strings in the population: It
repeatedly applies the mutation operator (with an increasing mutation rate) to
a duplicate string until it no longer matches any string in the new
population.  If the mutation rate exceeds 1.0, however, the duplicate string
{\em will} be allowed in the population, and a warning message will be issued.

Figure~\ref{fig:popreplace} shows the generic population replacement scheme in
\pga.  Both populations $k$ and $k+1$  are of fixed size (the value returned by
{\tt PGAGetPopSize}).  First, {\tt PGAGetPopSize} - {\tt
PGAGetNumReplaceValue} strings are copied over directly from generation $k$.
The way the strings are chosen, the most fit, or randomly with or without
replacement, depends on the value set by {\tt PGASetPopReplacementType}.  The
remaining {\tt PGAGetNumReplaceValue} strings are created by crossover and
mutation.

\begin{figure}
\centerline{\epsfbox{generation.eps}}
\caption{Population Replacement}\label{fig:popreplace}
\end{figure}


%*****************************************************************************
\section{Stopping Criteria}\label{sec:stopping-criteria}
%*****************************************************************************

\pga\  terminates when at least one of the stopping
rule(s) specified has been met.  The three stopping rules are (1) iteration
limit exceeded, (2) population too similar, and (3) no change in the best
solution found in a given number of iterations.  The default is to stop when
the iteration limit (by default, 1000 iterations) is reached.

The choice of stopping rule is set by {\tt PGASetStoppingRuleType}.  For
example, {\tt PGASetStoppingRuleType} {\tt (ctx,PGA\_STOP\_MAXITER)} is the
default.  Other choices are {\tt PGA\_STOP\_TOOSIMILAR} and {\tt
PGA\_STOP\_NOCHANGE} for population too similar and no change in the best
solution found, respectively.  {\tt PGASetStoppingRuleType} may be called more
than once. The different stopping rules specified are {\em or}ed together.


If {\tt PGA\_STOP\_MAXITER} is one of the stopping rules, {\tt
PGASetMaxGAIterValue(ctx,500)} will change the maximum iteration limit to 500.
If {\tt PGA\_STOP\_NOCHANGE} is one of the stopping rules, {\tt
PGASetMaxNoChangeValue(ctx,50)} will change from 100 (the default) to 50 the
maximum number of iterations in which no change in the best evaluation is
allowed before the GA stops.  If {\tt PGA\_STOP\_TOOSIMILAR} is one of the
stopping rules, {\tt PGASetMaxSimilarityValue(ctx,99)} will change from 95 to
99 the percentage of the population allowed to have the same evaluation
function value before the GA stops.



%*****************************************************************************
\section{Initialization}\label{sec:initialization}
%*****************************************************************************

Strings are either initialized randomly (the default),
or set to zero.  The choice is specified by setting the second argument of
{\tt PGASetRandomInitFlag} to either {\tt PGA\_TRUE} or {\tt PGA\_FALSE},
respectively.  Random initialization depends on the datatype.

If binary-valued strings are used, each gene is set to {\tt 1} or {\tt 0} with
an equal probability.  To set the probability of randomly setting a bit to
{\tt 1} to 0.3, use {\tt PGASetBinaryInitProb(ctx,0.3)}.

For integer-valued strings, the default is to set the strings to a permutation
on a range of integers.  The default range is $[0,L-1]$, where $L$ is the
string length.  {\tt PGASetIntegerInitPermute(ctx, 500, 599)} will set the
permutation range to $[500,599]$.  The length of the range {\em must} be the
same as the string length.

Alternatively, {\tt PGASetIntegerInitRange} will set each gene to a random value
selected uniformly from a specified range.  For example, the code
\begin{verbatim}
stringlen = PGAGetStringLength(ctx);
for(i=0;i<stringlen;i++) {
    low[i]  = 0;
    high[i] = i;
}
PGASetIntegerInitRange(ctx, low, high);
\end{verbatim}
will select a value for gene {\tt i} uniformly randomly from the interval
{\tt [0,i]}.

If real-valued strings are used, the alleles are set to a value selected
uniformly randomly from a specified interval.  The interval may be specified
with either the {\tt PGASetRealInitRange} or {\tt PGASetRealInitPercent}
functions.
For example, the code
\begin{verbatim}
stringlen = PGAGetStringLength(ctx);
for(i=0;i<stringlen;i++) {
    low[i]  = -10.0;
    high[i] = (double) i;
}
PGASetRealInitRange(ctx, low, high);
\end{verbatim}
will select a value for allele {\tt i} uniformly randomly from the interval
$[-10.0,{\tt i}]$.  This is the default strategy for initializing real-valued
strings.  The default interval is $[0,1.0]$.

{\tt PGASetRealInitPercent} specifies the interval with a median value and
percent offset.  For example,
\begin{verbatim}
stringlen = PGAGetStringLength(ctx);
for(i=1;i<=stringlen;i++) {
    median[i]  = (double)  i;
    percent[i] =          .5;
}
PGASetRealInitPercent(ctx, median, percent);
\end{verbatim}
will select a value for allele {\tt i} uniformly randomly from the increasing
intervals $[\frac{1}{2}i,\frac{3}{2}i]$.  Note that if 
the median value is zero for some $i$, than an 
interval of $[0,0]$ will be defined.

If character-valued strings are used,
{\tt PGASetCharacterInitType(ctx,PGA\_CINIT\_UPPER)} will set the  allele values
to uppercase alphabetic characters chosen uniformly randomly.
Other options are
{\tt PGA\_CINIT\_LOWER} for lower case letters only (the default) and 
{\tt PGA\_CINIT\_MIXED} for mixed case letters, respectively.

%*****************************************************************************
\section{Selection}\label{sec:selection}
%*****************************************************************************

The selection phase allocates reproductive trials to strings on the basis of
their fitness.  \pga\ supports four selection schemes: proportional selection,
stochastic universal selection, binary tournament selection, and probabilistic
binary tournament selection.  The choice may be specified by setting the
second argument of {\tt PGASetSelectType} to one of {\tt
PGA\_SELECT\_PROPORTIONAL}, {\tt PGA\_SELECT\_SUS}, {\tt
PGA\_SELECT\_TOURNAMENT}, and {\tt PGA\_SELECT\_PTOURNAMENT} for proportional,
stochastic universal, tournament, and probabilistic tournament selection,
respectively.  The default is tournament selection.  For probabilistic
tournament selection, the default probability that the string that wins the
tournament is selected is 0.6.  It may be set to 0.8, for example, with {\tt
PGASetPTournamentProb(ctx, 0.8)}.


% Baker's stochastic universal selection (SUS) is an optimal sampling algorithm
% \cite{Ba87}.  SUS may be thought of as constructing a roulette wheel using
% fitness proportionate selection and then spinning the wheel once, where the
% number of equally spaced markers on the wheel is equal to the population size.
% This method guarantees that each string is allocated $\lfloor expected value
% \rfloor$ reproductive trials and no more than $\lceil expected value
% \rceil$.
% 
% In {\em binary} tournament selection \cite{Go89,GoDe91} two strings are chosen
% randomly from the population.  The more fit string is then allocated a
% reproductive trial.  In order to produce an offspring, two binary tournaments
% are held, each of which produces one parent string.  These two parent strings
% then recombine to produce an offspring.  A variation of binary tournament
% selection is {\em probabilistic} binary tournament selection where the more
% fit string is selected with a probability $p_b$, $.5
% \leq p_b < 1$.  Probabilistic binary tournament selection does
% allow for the possibility that the best string in the population may be lost.
% Its advantage is a reduction in the selective pressure.

%*****************************************************************************
\section{Crossover}\label{sec:crossover}
%*****************************************************************************

The crossover operator takes bits from each parent string and
combines them to create child strings.  
%Figure~\ref{fig:one-point-crossover} illustrates one-point
%crossover operator. Starting with two parent strings of length $n=8$, a
%crossover site $c=3$ is chosen at random. Two new strings are then created;
%one uses bits 1--2 from the first parent string and bits
%3--8 from the second parent string; the other string uses the
%complementary bits from the two parent strings.
%
%\begin{figure}[tb]
%\begin{verbatim}
%        Parent Strings                    Child Strings
%        a a a a a a a a                   a a b b b b b b
%        b b b b b b b b                   b b a a a a a a
%\end{verbatim}
%\centering
%\caption
%{
%One-Point Crossover\label{fig:one-point-crossover}
%}
%\end{figure}
%
%Figure~\ref{fig:two-point-crossover} illustrates two-point crossover. Starting
%with two parent strings of length $n=8$, two crossover sites $c_1=3$ and
%$c_2=6$ are chosen at random. Two new strings are then created; one uses bits
%1--2 and 6--8 from the first parent string and bits 3--5 from the second parent
%string; the other string uses the complementary bits from each parent string.
%
%\begin{figure}
%\begin{verbatim}
%        Parent Strings                    Child Strings
%        a a a a a a a a                   a a b b b a a a
%        b b b b b b b b                   b b a a a b b b
%\end{verbatim}
%\centering
%\caption
%{
%Two-Point Crossover\label{fig:two-point-crossover}
%}
%\end{figure}
%
%Figure~\ref{fig:uniform-crossover} illustrates uniform crossover. Starting
%with two parent strings of length $n=8$, the bit-mask {\tt 01101001} is
%randomly generated.  This mask is applied to the parent strings such that a
%``{\tt 1}'' bit indicates that the next bit for the first child string should
%be taken from the first parent string, and a ``{\tt 0}'' bit indicates that
%the next bit for the first child string should be taken from the second parent
%string.  The bit-string is then complemented and the process repeated to
%create the second child string.
%
%\begin{figure}
%\begin{verbatim}
%        Parent Strings                    Child Strings
%        a a a a a a a a                   b a a b a b b a
%        b b b b b b b b                   a b b a b a a b
%\end{verbatim}
%\centering
%\caption
%{
%Uniform Crossover\label{fig:uniform-crossover}
%}
%\end{figure}
%
The type of crossover may be specified by setting {\tt PGASetCrossoverType} to
{\tt PGA\_CROSSOVER\_ONEPT}, {\tt PGA\_CROSSOVER\_TWOPT}, or {\tt
PGA\_CROSSOVER\_UNIFORM} for one-point, two-point, or uniform crossover,
respectively.  The default is two-point crossover.  By default the crossover
rate is 0.85.  It may be set to 0.6 by {\tt PGASetCrossoverProb(ctx, 0.6)},
for example.

Uniform crossover is parameterized by $p_u$, the probability of swapping two
parent bit values \cite{SpDe91}.  By default, $p_u = 0.5$.  The function call
{\tt PGASetUniformCrossoverProb(ctx, 0.7)} will set $p_u = 0.7$.


%*****************************************************************************
\section{Mutation}\label{sec:mutation}
%*****************************************************************************

The mutation {\em rate} is the probability that a gene will undergo
mutation.  The mutation rate is independent of the datatype used. The default
mutation rate is the reciprocal of the string length.  The function call {\tt
PGASetMutationProb(ctx,.001)} will set the mutation rate to .001.

The {\em type} of mutation depends on the data type.  For binary-valued
strings, mutation is a bit complement operation For
character-valued strings, mutation replaces one alphabetic character with
another chosen uniformly randomly.  The alphabetic characters will be lower,
upper, or mixed case depending on how the strings were initialized.

For integer-valued strings, if the strings were initialized to a permutation
and gene $i$ is to be mutated, the default mutation operator swaps gene $i$
with a randomly selected gene. If the strings were initialized to a random
value from a specified range and gene $i$ is to be mutated, by default gene
$i$ will be replaced by a value selected uniformly random from the
initialization range.

The mutation operator for integer-valued strings may be changed irrespective
of how the strings were initialized.  If {\tt PGASetMutationType} is set to
{\tt PGA\_MUTATION\_RANGE}, gene $i$ will be replaced with a value selected
uniformly randomly from the initialization range.  If the strings were
initialized to a permutation, the minimum and maximum values of the
permutation define the range.  If {\tt PGASetMutationType} is set to {\tt
PGA\_MUTATION\_PERMUTE}, gene $i$ will be swapped with a randomly selected
gene.  If {\tt PGASetMutationType} is set to {\tt PGA\_MUTATION\_CONSTANT}, a
constant integer value (by default one) will be added (subtracted) to (from)
the existing allele value.  The constant value may be set to 34, for example,
with {\tt PGASetMutationIntegerValue(ctx,34)}.

Three of the four real-valued mutation operators are of the form $v \leftarrow
v \pm p \times v$, where $v$ is the existing allele value.  They vary by how
$p$ is selected.  First, if {\tt PGASetMutationType} is set to {\tt
PGA\_MUTATION\_CONSTANT}, $p$ is the constant value 0.01. It may be set to
.02, for example, with {\tt PGASetMutationRealValue(ctx,.02)}.  Second, if
{\tt PGASetMutationType} is set to {\tt PGA\_MUTATION\_UNIFORM}, $p$ is
selected uniformly from the interval $(0,.1)$. To select $p$ uniformly from
the interval $(0,1)$ set {\tt PGASetMutationRealValue(ctx,1)}.  Third, if {\tt
PGASetMutationType} is set to {\tt PGA\_MUTATION\_GAUSSIAN}, $p$ is selected
from a Gaussian distribution (this is the default real-valued mutation
operator) with mean 0 and standard deviation 0.1.  To select $p$ from a
Gaussian distribution with mean 0 and standard deviation 0.5 set {\tt
PGASetMutationRealValue(ctx,.5)}.  Finally, if {\tt PGASetMutationType} is set
to {\tt PGA\_MUTATION\_RANGE}, gene $i$ will be replaced with a value selected
uniformly random from the initialization range of that gene.


Some of the integer- and real-valued mutation operators may generate allele
values outside the initialization range of that gene.  If this happens, by
default, the allele value will be reset to the lower (upper) value of the
initialization range for that gene.  By setting {\tt
PGASetMutationBoundedFlag(ctx, PGA\_FALSE)} the allele values will {\em not}
be reset if they fall outside of the initialization range.


%*****************************************************************************
\section{Restart}\label{sec:restart}
%*****************************************************************************

The restart operator reseeds a population from the best string.  It does so by
seeding the new population with the best string and generating the remainder
of the population as mutated variants of the best string.

By default the restart operator is not invoked.  Setting {\tt
PGASetRestartFlag(ctx,PGA\_TRUE)} will cause the restart operator to be
invoked.  By default \pga\ will restart every 50 iterations.  {\tt
PGASetRestartFrequencyValue} {\tt (ctx,100)} will restart every 100 iterations
instead.  When creating the new strings from the best string an individual
allele undergoes mutation with probability 0.5.  This can be changed to 0.9
with the function call {\tt PGASetRestartAlleleChangeProb(ctx,0.9)}.

For binary-valued strings the bits are complemented.  For integer- and
real-valued strings the amount to change is set with {\tt
PGASetMutationIntegerValue} and {\tt PGASetMutationRealValue}, respectively.
Character-valued strings are changed according to the rules in
Section~\ref{sec:mutation} for mutating character strings.

%*****************************************************************************
\section{String Evaluation and Fitness}\label{sec:evaluation}
%*****************************************************************************

In a genetic algorithm each string is assigned a nonnegative, real-valued {\em
fitness}.  This is a measure, relative to the rest of the population, of how
well that string satisfies a problem-specific metric.  In \pga\ calculating a
string's fitness is a two-step process.  First, the {\em user} supplies a
real-valued evaluation (sometimes called the raw fitness) of each string.
Second, this value is mapped to a fitness value.

It is the user's responsibility to supply a function to evaluate an individual
string.  As discussed in Section~\ref{sec:big-picture}, the name of this
function is specified as the second argument to {\tt PGARun}. The calling
sequence for this function (which we call {\tt evaluate} in the rest of this
section, but may have any name) {\em must} follow the format given here.  In C
the format is
\begin{verbatim}
double evaluate (PGAContext *ctx, int p, int pop);
\end{verbatim}
and in Fortran
\begin{verbatim}
double precision function evaluate (ctx, p, pop)
integer ctx, p, pop
\end{verbatim}

The function {\tt evaluate} will be called by {\tt PGARun} whenever a string
evaluation is required.  {\tt p} is the index of the string in population {\tt
pop} that will be evaluated.  The correct values of {\tt p} and {\tt pop} will
be passed to the evaluation function by {\tt PGARun}.  (If {\tt PGARun} is not
used, {\tt PGAEvaluate} must be.  See Chapter~\ref{chp:explicit}.)
As shown below,  {\tt p}
and {\tt pop} are used for reading (and sometimes writing) allele values
Sample evaluation functions
are shown in Figures~\ref{example:simple-main} and
\ref{example:maxbit-fortran}, and online in the {\tt ./examples} directory. 

Traditionally, genetic algorithms assume fitness values are nonnegative and
monotonically increasing the more fit a string is.  The user's evaluation of a
string, however, may reflect a minimization problem and/or be negative.
Therefore, the user's {\em evaluation value} is mapped to a nonnegative and
monotonically increasing {\em fitness value}.  First, all evaluations are
mapped to positive values (if any were negative).  Next, these values are
translated to a maximization problem (if the direction of optimization
specified was minimization).  Finally, these values are mapped to a fitness
value by using the identity (the default), linear ranking, or linear
normalization, The choice of fitness mapping may be set with the function {\tt
PGASetFitnessType}.  The second argument must be one of {\tt
PGA\_FITNESS\_RAW}, {\tt PGA\_FITNESS\_RANKING}, or {\tt
PGA\_FITNESS\_NORMAL}, for the identity, linear ranking, or linear
normalization, respectively.

A {\em linear rank} fitness function \cite{Ba87,Wh89} is given by
\begin{equation}
Min + (Max - Min)\frac{{\tt rank(p)}-1}{N-1},\label{eq:rank-select}
\end{equation}
where {\tt rank(p)} is the index of string {\tt p} in a list sorted in order
of decreasing evaluation function value, and $N$ is the population size.
Ranking requires that $1 \leq Max \leq 2$, and $Min + Max = 2$.  The default
value for $Max$ is 1.2.  It may be set to 1.1 with {\tt
PGASetMaxFitnessRank(ctx,1.1)}.

In {\em linear normalization} the fitness function is given by
\begin{equation}
K - ({\tt rank(p)} * C),
\end{equation}
where $K$ and $C$ are the constants $\sigma * N$ and $\sigma$, where $\sigma$
is the standard deviation of the user's evaluation function values after they
have been transformed to positive values for a maximization problem.

If the direction of optimization is minimization, the values are remapped for
maximization.  The function call {\tt
PGASetFitnessMinType(ctx,PGA\_FITNESSMIN\_CMAX)} will remap by subtracting the
worst evaluation value from each evaluation value (this is the default).  The
worst evaluation value is multiplied by 1.01 before the subtraction so that
the worst string has a nonzero fitness.  The function call {\tt
PGASetFitnessCmaxValue(ctx, 1.2)} will change the multiplier to 1.2
Alternatively, if {\tt PGA\_FITNESSMIN\_RECIPROCAL} is specified the remapping
is done by using the reciprocal of the evaluation function.

\section{Accessing Allele Values}\label{sec:allele-access}

For each of the native data types, \pga\ provides a matched pair of functions
that allow the user to read or write (change) any allele value.  If the data
type is {\tt PGA\_DATATYPE\_BINARY}
\begin{verbatim}
int bit;
bit = PGAGetBinaryAllele (ctx, p, pop, i);
\end{verbatim}
will assign to {\tt bit} the binary value of the {\tt i}th gene in string {\tt
p} in population {\tt pop}.  To set the {\tt i}th gene in string {\tt p} in
population {\tt pop} to {\tt 1}, use
\begin{verbatim}
PGASetBinaryAllele(ctx, p, pop, i, 1);
\end{verbatim}

If the data type is {\tt PGA\_DATATYPE\_INTEGER}
\begin{verbatim}
int k;
k = PGAGetIntegerAllele (ctx, p, pop, i);
\end{verbatim}
will assign to {\tt k} the integer value of the {\tt i}th gene in string
{\tt p} in population {\tt pop}.  
To set the {\tt i}th gene in string
{\tt p} in population {\tt pop} to 34, use
\begin{verbatim}
PGASetIntegerAllele(ctx, p, pop, i, 1, 34);
\end{verbatim}

If the data type is {\tt PGA\_DATATYPE\_REAL}
\begin{verbatim}
double x;
x = PGAGetRealAllele (ctx, p, pop, i);
\end{verbatim}
will assign to {\tt x} the real value of the {\tt i}th gene in string {\tt p}
in population {\tt pop}.
To set the {\tt i}th gene in string
{\tt p} in population {\tt pop} to 123.456, use
\begin{verbatim}
PGASetRealAllele(ctx, p, pop, i, 1, 123.456);
\end{verbatim}


If the data type is {\tt PGA\_DATATYPE\_CHARACTER}
\begin{verbatim}
char c;
c = PGAGetCharacterAllele (ctx, p, pop, i);
\end{verbatim}
will assign to {\tt c} the character value of the {\tt i}th gene in string
{\tt p} in population {\tt pop}.  To set the {\tt i}th gene in string {\tt p}
in population {\tt pop} to ``Z'', use
\begin{verbatim}
PGASetCharacterAllele(ctx, p, pop, i, 1, 'Z');
\end{verbatim}


\subsection{Representing an Integer with a Binary String}
\label{subsec:encode-integer}

A binary string may be used to represent an integer by {\em decoding} the
bits into an integer value.  In a binary coded decimal (BCD) representation, a
binary string is decoded into an integer $k
\in [0,2^{N}-1]$ according to
\begin{equation}
k = \sum_{i=1}^{N} b_{i} 2^{i-1},
\label{eq:bit}
\end{equation}
where $N$ is the string length, and $b_i$ the value of the $i$th bit.
For example, to decode the integer {\tt k} from the ten bits in bit positions
20--29, use
\begin{verbatim}
int k
k = PGAGetIntegerFromBinary(ctx,p,pop,20,29);
\end{verbatim}
The function {\tt PGAEncodeIntegerAsBinary} will encode an integer as a binary
string.  For example, to encode the integer 564 as a 12-bit binary
string\footnote{Even though only ten bits are necessary to encode 564, the
user may want to allow the GA any value between $[0,4095]$, hence the twelve
bits.}  in the substring defined by bits 12--23, use
\begin{verbatim}
PGAEncodeIntegerAsBinary(ctx,p,pop, 12, 23, 564);
\end{verbatim}

In a BCD representation, two numbers that are contiguous in their decimal
representations may be far from each other in their binary representations.
For example, 7 and 8 are consecutive integers, yet their 4-bit binary
representations, {\tt 0111} and {\tt 1000}, differ in the maximum number of
bit positions.\footnote{Technically, this is known as a Hamming cliff.}  {\em
Gray codes} define a different mapping of binary strings to integer values
from that given by Eq.~(\ref{eq:bit}) and may alternatively be used for
representing integer (or real, see below) values in a binary string.  The
second and third columns in Table~\ref{tab:gray-code} show how the integers
0--7 are mapped to Eq.~(\ref{eq:bit}) and to the {\em binary reflected} Gray
code (the most commonly used Gray code sequence), respectively.  In the binary
reflected Gray code sequence, the binary representations of consecutive
integers differ  by only one bit (a Hamming distance of one).

To decode the integer {\tt k} from a binary reflected Gray code
interpretation of the binary string, use
\begin{verbatim}
k = PGAGetIntegerFromGrayCode(ctx,p,pop,20,29);
\end{verbatim}
To encode 564 as a 12-bit binary string in the substring defined by bits 12--23 using a Gray code, use
\begin{verbatim}
PGAEncodeIntegerAsGaryCode(ctx,p,pop, 12, 23, 564);
\end{verbatim}



\begin{table}
\centering
\caption
{
Binary and Gray Codes\label{tab:gray-code}
}
\begin{tabular}{|r|r|r|} \hline\hline
    $k$ &      Eq.~(\ref{eq:bit}) &    Gray code \\  \hline
{\tt 0} &        {\tt 000} &         {\tt 000} \\
{\tt 1} &        {\tt 001} &         {\tt 001} \\
{\tt 2} &        {\tt 010} &         {\tt 011} \\
{\tt 3} &        {\tt 011} &         {\tt 010} \\
{\tt 4} &        {\tt 100} &         {\tt 110} \\
{\tt 5} &        {\tt 101} &         {\tt 111} \\
{\tt 6} &        {\tt 110} &         {\tt 101} \\
{\tt 7} &        {\tt 111} &         {\tt 100} \\ \hline
\end{tabular}
\end{table}

\subsection{Representing a Real Value with a Binary String}
\label{subsec:encode-real}

A binary string may also be used to represent a real value.  The decoding of a
binary string to a real-value is a two-step process.  First, the binary string
is decoded into an integer as described in
Section~\ref{subsec:encode-integer}.  Next, the integer is mapped from the
discrete interval $[0,2^{N}-1]$ to the real interval $[L,U]$ by using the
formula
\begin{displaymath}
x = (k-a) \times (U-L)/(b-a) + L
\end{displaymath}
(and generalizing $[0,2^{N}-1]$ to $[a,b]$).  For example, to decode the {\tt
double} {\tt x} from the 20 bits given by the binary string stored in bit
positions 10--29 onto the interval $[-10.0,20.0]$, use
\begin{verbatim}
x = PGAGetRealFromBinary(ctx,p,pop,10,29,-10.0,20.0);
\end{verbatim}
To encode -18.3 on the interval $[-50.0,50.0]$
using a 20-bit BCD binary string, use
\begin{verbatim}
PGAEncodeRealAsBinary(ctx,p,pop,0,19,-50.0,50.0,-18.3);
\end{verbatim}
The functions {\tt PGAGetRealFromGrayCode} and 
{\tt PGAEncodeRealAsGrayCode} provide similar functionality for Gray-coded
strings.

\subsection{Example}
\label{subsec:example}

As an example, suppose the user has a real-valued function $f$ of three real
variables $x_1$, $x_2$, and $x_3$.  Further, the variables are constrained as
follows.
\begin{displaymath}
-10 \leq x_1 \leq 0 
\end{displaymath}
\begin{displaymath}
0   \leq x_2 \leq 10
\end{displaymath}
\begin{displaymath}
-10 \leq x_3 \leq 10
\end{displaymath}
The user wishes to use 10 bits for the binary representation of $x_1$ and
$x_2$, and 20 bits for the binary representation of $x_3$ (perhaps for higher
accuracy), and a Gray code encoding.  This may be done as follows.
\begin{verbatim}
#include "pgapack.h"
double grayfunc (PGAContext *ctx, int p, int pop);
double f        (double x1, double x2, double x3);
int main(int argc, char **argv)
{
    PGAContext *ctx; 
    ctx = PGACreate (&argc, argv, PGA_DATATYPE_BINARY, 40, PGA_MINIMIZE);
    PGASetUp        (ctx                                               );
    PGARun          (ctx, grayfunc                                     );
    PGADestroy      (ctx                                               );
    return;
}

double grayfunc (PGAContext *ctx, int p, int pop)
{
    double x1, x2, x3, v;
    x1 =  PGAGetRealFromGrayCode (ctx, p, pop,  0,  9, -10.,  0.);
    x2 =  PGAGetRealFromGrayCode (ctx, p, pop, 10, 19,   0., 10.);
    x3 =  PGAGetRealFromGrayCode (ctx, p, pop, 20, 39, -10., 10.);
    v  =  f(x1,x2,x3);
    return(v);
}
\end{verbatim}
In Fortran, the bit indices would be 1--10, 11--20, and 21--40, respectively.
The number of bits allocated for the binary representation determines the
accuracy with which the real value can be calculated.  Note in this
example  the function {\tt f} {\em need not be modified}; the function
{\tt grayfunc} is used as a ``wrapper'' to get variable values out of the GA
and return the value calculated by {\tt f}.

%*****************************************************************************
\section{Report Options}\label{sec:report}
%*****************************************************************************

{\tt PGASetPrintFrequencyValue(ctx,40)} will print population statistics every
40 iterations.  The default is every ten iterations.  The best evaluation is
{\em always} printed.  To print additional statistics, set the second argument
of the function {\tt PGASetPrintOptions} to {\tt PGA\_REPORT\_ONLINE}, {\tt
PGA\_REPORT\_OFFLINE}, {\tt PGA\_REPORT\_WORST}, {\tt PGA\_REPORT\_AVERAGE},
{\tt PGA\_REPORT\_HAMMING}, or {\tt PGA\_REPORT\_STRING} to print the online
analysis, offline analysis, worst evaluation, average evaluation, Hamming
distance, or string itself, respectively.  {\tt PGASetPrintOptions} may be
called multiple times to specify multiple print options.


%*****************************************************************************
\section{Utility Functions}\label{sec:utility}
%*****************************************************************************

\subsection{Random Numbers}\label{subsec:random}

By default, \pga\ will seed its random number generator by using a value from the
system clock.  Therefore, each time \pga\ is run, a unique sequence of random
numbers will be used.  For debugging or reproducibility purposes, however, the
user may wish to use the same sequence of random numbers each time.  This may
be done using the function {\tt PGASetRandomSeed} to initialize the random
number generator with the same seed each time, for example, {\tt
PGASetRandomSeed(ctx,1)}.

{\tt PGARandom01(ctx,0)} will return a random number generated uniformly on
$[0,1]$.  If the second argument is not {\tt 0}, it will be used to reseed the
random number sequence. {\tt PGARandomFlip} flips a biased coin.  For example,
{\tt PGARandomFlip(ctx,.7)} will return {\tt PGA\_TRUE} approximately 70\% of
the time.  {\tt PGARandomInterval(-10,30)} will return an integer value
generated uniformly on $[-10,30]$.  {\tt PGARandomUniform} {\tt
(ctx,-50.,50.)} will return a real value generated uniformly randomly on the
interval [-50,50].  {\tt PGARandomGaussian} {\tt (ctx,0.,1.)} will return a
real value generated from a Gaussian distribution with mean zero and standard
deviation one.


\subsection{Print Functions}\label{subsec:print-functions}

{\tt PGAPrintPopulation(ctx,stdout,pop)} will print the evaluation function
value, fitness value, and string for each member of population {\tt pop} to
{\tt stdout}. This function may not be called until {\em after} {\tt PGASetUp}
has been called. {\tt PGAPrintContextVariable(ctx,stdout)} will print the
value of all fields in the context variable to {\tt stdout}.  {\tt
PGAPrintIndividual(ctx,stdout,p,pop)} will print the evaluation function
value, fitness value, and string of individual {\tt p} in population {\tt pop}
to {\tt stdout}.  {\tt PGAPrintString(ctx,stdout,p,pop)} will print the string
of individual {\tt p} in population {\tt pop} to {\tt stdout}.  {\tt
PGAPrintVersionNumber(ctx)} will print the \pga\ version number.


\subsection{Miscellaneous}\label{subsec:other}

{\tt PGAGetGAIterValue(ctx)} will return the current iteration of the GA.  {\tt
PGAGetBestIndex(ctx,pop)} ({\tt PGAGetWorstIndex}) will return the index of the most
(least) fit member of population {\tt pop}.

{\tt PGAUpdateOffline(ctx,pop)} ({\tt PGAUpdateOnline}) will update the offline
(online) analysis based on the new generation's results.  {\tt
PGAHammingDistance(ctx,pop)} returns a {\tt double}, which is the average
Hamming distance between the {\em binary} strings in population {\tt pop}.
The function call
\begin{verbatim}
PGAError(ctx, "popindex=", PGA_FATAL, PGA_INT, (void *)&popindex)
\end{verbatim}
will print the message ``popindex=-1'' (assuming the value of {\tt popindex}
is -1) and then exit \pga.  If the third argument had been {\tt PGA\_WARNING}
instead, execution would have continued.  In addition to {\tt PGA\_INT}, valid data
types are {\tt PGA\_DOUBLE}, {\tt PGA\_CHAR}, and {\tt PGA\_VOID}.


%*****************************************************************************
\section{Command-Line Arguments}\label{sec:cla}
%*****************************************************************************

\pga\ provides several  command-line arguments.
These are only available to C programs, although in some cases both C and
Fortran programs can achieve the equivalent functionality with function calls.
For example, {\tt PGAUsage(ctx)} provides the same functionality as the {\tt
-pgahelp} command line option.  See Chapter~\ref{chp:debug} for the function
call equivalents.

\begin{verbatim}
  -pgahelp            get this message
  -pgahelp   debug    list of debug options
  -pgadbg   <level>   set debug option
  -pgadebug <level>   set debug option
  -pgaversion         Print current PGAPack version number, parallel or
                      sequential, and debug or optimized
\end{verbatim}

%*****************************************************************************
\chapter{Explicit Usage}\label{chp:explicit}
%*****************************************************************************

This chapter discusses how the user may obtain greater control over the steps
of the GA by {\em not} using the {\tt PGARun} command, but instead calling the
data-structure-neutral functions directly.  One ramification of this is that
the {\tt PGARun} interface no longer masks some of the differences between
parallel and sequential execution.  The examples in this chapter are written
for sequential execution {\em only}.  Chapter~\ref{chp:parallel} shows how
they may be executed in parallel.


%*****************************************************************************
\section{Notation}
%*****************************************************************************

To understand the calling sequences of the functions discussed in
this chapter, one must know of the {\em existence} of certain data
structures and the user interface for accessing them.  It is {\em not}
necessary to know how these data structures are implemented, since that is
hidden by the user interface to \pga.

\pga\ maintains two populations: an {\em old} one and a {\em new} one.  The
size of each population is the value returned by {\tt PGAGetPopSize}.  In
addition, each population contains two temporary working locations.  The
string length is the value specified to {\tt PGACreate} and returned by {\tt
PGAGetStringLength}.

Formally, string $p$ in population $pop$ is referred to by the 2-tuple {\tt
(p,pop)} and the value of gene $i$ in that string by the 3-tuple {\tt
(i,p,pop)}.  In \pga, {\tt pop} {\em must} be one of the two symbolic
constants {\tt PGA\_OLDPOP} or {\tt PGA\_NEWPOP} to refer to the old or new
population, respectively.  At the end of each GA iteration, the function {\tt
PGAUpdateGeneration} makes sure these symbolic constants are remapped to the
correct population.  The string index {\tt p} must be either an integer
between 0 and $P-1$ (or 1 and $P$ in Fortran) or one of the symbolic constants
{\tt PGA\_TEMP1} or {\tt PGA\_TEMP2}, to reference one of the two temporary
locations, respectively.

%*****************************************************************************
\section{Simple Sequential Example}
%*****************************************************************************

The example in Figure~\ref{simple-example} is a complete \pga\ program that
does {\em not} use {\tt PGARun}.  It is an alternative way to write the main
program for the Maxbit example of Section~\ref{sec:simple-example}.  We refer
to it as a simple example because it uses {\tt PGARunMutationAndCrossover} to
encapsulate the recombination step.  The {\tt PGACreate} and {\tt PGASetUp}
functions were discussed in the last chapter.  {\tt PGASetUp} creates and
randomly initializes the initial population.  This population, referred to
initially by the symbolic constant {\tt PGA\_OLDPOP}, is evaluated by the {\tt
PGAEvaluate} function.  The third argument to {\tt PGAEvaluate} is the name of
the user's evaluation function.  The function prototype for {\tt evaluate}
must be as shown in Figure~\ref{simple-example} and discussed earlier in
Sections~\ref{sec:big-picture} and~ \ref{sec:evaluation}.  The {\tt
PGAFitness} function maps the user's evaluation function values into
fitness values.

The {\tt while} loop runs the genetic algorithm.  {\tt PGADone} returns {\tt
PGA\_TRUE} if any of the specified stopping criteria have been met, otherwise
{\tt PGA\_FALSE}.  {\tt PGASelect} performs selection on population {\tt
PGA\_OLDPOP}.  {\tt PGARunMutationAndCrossover} uses the selected strings to
create the new population by applying the crossover and mutation operators.
{\tt PGAEvaluate} and {\tt PGAFitness} evaluate and map to fitness values the
newly created population. {\tt PGAUpdateGeneration} updates the GA iteration
count and resets several important internal arrays (don't forget to call it!).
{\tt PGAPrintReport} writes out genetic algorithm statistics according to the
report options specified.  Note that the argument to {\tt PGAPrintReport} is
the old population, since after {\tt PGAUpdateGeneration} is called, the newly
created population is in {\tt PGA\_OLDPOP}.  Finally, {\tt PGADestroy}
releases any memory allocated by \pga\ when execution is complete.

The functions {\tt PGADone}, {\tt PGAUpdateGeneration}, and {\tt PGAEvaluate}
take an MPI communicator (see Appendix~\ref{app:par-background} and
Chapter~\ref{chp:parallel}) as an argument.  For {\em sequential} execution
the value {\tt NULL} should be specified for this argument.
A parallel, or sequential {\em and} parallel, version of this example is given
in Section~\ref{sec:par-explicit-usage}.

\begin{figure}
\begin{verbatim}
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop);

int main(int argc, char **argv)
{
    PGAContext *ctx; 

    ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
    PGASetUp   (ctx);
    PGAEvaluate(ctx, PGA_OLDPOP, evaluate, NULL);
    PGAFitness (ctx, PGA_OLDPOP);
    
    while(!PGADone(ctx, NULL)) {
        PGASelect                 (ctx, PGA_OLDPOP);
        PGARunMutationAndCrossover(ctx, PGA_OLDPOP, PGA_NEWPOP);
        PGAEvaluate               (ctx, PGA_NEWPOP, evaluate, NULL);
        PGAFitness                (ctx, PGA_NEWPOP);
        PGAUpdateGeneration       (ctx, NULL);
        PGAPrintReport            (ctx, stdout, PGA_OLDPOP);
    }
    PGADestroy(ctx);
    return(0);
}
\end{verbatim}
\caption{Simple Example of Explicit Usage}
\label{simple-example}
\end{figure}


%*****************************************************************************
\section{Complex Example}
%*****************************************************************************

\begin{figure}
\begin{verbatim}
#include "pgapack.h"
double evaluate(PGAContext *ctx, int p, int pop);

int main(int argc, char **argv)
{
    PGAContext *ctx; 
    int i, j, n, m1, m2, popsize, numreplace;
    double probcross;

    ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
    PGASetUp(ctx);
    probcross  = PGAGetCrossoverProb(ctx);
    popsize    = PGAGetPopSize(ctx);
    numreplace = PGAGetNumReplaceValue(ctx);
    PGAEvaluate(ctx, PGA_OLDPOP, evaluate, NULL);
    PGAFitness (ctx, PGA_OLDPOP          );
    
    while(!PGADone(ctx, NULL)) {
        PGASelect (ctx, PGA_OLDPOP);
        PGASortPop(ctx, PGA_OLDPOP);
        n = popsize - numreplace;
        for ( i=0; i < n; i++ ) {
            j = PGAGetSortedPopIndex(ctx, i);
            PGACopyIndividual(ctx, j, PGA_OLDPOP, i, PGA_NEWPOP);
        }
        while (n < popsize) { 
            m1 = PGASelectNextIndex(ctx);
            m2 = PGASelectNextIndex(ctx);        
            if(PGARandomFlip(ctx, probcross)) {
                PGACrossover(ctx, m1, m2, PGA_OLDPOP, PGA_TEMP1, PGA_TEMP2, PGA_NEWPOP);
                PGAMutate (ctx,PGA_TEMP1,PGA_NEWPOP);
                PGAMutate (ctx,PGA_TEMP2,PGA_NEWPOP);
                PGACopyIndividual (ctx,PGA_TEMP1,PGA_NEWPOP,n,  PGA_NEWPOP);
                PGACopyIndividual (ctx,PGA_TEMP2,PGA_NEWPOP,n+1,PGA_NEWPOP);
                n += 2;
            }
            else {
                PGACopyIndividual (ctx, m1, PGA_OLDPOP, n,   PGA_NEWPOP);
                PGACopyIndividual (ctx, m2, PGA_OLDPOP, n+1, PGA_NEWPOP);
                n += 2;
            }
        }
        PGAEvaluate(ctx, PGA_NEWPOP, evaluate, NULL);
        PGAFitness (ctx, PGA_NEWPOP);
        PGAPrintReport(ctx, stdout, PGA_NEWPOP);
        PGAUpdateGeneration(ctx, NULL);
    }
    PGADestroy(ctx);
    return 0;
}
\end{verbatim}
\caption{Example of Explicit Usage}
\label{complex-example}
\end{figure}

The primary difference between the ``complex'' example in
Figure~\ref{complex-example} and the ``simple'' example in
Figure~\ref{simple-example} is that the steps encapsulated by {\tt
PGARunMutationAndCrossover} have been written out explicitly.  The function
{\tt PGASortPop} sorts a population according to the criteria specified by
{\tt PGASetPopReplacementType} (Section~\ref{sec:population-replacement}).
The sorted indices are accessed via {\tt PGAGetSortedPopIndex}.  In the
example, the five lines that follow {\tt PGASortPop} copy the strings that are
not created by recombination from the old population to the new population.

The {\tt while} loop that follows creates the remainder of the new population.
{\tt PGASelectNextIndex} returns the indices of the strings selected by {\tt
PGASelect}.  {\tt PGARandomFlip} flips a coin biased by the crossover
probability to determine whether the selected strings should undergo crossover
and mutation or should be copied directly into the new population.  {\tt
PGACrossover} uses the parent strings {\tt m1} and {\tt m2} from population
{\tt PGA\_OLDPOP} to create two child strings in the temporary locations {\tt
PGA\_TEMP1} and {\tt PGA\_TEMP2} in {\tt PGA\_NEWPOP} population.

{\tt PGAMutate} mutates the child strings and {\tt PGACopyIndividual}, then
copies them into the new population.  If the strings do not undergo crossover
and mutation, they are copied into the new population unchanged.  The rest of
the steps are the same as those in Figure~\ref{simple-example}, {\em except}
that for illustrative purposes we call {\tt PGAPrintReport} {\em before} {\tt
PGAUpdateGeneration}.  In that case we use population {\tt PGA\_NEWPOP} as the
population pointer.

%*****************************************************************************
\section{Explicit \pga\ Functions}
%*****************************************************************************

This section briefly discusses other functions not shown in the previous
examples or discussed in Chapter~\ref{chp:functionality}.  Additional
information about these and other \pga\ functions is contained in
Appendix~\ref{chp:function-bindings} (function bindings) and the {\tt
./examples} directory.

{\tt PGARunMutationAndCrossover} and {\tt PGARunMutationOrCrossover} perform
the recombination step.  The former applies mutation to strings that undergo
crossover.  The latter applies only mutation to strings that did not undergo
crossover.

The restart operator described earlier in Section~\ref{sec:restart} can be
invoked explicitly with {\tt PGARestart(ctx, oldpop, newpop)}, where the best
string from population {\tt oldpop} is used to initialize population {\tt
newpop}.

{\tt PGADuplicate(ctx,p,PGA\_OLDPOP,PGA\_NEWPOP,20)} returns {\tt PGA\_TRUE}
if string {\tt p} in population {\tt PGA\_OLDPOP} is a duplicate of any of the
first 20 strings in population {\tt PGA\_NEWPOP}.  {\tt PGAChange(ctx, p,
PGA\_OLDPOP)} repeatedly applies the mutation operator to string {\tt p} in
population {\tt PGA\_OLDPOP} until at least one mutation has occurred.

In \pga\ three  values are associated with each string: (1) the user's
evaluation function value, (2) a Boolean flag to indicate whether the
evaluation function value is up to date with respect to the actual string, and
(3) the fitness value.  If {\tt PGARun} is not used, the user must manage
these values explicitly.

{\tt PGAEvaluate(ctx, PGA\_NEWPOP, evaluate, comm)} will execute the user's
evaluation function, {\tt evaluate}, on each string in population {\tt
PGA\_NEWPOP} that has changed (for example, from crossover) since its last
evaluation.  {\tt PGAEvaluate} will set both the evaluation function value and
associated Boolean flag automatically.  The argument {\tt comm} is an MPI
communicator.  Valid values are {\tt NULL} for an explicitly sequential
example, or any valid MPI communicator.  Depending on the number of processes
specified when the program was invoked, and the value of the {\tt comm}
argument, {\tt PGAEvaluate} may be run with one or more processes.  See
Chapter~\ref{chp:parallel} for further discussion.

{\tt PGAFitness} will calculate the population fitness values from the
evaluation function values.  It is an error to call {\tt PGAFitness} if {\em
all} the evaluation function values are not up to date.

These same three values may be read also.  {\tt PGAGetEvaluation(ctx, p,
PGA\_OLDPOP)} returns the evaluation function value. {\tt
PGAGetEvaluationUpToDateFlag(ctx, p, PGA\_OLDPOP)} returns {\tt PGA\_TRUE} or
{\tt PGA\_FALSE} to indicate whether the evaluation is up to date with the
actual string or not, respectively.  If \pga\ was compiled for debugging,{\tt
PGAGetEvaluation} will print a warning message if the evaluation is not up to
date.  {\tt PGAGetFitness(ctx, p, PGA\_OLDPOP)} returns the fitness value.

At times, (e.g., applying a hill-climbing function) the user may need to
explicitly set the evaluation function value and associated Boolean flag
(fitness values can be calculated {\em only} by calling {\tt PGAFitness}).
{\tt PGASetEvaluation(ctx, p, PGA\_OLDPOP, 123.4)} will set the evaluation
function value to 123.4 and the associated Boolean flag to {\tt PGA\_TRUE}.
The Boolean flag may be set independently with {\tt
PGASetEvaluationUpToDateFlag}.  For example, {\tt PGASetEvaluationUpToDateFlag
(ctx, p, PGA\_OLDPOP, PGA\_FALSE)} sets the status of the Boolean flag of
string {\tt p} in population {\tt PGA\_OLDPOP} to out of date.

{\tt PGAMean(ctx, a, n)} returns the mean of the {\tt n} values in array {\tt
a}. {\tt PGAStddev(ctx, a, n, mean)} returns the standard deviation of the
{\tt n} values in array {\tt a} whose mean is {\tt mean}.  {\tt PGARank(ctx,
p, order, n)} returns an index that is the rank of string p as given by the
sorted array {\tt order} of length {\tt n}.

{\tt PGAGetPrintFrequency(ctx)} returns the frequency with which GA statistics
are reported. {\tt PGAGetWorstIndex} {\tt (ctx, PGA\_OLDPOP)} returns the
index of the string in population {\tt PGA\_OLDPOP} with the worst evaluation
function value.  {\tt PGAGetBestIndex(ctx, PGA\_OLDPOP)} returns the index of
the string in population {\tt PGA\_OLDPOP} with the best evaluation function
value.


%*****************************************************************************
\chapter{Custom Usage: Native Data Types}\label{chp:custom1}
%*****************************************************************************

This chapter discusses how \pga\ may be extended by replacing some of the
standard \pga\ functions with user-defined functions for use with one of
\pga's four {\em native}  data types.  This can be done from both C and
Fortran. 

\section{Basics}

\begin{table}
\centering
\caption
{Customizeable Functions: Native Data Types\label{tab:custom-functions1} }
\begin{tabular}{|l|l|} \hline\hline
\multicolumn{1}{|c|}{Functionality} &
\multicolumn{1}{c|}{Symbolic Constant} \\ \hline
Initialization & {\tt PGA\_USERFUNCTION\_INITSTRING} \\
Crossover & {\tt PGA\_USERFUNCTION\_CROSSOVER} \\
Mutation & {\tt PGA\_USERFUNCTION\_MUTATION} \\
Duplicate Checking & {\tt PGA\_USERFUNCTION\_DUPLICATE} \\
String Printing & {\tt PGA\_USERFUNCTION\_PRINTSTRING} \\
Termination Criteria & {\tt PGA\_USERFUNCTION\_STOPCOND} \\
End of generation & {\tt PGA\_USERFUNCTION\_ENDOFGEN} \\ \hline
\end{tabular}
\end{table}

In \pga, high-level (data-structure-neutral) functions call
data-structure-specific functions that correspond to the data type used.  The
implementation uses function pointers that, by default, are set to the correct
values for the datatype used.  The user may change these defaults and set the
function pointers to execute their functions instead.  The functions the user
can substitute for are initialization, crossover, mutation, checking for
duplicate strings, string printing, termination criteria, and a generic
function called at the end of each GA iteration.

The function call {\tt PGASetUserFunction(ctx, PGA\_USERFUNCTION\_MUTATION,
mymute)} will cause
\pga\ to execute the function {\tt mymute} whenever the mutation operator is
called.  Table~\ref{tab:custom-functions1} is a list of functions that can be
customized for use with a native datatype.  The first column describes the
functionality, and the second column the symbolic constant for use with {\tt
PGASetUserFunction}.  The calling sequence for these functions is fixed and
{\em must} follow the function prototypes in Table~\ref{tab:custom-functions}.
The files {\tt ./examples/templates/uf\_native.c} and {\tt
./examples/templates/uf\_native.f} contain template routines for these
functions.  A specific example is given below.

Checking the termination criteria requires some discussion.  The function {\tt
PGADone} will {\em either} check to see if the standard stopping criteria (see
Section~\ref{sec:stopping-criteria}) have been met, or call the user function
specified by {\tt PGA\_USERFUNCTION\_STOPCOND}.  If you wish to have the user
function check for the  standard stopping criteria  in addition to whatever
else it does, it should call {\tt PGACheckStoppingConditions(ctx).}
Do {\em not} call {\tt PGADone} as this will cause an infinite loop to occur.
Note that in a parallel program {\tt PGACheckStoppingConditions} should only
be called by the master process (see Chapter~\ref{chp:parallel}).

The end of generation function (which is null by default) may be used for
gathering statistics about the GA, displaying custom output, etc.  This
function is called after all generational computation is complete, but before
the population pointers ({\tt PGA\_NEWPOP}, {\tt PGA\_OLDPOP}) have been
switched and the standard \pga\ output printed.  Therefore, be sure to use
{\tt PGA\_NEWPOP} as the population pointer.  There is no mechanism for
suppressing the standard \pga\ generational output.


\begin{table}
\centering
\caption
{
Calling Sequences for Customizable Functions\label{tab:custom-functions}
}
\begin{tabular}{|l|r|l|} \hline\hline
\multicolumn{1}{|c|}{Symbolic Constant} &
\multicolumn{1}{|c|}{Return} &
\multicolumn{1}{c|}{Function Prototype} \\ \hline
{\tt PGA\_USERFUNCTION\_INITSTRING}&{\tt void}&{\tt (PGAContext*, int, int)}\\
{\tt PGA\_USERFUNCTION\_CROSSOVER}&{\tt void}&{\tt (PGAContext*, int, int, int, int, int, int)}\\
{\tt PGA\_USERFUNCTION\_MUTATION}&{\tt int}&{\tt (PGAContext*, int, int, double)}\\
{\tt PGA\_USERFUNCTION\_DUPLICATE}&{\tt int}&{\tt (PGAContext*, int, int, int, int)}\\
{\tt PGA\_USERFUNCTION\_PRINTSTRING}&{\tt void}&{\tt (PGAContext*, FILE *, int, int)}\\
{\tt PGA\_USERFUNCTION\_STOPCOND}&{\tt int}&{\tt (PGAContext*)}\\
{\tt PGA\_USERFUNCTION\_ENDOFGEN}&{\tt void}&{\tt (PGAContext*)}\\
\hline
\end{tabular}
\end{table}


\section{Example Problem: C}

The example problem in Figure~\ref{example:maxbit-custom} is to maximize
$\sum_{j=1}^{L} x_{j}$ with $1 \leq x_j \leq L$, where $L$ is the string
length.  The optimal solution to this problem, $L^2$, is achieved by setting
each $x_j$ to $L$.  The files for this example, {\tt ./examples/maxint.c}
and {\tt ./examples/maxint.f}, contain template routines for these functions.

The example shows the use of a custom mutation function with an integer data
type.  The {\tt PGASetUserFunction} function specifies that this function,
{\tt MyMutation}, will be called when the mutation operator is applied, rather
than the default mutation operator.  {\tt MyMutation} generates a random
integer on the interval $[1,L]$.

\begin{figure}
\begin{verbatim}
#include <pgapack.h>

double evaluate (PGAContext *ctx, int p, int pop);
int myMutation  (PGAContext *ctx, int p, int pop, double pm);

int main( int argc, char **argv )
{
     PGAContext *ctx; 
     int i, maxiter;
     ctx = PGACreate (&argc, argv, PGA_DATATYPE_INTEGER, 10, PGA_MAXIMIZE);
     PGASetUserFunction      (ctx, PGA_USERFUNCTION_MUTATION, myMutation);
     PGASetIntegerInitPermute(ctx, 1, 10);
     PGASetUp                (ctx);
     PGARun                  (ctx, evaluate);
     PGADestroy              (ctx);
     return(0);
}
int myMutation(PGAContext *ctx, int p, int pop, double pm)
{
    int stringlen, i, k, count = 0;
    stringlen = PGAGetStringLength(ctx);
    for (i = 0; i < stringlen; i++)
    if (PGARandomFlip(ctx, pm)) {
        k = PGARandomInterval(ctx, 1, stringlen);
        PGASetIntegerAllele(ctx, p, pop, i, k);
        count++;
    }
    return ((double) count);
}
double evaluate(PGAContext *ctx, int p, int pop)
{
     int stringlen, i, sum = 0;
     stringlen = PGAGetStringLength(ctx);
     for (i = 0; i < stringlen; i++)
         sum += PGAGetIntegerAllele(ctx, p, pop, i);
     return ((double)sum);
}
\end{verbatim}
\caption{\pga\ C Example Using Custom Mutation Operator}
\label{example:maxbit-custom}
\end{figure}

\section{Example Problem: Fortran}

Figure~\ref{example:maxbit-custom-f77} is the same example as in 
Figure~\ref{example:maxbit-custom} written in Fortran.

\begin{figure}
\begin{verbatim}
      include 'pgapackf.h'
      include 'mpif.h'
      double precision evaluate
      integer          myMutation
      external         evaluate, myMutation
      integer ctx, i, maxiter, ierror
      call MPI_Init(ierror)
      ctx = PGACreate (PGA_DATATYPE_INTEGER, 10, PGA_MAXIMIZE)
      call PGASetUserFunction      (ctx, PGA_USERFUNCTION_MUTATION,
     &     myMutation)
      call PGASetIntegerInitPermute(ctx, 1, 10);
      call PGASetUp                (ctx);
      call PGARun                  (ctx, evaluate);
      call PGADestroy              (ctx);
      call MPI_Finalize(ierror)
      stop
      end
      
      integer function myMutation(ctx, p, pop, pm)
      include          'pgapackf.h'
      integer           ctx, p, pop
      double precision  pm
      integer           stringlen, i, k, count
      count = 0
      stringlen = PGAGetStringLength(ctx)
      do i=0, stringlen
         if (PGARandomFlip(ctx, pm) .eq. PGA_TRUE) then
            k = PGARandomInterval(ctx, 1, stringlen)
            call PGASetIntegerAllele(ctx, p, pop, i, k)
            count = count + 1
         endif
      enddo
      myMutation = count
      return
      end

      double precision function evaluate(ctx, p, pop)
      include      'pgapackf.h'
      integer ctx, p, pop
      integer       stringlen, i, sum
      sum = 0
      stringlen = PGAGetStringLength(ctx)
      do i=0, stringlen
         sum = sum + PGAGetIntegerAllele(ctx, p, pop, i)
      enddo
      evaluate = sum
      return
      end
\end{verbatim}
\caption{\pga\ Fortran Example Using Custom Mutation Operator}
\label{example:maxbit-custom-f77}
\end{figure}

%*****************************************************************************
\chapter{Custom Usage: New Data Types}\label{chp:new-data}
%*****************************************************************************

This chapter discusses how \pga\ may be extended by defining a new data type.
Defining a new data type may be done  only in C programs.

\section{Basics}

\begin{table}
\centering
\caption
{
Functions Required for New Data Types\label{tab:new-functions}
}
\begin{tabular}{|l|l|} \hline\hline
\multicolumn{1}{|c|}{Functionality} &
\multicolumn{1}{c|}{Symbolic Constant} \\ \hline
Memory allocation & {\tt PGA\_USERFUNCTION\_CREATESTRING} \\
String packing & {\tt PGA\_USERFUNCTION\_BUILDDATATYPE} \\
Mutation & {\tt PGA\_USERFUNCTION\_MUTATION} \\
Crossover & {\tt PGA\_USERFUNCTION\_CROSSOVER} \\
String printing & {\tt PGA\_USERFUNCTION\_PRINTSTRING} \\
String copying & {\tt PGA\_USERFUNCTION\_COPYSTRING} \\
Duplicate checking & {\tt PGA\_USERFUNCTION\_DUPLICATE} \\
\hline
\end{tabular}
\end{table}

To create a new data type, you must (1) specify {\tt PGA\_DATATYPE\_USER} for
the datatype in the {\tt PGACreate} call and (2) for {\em each} entry in
Table~\ref{tab:new-functions}, call {\tt PGASetUserFunction} to specify the
function that will perform the given operation on the new data type.  If the
data type is {\tt PGA\_DATATYPE\_USER}, the string length specified to {\tt
PGACreate} can be whatever the user desires.  It will be returned by {\tt
PGAGetStringLength} but is not otherwise used in the data-structure-neutral
functions of \pga.

The calling sequences for the functions in Table~\ref{tab:new-functions} are
given in Table~\ref{tab:new-functions1}.  The file {\tt
./examples/templates/uf\_new.c} contains template routines for these functions.

\begin{table}
\centering
\caption
{
Calling Sequences for New Data Type Functions\label{tab:new-functions1}
}
\begin{tabular}{|l|r|r|} \hline\hline
\multicolumn{1}{|c|}{Symbolic Constant} &
\multicolumn{1}{|c|}{Return} &
\multicolumn{1}{c|}{Function Prototype} \\ \hline
{\tt PGA\_USERFUNCTION\_CREATESTRING}&{\tt void}&{\tt (PGAContext*, int, int, int)}\\
{\tt PGA\_USERFUNCTION\_BUILDDATATYPE}&{\tt int}&{\tt (PGAContext*, int, int)}\\
{\tt PGA\_USERFUNCTION\_MUTATION}&{\tt int}&{\tt (PGAContext*, int, int, double)}\\
{\tt PGA\_USERFUNCTION\_CROSSOVER}&{\tt void}&{\tt (PGAContext*, int, int, int, int, int, int)}\\
{\tt PGA\_USERFUNCTION\_PRINTSTRING}&{\tt void}&{\tt (PGAContext*, FILE *, int, int)}\\
{\tt PGA\_USERFUNCTION\_COPYSTRING}&{\tt int}&{\tt (PGAContext*, int, int,
int, int)}\\
{\tt PGA\_USERFUNCTION\_DUPLICATE}&{\tt int}&{\tt (PGAContext*, int, int, int, int)}\\
\hline
\end{tabular}
\end{table}

While \pga\ requires that the user supply all the functions in
Table~\ref{tab:new-functions}, your program may not require the functionality
of all of them.  For example, the user really does not need to write a
function to pack the strings for message-passing unless a parallel version of
\pga\ is being used.  In these cases, we
suggest that the user supply a stub function; i.e., a function with the
correct calling sequence but no functionality.


\section{Example Problem}

\begin{figure}
\begin{verbatim}
#include <pgapack.h>

double       energy           (double *, int *);
double       Evaluate         (PGAContext *, int, int);
void         CreateString     (PGAContext *, int, int, int);
int          Mutation         (PGAContext *, int, int, double);
void         Crossover        (PGAContext *, int, int, int, int, int, int);
void         WriteString      (PGAContext *, FILE *, int, int);
void         CopyString       (PGAContext *, int, int, int, int);
int          DuplicateString  (PGAContext *, int, int, int, int);
MPI_Datatype BuildDT          (PGAContext *, int, int);

typedef struct {
    double t[6];          /* ligand translation and rotation */
    int    sc[40];        /* ligand sidechain rotations      */
} ligand;

int main(int argc, char **argv) {
    PGAContext *ctx;
    int maxiter;
    ctx = PGACreate(&argc, argv, PGA_DATATYPE_USER, 46, PGA_MINIMIZE);
    PGASetRandomSeed    (ctx, 1);
    PGASetMaxGAIterValue(ctx, 5000);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_CREATESTRING,  CreateString);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_MUTATION,      Mutation);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_CROSSOVER,     Crossover);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_PRINTSTRING,   WriteString);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_COPYSTRING,    CopyString);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_DUPLICATE,     DuplicateString);
    PGASetUserFunction  (ctx, PGA_USERFUNCTION_BUILDDATATYPE, BuildDT);
    PGASetUp            (ctx);
    PGARun              (ctx, Evaluate);
    PGADestroy          (ctx);
    return (0);
}
\end{verbatim}
\caption{Main Program for Structure Data Type}
\label{example1:new-datatype-main}
\end{figure}

This example illustrates use of a user-defined structure as the new data type.
The problem is one of molecular docking where one protein molecule (the
ligand) is to be docked into a second, target protein molecule.
Figure~\ref{example1:new-datatype-main} contains the function prototypes for
each function that will operate on the new datatype, the definition of the
user's structure ({\tt ligand}), and the main program.

The first three {\tt doubles} of the array {\tt t} in structure {\tt ligand}
represent the translation of the ligand molecule in the $x$-, $y$-, and
$z$-axes, respectively.  The last three {\tt doubles} in the array {\tt t}
represent the rotation of the ligand molecule about each of the axes.  The
{\tt int}s in the {\tt sc} array represent side chain rotations (which are
discrete) of the ligand molecule.

% The appropriate symbolic constant is given as an argument to {\tt
% PGASetUserFunction} to specify these functions.
% The cast before each function is because the
% third argument to {\tt PGASetUserFunction} is a void pointer.
% Next, the structure that is the new data type is defined.  The value 46, the
% total number of variables in the structure, is specified to {\tt PGACreate}.


\begin{figure}
\begin{verbatim}
void CreateString(PGAContext *ctx, int p, int pop, int InitFlag) {
    int i;
    ligand *ligand_ptr;
    PGAIndividual *new;

    new = PGAGetIndividual(ctx, p, pop);
    if (!(new->chrom = malloc(sizeof(ligand)))) {
        fprintf(stderr, "No room for new->chrom");
        exit(1);
    }
    ligand_ptr = (ligand *)new->chrom;
    if (InitFlag) {
        for (i = 0; i < 3; i++)
            ligand_ptr->t[i] = PGARandom01(ctx, 0) * 20.0 - 10.0;
        for (i = 3; i < 6; i++)
            ligand_ptr->t[i] = PGARandom01(ctx, 0) * 6.28 - 3.14;
        for (i = 0; i < 40; i++)
            ligand_ptr->sc[i] = PGARandomInterval(ctx, -20, 20);
    } else {
        for (i = 0; i < 6; i++)
            ligand_ptr->t[i] = 0.0;
        for (i = 0; i < 40; i++)
            ligand_ptr->sc[i] = 0;
    }
}
\end{verbatim}
\caption{Creation and Initialization Function for Structure Data Type}
\label{example1:new-datatype-create}
\end{figure}


Figure~\ref{example1:new-datatype-create} contains the function {\tt
CreateString} that allocates and initializes the ligand structure.  At this
level of usage it is no longer always possible to maintain the {\tt (p,pop)}
abstraction to specify an individual (a string and associated fields).  {\tt
CreateString} works directly with the string pointer that {\tt
(p,pop)} is mapped to.  If {\tt InitFlag} is true, {\tt CreateString} will
initialize the fields; otherwise they are set to 0.

{\tt PGAGetIndividual(ctx, p, pop)} returns a pointer of type {\tt
PGAIndividual} to the individual (the string and associated fields) specified
by {\tt (p,pop)}.  {\tt PGAIndividual} is a structure, one of the fields of
which is {\tt chrom}, a {\tt void} pointer to the string itself. That pointer,
{\tt new->chrom}, is assigned the address of the memory allocated by
the {\tt malloc} function.  As {\tt malloc} returns a {\tt void} pointer, no
cast is necessary.

The value of {\tt InitFlag} is passed by \pga\ to the user's string creation
routine. It specifies whether to randomly initialize the string or set it to
zero. By default, {\tt PGA\_OLDPOP} (except for {\tt PGA\_TEMP1} and {\tt
PGA\_TEMP1} which are set to zero) is randomly initialized, and {\tt
PGA\_NEWPOP} is set to zero.  This choice may be changed with the {\tt
PGASetRandomInitFlag} function discussed in Section~\ref{sec:initialization}.)


\begin{figure}
\begin{verbatim}
int Mutation(PGAContext *ctx, int p, int pop, double mr) {
    ligand *ligand_ptr;
    int i, count = 0;

    ligand_ptr = (ligand *)PGAGetIndividual(ctx, p, pop)->chrom;
    for (i = 0; i < 6; i++)
        if (PGARandomFlip(ctx, mr)) {
            if (PGARandomFlip(ctx, 0.5))
                ligand_ptr->t[i] += 0.1*ligand_ptr->t[i];
            else
                ligand_ptr->t[i] -= 0.1*ligand_ptr->t[i];
            count++;
        }
    for (i = 0; i < 40; i++)
        if (PGARandomFlip(ctx, mr)) {
            if (PGARandomFlip(ctx, 0.5))
                ligand_ptr->sc[i] += 1;
            else
                ligand_ptr->sc[i] -= 1;
            count++;
        }
    return (count);
}
\end{verbatim}
\caption{Mutation for Structure Data Type}
\label{example1:new-datatype-mutation}
\end{figure}

Figure~\ref{example1:new-datatype-mutation} contains the mutation function
{\tt Mutation} for the ligand data type.  Each of the 46 genes has a
probability of {\tt mr} of being changed.  If a mutation occurs, {\tt
Mutation} adds or subtracts one tenth to the existing value of a {\tt double},
and adds or subtracts one to an {\tt int}.


\begin{figure}
\begin{verbatim}
void Crossover(PGAContext *ctx, int p1, int p2, int pop1, int t1, int t2,
               int pop2) {
    int i;
    ligand *parent1, *parent2, *child1, *child2;
    double pu;

    parent1 = (ligand *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    parent2 = (ligand *)PGAGetIndividual(ctx, p2, pop1)->chrom;
    child1  = (ligand *)PGAGetIndividual(ctx, t1, pop2)->chrom;
    child2  = (ligand *)PGAGetIndividual(ctx, t2, pop2)->chrom;

    pu = PGAGetUniformCrossoverProb(ctx);

    for (i = 0; i < 6; i++)
            if (PGARandomFlip(ctx, pu)) {
                child1->t[i] = parent1->t[i];
                child2->t[i] = parent2->t[i];
            } else {
                child1->t[i] = parent2->t[i];
                child2->t[i] = parent1->t[i];
            }
    for (i = 0; i < 40; i++)
            if (PGARandomFlip(ctx, pu)) {
                child1->sc[i] = parent1->sc[i];
                child2->sc[i] = parent2->sc[i];
            } else {
                child1->sc[i] = parent2->sc[i];
                child2->sc[i] = parent1->sc[i];
            }
}
\end{verbatim}
\caption{Crossover for Structure Data Type}
\label{example1:new-datatype-crossover}
\end{figure}

Figure~\ref{example1:new-datatype-crossover} contains the crossover function
{\tt Crossover}, which implements uniform crossover for the ligand data type.
The lines
\begin{verbatim}
    parent1 = (ligand *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    parent2 = (ligand *)PGAGetIndividual(ctx, p2, pop1)->chrom;
    child1  = (ligand *)PGAGetIndividual(ctx, t1, pop2)->chrom;
    child2  = (ligand *)PGAGetIndividual(ctx, t2, pop2)->chrom;
\end{verbatim}
are worthy of  mention.  Each implements in one line what the two lines 
\begin{verbatim}
    new = PGAGetIndividual(ctx, p, pop);
    string = (ligand *)new->chrom;
\end{verbatim}
in {\tt Mutation} did.  Either style is acceptable.  {\tt PGAGetIndividual}
returns a pointer whose {\tt chrom} field (a {\tt void} pointer) is cast to
the {\tt ligand} data type.

\begin{figure}
\begin{verbatim}
int DuplicateString(PGAContext *ctx, int p1, int pop1, int p2, int pop2) {
    void *a, *b;

     a = PGAGetIndividual(ctx, p1, pop1)->chrom;
     b = PGAGetIndividual(ctx, p2, pop2)->chrom;
     return (!memcmp(a, b, sizeof(ligand)));
}
\end{verbatim}
\caption{Duplicate Testing for Structure Data Type}
\label{example1:new-datatype-duplicate}
\end{figure}

Figure~\ref{example1:new-datatype-duplicate} contains the code for {\tt
DuplicateString}, which checks for duplicate ligand structures.  It uses the
ANSI C {\tt memcmp} function for this purpose.

\begin{figure}
\begin{verbatim}
double Evaluate(PGAContext *ctx, int p, int pop) {
    int i, j;
    double x[6];
    int sc[40];
    PGAIndividual *ind;
    ligand *lig;

    lig = (ligand *)PGAGetIndividual(ctx, p, pop)->chrom;
    for (i = 0; i < 6; i++)
        x[i] = lig->t[i];
    for (i = 0; i < 40; i++)
        sc[i] = lig->sc[i];
    return ( energy(x,sc) );
}
\end{verbatim}
\caption{Evaluation Function for Structure Data Type}
\label{example1:new-datatype-evaluate}
\end{figure}

Figure~\ref{example1:new-datatype-evaluate} contains the evaluation function
for this example.  It again uses {\tt PGAGetIndividual} to map {\tt (p, pop)}
into a pointer to the string of interest.  For user data types, \pga\ does
{\em not} provide a {\tt PGAGetUserAllele} function, so access to the allele
values is made directly through the pointer.

\begin{figure}
\begin{verbatim}
MPI_Datatype BuildDT(PGAContext *ctx, int p, int pop) {
  int             counts[5];
  MPI_Aint        displs[5];
  MPI_Datatype    types[5];
  MPI_Datatype    DT_PGAIndividual;
  PGAIndividual  *P;
  ligand         *S;

  P = PGAGetIndividual(ctx, p, pop);
  S = (ligand *)P->chrom;

  /*  Build the MPI datatype.  Every user defined function needs these.
   *  The first two calls are stuff that is internal to PGAPack, but 
   *  the user still must include it.  See pgapack.h for details one the
   *  fields (under PGAIndividual)
   */
  MPI_Address(&P->evalfunc, &displs[0]);
  counts[0] = 2;
  types[0]  = MPI_DOUBLE;

  /*  Next, we have an integer, evaluptodate.  */  
  MPI_Address(&P->evaluptodate, &displs[1]);
  counts[1] = 1;
  types[1]  = MPI_INT;

  /*  Finally, we have the actual user-defined string.  */
  MPI_Address(S->t, &displs[2]);
  counts[2] = 6;
  types[2]  = MPI_DOUBLE;

  MPI_Address(S->sc, &displs[3]);
  counts[3] = 40;
  types[3]  = MPI_INT;

  MPI_Type_struct(4, counts, displs, types, &DT_PGAIndividual);
  MPI_Type_commit(&DT_PGAIndividual);
  return(DT_PGAIndividual);
}
\end{verbatim}
\caption{Message Packing Function for Structure Data Type}
\label{example1:new-datatype-build}
\end{figure}

Figure~\ref{example1:new-datatype-build} contains the function {\tt BuildDT}
that builds an MPI datatype for sending strings to other processors.  Consult
an MPI manual for further information.


%*****************************************************************************
\chapter{Hill-Climbing and Hybridization}\label{chp:hill-climbing}
%*****************************************************************************

Hill-climbing heuristics attempt to improve a solution by moving to a better
{\em neighbor} solution.  Whenever the neighboring solution is better than the
current solution, it replaces the current solution.  Genetic algorithms and
hill-climbing heuristics have complementary strong and weak points.  GAs are
good at finding promising areas of the search space, but not as good at
fine-tuning within those areas.  Hill-climbing heuristics, on the other
hand, are good at fine-tuning, but lack a global perspective.  Practice has
shown that a {\em hybrid} algorithm that combines GAs with hill-climbing
heuristics often results in an algorithm that can outperform either one
individually.

There are two general schemes for creating hybrid algorithms.  The simplest is
to run the genetic algorithm until it terminates and then apply a
hill-climbing heuristic to each (or just the best) string.  The second
approach is to integrate a hill-climbing heuristic with the genetic algorithm.
Choices to be made in the second case include how often to apply the
hill-climbing heuristic and how many strings in the population to apply it to.


\pga\ supports hybrid schemes in the following ways:
\begin{itemize}
\item By passing, the context variable as a parameter to the user's
hill-climbing function, the user has access to solution and parameter values,
debug flags, and other information.
\item The functions {\tt PGAGetBinaryAllele}, {\tt PGAGetIntegerAllele},
{\tt PGAGetRealAllele}, and {\tt PGAGetCharacterAllele} allow the user's 
hill-climbing function to read allele values, and the functions {\tt
PGASetBinaryAllele}, {\tt PGASetIntegerAllele}, {\tt PGASetRealAllele}, and
{\tt PGASetCharacterAllele} allow the user's hill-climbing function to set
allele values explicitly.
\item The functions
{\tt PGADecodeRealAsBinary}, {\tt PGADecodeRealAsGrayCode}, {\tt
PGADecodeIntegerAsBinary}, and {\tt PGADecodeIntegerAsGrayCode} allow the
user's hill-climbing function to read integer or real numbers encoded as
binary or Gray code strings.
\item The functions
{\tt PGAEncodeRealAsBinary}, {\tt PGAEncodeRealAsGrayCode}, {\tt
PGAEncodeIntegerAsBinary}, and {\tt PGAEncodeIntegerAsGrayCode} allow the
user's hill-climbing function to encode integer or real numbers as binary or
Gray code strings.
\item The functions {\tt PGAGetEvaluation} and {\tt PGASetEvaluation} allow the
user's hill-climbing function to get and set evaluation function values, and
{\tt PGASetEvaluationUpToDateFlag} and {\tt PGAGetEvaluationUpToDateFlag} to get and set the flag
that indicates whether an evaluation function value is up to date.
\end{itemize}

One way to run a hybrid GA and use {\tt PGARun} is to use the {\tt
PGASetUserFunction} discussed in Chapter~\ref{chp:custom1} to specify a user
function to be called at the end of each GA iteration.  A more flexible
approach would be for the user to call the high-level \pga\ functions, and
their hillclimber to explicitly specify the steps of the hybrid GA.

Figure~\ref{example:hill} is a version of the Maxbit problem given in
Section~\ref{sec:simple-example}.  It uses the hill-climbing function {\tt
hillclimb}, which is called after the recombination step.  It randomly selects
a gene to set to one.  Note the {\tt PGASetEvaluationUpToDateFlag} call.  It
sets the flag that indicates the evaluation function is not current with the
string (since the string was changed).  It is {\em critical} that this flag be
set when the user changes a string, since the value of this flag
determines whether {\tt PGAEvaluate} will invoke the user's function
evaluation routine.

\begin{figure}[th]
\begin{verbatim}
#include "pgapack.h"

double evaluate(PGAContext *, int, int);
void hillclimb (PGAContext *, int);

int main(int argc, char **argv)
{
     PGAContext *ctx;

     ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
     PGASetUp   (ctx);
     PGAEvaluate(ctx, PGA_OLDPOP, evaluate, NULL);  
     PGAFitness (ctx, PGA_OLDPOP);
     while(!PGADone(ctx, NULL)) {
         PGASelect                 (ctx, PGA_OLDPOP);
         PGARunMutationAndCrossover(ctx, PGA_OLDPOP, PGA_NEWPOP);
         hillclimb                 (ctx, PGA_NEWPOP);
         PGAEvaluate               (ctx, PGA_NEWPOP, evaluate, NULL);
         PGAFitness                (ctx, PGA_NEWPOP);
         PGAUpdateGeneration       (ctx, NULL);
         PGAPrintReport            (ctx, stdout, PGA_OLDPOP);
     }
     PGADestroy(ctx);
     return 0;
}

void hillclimb(PGAContext *ctx, int pop)
{
     int i, p, popsize, stringlen;
     popsize   = PGAGetPopSize(ctx);
     stringlen = PGAGetStringLength(ctx);
     for (p=0; p<popsize; p++) {
         i = PGARandomInterval(ctx, 0, stringlen-1);
         PGASetBinaryAllele   (ctx, p, pop, i, 1);
         PGASetEvaluationUpToDateFlag   (ctx, p, pop, PGA_FALSE);
     }
}
\end{verbatim}
\caption{Hill-Climbing Heuristic for Maxbit Example}\label{example:hill}
\end{figure}

%*****************************************************************************
\chapter{Parallel Aspects}\label{chp:parallel}
%*****************************************************************************

This chapter assumes familiarity with the background material in
Appendix~\ref{app:par-background}.  It also assumes that a parallel version of
\pga\ was built and that programs are linked with
an MPI library (see Section~\ref{sec:install}).

Version 1.0 of \pga\ supports parallel and sequential {\em implementations} of
the single population global model (GM).  The parallel implementation uses a
master/slave algorithm in which one process, the {\em master}, executes all
steps of the genetic algorithm {\em except} the function evaluations.  The
function evaluations are executed by the {\em slave} processes\footnote{In the
special case of exactly two processes, the master executes function
evaluations as well.}.

\section{Basic Usage}\label{sec:par-basic-usage}

Both sequential and parallel versions of \pga\ may be run by using {\tt
PGARun}.  The choice of sequential or parallel execution depends on the number
of processes specified when the program is started.  If one process is
specified, the sequential implementation of the GM is used (even in a parallel
version of
\pga).  If two or more processes are specified, the parallel implementation of
the GM is used.  The examples in Chapter~\ref{chp:examples} can all be run in
parallel by specifying more than one process at startup.

The specification of the number of processors is done at run time.  The actual
format of the specification depends on the MPI implementation and computer
used (see Appendix~\ref{app:par-background} for some examples).  {\tt PGARun}
uses the default MPI communicator, {\tt MPI\_COMM\_WORLD}.  This specifies
that all processes specified at startup participate in the computation: one as
the master process, the others as slave processes.  A different communicator
may be specified with {\tt PGASetCommunicator(ctx, comm)}, where {\tt comm} is
an MPI communicator.

{\tt PGARun} is really a ``wrapper'' function that calls {\tt PGARunGM} with
the {\tt MPI\_COMM\_WORLD} communicator.  The user may call {\tt PGARunGM}
directly, that is, {\tt PGARunGM(ctx,evaluate,MPI\_COMM\_WORLD)} where {\tt
evaluate} is the name of the user's evaluation function and the third argument
is an MPI communicator.  Note that the communicator specified by {\tt
PGASetCommunicator} does {\em not} affect {\tt PGARunGM}.

\section{Explicit Use}\label{sec:par-explicit-usage}

In general, explicit use of the parallel features is more complicated than in
the case of sequential functions.  This is because the user's program must
coordinate the execution threads of {\em multiple} processes.  {\tt PGARunGM}
encapsulates all that is necessary into one routine, and parts of its source
code may serve as a useful starting point if one wishes to develop an
explicitly parallel program.  The parallel functions in \pga\ may be viewed as
a hierarchy with {\tt PGARun} and {\tt PGARunGM} at the top of the hierarchy,
{\tt PGAEvaluate} next, {\tt PGASendIndividual}, {\tt PGAReceiveIndividual},
and {\tt PGASendReceiveIndividual} next, and {\tt PGABuildDatatype} at the
bottom of the hierarchy.

{\tt PGAGetRank(ctx,comm)} returns the rank of the process in communicator
{\tt comm}.  If {\tt comm} is {\tt NULL} it returns 0. {\tt
PGAGetNumProcs(ctx,comm)} returns the number of processes in communicator {\tt
comm}.  If {\tt comm} is {\tt NULL} it returns 1.

The type of algorithm used to execute {\tt PGAEvaluate(ctx,pop,f,comm)} will
depend on the number of processes in the communicator {\tt comm}.  If it is
{\tt NULL} or contains one process, a sequential implementation will be used.
If more than one process is specified it will execute a master/slave
evaluation of the strings in population {\tt pop} that require evaluation by
applying, {\tt f}, the user's evaluation function.  {\tt PGAEvaluate} should
be called by {\em all} processes in communicator {\tt comm}.

{\tt PGASendIndividual(ctx,p,pop,dest,tag,comm)} will send string {\tt p} in
population {\tt pop} to process {\tt dest}.  {\tt tag} is a tag used to
identify the message, and {\tt comm} is an MPI communicator. This function
calls {\tt MPI\_Send} to perform the actual message passing.  In addition to
string {\tt p} itself, the evaluation function value, fitness function value,
and evaluation status flag are also sent.
 

{\tt PGAReceiveIndividual} is the complementary function to {\tt
PGASendIndividual}.  For example, {\tt PGAReceiveIndividual} {\tt
(ctx,p,pop,source,tag,comm,status)} will store in location {\tt p} in
population {\tt pop} the string and fields of the individual sent from process
{\tt source} with the MPI tag {\tt tag} and MPI communicator {\tt comm}.  {\tt
status} is an MPI status vector.


{\tt PGASendReceiveIndividual} combines the functionality of {\tt
PGASendIndividual} and {\tt PGAReceiveIndividual}.  This may be useful in
avoiding potential deadlock on some systems.  For example, {\tt
PGASendReceiveIndividual} {\tt (ctx,sp,spop,dest,stag,rp,rpop,source,
rtag,comm,status)}.  Here, {\tt sp} is the index of the string in population
{\tt spop} to send to process {\tt dest} with tag {\tt stag}.  The string
received from process {\tt source} with tag {\tt rtag} is stored in location
{\tt rp} in population {\tt rpop}.  {\tt comm} and {\tt status} are the same
as defined earlier.

{\tt PGABuildDatatype(ctx,p,pop)} packs together the string and fields that
{\tt PGASendIndividual}, {\tt PGAReceiveIndividual}, and {\tt
PGASendReceiveIndividual} send and receive.  The result is of type {\tt
MPI\_Datatype}.
 

\section{Example}\label{sec:par-example}

Figure~\ref{simple-parexample} is a parallel version of the example in
Figure~\ref{simple-example}.  Since we now have {\em multiple} processes
executing the program at the same time, we must coordinate each ones
execution.  In the example, the master process (the one with rank 0 as
determined by {\tt PGAGetRank}) executes all functions, and the slave
processes execute only those functions that take a communicator as an
argument.  Note that this example will execute correctly even if only one
process is in the communicator.

\begin{figure}
\begin{verbatim}
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop);

int main(int argc, char **argv)
{
    PGAContext *ctx;
    int rank;

    ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
    PGASetUp   (ctx);
    rank = PGAGetRank(ctx, MPI_COMM_WORLD);
    PGAEvaluate(ctx, PGA_OLDPOP, evaluate, MPI_COMM_WORLD);
    if ( rank == 0 )
        PGAFitness (ctx, PGA_OLDPOP);
    while(!PGADone(ctx, MPI_COMM_WORLD)) {
        if ( rank == 0 ) {
            PGASelect                 (ctx, PGA_OLDPOP);
            PGARunMutationAndCrossover(ctx, PGA_OLDPOP, PGA_NEWPOP);
        }
        PGAEvaluate(ctx, PGA_OLDPOP, evaluate, MPI_COMM_WORLD);
        if ( rank == 0 )
            PGAFitness                (ctx, PGA_NEWPOP);
        PGAUpdateGeneration           (ctx, MPI_COMM_WORLD);
        if ( rank == 0 )
            PGAPrintReport            (ctx, stdout, PGA_OLDPOP);
    }
    PGADestroy(ctx);
    return(0);
}
\end{verbatim}
\caption{Simple Parallel Example of Explicit Usage}
\label{simple-parexample}
\end{figure}



\section{Performance}\label{sec:par-performance}

The parallel implementation of the GM will produce the {\em same} result as
the sequential implementation, usually faster.  However, the parallel
implementation varies with the number of processes.  If two processes are
used, both the master process and the slave process will compute the function
evaluations.  If more than two processes are used, the master is responsible
for bookkeeping only, and the slaves for executing the function evaluations.
% Therefore, the performance of the parallel implementation using two processes
% is approximately equivalent to the sequential implementation using one
% process.  In fact, it will probably be somewhat slower, since the master
% process must distribute and collect information on the function evaluations
% to be performed by the slave process.
In general, the speedup obtained will vary with the amount of computation
associated with a function evaluation and the computational overhead of
distributing and collecting information to and from the slave processes.

The speedup that can be achieved with the master/slave model is limited by the
number of function evaluations that can be executed in parallel.  This number
depends on the population size and the number of new strings created each
generation.  For example, if the population size is 100 and a 100 new strings
are created each GA generation, then up to 100 processors can be put to
effective use to run the slave processes.  However, with the default rule of
replacing only 10\% of the population each GA generation, only 10 processors
can be used effectively.



%*****************************************************************************
\chapter{Fortran Interface}\label{chp:fortran}
%*****************************************************************************

\pga\ is written entirely in ANSI C.  A set of interface functions, also
written in C, is designed to be called by Fortran programs and then call the
``real'' C routine.  This mechanism provides  most of
\pga's functionality to Fortran programs.  The following list contains most
major differences between C and Fortran.  Additional, machine-specific
idiosyncrasies are noted in Appendix~\ref{chp:start-up}.

\begin{itemize}

\item The {\tt Makefile}s for the Fortran examples (in {\tt
./examples/fortran} and {\tt ./examples/mgh}) are {\em not} configured to use
the -I mechanism for specifying the include file search path (since not all
Fortran compilers support this).  Therefore, you will need to copy or set up a
symbolic link to {\tt ./include/pgapackf.h} from the directory you are
compiling a Fortran program in.

\item The context variable is declared {\tt integer} 
(or {\tt integer*8}, see Appendix~\ref{chp:start-up})
in Fortran.

\item {\tt PGACreate} takes only three arguments in Fortran (not {\tt argc} or
{\tt argv} as in C).

\item The Fortran include file is {\tt pgapackf.h} and should be included in
any Fortran subroutine or function that calls a \pga\ function, to ensure
correct typing and definition of functions and symbolic constants.

\item If a C function returns an \{ {\tt int}, {\tt double}, pointer\},
the corresponding Fortran function returns an \{ {\tt integer}, {\tt double
precision}, {\tt integer}\}.  If the C function is {\tt void} it is implemented
as a Fortran subroutine.

\item When supplying function arguments, a C {\tt int} corresponds to
a Fortran {\tt integer}, and a C {\tt double} corresponds to a Fortran {\tt
double precision}.
For example, to set the
crossover probability to 0.6, use\\
{\tt call PGASetCrossoverProb(ctx, 0.6d0)},\\
or\\
{\tt double precision pc}\\
{\tt pc = 0.6}\\
{\tt call PGASetCrossoverProb(ctx, pc)}

\item Gene indices are $[0,L-1]$ in C, and $[1,L]$ in Fortran, where $L$ is
the string length.

\item Population member indices are $[0,N-1]$ in C, and $[1,N]$ in Fortran,
where $N$ is the population size.

\item Fortran does not support command line arguments
(Section~\ref{sec:cla}).

\item Fortran allows custom usage with native data types
(Chapter~\ref{chp:custom1}), but not with new data types
(Chapter~\ref{chp:new-data}).

\item In the {\tt MPICH} implementation of MPI, the Fortran and C versions of
{\tt MPI\_Init} are different.  If the main program is in C, then the C
version of {\tt MPI\_Init} must be called.  If the main program is in Fortran,
the Fortran version of {\tt MPI\_Init} must be called.  Therefore, Fortran
users of PGAPack with {\tt MPICH} must call {\tt MPI\_Init} themselves since
{\tt PGACreate}, which calls {\tt MPI\_Init} if users haven't called it
themselves, is written in C.

\item The DEC Alpha and Silicon Graphics Power Challenge, which have
64-bit C pointers and 32-bit Fortran integers (but not the Cray T3D which has
64-bit Fortran integers), have additional differences\footnote{More generally,
these issues arise whenever the size of a Fortran integer is less than the
size of a pointer.}.  These arise because a Fortran integer is too small to
hold the address returned by the C interface routine.

\begin{itemize}

\item The context variable should be declared {\tt integer*8}. 

\item {\tt MPI\_COMM\_WORLD} should {\em not} be passed directly to 
\pga\ Fortran functions.  Instead, {\tt PGAGetCommunicator} should be
called to return the address into an {\tt integer*8} variable.  
For example
\begin{verbatim}
       integer pid
       integer*8 comm
       comm = PGAGetCommunicator(ctx)
       :
       pid  = PGAGetRank(ctx, comm)       
\end{verbatim}

\item {\tt MPI\_COMM\_WORLD} {\em can} and {\em should} be passed directly to
any MPI routines called directly from Fortran.

\item Calling an MPI routine that returns a communicator is safe.  However,
passing the returned communicator to a \pga\ Fortran function will usually
fail.


\end{itemize}

\end{itemize}


\findex{PGACreate}
\sindex{PGARun}


%*****************************************************************************
\chapter{Debugging Tools}\label{chp:debug}
%*****************************************************************************

\begin{table}[b]
\centering
\caption
{
Debug Levels in \pga\
}
\begin{tabular}{|r|l|} \hline\hline
  0 & Trace all debug prints \\
 11 & Trace high-level functions \\
 12 & Trace all function entries \\
 13 & Trace all function exits \\
 20 & Trace high-level parallel functions \\
 21 & Trace all parallel functions \\
 22 & Trace all send calls \\
 23 & Trace all receive calls \\
 30 & Trace Binary    functions \\
 32 & Trace Integer   functions \\
 34 & Trace Real      functions \\
 36 & Trace Character functions \\
 40 & Trace population creation functions \\
 42 & Trace select functions \\
 44 & Trace mutation functions \\
 46 & Trace crossover functions \\
 48 & Trace function evaluation functions \\
 50 & Trace fitness calculation  functions \\
 52 & Trace duplicate checking functions \\
 54 & Trace restart functions \\
 56 & Trace reporting functions \\
 58 & Trace stopping functions \\
 60 & Trace sorting functions \\
 62 & Trace random number functions \\
 64 & Trace system routines \\
 66 & Trace utility functions \\
 80 & Trace memory allocations \\
 82 & Trace variable print statements \\
\hline
\end{tabular}
\label{tab:debug-levels}
\end{table}
    

\pga\ has a sophisticated built-in trace facility that is useful for
debugging.  When the facility is invoked, print statements to {\tt stdout}
allow the programmer to trace the sequence of functions \pga\ executes.  Due
to the negative impact on performance this facility is {\em not} available by
default.  Instead, you must explicitly enable tracing when configuring 
\pga\  with the {\tt -debug} flag.  See 
Section~\ref{sec:install}.

The trace facility uses the concept  of a {\em debug
level}.  For example, executing the Maxbit example
(Figure~\ref{example:simple-main}) with a debug level of 12, {\tt maxbit
-pgadbg 12}, will print the output shown in Figure~\ref{fig:trace}.  The
``{\tt 0:}'' is the process rank.  This is followed by the name of a
\pga\ function and the ``action'' that caused the print statement to execute.
In this case, the action is entering the function.  Note that the rank printed
for a process is {\em always} its rank in the {\tt MPI\_COMM\_WORLD}
communicator, even if another communicator was set.


\begin{figure}
\begin{verbatim}
   0: PGACreate                       : Entered
   0: PGASetRandomSeed                : Entered
   0: PGASetMaxGAIterValue            : Entered
   0: PGASetUp                        : Entered
   0: PGACreatePop                    : Entered
   0: PGACreateIndividual             : Entered
   :
   :
   0: PGACreateIndividual             : Entered
   0: PGACreatePop                    : Entered
   0: PGACreateIndividual             : Entered
   :
   :
   0: PGARun                          : Entered
   0: PGARunSeq                       : Entered
   0: PGAEvaluate                     : Entered
   0: PGAFitness                      : Entered
   0: PGAGetStringLength              : Entered
   :
   :
\end{verbatim}
\caption{\pga\ Partial Trace Output for Maxbit Example}
\label{fig:trace}
\end{figure}


Tracing is enabled by specifying one or more debug levels to trace.  A list of
debug levels is given in Table~\ref{tab:debug-levels}.  Not all debug level
values are currently used.  The values 1--10 are reserved for users as
described below.

C programmers may set the debug level from the command line using either {\tt
-pgadbg <debug\_level>} or {\tt -pgadebug <debug\_level>}.  Several forms of
the {\tt <debug\_level>} argument are allowed.  {\tt -pgadbg 12} will trace
entering all high-level functions as shown in Figure~\ref{fig:trace}.  {\tt
-pgadbg 12,13} or {\tt -pgadbg 12-13} will trace entering {\em and} exiting of
all high-level functions.  The command line option {\tt -pgahelp debug} will
list the debug level options and then exit.

Fortran (and C) programmers may access the trace facility via function calls.
The function {\tt PGASetDebugLevel} may be called to set a debug level.  For
example, {\tt call PGASetDebugLevel(ctx,12)} would produce the same output
shown in Figure~\ref{fig:trace}.  {\tt PGAClearDebugLevel(ctx,12)} will clear
prints associated with debug level 12.  {\tt PGAPrintDebugOptions(ctx)} will
print the list of available debug options.

The function {\tt PGASetDebugLevelByName} will turn on debugging of the named
function.  For example, {\tt PGASetDebugLevelByName(ctx,''PGACrossover'')}
will enable all the trace prints of {\tt PGACrossover}.  {\tt
PGAClearDebugLevelByName} will disable the tracing of the specified function.


Users can use the trace facility in their own functions (e.g., their
evaluation function) in two ways.  First, they can insert {\tt PGADebugPrint}
function calls in their functions using one of the symbolic constants defined
in the header file {\tt pgapack.h}.  These are {\tt PGA\_DEBUG\_ENTERED}, {\tt
PGA\_DEBUG\_EXIT}, {\tt PGA\_DEBUG\_MALLOC}, {\tt PGA\_DEBUG\_PRINTVAR}, {\tt
PGA\_DEBUG\_SEND}, and {\tt PGA\_DEBUG\_RECV} for entering a function, exiting
a function, allocating memory, print a variable's value, and sending or
receiving a string, respectively.

For example, {\tt PGADebugPrint(ctx,
PGA\_DEBUG\_ENTERED, "MyFunc", "Entered", PGA\_VOID, NULL)} will print the
line
\begin{verbatim}
   0: MyFunc                          : Entered
\end{verbatim}
when the debug level of 12 is specified.  {\tt PGADebugPrint(ctx,
PGA\_DEBUG\_PRINTVAR, "MyFunc", "i = ", PGA\_INT, (void *) \&i)} will print the
line
\begin{verbatim}
   0: MyFunc                          : i =  1
\end{verbatim}
when the debug level of 82 is specified.  Users can also use the reserved
debug levels of 1--10 to customize the trace facilities for use in their own
functions.  For example {\tt PGADebugPrint( ctx, 5, "MyFunc", "After call to
MyCleanUp", PGA\_VOID, NULL)}; will print the line
\begin{verbatim}
   0: MyFunc                          : After call to MyCleanUp
\end{verbatim}
when the debug level of five is specified.

Note that we use {\tt MPI\_COMM\_WORLD} (1) for the random number seed and (2)
for {\tt PGADebugPrint} calls.

%*****************************************************************************
%*****************************************************************************
\part{Appendixes}\label{part:appendices}
%*****************************************************************************
%*****************************************************************************
\appendix

%*****************************************************************************
\chapter{Default Values}\label{app:default-values}
%*****************************************************************************

\begin{table}
\centering
\caption
{
\pga\ Default Values\label{tab:default-values}
}
\begin{tabular}{|l|r|l|} \hline
\multicolumn{1}{|c|}{CONCEPT} &
\multicolumn{1}{c|}{DEFAULT} &
\multicolumn{1}{c|}{SET WITH}  \\  \hline
Population size                   & 100 &  {\tt PGASetPopSize} \\ \hline
Copied for population replacement & {\tt PGA\_POPREPL\_BEST} & {\tt PGASetPopReplacementType} \\ \hline
Stopping rule                     & {\tt PGA\_STOP\_MAXITER} & {\tt PGASetStoppingRuleType} \\ \hline
Maximum iterations             & 1000 &  {\tt PGASetMaxGAIterValue} \\ \hline
Maximum no change iters        &  100  & {\tt PGASetMaxNoChangeValue} \\ \hline
Max. population homogeneity before stopping  & 95 & {\tt PGASetMaxSimilarityValue} \\ \hline
Number of new strings to generate & 10 & {\tt PGASetNumReplaceValue} \\ \hline
Apply mutation and crossover     & {\tt PGA\_FALSE}  & {\tt PGASetMutationAndCrossoverFlag } \\ \hline
Apply mutation or crossover     & {\tt PGA\_TRUE}  & {\tt PGASetMutationOrCrossoverFlag} \\ \hline
Crossover type            & {\tt PGA\_CROSSOVER\_TWOPT} & {\tt PGASetCrossoverType} \\ \hline
Probability of crossover &  0.85 & {\tt PGASetCrossoverProb} \\ \hline
Uniform crossover bias &  0.6  & {\tt PGASetUniformCrossoverProb} \\ \hline
Mutation type (Real strings)      &  {\tt PGA\_MUTATION\_GAUSSIAN}  & {\tt PGASetMutationType} \\ \hline
Mutation type (Integer strings)      &  {\tt PGA\_MUTATION\_PERMUTE}  & {\tt PGASetMutationType} \\ \hline
Mutation type (Character strings)      &  Same as initialization  & {\tt PGASetCharacterInitType} \\ \hline
Mutation probability      &  1/L  & {\tt PGASetMutationProb} \\ \hline
Real mutation constant  &  0.1  & {\tt PGASetMutationRealValue} \\ \hline
Integer mutation constant  & 1  & {\tt PGASetMutationIntegerValue} \\ \hline
Mutation range bounded  & {\tt PGA\_TRUE}  & {\tt PGASetMutationBoundedFlag} \\ \hline
Select type               & {\tt PGA\_SELECT\_TOURNAMENT} &  {\tt PGASetSelectType} \\ \hline
Probabilistic binary tournament parameter &   0.6  & {\tt PGASetPTournamentProb} \\ \hline
Use restart operator & {\tt PGA\_FALSE} & {\tt PGASetRestartFlag} \\ \hline
Restart frequency    & 50               & {\tt PGASetRestartFrequencyValue} \\ \hline
Restart allele mutation rate & 0.5 & {\tt PGASetRestartAlleleChangeProb} \\ \hline
Allow duplicate strings &  {\tt PGA\_FALSE}  & {\tt PGASetNoDuplicatesFlag} \\ \hline
Fitness type              & {\tt PGA\_FITNESS\_RAW}  & {\tt PGASetFitnessType} \\ \hline
Fitness type for minimization & {\tt PGA\_FITNESSMIN\_CMAX}  & {\tt PGASetFitnessMinType} \\ \hline
Multiplier for minimization problems &  1.01  & {\tt PGASetCMaxValue} \\ \hline
Parameter MAX in fitness by ranking &  1.2  & {\tt PGASetMaxFitnessRank} \\ \hline
Frequency of statistics printing & 10  & {\tt PGASetPrintFrequencyValue} \\ \hline
Print strings            &  {\tt PGA\_FALSE}  & {\tt PGASetPrintOptions} \\ \hline
Print offline statistics &  {\tt PGA\_FALSE}  & {\tt PGASetPrintOptions} \\ \hline
Print online statistics   &  {\tt PGA\_FALSE}  & {\tt PGASetPrintOptions} \\ \hline
Print best string        &  {\tt PGA\_FALSE}  & {\tt PGASetPrintOptions} \\ \hline
Print worst string       &  {\tt PGA\_FALSE}  & {\tt PGASetPrintOptions} \\ \hline
Print Hamming distance   &  {\tt PGA\_FALSE}  & {\tt PGASetPrintOptions} \\ \hline
Randomly initialize population  &  {\tt PGA\_TRUE}   & {\tt PGASetRandomInitFlag} \\ \hline
Probability of initializing a bit to one & 0.5  & {\tt PGASetBinaryInitProb} \\ \hline
How to initialize real strings & Range & {\tt PGASetrealInitRange} \\ \hline
Real initialization range & $[0,1]$ & {\tt PGASetRealInitRange} \\ \hline
How to initialize integer strings & Permutation  & {\tt PGASetIntegerInitPermute} \\ \hline
Integer initialization range & $[0,L-1]$ & {\tt PGASetIntegerInitPermute} \\ \hline
How to initialize character strings & {\tt PGA\_CINIT\_LOWER}  & {\tt PGASetCharacterInitFlag} \\ \hline
Seed random number with clock & {\tt PGA\_TRUE}  & {\tt PGASetRandomSeed} \\ \hline
Default MPI communicator & {\tt MPI\_COMM\_WORLD} & {\tt PGASetCommunicator} \\ \hline
\multicolumn{1}{l}{$L$ is the string length} & & 
\end{tabular}
\end{table}

%*****************************************************************************
\chapter{Function Bindings}\label{chp:function-bindings}
%*****************************************************************************

%*****************************************************************************
\section*{Symbolic Constants}\label{app:symbolic-constants}
%*****************************************************************************

\pga\ defines many symbolic constants that are used as arguments
to \pga\ functions.  These constants are the same for both Fortran and C.
Below is a list of these constants.  These constants are the same for both
Fortran and C.

\begin{itemize}

\item \pga\ Data Types
\begin{itemize}
\item {\tt PGA\_DATATYPE\_BINARY}
\item {\tt PGA\_DATATYPE\_INTEGER}
\item {\tt PGA\_DATATYPE\_REAL}
\item {\tt PGA\_DATATYPE\_CHARACTER}
\item {\tt PGA\_DATATYPE\_USER}
\end{itemize}
    
\item String Types
\begin{itemize}
\item {\tt PGABinary}
\item {\tt PGAInteger}
\item {\tt PGAReal}
\item {\tt PGACharacter}
\end{itemize}

\item Data Types used in {\tt PGAError} Calls
\begin{itemize}
\item {\tt PGA\_INT}
\item {\tt PGA\_DOUBLE}
\item {\tt PGA\_CHAR}
\item {\tt PGA\_VOID}
\end{itemize}

\item True and False
\begin{itemize}
\item {\tt PGA\_TRUE}
\item {\tt PGA\_FALSE}
\end{itemize}

\item Miscellaneous \pga\ Flags
\begin{itemize}
\item {\tt PGA\_FATAL}
\item {\tt PGA\_WARNING}
\item {\tt PGA\_UNINITIALIZED\_INT}
\item {\tt PGA\_UNINITIALIZED\_DOUBLE}
\end{itemize}

\item \pga\ Temporary and Population Constants
\begin{itemize}
\item {\tt PGA\_TEMP1}
\item {\tt PGA\_TEMP2}
\item {\tt PGA\_OLDPOP}
\item {\tt PGA\_NEWPOP}
\end{itemize}


\item Debug Levels
\begin{itemize}
\item {\tt PGA\_DEBUG\_ENTERED}
\item {\tt PGA\_DEBUG\_EXIT}
\item {\tt PGA\_DEBUG\_MALLOC}
\item {\tt PGA\_DEBUG\_PRINTVAR}
\item {\tt PGA\_DEBUG\_SEND}
\item {\tt PGA\_DEBUG\_RECV}
\end{itemize}


\item Direction of Optimization
\begin{itemize}
\item {\tt PGA\_MAXIMIZE}
\item {\tt PGA\_MINIMIZE}
\end{itemize}
    
\item Stopping Criteria
\begin{itemize}
\item {\tt PGA\_STOP\_MAXITER}
\item {\tt PGA\_STOP\_NOCHANGE}
\item {\tt PGA\_STOP\_TOOSIMILAR}
\end{itemize}

\item Crossover
\begin{itemize}
\item {\tt PGA\_CROSSOVER\_ONEPT}
\item {\tt PGA\_CROSSOVER\_TWOPT}
\item {\tt PGA\_CROSSOVER\_UNIFORM}
\end{itemize}

\item Fitness
\begin{itemize}
\item {\tt PGA\_FITNESS\_RAW}
\item {\tt PGA\_FITNESS\_NORMAL}
\item {\tt PGA\_FITNESS\_RANKING}
\end{itemize}

\item Fitness Minimization
\begin{itemize}
\item {\tt PGA\_FITNESSMIN\_RECIPROCAL}
\item {\tt PGA\_FITNESSMIN\_CMAX}
\end{itemize}

\item Mutation Type
\begin{itemize}
\item {\tt PGA\_MUTATION\_CONSTANT}
\item {\tt PGA\_MUTATION\_RANGE}
\item {\tt PGA\_MUTATION\_UNIFORM}
\item {\tt PGA\_MUTATION\_GAUSSIAN}
\item {\tt PGA\_MUTATION\_PERMUTE}
\end{itemize}
    
\item Population Replacement
\begin{itemize}
\item {\tt PGA\_POPREPL\_BEST}
\item {\tt PGA\_POPREPL\_RANDOM\_NOREP}
\item {\tt PGA\_POPREPL\_RANDOM\_REP}
\end{itemize}

\item Initialization Options
\begin{itemize}
\item {\tt PGA\_CINIT\_LOWER}
\item {\tt PGA\_CINIT\_UPPER}
\item {\tt PGA\_CINIT\_MIXED}
\item {\tt PGA\_IINIT\_PERMUTE}
\item {\tt PGA\_IINIT\_RANGE}
\item {\tt PGA\_RINIT\_PERCENT}
\item {\tt PGA\_RINIT\_RANGE}
\end{itemize}

\item Report Options
\begin{itemize}
\item {\tt PGA\_REPORT\_ONLINE}
\item {\tt PGA\_REPORT\_OFFLINE}
\item {\tt PGA\_REPORT\_HAMMING}
\item {\tt PGA\_REPORT\_STRING}
\item {\tt PGA\_REPORT\_WORST}
\item {\tt PGA\_REPORT\_AVERAGE}
\end{itemize}

\item Selection
\begin{itemize}
\item {\tt PGA\_SELECT\_PROPORTIONAL}
\item {\tt PGA\_SELECT\_SUS}
\item {\tt PGA\_SELECT\_TOURNAMENT}
\item {\tt PGA\_SELECT\_PTOURNAMENT}
\end{itemize}

\item User Functions
\begin{itemize}
\item {\tt PGA\_USERFUNCTION\_CREATESTRING}
\item {\tt PGA\_USERFUNCTION\_MUTATION}
\item {\tt PGA\_USERFUNCTION\_CROSSOVER}
\item {\tt PGA\_USERFUNCTION\_PRINTSTRING}
\item {\tt PGA\_USERFUNCTION\_COPYSTRING}
\item {\tt PGA\_USERFUNCTION\_DUPLICATE}
\item {\tt PGA\_USERFUNCTION\_INITSTRING}
\item {\tt PGA\_USERFUNCTION\_BUILDDATATYPE}
\item {\tt PGA\_USERFUNCTION\_STOPCOND}
\item {\tt PGA\_USERFUNCTION\_ENDOFGEN}
\end{itemize}

\end{itemize}

%*****************************************************************************
\section*{ANSI C Bindings}\label{app:bindings-c}
%*****************************************************************************

The use of any \pga\ function requires that the user have {\tt \#include
"pgapack.h"} at the top of the file that references \pga\ functions.
\vspace{.5in}

\begin{tabular}{|l|l|} \hline\hline
\multicolumn{1}{|c|}{Type} &
\multicolumn{1}{c|}{Function}  \\  \hline\hline
MPI\_Datatype & PGABuildDatatype(PGAContext *ctx, int p, int pop) \\ \hline
void &  PGAChange(PGAContext *ctx, int p, int pop) \\ \hline
int &  PGACheckStoppingConditions(PGAContext *ctx) \\ \hline
int &  PGACheckSum(PGAContext *ctx, int p, int pop) \\ \hline
void &  PGAClearDebugLevel(PGAContext *ctx, int level) \\ \hline
void &  PGAClearDebugLevelByName(PGAContext *ctx, char *funcname) \\ \hline
void &  PGACopyIndividual(PGAContext *ctx, int p1, int pop1, int p2, int pop2)
\\ \hline
PGAContext* &  PGACreate(int *argc, char **argv, int datatype, int len, int maxormin) \\ \hline
void &  PGACrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1, int
c2, int pop2) \\ \hline
void &  PGADebugPrint(PGAContext *ctx, int level, char *funcname, \\
     &  char *msg, int datatype, void *data) \\ \hline
void &  PGADestroy(PGAContext *ctx) \\ \hline
int &  PGADone(PGAContext *ctx, MPI\_Comm comm) \\ \hline
int &  PGADuplicate(PGAContext *ctx, int p, int pop1, int pop2, int n) \\ \hline
void &  PGAEncodeIntegerAsBinary(PGAContext *ctx, int p, int pop, int start,
int end, int val) \\ \hline
void &  PGAEncodeIntegerAsGrayCode(PGAContext *ctx, int p, int pop, int start,
int end, int val) \\ \hline
void &  PGAEncodeRealAsBinary(PGAContext *ctx, int p, int pop, \\
     &  int start, int end, double low, double high, double val) \\ \hline
void &  PGAEncodeRealAsGrayCode(PGAContext *ctx, int p, int pop, \\
     &  int start, int end, double low, double high, double val) \\ \hline
void &  PGAError(PGAContext *ctx, char *msg, int level, int datatype, void
*data) \\ \hline
void &  PGAEvaluate(PGAContext *ctx, int pop, \\ 
     & double(*f)(PGAContext *, int, int), MPI\_Comm comm) \\ \hline
void &  PGAFitness(PGAContext *ctx, int popindex) \\ \hline
int &  PGAGetBestIndex(PGAContext *ctx, int pop) \\ \hline
int &  PGAGetBinaryAllele(PGAContext *ctx, int p, int pop, int i) \\ \hline
double &  PGAGetBinaryInitProb(PGAContext *ctx) \\ \hline
char &  PGAGetCharacterAllele(PGAContext *ctx, int p, int pop, int i) \\ \hline
MPI\_Comm & PGAGetCommunicator(PGAContext *ctx) \\ \hline
double &  PGAGetCrossoverProb(PGAContext *ctx) \\ \hline
int &  PGAGetCrossoverType(PGAContext *ctx) \\ \hline
int &  PGAGetDataType(PGAContext *ctx) \\ \hline
double &  PGAGetEvaluation(PGAContext *ctx, int p, int pop) \\ \hline
int &  PGAGetEvaluationUpToDateFlag(PGAContext *ctx, int p, int pop) \\ \hline
double &  PGAGetFitness(PGAContext *ctx, int p, int pop) \\ \hline
double &  PGAGetFitnessCmaxValue(PGAContext *ctx) \\ \hline
int &  PGAGetFitnessMinType(PGAContext *ctx) \\ \hline
int &  PGAGetFitnessType(PGAContext *ctx) \\ \hline
int &  PGAGetGAIterValue(PGAContext *ctx) \\ \hline
int &  PGAGetIntegerAllele(PGAContext *ctx, int p, int pop, int i) \\ \hline
int &  PGAGetIntegerFromBinary(PGAContext *ctx, int p, int pop, int start, int
end) \\ \hline
int &  PGAGetIntegerFromGrayCode(PGAContext *ctx, int p, int pop, int start,
int end) \\ \hline
int &  PGAGetIntegerInitType(PGAContext *ctx) \\ \hline
\end{tabular}



\begin{tabular}{|l|l|} \hline\hline
\multicolumn{1}{|c|}{Type} &
\multicolumn{1}{c|}{Function}  \\  \hline\hline
double &  PGAGetMaxFitnessRank(PGAContext *ctx) \\ \hline
int &  PGAGetMaxGAIterValue(PGAContext *ctx) \\ \hline
int &  PGAGetMaxIntegerInitValue(PGAContext *ctx, int i) \\ \hline
double &  PGAGetMaxMachineDoubleValue(PGAContext *ctx) \\ \hline
int &  PGAGetMaxMachineIntValue(PGAContext *ctx) \\ \hline
double &  PGAGetMaxRealInitValue(PGAContext *ctx, int i) \\ \hline
int &  PGAGetMinIntegerInitValue(PGAContext *ctx, int i) \\ \hline
double &  PGAGetMinMachineDoubleValue(PGAContext *ctx) \\ \hline
int &  PGAGetMinMachineIntValue(PGAContext *ctx) \\ \hline
double &  PGAGetMinRealInitValue(PGAContext *ctx, int i) \\ \hline
int &  PGAGetMutationAndCrossoverFlag(PGAContext *ctx) \\ \hline
int &  PGAGetMutationBoundedFlag(PGAContext *ctx) \\ \hline
int &  PGAGetMutationIntegerValue(PGAContext *ctx) \\ \hline
int &  PGAGetMutationOrCrossoverFlag(PGAContext *ctx) \\ \hline
double &  PGAGetMutationProb(PGAContext *ctx) \\ \hline
double &  PGAGetMutationRealValue(PGAContext *ctx) \\ \hline
int &  PGAGetMutationType(PGAContext *ctx) \\ \hline
int &  PGAGetNoDuplicatesFlag(PGAContext *ctx) \\ \hline
int &  PGAGetNumProcs(PGAContext *ctx, MPI\_Comm comm) \\ \hline
int &  PGAGetNumReplaceValue(PGAContext *ctx) \\ \hline
int &  PGAGetOptDirFlag(PGAContext *ctx) \\ \hline
double &  PGAGetPTournamentProb(PGAContext *ctx) \\ \hline
int &  PGAGetPopReplaceType(PGAContext *ctx) \\ \hline
int &  PGAGetPopSize(PGAContext *ctx) \\ \hline
int &  PGAGetPrintFrequencyValue(PGAContext *ctx) \\ \hline
int &  PGAGetRandomInitFlag(PGAContext *ctx) \\ \hline
int &  PGAGetRandomSeed(PGAContext *ctx) \\ \hline
int &  PGAGetRank(PGAContext *ctx, MPI\_Comm comm) \\ \hline
double &  PGAGetRealAllele(PGAContext *ctx, int p, int pop, int i) \\ \hline
double &  PGAGetRealFromBinary(PGAContext *ctx, int p, int pop, \\
       &  int start, int end, double lower, double upper) \\ \hline
double &  PGAGetRealFromGrayCode(PGAContext *ctx, int p, int pop, \\
       &  int start, int end, double lower, double upper) \\ \hline
int &  PGAGetRealInitType(PGAContext *ctx) \\ \hline
double &  PGAGetRestartAlleleChangeProb(PGAContext *ctx) \\ \hline
int &  PGAGetRestartFlag(PGAContext *ctx) \\ \hline
int &  PGAGetRestartFrequencyValue(PGAContext *ctx) \\ \hline
int &  PGAGetSelectType(PGAContext *ctx) \\ \hline
int &  PGAGetSortedPopIndex(PGAContext *ctx, int n) \\ \hline
int &  PGAGetStoppingRuleType(PGAContext *ctx) \\ \hline
int &  PGAGetStringLength(PGAContext *ctx) \\ \hline
double &  PGAGetUniformCrossoverProb(PGAContext *ctx) \\ \hline
int &  PGAGetWorstIndex(PGAContext *ctx, int pop) \\ \hline
double &  PGAHammingDistance(PGAContext *ctx, int popindex) \\ \hline
double &  PGAMean(PGAContext *ctx, double *a, int n) \\ \hline
int &  PGAMutate(PGAContext *ctx, int p, int pop) \\ \hline
void &  PGAPrintContextVariable(PGAContext *ctx, FILE *fp) \\ \hline
void &  PGAPrintIndividual(PGAContext *ctx, FILE *fp, int p, int pop) \\ \hline
void &  PGAPrintPopulation(PGAContext *ctx, FILE *fp, int pop) \\ \hline
void &  PGAPrintReport(PGAContext *ctx, FILE *fp, int pop) \\ \hline
void &  PGAPrintString(PGAContext *ctx, FILE *file, int p, int pop) \\ \hline
void &  PGAPrintVersionNumber(PGAContext *ctx) \\ \hline
\end{tabular}


\begin{tabular}{|l|l|} \hline\hline
\multicolumn{1}{|c|}{Type} &
\multicolumn{1}{c|}{Function}  \\  \hline\hline
double &  PGARandom01(PGAContext *ctx, int newseed) \\ \hline
int &  PGARandomFlip(PGAContext *ctx, double p) \\ \hline
double &  PGARandomGaussian(PGAContext *ctx, double mean, double sigma) \\ \hline
int &  PGARandomInterval(PGAContext *ctx, int start, int end) \\ \hline
double &  PGARandomUniform(PGAContext *ctx, double start, double end) \\ \hline
int &  PGARank(PGAContext *ctx, int p, int *order, int n) \\ \hline
void &  PGAReceiveIndividual(PGAContext *ctx, int p, int pop, int source, \\
     &  int tag, MPI\_Comm comm, MPI\_Status *status) \\ \hline
void &  PGARestart(PGAContext *ctx, int source\_pop, int dest\_pop) \\ \hline
int &  PGARound(PGAContext *ctx, double x) \\ \hline
void &  PGARun(PGAContext *ctx, double(*evaluate)(PGAContext *c, int p, int
pop)) \\ \hline
void &  PGARunGM(PGAContext *ctx, double(*f)(PGAContext *, int, int), MPI\_Comm
comm) \\ \hline
void &  PGARunMutationAndCrossover(PGAContext *ctx, int oldpop, int newpop) \\
\hline
void &  PGARunMutationOrCrossover(PGAContext *ctx, int oldpop, int newpop) \\ \hline
void &  PGASelect(PGAContext *ctx, int popix) \\ \hline
int &  PGASelectNextIndex(PGAContext *ctx) \\ \hline
void &  PGASendIndividual(PGAContext *ctx, int p, int pop, int dest, int tag,
MPI\_Comm comm) \\ \hline
void &  PGASendReceiveIndividual(PGAContext *ctx, int send\_p, \\
     &  int send\_pop, int dest, int send\_tag, int recv\_p, int recv\_pop, \\
     &  int source, int recv\_tag, MPI\_Comm comm, MPI\_Status *status) \\ \hline
void &  PGASetBinaryAllele(PGAContext *ctx, int p, int pop, int i, int val) \\
\hline
void &  PGASetBinaryInitProb(PGAContext *ctx, double probability) \\ \hline
void &  PGASetCharacterAllele(PGAContext *ctx, int p, int pop, int i, char
value) \\ \hline
void &  PGASetCharacterInitType(PGAContext *ctx, int value) \\ \hline
void &  PGASetCommunicator(PGAContext *ctx, MPI\_Comm comm) \\ \hline
void &  PGASetCrossoverProb(PGAContext *ctx, double crossover\_prob) \\ \hline
void &  PGASetCrossoverType(PGAContext *ctx, int crossover\_type) \\ \hline
void &  PGASetDebugLevel(PGAContext *ctx, int level) \\ \hline
void &  PGASetDebugLevelByName(PGAContext *ctx, char *funcname) \\ \hline
void &  PGASetEvaluation(PGAContext *ctx, int p, int pop, double val) \\ \hline
void &  PGASetEvaluationUpToDateFlag(PGAContext *ctx, int p, int pop, int
status) \\ \hline
void &  PGASetFitnessCmaxValue(PGAContext *ctx, double val) \\ \hline
void &  PGASetFitnessMinType(PGAContext *ctx, int fitness\_type) \\ \hline
void &  PGASetFitnessType(PGAContext *ctx, int fitness\_type) \\ \hline
void &  PGASetIntegerAllele(PGAContext *ctx, int p, int pop, int i, int value)
\\ \hline
void &  PGASetIntegerInitPermute(PGAContext *ctx, int min, int max) \\ \hline
void &  PGASetIntegerInitRange(PGAContext *ctx, int *min, int *max) \\ \hline
void &  PGASetMaxFitnessRank(PGAContext *ctx, double fitness\_rank\_max) \\ \hline
void &  PGASetMaxGAIterValue(PGAContext *ctx, int maxiter) \\ \hline
void &  PGASetMaxNoChangeValue(PGAContext *ctx, int max\_no\_change) \\ \hline
void &  PGASetMaxSimilarityValue(PGAContext *ctx, int max\_similarity) \\ \hline
void &  PGASetMutationAndCrossoverFlag(PGAContext *ctx, int flag) \\ \hline
void &  PGASetMutationBoundedFlag(PGAContext *ctx, int val) \\ \hline
void &  PGASetMutationIntegerValue(PGAContext *ctx, int val) \\ \hline
void &  PGASetMutationOrCrossoverFlag(PGAContext *ctx, int flag) \\ \hline
void &  PGASetMutationProb(PGAContext *ctx, double mutation\_prob) \\ \hline
void &  PGASetMutationRealValue(PGAContext *ctx, double val) \\ \hline
void &  PGASetMutationType(PGAContext *ctx, int mutation\_type) \\ \hline
\end{tabular}



\begin{tabular}{|l|l|} \hline\hline
\multicolumn{1}{|c|}{Type} &
\multicolumn{1}{c|}{Function}  \\  \hline\hline
void &  PGASetNoDuplicatesFlag(PGAContext *ctx, int no\_dup) \\ \hline
void &  PGASetNumReplaceValue(PGAContext *ctx, int pop\_replace) \\ \hline
void &  PGASetPTournamentProb(PGAContext *ctx, double ptournament\_prob) \\ \hline
void &  PGASetPopReplaceType(PGAContext *ctx, int pop\_replace) \\ \hline
void &  PGASetPopSize(PGAContext *ctx, int popsize) \\ \hline
void &  PGASetPrintFrequencyValue(PGAContext *ctx, int print\_freq) \\ \hline
void &  PGASetPrintOptions(PGAContext *ctx, int option) \\ \hline
void &  PGASetRandomInitFlag(PGAContext *ctx, int RandomBoolean) \\ \hline
void &  PGASetRandomSeed(PGAContext *ctx, int seed) \\ \hline
void &  PGASetRealAllele(PGAContext *ctx, int p, int pop, int i, double value)
\\ \hline
void &  PGASetRealInitPercent(PGAContext *ctx, double *median, double
*percent) \\ \hline
void &  PGASetRealInitRange(PGAContext *ctx, double *min, double *max) \\ \hline
void &  PGASetRestartAlleleChangeProb(PGAContext *ctx, double prob) \\ \hline
void &  PGASetRestartFlag(PGAContext *ctx, int val) \\ \hline
void &  PGASetRestartFrequencyValue(PGAContext *ctx, int numiter) \\ \hline
void &  PGASetSelectType(PGAContext *ctx, int select\_type) \\ \hline
void &  PGASetStoppingRuleType(PGAContext *ctx, int stoprule) \\ \hline
void &  PGASetUniformCrossoverProb(PGAContext *ctx, double uniform\_cross\_prob)
\\ \hline
void &  PGASetUp(PGAContext *ctx) \\ \hline
void &  PGASetUserFunction(PGAContext *ctx, int constant, void *f) \\ \hline
void &  PGASortPop(PGAContext *ctx, int pop) \\ \hline
double &  PGAStddev(PGAContext *ctx, double *a, int n, double mean) \\ \hline
void &  PGAUpdateGeneration(PGAContext *ctx, MPI\_Comm comm) \\ \hline
void &  PGAUsage(PGAContext *ctx) \\ \hline
\end{tabular}


%*****************************************************************************
\section*{Fortran 77 Bindings}\label{app:bindings-fortran}
%*****************************************************************************

Use the rules defined in Chapter~\ref{chp:fortran} (and the machine-specific
idiosyncrasies noted in Appendix~\ref{chp:start-up}) to determine the Fortran
bindings.

%*****************************************************************************
\chapter{Parallelism Background}\label{app:par-background}
%*****************************************************************************

\section*{Parallel Computer Taxonomy}

Traditionally, parallel computers are classified according to Flynn's
taxonomy \cite{Fl72}.  Flynn's classification distinguishes parallel computers
according to the number of instruction streams and data operands being
computed on simultaneously.  

Flynn's single-instruction single-data (SISD) model is the traditional
sequential computer.  A single program counter fetches instructions from
memory.  The instructions are executed on {\em scalar} operands.  There is no
parallelism in this model.

In the single-instruction multiple-data (SIMD) model there is again a single
program counter fetching instructions from memory.  However, now the operands
of the instructions can be one of two types: either scalar or array.  If the
instruction calls for execution involving only scalar operands, it is executed
by the control processor (i.e., the central processing unit fetching
instructions from memory).  If, on the other hand, the instruction calls for
execution using array operands, it is broadcast to the {\em array} of
processing elements.  The processing elements are separate computing devices
that rely upon the control processor to determine the instructions they will
execute.

In a multiple-instruction multiple-data (MIMD) computer there exist multiple
processors each of which has its own program counter.  Processors execute
independently of each other according to whatever instruction the program
counter points to next.  MIMD computers are usually further subdivided
according to whether the processors share memory or each has its own memory.

In a shared-memory MIMD computer both the program's instructions and the part
of the program's data to be shared exist within a single shared memory.
Additionally, some data may be private to a processor and not be globally
accessible by other processors.  The processors execute asynchronously of each
other.  Communication and synchronization between the processors are handled
by having them each read or write a shared-memory location.

A distributed-memory MIMD computer consists of multiple ``nodes.''  A node
consists of a processor, its own memory, a network interface, and sometimes a
local disk.  The program instructions and data reside in the node's memory.
The nodes are connected via some type of network that allows them to
communicate with each other.  Parallelism is achieved by having each processor
compute simultaneously on the data in its own memory.  Communication and
synchronization are handled by passing of messages (a destination node address
and the local data to be sent) over the interconnection network.

\section*{Processes vs. Processors}

We distinguish the  two terms process and processor.  A {\em process} is a
software abstraction with a unique address space that can be scheduled by the
operating system.  A {\em processor} is the physical computer hardware on
which computations take place. 

On MIMD parallel computers, usually one process executes on
each processor (although this is not required).  On a uniprocessor,
multiple processes timeshare the single processor.


\section*{Message-Passing Programming Model}

In the message-passing programming model multiple processes communicate by
passing messages---transferring data from the address space of one process
into the address space of another process.  When a process needs data stored
in the memory of another process, the data must be sent from the process that
``owns'' it, to the memory of the process that needs it.

The message-passing programming model is currently one of the most popular.
One reason for the popularity is portability. Message passing is the natural
programming model on distributed-memory MIMD computers.  Each process is
naturally mapped to one of the machine's nodes.  A similar implementation is
common on a workstation network where one process runs on each workstation.
On a shared-memory MIMD computer multiple processes can emulate
message passing by communicating only via logical message queues---areas of
shared memory partitioned by process. On a uniprocessor the multiple processes
that timeshare the physical processor can also emulate the idea of 
logical message queues for their communication.

One example of the message-passing programming model is the master/slave
model.  In this model a {\em master} process distributed work (computation to
be performed) to the slave processes.  The slaves perform the work and return
the result to the master.  In many implementations the master plays a
bookkeeping role only and does not perform any computation.


\section*{Parallel Genetic Algorithms}

When using the term ``parallel genetic algorithm'' it is important to
distinguish between parallel models, their (parallel or sequential)
implementation, and the computer hardware.

\subsection*{Models}

A sequential GA model (more accurately called a {\em global} model) has a
single population and no restrictions (partitioning) upon which strings
recombine with which.  The sequential GA is the traditional GA model given in
the literature.  In a parallel GA model there are either multiple
populations (an island model) or a partitioning of a single population (often
called a fine-grained model).
  
\subsection*{Implementations}

Both parallel and sequential GA models can have parallel or sequential
implementations.  A sequential implementation of the global model is the
traditional approach discussed in the GA literature.  One process, running on
a uniprocessor (PCs and workstations), performs all the calculations.  In a
parallel implementation of the global model the steps of the GA (some or all
of selection, crossover, mutation, and fitness calculation) are executed
simultaneously by multiple processes running on a parallel computer or
workstation network.

In a sequential implementation of a parallel GA model, multiple processes,
each responsible for a subpopulation or partition of the full population, time
share the processor of the  uniprocessor they are running on.  In a parallel
implementation of a parallel GA model, the multiple processes each run on a
unique processor of a parallel computer or workstation network.



\section*{MPI}


MPI (Message Passing Interface) is a {\em specification} of a message-passing
library for parallel computers and workstation networks---it defines a set of
functions and their behavior.  The actual {\em implementation} of this
interface is left up to vendors and researchers to develop.  At the time of
this writing several implementations of MPI, both proprietary and freely
available, exist.  MPI was designed by a large group of parallel computer
vendors, computer researchers, and application developers as a standard for
message passing.

\subsection*{Communicators}

Almost all MPI functions require a {\em communicator}.  If MPI routines are
called directly, the user must supply a communicator.  Also, if any of \pga's
parallel routines, other than {\tt PGARun}, are used, the user must supply a
communicator as well.

A communicator combines the notions of context and group.  A {\em context} is
an extension of the notion of a ``tag'' used in many other message-passing
systems to identify a message.  Contexts differ from tags in that they are
allocated by the system, not the user, and that no wild-card matching among
contexts is allowed.  A {\em group} contains $n$ processes whose {\em rank} is
an integer between $0,\ldots,n-1$.  Processes may belong to more than one
group and have a unique rank within each.

Any MPI implementation will always supply the default communicator {\tt
MPI\_COMM\_WORLD}.  This communicator contains all processes that were created
when MPI was initialized.  For most users this is all they have to know about
communicators.  Simply supply {\tt MPI\_COMM\_WORLD} whenever a communicator
is required as an argument.  For more sophisticated use, users are referred to
\cite{MPI-final,GrLuSk94}.



\subsection*{Parallel I/O}

The issue of parallel I/O is independent of \pga.  However, since we assume
many \pga\ users will wish to do I/O we address this topic.  A primary
consideration has to do with whether one or all processors do I/O.
Consider the following two code fragments, keeping in mind that they are being
executed simultaneously by {\em multiple} processes:
\begin{verbatim}
ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, 30, PGA_MINIMIZE) 
\end{verbatim}
and 
\begin{verbatim}
int len;
scanf("%d",&len);
ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, len, PGA_MINIMIZE);
\end{verbatim}
In the first case, all processes will receive the value of 30 for the string
length since it is a constant.  In the second case, however, the value of the
string length is determined at run time.  Whether 
one or all processes execute the {\tt scanf} function is undefined in MPI
and depends on the particular parallel computing environment.
In \pga\ we require that all processes have the same values for all
fields in the context variable.  Since some of these fields may be set by using
values specified at run time, we suggest that  your I/O that reads in \pga\
parameters be done as follows:
\begin{verbatim}
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop);

int main( int argc, char **argv )
{
     PGAContext *ctx;
     int myid, len;

     MPI_Init(&argc, &argv);
     MPI_Comm_rank(MPI_COMM_WORLD, &myid);
     if (myid == 0) {                        /* Process 0 has a dialog */
         printf("String length? ");          /* with the user and      */
         scanf("%d", &len);                  /* broadcasts the user's  */
     }
     MPI_Bcast(&len, 1, MPI_INT, 0, MPI_COMM_WORLD);

     ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, len, PGA_MAXIMIZE);
     PGASetUp(ctx);
     PGARun(ctx, evaluate);
     PGADestroy(ctx);

     MPI_Finalize();
     return(0);
}
\end{verbatim}

The key point is that {\em only} process 0 (as determined by {\tt
MPI\_Comm\_rank}) performs I/O and the value of {\tt len} is then broadcast
(using {\tt MPI\_Bcast}) to the other processes.


%*****************************************************************************
\chapter{Machine Idiosyncrasies}\label{chp:start-up}
%*****************************************************************************


\section*{Data Type Sizes} 

\pga\ is written entirely in ANSI C.  However, because it is callable from
Fortran, and no standards exist for interlanguage communication, problems may
arise.  These have to do with a lack of consistency in the size of data types
between the two languages.

On all machines we have tested, an {\tt integer} declaration in Fortran is the
same size as an {\tt int} declaration in C and everything works properly.  For
floating-point numbers, however, we have found at least one inconsistency.
The requirement is for the Fortran floating-point number to be the same size
as a C {\tt double}.  On most machines a Fortran {\tt double precision}
declaration is the equivalent size.  On the Cray T3D, however, by default, the
Fortran data type {\tt double precision} is not supported and must be handled
as described below.

Since Fortran does not support pointers, an {\tt integer} variable is used to
hold the address of the context variable (and possibly MPI communicator
addresses as well).  Therefore, a Fortran {\tt integer} must be ``large
enough'' to hold an address on the machine.  For all 32-bit address space
machines we have tested this is the case.  On machines with a 64-bit address
space, however, this may not be true.  In particular, the size of a Fortran
{\tt integer} on the Silicon Graphics Power Challenge and DEC Alpha (but {\em
not} the Cray T3D) is 32-bits and is not large enough to hold a machine
address.  The solution on these machines is to use the (nonstandard, but
supported) Fortran declaration {\tt integer*8} for the context variable.

% Wordsize table: /home/pgapack/util/wordsizes.txt (see also wordsizes.c)
% For information purposes, we give the table below which contains the sizes of
% various datatypes in bytes.
% \begin{verbatim}
%  
%                          PowerChallenge
%                             Challenge
%                                Paragon
%                                   T3D
%                                      Exemplar
%                                         Alpha
%                                            NeXT, sun
%  sizeof(PGAContext *):   8  4  4  8  4  8  4
%  sizeof(PGABinary):      8  4  4  8  4  8  4
%  sizeof(PGAReal):        8  8  8  8  8  8  8
%  sizeof(PGAInteger):     8  4  4  8  4  8  4
%  sizeof(PGACharacter):   1  1  1  1  1  1  1
%  sizeof(int):            4  4  4  8  4  4  4
%  sizeof(long int):       8  4  4  8  4  8  4
%  sizeof(double):         8  8  8  8  8  8  8
%  sizeof(char):           1  1  1  1  1  1  1
% \end{verbatim}



\section*{Startup}



The MPI standard provides for {\em source code} portability.  However, the MPI
standard does {\em not} specify how an MPI program shall be started or how the
number of processes in the computation is specified.  These will vary
according to the computer being used and the choice of MPI implementation.
The notes below are from our experiences testing \pga\ on different machines.


\subsection*{Silicon Graphics Challenge}

The Silicon Graphics Challenge is a 32-bit symmetric multiprocessor.  We used
{\tt MPICH} with the {\tt ch\_shmem} device and the {\tt ncc} C compiler.
Several warnings were received
\begin{verbatim}
warning(3262): parameter "ctx" declared and never referenced
warning(3141): cast between pointer-to-object and pointer-to-function
\end{verbatim}
but the library was successfully built.
To run a parallel \pga\ program, use either
\begin{verbatim}
a.out -np nprocs
\end{verbatim}
or {\tt MPICH}'s {\tt mpirun} command.


\subsection*{Silicon Graphics Power Challenge}

The Silicon Graphics Power Challenge is similar to the Challenge, except that
it has a 64-bit address space.  On this machine the size of an integer ({\tt
int} in C and {\tt integer} in Fortran) is not the same as the size of an
address.  Fortran users should use the declaration {\tt integer*8} for the
context variable (and {\tt integer} for other Fortran integer declarations).
See also Chapter~\ref{chp:fortran}.

We used {\tt MPICH} with the {\tt ch\_p4} device and the the MIPSpro C
compiler ({\tt cc}).  We found a bug in {\tt pca}, the Power C Analyzer, and
recommend not using it for now.  (To do this do
not specify the {\tt -pca} switch to {\tt cc}).  To run a parallel \pga\
program, use
\begin{verbatim}
a.out -np nprocs
\end{verbatim}
or {\tt MPICH}'s {\tt mpirun} command.


\subsection*{Cray T3D}

The Cray T3D has a 64-bit address space. However, the size of an integer on
the T3D is the same as the size of an address, and therefore no special
considerations are needed for declaring the context variable in Fortran.

On the T3D a C {\tt double} is 64 bits.  The Fortran {\tt double precision}
data type, however, is not supported (by default).  One workaround is to
declare all floating-point numbers {\tt REAL}, as these are 64 bits on the
T3D.  The other workaround is to use the compiler switch ``-dp''.

To compile for a Cray T3D, cross compilation is done on a front-end machine (a
Cray C90 in our case).  Set Cray's {\tt TARGET} environment variable so the
compiler, linker, etc., will know which architecture to compile for.
\begin{verbatim}
setenv TARGET cray-t3d
\end{verbatim}
An alternative is to use ``-T cray-t3d'' with {\tt cc} and ``-C cray-t3d''
with {\tt cf77}.  Another alternative is to explicitly use the cross
compilers ({\tt /mpp/bin/cc} and {\tt /mpp/bin/cf77}) and linker
({\tt /mpp/bin/mppldr}).

We used the MPI in {\tt /usr/local/mpp/lib/libmpi.a}.  Adding {\tt -lmpi} in
your link step may also find the MPI library.  If a successful T3D executable
was built, the command ``file a.out'' should say ``MPP absolute.''

To run a parallel \pga\ program, use
\begin{verbatim}
a.out -npes nprocs
\end{verbatim}
where {\tt nprocs} is a power of two.


\subsection*{Intel Paragon}

We used {\tt MPICH} with the {\tt ch\_nx} device and compiled with
{\tt cc -nx}. 
To run a parallel \pga\ program, use
\begin{verbatim}
a.out -sz nprocs
\end{verbatim}
or {\tt MPICH}'s {\tt mpirun} command.


\subsection*{IBM SP2}

% I have tested PETSc with IBM's research MPI called MPI-F developed at
% Yorktown. You can see how I did it by looking in
% /home/bsmith/petsc/bmake/rs6000_mpif/rs6000_mpif and rs6000_mpif.site

We tested the IBM SP2 using both {\tt MPICH} with the {\tt ch\_eui} device,
and IBM's research MPI, MPI-F. We compiled \pga\ with {\tt xlc} and linked
with {\tt mpCC}.  Execution required setting a number of environment
variables.  We were successful with the following, but this may vary with the
system software installed on the SP you are using.

\begin{verbatim}
setenv MP_HOSTFILE /sphome/hostfile
setenv MP_PROCS       np
setenv MP_EUILIB      us
setenv MP_INFOLEVEL    0
setenv MP_HOLD_STDIN YES
setenv MP_PULSE        0
a.out
\end{verbatim}


\subsection*{Convex Exemplar}

We used {\tt MPICH} with the {\tt ch\_shmem} device.  Be sure to compile (the
Fortran examples) with {\tt fort77}, not {\tt f77}.  Also, you must link with
{\tt /usr/lib/libU77.a} {\em last} to satisfy {\tt iargc} and {\tt getarg}.
This {\em must} be done {\em manually} in the prototype makefiles {\tt
./examples/fortran/Makefile.in} and {\tt ./examples/mgh/Makefile.in} {\em
before} running {\tt configure}.  To run a parallel \pga\ program using {\tt
MPICH} use the {\tt mpirun} command.

%\subsection*{NeXT Workstation}
%\vspace{.3in}

%\subsection*{FreeBSD}
%\vspace{.3in}

\subsection*{Sun SparcStation}

We used {\tt MPICH} with the {\tt ch\_p4} device and the GNU C compiler {\tt
gcc}.  The {\tt instverf} test program was run using 4 processes with:
\begin{verbatim}
/usr/local/mpi/bin/mpirun instverf -arch sun4 -np 4
\end{verbatim}

\subsection*{Silicon Graphics Workstation}

We used {\tt MPICH} with the {\tt ch\_p4} device and {\tt mpirun} command, the
{\tt cc} C compiler, and {\tt f77} Fortran compiler.

\subsection*{IBM/RS6000 Workstation}

We have successfully run \pga\ on both single workstations and networks of
workstations using the {\tt MPICH} implementation with the {\tt ch\_p4}
device.

\subsection*{Hewlett Packard Workstation}

We used {\tt MPICH} with the {\tt ch\_shmem} device and {\tt mpirun} command,
the {\tt gcc} C compiler, and {\tt fort77} Fortran compiler.

\subsection*{DEC Alpha Workstation}

DEC Alpha workstations have a 64-bit address space.
On this machine the size of an integer ({\tt int} in C and {\tt integer} in
Fortran) is not the same as the size of an address.  Fortran users should use
the declaration {\tt integer*8} for the context variable (and {\tt integer}
for other Fortran integer declarations).
See also Chapter~\ref{chp:fortran}.

% When compiling Fortran programs
% use ``-i8'' or ``-integer\_size 64'' to get 64-bit integers.  Otherwise,
% passing pointers between C and Fortran will fail.






%*****************************************************************************
\chapter{Common Problems}\label{chp:problems}
%*****************************************************************************

\begin{itemize}

\item When reading input value to be used as parameters in {\tt PGASet} calls,
the {\tt PGAset} calls themselves may not be executed until {\em after} {\tt
PGACreate} has been called.

\item In C, when reading input parameters which are of type {\tt double}, the
{\tt scanf} conversion specification should be of the form
{\tt \%lf}, {\em not } {\tt \%f} which is appropriate for {\tt float}s.


\item 
An infinite loop can occur if the number of permutations
of the bit string is less than the population size.  For example, for a
binary-valued string of length four, there are $2^4 = 16$ possibilities.  If
the population size is greater than 16, and duplicate strings are not allowed
in the population, an infinite loop will occur.

\item Erroneous results can occur if
the name of a user's function conflicts with a library function used by \pga.
For example, if a program defined its own {\tt ceil} function, this would
conflict with the C math library function of the same name.

\item All floating point constants and variables used in \pga\ are 
of type {\tt double}.  Particularly from Fortran,
the user should be careful to make sure that they pass 
a {\tt double precision} constant or variable.

\item {\tt PGACreate} removes command line arguments.  One
consequence is that if {\tt PGACreate} is called twice in the same program
(unusual, but legal), the second {\tt PGACreate} call will {\em not} receive
the command-line arguments.

\item If one includes {\tt mpi.h} (or {\tt mpif.h}) when it should not be,
errors will result, as well as warnings about redefining macros and typedefs.
This usually happens when a sequential version of \pga\ is used (with ``fake''
MPI stub routines and definitions) and the user's program explicitly includes
``real'' {\tt mpi.h} or {\tt mpif.h} header files.

\item If one fails to include {\tt mpi.h} (or {\tt mpif.h}) when it
should be (such as calling MPI functions directly) errors may result.  Since
{\tt pgapack.h} includes {\tt mpi.h} this should not happen in C.
The Fortran include file, {\tt pgapackf.h}, however, does {\em not} include
{\tt mpif.h}.  The user must explicitly include it in every subroutine and
function that makes MPI calls.  Not including {\tt mpif.h} could result in
any of several different errors, including
\begin{itemize}
\item syntax errors when compiling (for example, {\tt MPI\_COMM\_WORLD} being
undefined)
\item general errors in the computed results
\item the program crashing when it calls the undefined subroutine {\tt MPI\_Init}
\item general MPI errors such as:
\begin{verbatim}
	0 - Error in MPI_COMM_RANK : Invalid communicator
	[0] Aborting program!
\end{verbatim}
\end{itemize}
We have also seen the following error from not including {\tt bmpif.h} in the
main program:
\begin{verbatim}
PGACreate: Invalid value of datatype: 0
PGAError: Fatal
\end{verbatim}

\item If the {\tt ch\_p4} device in {\tt MPICH} is used to run on workstations 
one must have a correct processor group file ({\tt procgroup}).  The error
message
\begin{verbatim}
(ptera-36%)a.out
p0_18429:  p4_error: open error on procgroup file (procgroup): 0
(ptera-37%)
\end{verbatim}
may occur if the processor group file is not specified correctly.  See the
{\tt MPICH} users guide for more details.

\item A common error with the {\tt procgroup} file when using the 
{\tt ch\_p4} device in {\tt MPICH} is to have an incorrect path to the
executable.

\item When compiling the {\tt examples} directory we have seen ``multiply
defined'' error messages. For example:
\begin{verbatim}
Making C examples
  Compiling classic
ld: /usr/local/mpi/lib/sun4/ch_p4/libmpi.a(initialize.o): _MPI_Initialized: multiply defined
collect2: ld returned 2 exit status
\end{verbatim}
We have seen this error occur when a sequential version of \pga\ was built and
the library ({\tt ./lib/arch/libpgag.a} or {\tt ./lib/arch/libpgaO.a}) was not
deleted before attempting to build a new, parallel version of \pga.  The
``fake'' MPI stub routines are in the sequential library and have name
conflicts when a ``real'' MPI library is referenced.  The solution is to
delete the old {\tt .a} file and rerun {\tt make install}.


\end{itemize}



%*****************************************************************************
% \chapter{Error Messages}\label{app:error-messages}
%*****************************************************************************

\vfill
\eject

% \include{sindex}
% \include{findex}

\bibliographystyle{plain}
\addcontentsline{toc}{chapter}{Bibliography}
\bibliography{user_guide}

\end{document}


99999999999
