You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spamassassin.apache.org by da...@apache.org on 2017/05/28 18:31:51 UTC
svn commit: r1796518 [3/19] - in /spamassassin/trunk/build/pga: ./ docs/
examples/ examples/c/ examples/fortran/ examples/mgh/ examples/templates/
include/ lib/ lib/linux/ man/ man/man1/ man/man2/ man/man3/ man/man4/
man/man5/ man/man6/ man/man7/ man/m...
Added: spamassassin/trunk/build/pga/docs/user_guide.tex
URL: http://svn.apache.org/viewvc/spamassassin/trunk/build/pga/docs/user_guide.tex?rev=1796518&view=auto
==============================================================================
--- spamassassin/trunk/build/pga/docs/user_guide.tex (added)
+++ spamassassin/trunk/build/pga/docs/user_guide.tex Sun May 28 18:31:49 2017
@@ -0,0 +1,4277 @@
+%\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
[... 2371 lines stripped ...]