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

PGAPack C Program for the Maxbit Example

#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 ith bit of string p in population pop.

Maxbit Problem in Fortran

PGAPack Fortran Program for the Maxbit Example

      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

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.

Specifying Nondefault Values for Differential Evolution

    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

PGAPack Maxbit Example in C with 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).

PGAPack Maxbit Example in Fortran with I/O

      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 to pgapackf.h from the directory you are compiling a Fortran program in.
2: See Appendix Parallelism Background