source: trunk/optimizer/src/pgapack/pgapack/source/binary.c @ 816

/*
 *  
 *  ********************************************************************* 
 *  (C) COPYRIGHT 1995 UNIVERSITY OF CHICAGO 
 *  *********************************************************************
 *  
 *  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 Argonne National 
 *  Laboratory's SERS program.
 *  
 *  This program contains material protectable under copyright laws of the 
 *  United States.  Permission is hereby granted to use it, reproduce it, 
 *  to translate it into another language, and to redistribute it to 
 *  others at no charge except a fee for transferring a copy, provided 
 *  that you conspicuously and appropriately publish on each copy the 
 *  University of Chicago's copyright notice, and the disclaimer of 
 *  warranty and Government license included below.  Further, permission 
 *  is hereby granted, subject to the same provisions, to modify a copy or 
 *  copies or any portion of it, and to distribute to others at no charge 
 *  materials containing or derived from the material.
 *  
 *  The developers of the software ask that you acknowledge its use in any 
 *  document referencing work based on the  program, such as published 
 *  research.  Also, they ask that you supply to Argonne National 
 *  Laboratory a copy of any published research referencing work based on 
 *  the software.
 *  
 *  Any entity desiring permission for further use must contact:
 *  
 *  J. Gleeson
 *  Industrial Technology Development Center Argonne National Laboratory
 *  Argonne IL 60439
 *  gleesonj@smtplink.eid.anl.gov
 *  (708) 252-6055
 *  
 *  ******************************************************************** 
 *  DISCLAIMER
 *  
 *  THIS PROGRAM WAS PREPARED AS AN ACCOUNT OF WORK SPONSORED BY AN AGENCY 
 *  OF THE UNITED STATES GOVERNMENT.  NEITHER THE UNIVERSITY OF CHICAGO, 
 *  THE UNITED STATES GOVERNMENT NOR ANY OF THEIR EMPLOYEES MAKE ANY 
 *  WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL LIABILITY OR 
 *  RESPONSIBILITY FOR THE ACCURACY, COMPLETENESS, OR USEFULNESS OF ANY 
 *  INFORMATION OR PROCESS DISCLOSED, OR REPRESENTS THAT ITS USE WOULD NOT 
 *  INFRINGE PRIVATELY OWNED RIGHTS.
 *  
 *  ********************************************************************** 
 *  GOVERNMENT LICENSE
 *  
 *  The Government is granted for itself and others acting on its behalf a 
 *  paid-up, non-exclusive, irrevocable worldwide license in this computer 
 *  software to reproduce, prepare derivative works, and perform publicly 
 *  and display publicly.
 */

/*****************************************************************************
*     File: binary.c: This file contains routines specific to the binary
*                     datatype.
*
*     Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
*              Brian P. Walenz
*****************************************************************************/

#include "pgapack.h"

/*U****************************************************************************
   PGASetBinaryAllele - sets a binary allele to the specified value.

   Category: Fitness & Evaluation

   Inputs:
      ctx - context variable
      p   - string index
      pop - symbolic constant of the population the string is in
      i   - allele index
      val - binary value (either 1 or 0) to set the allele to

   Outputs:
      The allele is changed by side-effect.

   Example:
      Copies the alleles from member p in PGA_OLDPOP to member q PGA_NEWPOP.
      Assumes strings are of the same length.

      PGAContext *ctx;
      int p, q, i;
      :
      for (i=PGAGetStringLength(ctx)-1; i>=0; i--)
          PGASetBinaryAllele(ctx, q, PGA_NEWPOP, i,
                             PGAGetBinaryAllele(ctx, p, PGA_OLDPOP, i))

****************************************************************************U*/
void PGASetBinaryAllele ( PGAContext *ctx, int p, int pop, int i, int val )
{
    int windex;        /* index of the computer word allele i is in      */
    int bix;           /* bit position in word chrom[windex] of allele i */
    PGAIndividual *ind;
    PGABinary *chrom;

    PGADebugEntered("PGASetBinaryAllele");
    PGACheckDataType("PGAGetBinaryAllele", PGA_DATATYPE_BINARY);

    INDEX( windex,bix,i,WL );
    ind = PGAGetIndividual ( ctx, p, pop );
    chrom = (PGABinary *)ind->chrom;
    if ( val == 0 )
        UNSET( bix, chrom[windex] );
    else
        SET( bix, chrom[windex] );

    PGADebugExited("PGASetBinaryAllele");
}

/*U****************************************************************************
   PGAGetBinaryAllele - returns the value of a (binary) allele in a
   PGA_DATATYPE_BINARY string

   Category: Fitness & Evaluation

   Inputs:
      ctx - context variable
      p   - string index
      pop - symbolic constant of the population the string is in
      i   - allele index

   Outputs:
      The value of the ith allele of string p in population pop.

   Example:
      Copies the alleles from member p in PGA_OLDPOP to member q PGA_NEWPOP.
      Assumes the strings are of the same length.

      PGAContext *ctx;
      int p, q, i;
      :
      for (i=PGAGetStringLength(ctx)-1; i>=0; i--)
          PGASetBinaryAllele(ctx, q, PGA_NEWPOP, i,
                             PGAGetBinaryAllele(ctx, p, PGA_OLDPOP, i))

****************************************************************************U*/
int PGAGetBinaryAllele ( PGAContext *ctx, int p, int pop, int i )
{

    int windex;        /* index of the computer word allele i is in      */
    int bix;           /* bit position in word chrom[windex] of allele i */
    PGAIndividual *ind;
    PGABinary *chrom;

    PGADebugEntered("PGAGetBinaryAllele");
    PGACheckDataType("PGAGetBinaryAllele", PGA_DATATYPE_BINARY);

    INDEX( windex,bix,i,WL );
    ind = PGAGetIndividual ( ctx, p, pop );
    chrom = (PGABinary *)ind->chrom;

    PGADebugExited("PGAGetBinaryAllele");
    return( BIT(bix, chrom[windex]) != 0 );
}

/*U****************************************************************************
   PGASetBinaryInitProb - specify the probability of initializing an allele to
   "1" when creating a PGA_DATATYPE_BINARY string.  The default value is 0.5.

   Category: Initialization

   Inputs:
      ctx - context variable
      p   - the binary initialization probability

   Outputs:
      None

   Example:
      Set approximately 1 percent of all binary alleles to "1" when randomly
      initializing the population.

      PGAContext *ctx;
      :
      PGASetBinaryInitProb(ctx, 0.01);

****************************************************************************U*/
void PGASetBinaryInitProb ( PGAContext *ctx, double probability )
{
    PGADebugEntered("PGASetBinaryInitProb");
    PGAFailIfSetUp("PGASetBinaryInitProb");
    PGACheckDataType("PGASetBinaryInitProb", PGA_DATATYPE_BINARY);

     if ( (probability <= 1.0) && (probability >= 0.0) )
          ctx->init.BinaryProbability = probability;
     else
          PGAError( ctx, "PGASetBinaryInitProb: Invalid value of probability:",
                   PGA_FATAL, PGA_DOUBLE, (void *) &probability );

    PGADebugExited("PGASetBinaryInitProb");
}

/*U***************************************************************************
   PGAGetBinaryInitProb - Returns the probability that an allele will be
   randomly initialized to "1" in a PGA_DATATYPE_BINARY string.

   Category: Initialization

   Inputs:
      ctx - context variable

   Outputs:
      The probability that a bit will be randomly initialized to one

   Example:
      PGAContext *ctx;
      double prob;
      :
      prob = PGAGetBinaryInitProb(ctx);

***************************************************************************U*/
double PGAGetBinaryInitProb (PGAContext *ctx)
{
    PGADebugEntered("PGAGetBinaryInitProb");
    PGAFailIfNotSetUp("PGAGetBinaryInitProb");
    PGACheckDataType("PGAGetBinaryInitProb", PGA_DATATYPE_BINARY);

    PGADebugExited("PGAGetBinaryInitProb");
    return(ctx->init.BinaryProbability);
}


/*I****************************************************************************
   PGABinaryCreateString - Allocate a PGA_DATATYPE_BINARY string for member
   p of population pop.  If initflag is PGA_TRUE, randomly initialize all
   alleles, otherwise clear all alleles.

   Inputs:
      ctx      - context variable
      p        - string index
      pop      - symbolic constant of the population string p is in
      initflag - a flag, if set, randomly initialize, else clear alleles

   Outputs:
      Member p in population pop is allocated and initialized.

   Example:
      Allocates and clears alleles for all strings in PGA_NEWPOP

      PGAContext *ctx;
      int p;
      :
      for (p=PGAGetPopSize(ctx)-1; p>=0; p--)
          PGABinaryCreateString( ctx, p, PGA_NEWPOP, PGA_FALSE );

****************************************************************************I*/
void PGABinaryCreateString(PGAContext *ctx, int p, int pop, int initflag)
{
    int i, fp;
    PGABinary *s;
    PGAIndividual *new = PGAGetIndividual(ctx, p, pop);
    
    PGADebugEntered("PGABinaryCreateString");
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR, "PGABinaryCreateString",
                  "initflag = ", PGA_INT, (void *) &initflag );
    
    new->chrom = (void *)malloc(ctx->ga.tw * sizeof(PGABinary));
    if (new->chrom == NULL)
        PGAError(ctx, "PGABinaryCreateString: No room to allocate "
                 "new->chrom", PGA_FATAL, PGA_VOID, NULL);
    
    s = (PGABinary *)new->chrom;
    if (initflag)
        if (ctx->fops.InitString) {
            fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
            (*ctx->fops.InitString)(&ctx, &fp, &pop);
        } else {
            (*ctx->cops.InitString)(ctx, p, pop);
        }
    else
        for ( i=0; i<ctx->ga.tw; i++ )
            s[i] = 0;
    
    PGADebugExited("PGABinaryCreateString");
}

/*I****************************************************************************
   PGABinaryMutation - randomly mutates a bit with a specified probability.
   This routine is called from PGAMutation.

   Inputs:
      ctx - context variable
      p   - string index
      pop - symbolic constant for the population string p is in
      mr  - probability of mutating (toggling) a bit

   Outputs:
      Returns the number of mutations

   Example:
      Mutates string p in population PGA_NEWPOP with a probability of 0.001
      for each bit.

      PGAContext *ctx;
      int p;
      :
      PGABinaryMutation( ctx, p, PGA_NEWPOP, .001 );

****************************************************************************I*/
int PGABinaryMutation( PGAContext *ctx, int p, int pop, double mr )
{
     int i,wi;
     int count = 0;
     PGABinary *c;

     PGADebugEntered("PGABinaryMutation");

     c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
     for(wi=0; wi<ctx->ga.fw; wi++)
          for(i=0; i<WL; ++i)
               if ( PGARandomFlip(ctx, mr) )
               {
                    TOGGLE(i,c[wi]);
                    count++;
               }

     /* clean up the partial word if eb > 0 */
     if (ctx->ga.eb > 0 )
          for(i=0;i<ctx->ga.eb;++i)
               if ( PGARandomFlip(ctx, mr) )
               {
                    TOGGLE(i,c[ctx->ga.fw]);
                    count++;
               }

    PGADebugExited("PGABinaryMutation");
    return(count);

}

/*I****************************************************************************
   PGABinaryOneptCrossover - performs one-point crossover on two parent strings
   to create two children via side-effect

   Inputs:
      ctx  - context variable
      p1   - the first parent string
      p2   - the second parent string
      pop1 - symbolic constant of the population containing p1 and p2
      c1   - the first child string
      c2   - the second child string
      pop2 - symbolic constant of the population containing c1 and c2

   Outputs:
      None.

   Example:
      Performs crossover on the two parent strings m and d, producing
      children s and b.

      PGAContext *ctx;
      int m, d, s, b;
      :
      PGABinaryOneptCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryOneptCrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1,
                             int c2, int pop2)
{
    PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
    PGABinary *child1  = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
    PGABinary *child2  = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;

    /*
      If the bits are numbered from 0 as follows:

      b   b   b   b   b   b   b   b          b  b
      0   1   2   3   4   5   6   7         30 31

      Then if the cross site is bit 5 (which is the sixth bit by our
      numbering scheme) we would get

      o   o   o   o   o   n   n   n          n  n
      0   1   2   3   4   5   6   7         30 31

      where o indicates the original bit and n is a new bit from the crossover
      operator.
    */

    PGABinary mask;
    int windex;   /* index of the word the crossover bit position is in */
    int bix;      /* bit position to perform crossover (mod WL)         */
    int i;
    int xsite;

    PGADebugEntered("PGABinaryOneptCrossover");

    xsite = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);

    INDEX(windex,bix,xsite,WL);

    for(i=0;i<windex;i++) {
        child1[i] = parent1[i];
        child2[i] = parent2[i];
    }

    mask = ~0;
    mask = mask >> bix;

    child1[windex] = (~mask & parent1[windex])|(mask & parent2[windex]);
    child2[windex] = (~mask & parent2[windex])|(mask & parent1[windex]);

    for(i=windex+1;i<ctx->ga.tw;i++) {
        child1[i] = parent2[i];
        child2[i] = parent1[i];
    }

    PGADebugExited("PGABinaryOneptCrossover");
}


/*I****************************************************************************
   PGABinaryTwoptCrossover - performs two-point crossover on two parent strings
   producing two children via side-effect

   Inputs:
      ctx  - context variable
      p1   - the first parent string
      p2   - the second parent string
      pop1 - symbolic constant of the population containing string p1 and p2
      c1   - the first child string
      c2   - the second child string
      pop2 - symbolic constant of the population to contain string c1 and c2

   Outputs:
      None.

   Example:
      Performs crossover on the two parent strings m and d, producing
      children s and b.

      PGAContext *ctx;
      int m, d, s, b;
      :
      PGABinaryTwoptCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryTwoptCrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1,
                             int c2, int pop2)
{
    PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
    PGABinary *child1  = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
    PGABinary *child2  = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;

    PGABinary mask, mask1, mask2;
    int windex1, windex2;
    int bix1, bix2;
    int i;
    int xsite1, xsite2;
    int temp;

    PGADebugEntered("PGABinaryTwoptCrossover");

    /* pick two cross sites such that xsite2 > xsite1 */
    xsite1 = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
    xsite2 = xsite1;
    while ( xsite2 == xsite1 )
        xsite2 = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
    if ( xsite1 > xsite2 ) {
        temp   = xsite1;
        xsite1 = xsite2;
        xsite2 = temp;
    }

    INDEX(windex1,bix1,xsite1,WL);
    INDEX(windex2,bix2,xsite2,WL);

    if ( windex1 == windex2 ) {     /* both cross sites in the same word */

        for(i=0;i<windex1;i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }

        mask1 = ~0;
        if (bix1 == 0)
             mask1 = 0;
        else
             mask1 = mask1 << (WL-bix1);
        mask2 = ~0;
        mask2 = mask2 >> bix2;
        mask  = mask1 | mask2;

        child1[windex1] = (mask & parent1[windex1])|(~mask & parent2[windex1]);
        child2[windex1] = (mask & parent2[windex1])|(~mask & parent1[windex1]);

        for(i=windex1+1;i<ctx->ga.tw;i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }
    }
    else {                          /* cross sites in different words */

        for(i=0;i<windex1;i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }

        mask = ~0;
        mask = mask >> bix1;

        child1[windex1] = (~mask & parent1[windex1])|(mask & parent2[windex1]);
        child2[windex1] = (~mask & parent2[windex1])|(mask & parent1[windex1]);

        for(i=windex1+1; i<windex2; i++) {
            child1[i] = parent2[i];
            child2[i] = parent1[i];
        }

        mask = ~0;
        mask = mask >> bix2;

        child1[windex2] = (mask & parent1[windex2])|(~mask & parent2[windex2]);
        child2[windex2] = (mask & parent2[windex2])|(~mask & parent1[windex2]);

        for(i=windex2+1; i<ctx->ga.tw; i++) {
            child1[i] = parent1[i];
            child2[i] = parent2[i];
        }
    }

    PGADebugExited("PGABinaryTwoptCrossover");
}


/*I****************************************************************************
   PGABinaryUniformCrossover - performs uniform crossover on two parent strings
   producing two children via side-effect

   Inputs:
      ctx  - context variable
      p1   - the first parent string
      p2   - the second parent string
      pop1 - symbolic constant of the population containing string p1 and p2
      c1   - the first child string
      c2   - the second child string
      pop2 - symbolic constant of the population to contain string c1 and c2

   Outputs:
      None.

   Example:
      Performs crossover on the two parent strings m and d, producing
      children s and b.

      PGAContext *ctx;
      int m, d, s, b;
      :
      PGABinaryUniformCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryUniformCrossover(PGAContext *ctx, int p1, int p2, int pop1,
                               int c1, int c2, int pop2)
{
     PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
     PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
     PGABinary *child1  = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
     PGABinary *child2  = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;
     PGABinary mask;
     int j,wi;

    PGADebugEntered("PGABinaryUniformCrossover");

    for(wi=0;wi<ctx->ga.tw;wi++) {
        if ( parent1[wi] == parent2[wi] ) {
            child1[wi] = parent1[wi];
            child2[wi] = parent2[wi];
        }
        else {
            mask = 0;
            for (j=0;j<WL;j++)
                if(PGARandomFlip(ctx, ctx->ga.UniformCrossProb))
                    SET(j,mask);
            child1[wi] = (mask & parent1[wi])|(~mask & parent2[wi]);
            child2[wi] = (mask & parent2[wi])|(~mask & parent1[wi]);
        }
    }

    PGADebugExited("PGABinaryUniformCrossover");
}

/*I****************************************************************************
   PGABinaryPrintString - writes a bit string to a file.

   Inputs:
      ctx - context variable
      fp  - file pointer to file to write bit string to
      p   - index of the string to write out
      pop - symbolic constant of the population string p is in

   Outputs:
      None.

   Example:
      Write string s to stdout.

      PGAContext *ctx;
      int s;
      :
      PGABinaryPrintString( ctx, stdout, s, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryPrintString( PGAContext *ctx, FILE *fp, int p, int pop )
{
     PGABinary *c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
     int i;

     PGADebugEntered("PGABinaryPrintString");

     for( i=0; i<ctx->ga.fw; i++ ) {
          fprintf(fp,"[ ");
          PGABinaryPrint( ctx, fp, (c+i), WL );
          fprintf(fp," ]\n");
     }
     if ( ctx->ga.eb > 0 ) {
          fprintf(fp,"[ ");
          PGABinaryPrint( ctx, fp, (c+ctx->ga.fw), ctx->ga.eb );
          fprintf(fp," ]");
     }

     PGADebugExited("PGABinaryPrintString");
}

/*I****************************************************************************
   PGABinaryCopyString - Copy one bit string to another

   Inputs:
      ctx  - context variable
      p1   - string to copy
      pop1 - symbolic constant of population containing string p1
      p2   - string to copy p1 to
      pop2 - symbolic constant of population containing string p2

   Outputs:
      None.

   Example:
      Copy bit string x to y (both are implicitly assumed to have the same
      length).

      PGAContext *ctx;
      int x, y
      :
      PGABinaryCopyString ( ctx, x, PGA_OLDPOP, y, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryCopyString (PGAContext *ctx, int p1, int pop1, int p2, int pop2)
{
    PGABinary *source = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
    PGABinary *dest   = (PGABinary *)PGAGetIndividual(ctx, p2, pop2)->chrom;
    int i;

    PGADebugEntered("PGABinaryCopyString");

    for (i = ctx->ga.tw-1; i>=0; i--)
        dest[i] = source[i];

    PGADebugExited("PGABinaryCopyString");
}

/*I****************************************************************************
   PGABinaryDuplicate - Returns true if bit string a is a duplicate of bit
   string b, else returns false.

   Inputs:
      ctx  - context variable
      p1   - string index of the first string to compare
      pop1 - symbolic constant of the population string p1 is in
      p2   - string index of the second string to compare
      pop2 - symbolic constant of the population string p2 is in

   Outputs:
      Returns true/false if strings are duplicates

   Example:
      Compare bit string x with y and print a message if they are the same.

      PGAContext *ctx;
      int x, y;
      :
      if ( PGABinaryDuplicate( ctx, x, PGA_NEWPOP, y, PGA_NEWPOP ) )
          printf("strings are duplicates\n");

****************************************************************************I*/
int PGABinaryDuplicate( PGAContext *ctx, int p1, int pop1, int p2, int pop2)
{
     PGABinary *a = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
     PGABinary *b = (PGABinary *)PGAGetIndividual(ctx, p2, pop2)->chrom;
     int wi;

     PGADebugEntered("PGABinaryDuplicate");

     wi = ctx->ga.tw-1;
     if (a[0] == b[0])
         for (; (wi>0) && (a[wi] == b[wi]); wi--);

     PGADebugExited("PGABinaryDuplicate");

     return((wi==0) ? PGA_TRUE : PGA_FALSE);
}

/*I****************************************************************************
   PGABinaryInitString - randomly initialize a string of type PGABinary

   Inputs:
      ctx - context variable
      p   - index of string to randomly initialize
      pop - symbolic constant of the population string p is in

   Outputs:

   Example:
      PGAContext *ctx;
      int p;
      :
      PGABinaryInitString ( ctx, p, PGA_NEWPOP );

****************************************************************************I*/
void PGABinaryInitString(PGAContext *ctx, int p, int pop)
{
     PGABinary *c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
     int i;
     int windex;        /* index of the computer word allele i is in      */
     int bix;           /* binary position in word chrom[windex] of allele i */

     PGADebugEntered("PGABinaryInitString");

     for (i = 0; i < ctx->ga.tw; i++)
          c[i] = 0;
     for (i = 0; i < ctx->ga.StringLen; i++)
     {
          INDEX(windex,bix,i,WL);
          if ( PGARandomFlip(ctx, ctx->init.BinaryProbability) )
               SET  ( bix, c[windex] );
     }

     PGADebugExited("PGABinaryInitString");
}


/*I****************************************************************************
  PGABinaryBuildDatatype - Build an MPI_Datatype for a binary string
  datatype.

  Inputs:
      ctx  - context variable
      p    - index of the string to build a datatype from
      pop  - symbolic constant of the population string p is in

  Outputs:
      MPI_Datatype.

  Example:
      Called only by MPI routines.  Not for user consumption.

****************************************************************************I*/
MPI_Datatype PGABinaryBuildDatatype(PGAContext *ctx, int p, int pop)
{

     int            counts[4];      /* Number of elements in each
                                       block (array of integer) */
     MPI_Aint       displs[4];      /* byte displacement of each
                                       block (array of integer) */
     MPI_Datatype   types[4];       /* type of elements in each block (array
                                       of handles to datatype objects) */
     MPI_Datatype   individualtype; /* new datatype (handle) */
     PGAIndividual *traveller;      /* address of individual in question */

     PGADebugEntered("PGABinaryBuildDatatype");

     traveller = PGAGetIndividual(ctx, p, pop);
     MPI_Address(&traveller->evalfunc, &displs[0]);
     counts[0] = 1;
     types[0]  = MPI_DOUBLE;

     MPI_Address(&traveller->fitness, &displs[1]);
     counts[1] = 1;
     types[1]  = MPI_DOUBLE;

     MPI_Address(&traveller->evaluptodate, &displs[2]);
     counts[2] = 1;
     types[2]  = MPI_INT;

     MPI_Address(traveller->chrom, &displs[3]);
     counts[3] = ctx->ga.tw;
     types[3]  = MPI_UNSIGNED_LONG;

     MPI_Type_struct(4, counts, displs, types, &individualtype);
     MPI_Type_commit(&individualtype);

     PGADebugExited("PGABinaryBuildDatatype");

     return (individualtype);
}


/*I****************************************************************************
   PGABinaryHammingDistance - Returns the Hamming distance between two strings

   Inputs:
      ctx - context variable
      s1  - the first string to compare
      s2  - the second string to compare

   Outputs:
      The Hamming distance between two strings

   Example:
      Returns the Hamming distance between bit strings x and y.

      PGAContext *ctx;
      PGABinary *x, *y;
      int d;
      :
      d = PGABinaryHammingDistance( ctx, x, y );

****************************************************************************I*/
int PGABinaryHammingDistance ( PGAContext *ctx, PGABinary *s1, PGABinary *s2 )
{
    int        j, wi, distance;
    PGABinary  t1, t2, mask;

    PGADebugEntered("PGABinaryHammingDistance");

    distance = 0;
    for(wi=0; wi<ctx->ga.tw; wi++)  /* step through each word in the string */
        if ( s1[wi] != s2[wi] ) {   /* if equal, no bits are different      */
            /*fprintf(stdout,"s1[wi] = %x, s2[wi] = %x\n",s1[wi],s2[wi]);*/
            mask = 1;
            for(j=0;j<WL;++j) {     /* not equal, compare all bits          */
                /* Build bit mask in position j. Mask bit from each         */
                /* string into t1 and t2 and test if bits are the same      */
                t1 = s1[wi] & mask;
                t2 = s2[wi] & mask;
                /*fprintf(stdout,"mask = %u, t1 = %u, t2 = %u, j = %d, wi = %d\n",mask,t1,t2,j,wi);*/
                if ( t1 != t2 )
                    distance++;
                mask <<= 1;          /* shift mask 1 position */
            }
        }

    PGADebugExited("PGABinaryHammingDistance");

    return(distance);
}

/*I****************************************************************************
   PGABinaryPrint - writes a bit string to a file.  Puts the binary
   representation of the bit string pointed to by chrom into a character
   string and writes that out. Assumes the maximum length of string to
   print is WL, and that all bits are in the same word.

   Inputs:
      ctx   - context variable
      fp    - file to write the bit string to
      chrom - pointer to the bit string to write
      nb    - number of bits to write out

   Outputs:

   Example:
      Internal function.  Use PGABinaryPrintString to print a binary string.

****************************************************************************I*/
void PGABinaryPrint( PGAContext *ctx, FILE *fp, PGABinary *chrom, int nb )
{
     char *s, string[WL+1];
     PGABinary mask;
     int i;

     PGADebugEntered("PGABinaryPrint");

     mask = ((PGABinary)1)<<(WL-1);
     s = string;
     for(i=0; i<nb; mask>>=1,i++)              /* mask each bit and set the  */
          *s++ = (mask&(*chrom)?'1':'0');      /* appropriate character      */
     *s=0;                                     /* string terminator          */
     fprintf(fp, "%s", string);                /* print out character string */

     PGADebugExited("PGABinaryPrint");
}