Getting Started
Introduction
PGAPack 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 PGAPack are as follows:
Ability to be called from Fortran or C.
Executable on uniprocessors, multiprocessors, multicomputers, and workstation networks.
Binary-, integer-, real-, and character-valued native data types.
Object-oriented data structure neutral design.
Parameterized population replacement.
Multiple choices for selection, crossover, and mutation operators.
Easy integration of hill-climbing heuristics.
Easy-to-use interface for novice and application users.
Multiple levels of access for expert users.
Full extensibility to support custom operators and new data types.
Extensive debugging facilities.
Large set of example problems.
Examples
This chapter presents some simple PGAPack programs. The problem chosen is the Maxbit problem. The objective is to maximize the number of 1-bits in a string.
Section Maxbit Problem in C presents a simple PGAPack program
in C whose structure is sufficient to solve many problems.
Section Maxbit Problem in Fortran presents this same program
in Fortran. Section Specifying Nondefault Values shows how to change
default values in PGAPack.
Section Parallel I/O contains an example that
shows how keyboard input may be read in an MPI environment. Finally,
Section Compiling, Linking, and Execution shows how to compile, link, and execute a
PGAPack program. These and other examples may be found in the
./examples/c
and ./examples/fortran
directories.
Maxbit Problem in C
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop, double *aux);
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, double *aux)
{
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;
}
Figure PGAPack C Program for the Maxbit Example shows a minimal
program and evaluation function in C for the Maxbit problem. All
PGAPack C programs must include the header file pgapack.h
. The
PGACreate()
call is always the first function called in a
PGAPack program. It initializes the context variable, ctx
. The
parameters to PGACreate()
are the arguments to the program (given by
argc
and argv
), the data type selected
(PGA_DATATYPE_BINARY
), the string length (100
), and the
direction of optimization (PGA_MAXIMIZE
). The
PGASetUp()
call initializes all parameters and function pointers
not explicitly set by the user to default values.
PGARun()
executes the genetic algorithm. Its second argument is the
name of a user-defined function (evaluate
) that will be called to
evaluate the strings. PGADestroy()
releases all memory allocated by
PGAPack. Note that all PGAPack functions take the context variable as an
argument (except PGACreate()
, which creates the context variable).
The evaluate
function must be written by the user, must return a
double
, and must follow the exact calling sequence shown. An
evaluation function may return more values than just the return value in
the array pointed to by aux
. This can be used for evaluating
constraints for constrained problems or for multi-objective
optimization. Often the number of auxiliary return values is zero and
the aux
argument is ignored. For details, see
section String Evaluation and Fitness. PGAGetStringLength()
returns the
string length. PGAGetBinaryAllele()
returns the value of the i
th
bit of string p
in population pop
.
Maxbit Problem in Fortran
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
The Fortran Maxbit problem in Figure PGAPack Fortran Program for the Maxbit Example
is similar to the C version above. The Fortran
include file is pgapackf.h
and should be included in every Fortran
function or subroutine that makes PGAPack calls 1. Since Fortran
provides no standard mechanism for specifying command line arguments,
these are omitted from the PGACreate()
function call. The context
variable, ctx
, is declared integer
in Fortran.
The evaluation function evaluate
must contain exactly the calling
sequence shown and must return a double precision
value. The aux
value is optional in fortran because fortran does less strict
type-checking than C and with standard calling conventions the argument
can be omitted if not needed. Note that evaluate
is declared in an
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 1:stringlen
, rather than
0:stringlen-1
as in C.
Specifying Nondefault Values
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop, double *aux);
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;
}
PGAPack offers a wide range of choices for parameter values, operators,
and algorithmic choices. These will be set to default values in
PGASetUp()
if the user does not explicitly set a value for them. A
nondefault value may be set by using the PGASet
family of calls after PGACreate()
has been called, but
before PGASetUp()
has been called.
In Figure Specifying Nondefault values the PGASet
calls change the default values for population size, fitness
calculation, and crossover type. PGASetPopSize()
changes the
population size to 500. PGASetFitnessType()
specifies that the fitness
values be determined by using a ranking procedure rather than by direct
use of the evaluation function values. PGASetCrossoverType()
specifies
that uniform crossover, rather than the default of two-point crossover
is to be used. Most PGASet calls are discussed in
Chapter Basic Usage.
Differential Evolution
Differential Evolution (DE) is an evolutionary algorithm (EA) invented
by Price and Storn in the 1990’s [SP95], [SP97], [PSL05]. It
is used with floating-point and integer genes and uses differences of
individuals (floating-point vectors) which are added to another vector
to form a donor vector which is then crossed-over with an existing
individual. The algorithm is described in more detail in
section Mutation. Since in PGAPack the DE
algorithm is implemented in a mutation strategy, typically for DE a
strategy with only mutation is selected, see PGASetMixingType()
with
option PGA_MIX_MUTATE_ONLY
in
section Population Replacement.
DE applies selection pressure during population replacement: A
newly-mutated string replaces its parent if it has the same or a better
fitness. There is no selection mechanism during the selection phase like
in other EAs. To emulate this (non-) selection, PGAPack introduces a new
selection type, linear selection, enabled with the parameter
PGA_SELECT_LINEAR
of PGASetPopReplaceType()
which just returns all individuals in
sequence and is no selection operator in the genetic-algorithm sense
because no selection pressure is applied. More details of the selection
operator for DE are given in section Selection.
PGASetPopSize (ctx, 30);
PGASetNumReplaceValue (ctx, 30);
PGASetSelectType (ctx, PGA_SELECT_LINEAR);
PGASetPopReplaceType (ctx, PGA_POPREPL_PAIRWISE_BEST);
PGASetMixingType (ctx, PGA_MIX_MUTATE_ONLY);
PGASetMutationType (ctx, PGA_MUTATION_DE);
PGASetMutationBounceBackFlag (ctx, PGA_TRUE);
For the population replacement strategy the pairwise-best replacement
type is introduced for DE, enabled with the parameter
PGA_POPREPL_PAIRWISE_BEST
of PGASetPopReplaceType()
,
which can also be used in other EA variants
due to the modular nature of PGAPack, more details are given in
section Population Replacement. Typical settings for
Differential Evolution are given in
figure Specifying Nondefault Values for Differential Evolution. In that example
the population size and the number of individuals replaced in each
generation are set to the same value (with PGASetPopSize()
and
PGASetNumReplaceValue()
, respectively):
Since DE’s replacement strategy
replaces individuals only if they are better than an existing individual
this strategy is elitist and it makes sense to apply DE to all
individuals in each generation.
Parallel I/O
#include "pgapack.h"
double evaluate (PGAContext *ctx, int p, int pop, double *aux);
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;
}
The examples in
Figures PGAPack Maxbit Example in C with I/O (C) and
PGAPack Maxbit Example in Fortran with I/O
(Fortran) read values for the two parameters len
(string length) and
maxiter
(maximum number of GA iterations) from standard input. These
examples will work correctly with either a sequential or parallel
version of PGAPack. However, the explicit use of MPI calls for I/O is
necessary only if a parallel version of PGAPack 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 Parallelism Background for further details.
MPI_Init(&argc, &argv)
is always the first function called in any
MPI program. Each process executes
MPI_Comm_rank(MPI_COMM_WORLD, &myid)
to determine its unique rank in
the communicator 2 MPI_COMM_WORLD
. The logic used in this program
is to have process 0
read and write from/to standard input/output
and broadcast (using MPI_Bcast
) the parameters to the other
processes. The PGAPack function calls are similar to those in the
previous examples. If the user called MPI_Init
, the user must also
call MPI_Finalize
before exiting.
We elaborate here on the 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
[MPI94], [GLS94] or a newer MPI reference [MPI21].
The C binding for MPI_Bcast
is
int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int root, MPI_Comm comm)
and the Fortran binding
MPI_BCAST(buffer, count, datatype, root, comm, ierror)
<type> buffer(*)
integer count, datatype, root, comm, ierror
MPI_Bcast
will result in every process in communicator comm
receiving a copy of the contents of buf
/buffer
. The other
parameters are the number of items (count
), the datatype
(datatype
), which may be one of MPI_DOUBLE
, MPI_INT
,
MPI_CHAR
, MPI_UNSIGNED
, or MPI_LONG
; the rank of the process
with the original copy (root
); the MPI communicator (comm
); and,
for Fortran, a variable to handle an error return code (ierror
).
include 'pgapackf.h'
include 'mpif.h'
double precision evaluate
external evaluate
integer(8) ctx
integer myid, len, maxiter, ierror
call MPI_Init(ierror)
call MPI_Comm_rank(MPI_COMM_WORLD, myid, ierror)
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
Compiling, Linking, and Execution
When PGAPack was installed, the makefiles in the ./examples/c
and
./examples/fortran
directories were correctly configured for the
machine PGAPack 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 PGAPack library (and MPI library if a parallel version of
PGAPack was built), and build your executable.
How you execute your program will depend on whether a sequential or
parallel version of PGAPack was built, the MPI implementation used and
the machine you are running on. If a sequential version of PGAPack was
built (i.e., one where the user did not supply a version of MPI), the
executable maxbit
can be executed on a uniprocessor Unix system by
typing maxbit
. If the MPICH
implementation of MPI was used, it
may be executed (using four processes) by mpirun maxbit -np 4
.
Appendix Machine Idiosyncrasies contains some examples.
- 1
Since not all Fortran compilers support the
-I
mechanism for specifying the include file search path, you may need to copy or set up a symbolic link topgapackf.h
from the directory you are compiling a Fortran program in.- 2
See Appendix Parallelism Background