source: trunk/optimizer/src/pgapack/pgapack/source/pga.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: pga.c: This file contains all the routines that are data structure
*                  neutral
*
*     Authors: David M. Levine, Philip L. Hallstrom, and David M. Noelle,
*              Brian P. Walenz
*****************************************************************************/

#include "pgapack.h"

/*U****************************************************************************
  PGARun - Highest level routine to execute the genetic algorithm.  It
  is called after PGACreate and PGASetup have been called.

  Category: Generation

  Inputs:
    ctx      - context variable
    evaluate - a pointer to the user's evaluation function, which must
               have the calling sequence shown in the example.

  Outputs:
    none

  Example:
    PGAContext *ctx,
    double f(PGAContext *ctx, int p, int pop);
    :
    ctx = PGACreate(&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE);
    PGASetUp(ctx);
    PGARun(ctx, f);
    PGADestroy(ctx);

****************************************************************************U*/
void PGARun(PGAContext *ctx, double (*evaluate)(PGAContext *c, int p, int pop))
{
     MPI_Comm comm;                  /* value of default communicator */
     int nprocs;                     /* number of processes in above  */
     int npops;                      /* number of populations         */
     int ndemes;                     /* number of demes               */
     

     PGADebugEntered("PGARun");
     PGAFailIfNotSetUp("PGARun");

     comm   = PGAGetCommunicator(ctx);
     nprocs = PGAGetNumProcs    (ctx, comm);
     npops  = PGAGetNumIslands  (ctx);
     ndemes = PGAGetNumDemes    (ctx);

     /**********************************************************************/
     /*              Global model, one island, one deme                    */
     /**********************************************************************/
     if     ( (npops == 1) && (ndemes == 1) ) {

         PGARunGM(ctx, evaluate, comm);
     }
     
     /**********************************************************************/
     /*              Island model, > one island, one deme                  */
     /**********************************************************************/
     else if( (npops > 1) && (ndemes == 1) ) {
         if ( nprocs == 1 )
             PGAError (ctx, "PGARun: island model with one process",
                       PGA_FATAL, PGA_VOID, (void *) &nprocs);
         if ( nprocs != npops) {
             PGAError (ctx, "PGARun: island model no. processes != no. pops",
                       PGA_FATAL, PGA_VOID, (void *) &nprocs);
         }
         PGARunIM(ctx,evaluate,comm);
     }
             
     /**********************************************************************/
     /*              Neighborhood model, one island, > one deme            */
     /**********************************************************************/
     else if( (npops == 1) && (ndemes > 1) ) {
         if ( nprocs == 1 )
             PGAError (ctx, "PGARun: neighborhood model with one process",
                       PGA_FATAL, PGA_VOID, (void *) &nprocs);
         if ( nprocs != ndemes)
             PGAError (ctx, "PGARun: neighborhood model no. processes "
                       "!= no. demes", PGA_FATAL, PGA_VOID, (void *) &nprocs);
         PGARunNM(ctx,evaluate,comm);
     }
             
     /**********************************************************************/
     /*              Mixed model, > one island, > one deme                 */
     /**********************************************************************/
     else if( (npops > 1) && (ndemes > 1) ) {
         PGAError (ctx, "PGARun: Cannot execute mixed models",
                   PGA_FATAL, PGA_VOID, (void *) &nprocs);
     }

     /**********************************************************************/
     /*                        E R R O R                                   */
     /**********************************************************************/
     else {
         PGAError (ctx, "PGARun: Invalid combination of numislands,"
                   "ndemes, and nprocs.",
                   PGA_FATAL, PGA_VOID, (void *) &nprocs);
     }

     /**********************************************************************/
     /*                         E X I T                                    */
     /**********************************************************************/
     PGADebugExited("PGARun");
     return;
 }


/*U****************************************************************************
  PGARunMutationAndCrossover - Performs crossover and mutation from one
  population to create the next.  Assumes PGASelect has been called.

  Category: Generation

  Inputs:
    ctx - context variable
    oldpop - symbolic constant of old population
    newpop - symbolic constant of new population

  Outputs:
    newpop is modified by side-effect.

  Example:
     PGAContext *ctx,
    :
    PGARunMutationAndCrossover(ctx, PGA_OLDPOP, PGA_NEWPOP);

****************************************************************************U*/
void PGARunMutationAndCrossover (PGAContext *ctx, int oldpop, int newpop)
{
    int i, j, n, m1, m2;
    int popsize, numreplace;
    double pc;

    PGADebugEntered("PGARunMutationAndCrossover");

    popsize = PGAGetPopSize(ctx);
    numreplace = PGAGetNumReplaceValue(ctx);
    /*** first, copy n best strings (sorted by fitness) to new pop ***/
    PGASortPop( ctx, oldpop );
    n = popsize - numreplace;
    for ( i=0; i < n; i++ ) {
        j = PGAGetSortedPopIndex( ctx, i );
        PGACopyIndividual ( ctx, j, oldpop, i, newpop );
    }
    pc = PGAGetCrossoverProb(ctx);
    /*** reproduce to create the rest of the new population ***/
    while ( n < popsize) {
        m1 = PGASelectNextIndex( ctx );
        m2 = PGASelectNextIndex( ctx );
        if ( PGARandomFlip(ctx, pc) ) {
             PGACrossover ( ctx, m1, m2, oldpop, PGA_TEMP1,
                            PGA_TEMP2, newpop);

              /*** mutate and copy first string to new population ***/
              PGAMutate ( ctx, PGA_TEMP1, newpop);
              while (PGADuplicate( ctx, PGA_TEMP1, newpop, newpop, n))
                   PGAChange ( ctx, PGA_TEMP1, newpop );
              PGACopyIndividual ( ctx, PGA_TEMP1, newpop, n, newpop);
              n++;

              if ( n < popsize ) {
              /*** mutate and copy second string to new population ***/
              PGAMutate ( ctx, PGA_TEMP2, newpop);
              while ( PGADuplicate( ctx, PGA_TEMP2, newpop, newpop, n))
                   PGAChange ( ctx, PGA_TEMP2, newpop );
              PGACopyIndividual ( ctx, PGA_TEMP2, newpop, n, newpop);
              n++;
              }
         }
         else {
            PGACopyIndividual ( ctx, m1, oldpop, n, newpop );
            n++;
            if ( n < ctx->ga.PopSize ) {
                PGACopyIndividual ( ctx, m2, oldpop, n, newpop );
                n++;
            }
       }
    }

    PGADebugExited("PGARunMutationAndCrossover");
}


/*U****************************************************************************
  PGARunMutationOrCrossover - Performs crossover or mutation (but not both)
  from one populationto create the next.  Assumes PGASelect has been called.

  Category: Generation

  Inputs:
    ctx - context variable
    oldpop - symbolic constant of old population
    newpop - symbolic constant of new population

  Outputs:
    newpop is modified by side-effect.

  Example:
    PGAContext *ctx,
    :
    PGARunMutationOrCrossover(ctx, PGA_OLDPOP, PGA_NEWPOP);

****************************************************************************U*/
void PGARunMutationOrCrossover ( PGAContext *ctx, int oldpop, int newpop )
{
    int i, j, n, m1, m2;
    int popsize, numreplace;
    double pc;

    PGADebugEntered("PGARunMutationOrCrossover");

    popsize = PGAGetPopSize(ctx);
    numreplace = PGAGetNumReplaceValue(ctx);
    /*** first, copy n best strings (sorted by fitness) to new pop ***/
    PGASortPop( ctx, oldpop );
    n = popsize - numreplace;
    for ( i=0; i < n; i++ ) {
        j = PGAGetSortedPopIndex( ctx, i );
        PGACopyIndividual ( ctx, j, oldpop, i, newpop );
    }
    pc = PGAGetCrossoverProb(ctx);
    /*** reproduce to create the rest of the new population ***/
    while ( n < popsize ) {
        m1 = PGASelectNextIndex( ctx );
        m2 = PGASelectNextIndex( ctx );
        if ( PGARandomFlip(ctx, pc) ) {
            PGACrossover ( ctx, m1, m2, oldpop, PGA_TEMP1,
                                        PGA_TEMP2, newpop);

            /*** copy first string to new population ***/
            while (PGADuplicate(ctx, PGA_TEMP1, newpop,  newpop, n))
                PGAChange ( ctx, PGA_TEMP1, newpop );
            PGACopyIndividual ( ctx, PGA_TEMP1, newpop, n, newpop);
            n++;

            if ( n < popsize )
            {
                 /*** copy second string to new population ***/
                 while (PGADuplicate(ctx, PGA_TEMP2, newpop,  newpop, n))
                      PGAChange ( ctx, PGA_TEMP2, newpop );
                 PGACopyIndividual ( ctx, PGA_TEMP2, newpop, n, newpop);
                 n++;
            }
        }
        else
        {
             PGACopyIndividual(ctx, m1, oldpop, PGA_TEMP1, newpop);
             PGAMutate ( ctx, PGA_TEMP1, newpop );
             while (PGADuplicate(ctx, PGA_TEMP1, newpop, newpop, n ))
                  PGAChange ( ctx, PGA_TEMP1, newpop );
             PGACopyIndividual ( ctx, PGA_TEMP1, newpop, n, newpop);
             n++;

             if ( n < popsize ) {
                  PGACopyIndividual(ctx, m2, oldpop, PGA_TEMP2, newpop);
                  PGAMutate ( ctx, PGA_TEMP2, newpop );
                  while (PGADuplicate(ctx, PGA_TEMP2, newpop, newpop, n ))
                       PGAChange ( ctx, PGA_TEMP2, newpop );
                  PGACopyIndividual ( ctx, PGA_TEMP2, newpop, n, newpop);
                  n++;
             }
        }
    }

    PGADebugExited("PGARunMutationOrCrossover");
}


/*U****************************************************************************
  PGAUpdateGeneration - updates internal data structures for the next
  genetic algorithm iteration, and checks if the termination conditions, both
  user and PGAPack, have been met.  This routine must be called by both
  master and slave processes at the end of each GA generation.

  Category: Generation

  Inputs:
     ctx  - context variable
     comm - an MPI communicator

  Outputs:
     PGA_TRUE if the genetic algorithm has terminated, otherwise PGA_FALSE.

  Example:
    PGAContext *ctx;
    :
    PGAUpdateGeneration(ctx, MPI_COMM_WORLD);

****************************************************************************U*/
void PGAUpdateGeneration(PGAContext *ctx, MPI_Comm comm)
{
    PGAIndividual *temp;
    int i, rank;

    PGADebugEntered("PGAUpdateGeneration");
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGAUpdateGeneration",
                  "ga.iter = ", PGA_INT, (void *) &(ctx->ga.iter) );

    rank = PGAGetRank(ctx, comm);

    ctx->ga.iter++;

    if (rank == 0) {
        if (ctx->rep.PrintOptions & PGA_REPORT_AVERAGE)
            PGAUpdateAverage(ctx, PGA_NEWPOP);

        if (ctx->rep.PrintOptions & PGA_REPORT_ONLINE)
            PGAUpdateOnline(ctx, PGA_NEWPOP);

        if (ctx->rep.PrintOptions & PGA_REPORT_OFFLINE)
            PGAUpdateOffline(ctx, PGA_NEWPOP);

        if ((ctx->ga.StoppingRule & PGA_STOP_NOCHANGE) || ctx->ga.restart) {
            i = PGAGetBestIndex(ctx, PGA_NEWPOP);
            if (ctx->rep.Best == PGAGetEvaluation(ctx, i, PGA_NEWPOP))
                ctx->ga.ItersOfSame++;
            else {
                ctx->rep.Best = PGAGetEvaluation(ctx, i, PGA_NEWPOP);
                ctx->ga.ItersOfSame = 1;
            }
        }

        if (ctx->ga.StoppingRule & PGA_STOP_TOOSIMILAR)
            ctx->ga.PercentSame = PGAComputeSimilarity(ctx, ctx->ga.newpop);

        /*  Clear this twice in case the user EOG calls PGASelect.  */
        ctx->ga.SelectIndex = 0;

        if (ctx->fops.EndOfGen)
            (*ctx->fops.EndOfGen)(&ctx);
        if (ctx->cops.EndOfGen)
            (*ctx->cops.EndOfGen)(ctx);

        ctx->ga.SelectIndex = 0;
        temp           = ctx->ga.oldpop;
        ctx->ga.oldpop = ctx->ga.newpop;
        ctx->ga.newpop = temp;
    }

    PGADebugExited("PGAUpdateGeneration");
}


/*U***************************************************************************
   PGAGetDataType - Returns the data type used by the given context.

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      Returns the integer corresponding to the symbolic constant
      used to specify the data type.

   Example:
      PGAContext *ctx;
      int datatype;
      :
      datatype = PGAGetDataType(ctx);
      switch (datatype) {
      case PGA_DATATYPE_BINARY:
          printf("Data Type = PGA_DATATYPE_BINARY\n");
          break;
      case PGA_DATATYPE_CHARACTER:
          printf("Data Type = PGA_DATATYPE_CHARACTER\n");
          break;
      case PGA_DATATYPE_INTEGER:
          printf("Data Type = PGA_DATATYPE_INTEGER\n");
          break;
      case PGA_DATATYPE_REAL:
          printf("Data Type = PGA_DATATYPE_REAL\n");
          break;
      case PGA_DATATYPE_USER:
          printf("Data Type = PGA_DATATYPE_USER\n");
          break;
      }

***************************************************************************U*/
int PGAGetDataType (PGAContext *ctx)
{
    PGADebugEntered("PGAGetDataType");

    PGADebugExited("PGAGetDataType");

    return(ctx->ga.datatype);
}

/*U***************************************************************************
   PGAGetOptDirFlag - Returns a symbolic constant that represents the
   direction of optimization

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      Returns the integer corresponding to the symbolic constant
      used to specify the  direction of optimization

   Example:
      PGAContext *ctx;
      int optdir;
      :
      optdir = PGAGetOptDirFlag(ctx);
      switch (optdir) {
      case PGA_MAXIMIZE:
          printf("Optimization direction = PGA_MAXIMIZE\n");
          break;
      case PGA_MINIMIZE:
          printf("Optimization direction = PGA_MINIMIZE\n");
          break;
      }

***************************************************************************U*/
int PGAGetOptDirFlag (PGAContext *ctx)
{
    PGADebugEntered("PGAGetOptDirFlag");

    PGADebugExited("PGAGetOptDirFlag");

    return(ctx->ga.optdir);
}

/*U***************************************************************************
   PGAGetStringLength - Returns the string length

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      The string length

   Example:
      PGAContext *ctx;
      int stringlen;
      :
      stringlen = PGAGetStringLength(ctx);

***************************************************************************U*/
int PGAGetStringLength (PGAContext *ctx)
{
    PGADebugEntered("PGAGetStringLength");

    PGADebugExited("PGAGetStringLength");

    return(ctx->ga.StringLen);
}

/*I***************************************************************************
   PGAGetVariableStringLength - Returns the length of a variable length
   string.

   Category: Generation

   Inputs:
      ctx - context variable
      p   - index into the population
      pop - symbolic constant for the population

   Outputs:
      The string length

   Example:
      PGAContext *ctx;
      int stringlen;
      :
      stringlen = PGAGetVariableStringLength(ctx, 0, PGA_NEWPOP);

***************************************************************************I*/
int PGAGetVariableStringLength (PGAContext *ctx, int p, int pop)
{
    PGADebugEntered("PGAGetVariableStringLength");

    PGADebugExited("PGAGetVariableStringLength");

    PGAError(ctx, "PGAGetVariableStringLength:  Variable length strings not "
             "currently supported.", PGA_FATAL, PGA_VOID, NULL);
#if 0
    ind = PGAGetIndividual(ctx, p, pop);
    return(ind->StringLength);
#endif
    /*  Make the compilers be quiet.  */
    return(0);
}

/*U***************************************************************************
  PGAGetGAIterValue - returns the number of the current genetic
  algorithm generation

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      The genetic algorithm generation number

   Example:
      PGAContext *ctx;
      int g;
      :
      g = PGAGetGAIterValue(ctx);

***************************************************************************U*/
int PGAGetGAIterValue (PGAContext *ctx)
{
    PGADebugEntered("PGAGetGAIterValue");
    PGAFailIfNotSetUp("PGAGetGAIterValue");

    PGADebugExited("PGAGetGAIterValue");

    return(ctx->ga.iter);
}

/*U****************************************************************************
  PGASetMutationOrCrossoverFlag - A boolean flag to indicate if recombination
  uses exactly one of crossover or mutation on selected strings.

   Category: Generation

   Inputs:
      ctx  - context variable
      flag - PGA_TRUE (default) or PGA_FALSE

   Outputs:
      None

   Example:
      Set the genetic algorithm to use mutation only when crossover is
      not used.

      PGAContext *ctx;
      :
      PGASetMutationOrCrossoverFlag(ctx,PGA_FALSE);

****************************************************************************U*/
void PGASetMutationOrCrossoverFlag( PGAContext *ctx, int flag)
{
    PGADebugEntered("PGASetMutationOrCrossoverFlag");

     switch (flag)
     {
     case PGA_TRUE:
     case PGA_FALSE:
          ctx->ga.MutateOnlyNoCross = flag;
          break;
     default:
          PGAError (ctx, "PGASetMutationOrCrossoverFlag: Invalid value of "
                    "flag:", PGA_FATAL, PGA_INT, (void *) &flag);
          break;
     }

    PGADebugExited("PGASetMutationOrCrossoverFlag");
}

/*U****************************************************************************
  PGASetMutationAndCrossoverFlag - A boolean flag to indicate if
  recombination uses both crossover and mutation on selected strings

   Category: Generation

   Inputs:
      ctx  - context variable
      flag - PGA_TRUE (default) or PGA_FALSE

   Outputs:
      None

   Example:
      Set the genetic algorithm to use both crossover and mutation when
      reproducing strings.

      PGAContext *ctx;
      :
      PGASetMutationAndCrossoverFlag(ctx,PGA_FALSE);

****************************************************************************U*/
void PGASetMutationAndCrossoverFlag( PGAContext *ctx, int flag)
{
    PGADebugEntered("PGASetMutationAndCrossoverFlag");

     switch (flag)
     {
     case PGA_TRUE:
     case PGA_FALSE:
          ctx->ga.MutateOnlyNoCross = !flag;
          break;
     default:
          PGAError (ctx, "PGASetMutationAndCrossoverFlag: Invalid value of "
                    "flag:", PGA_FATAL, PGA_INT, (void *) &flag);
          break;
     }

    PGADebugExited("PGASetMutationAndCrossoverFlag");
}
/*U***************************************************************************
   PGAGetMutationOrCrossoverFlag - Returns true if mutation only occurs when
   crossover does not.

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      Returns PGA_TRUE if mutation only occurs when crossover does not,
      otherwise, returns PGA_FALSE.

   Example:
      PGAContext *ctx;
      int mutatetype;
      :
      mutatetype = PGAGetMutationOrCrossoverFlag(ctx);
      switch (mutatetype) {
      case PGA_TRUE:
          printf("Only mutating strings not undergoing crossover\n");
          break;
      case PGA_FALSE:
          printf("Mutating strings only after crossover\n");
          break;
      }

***************************************************************************U*/
int PGAGetMutationOrCrossoverFlag (PGAContext *ctx)
{
    PGADebugEntered("PGAGetMutationOrCrossoverFlag");
    PGAFailIfNotSetUp("PGAGetMutationOrCrossoverFlag");

    PGADebugExited("PGAGetMutationOrCrossoverFlag");

    return(ctx->ga.MutateOnlyNoCross);
}

/*U***************************************************************************
   PGAGetMutationAndCrossoverFlag - Returns true if mutation occurs only
   when crossover does.

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      Returns PGA_TRUE if mutation is applied to crossed-over strings.
      Otherwise, returns PGA_FALSE

   Example:
      PGAContext *ctx;
      int mutatetype;
      :
      mutatetype = PGAGetMutationAndCrossoverFlag(ctx);
      switch (mutatetype) {
      case PGA_TRUE:
          printf("Mutating strings only after crossover\n");
          break;
      case PGA_FALSE:
          printf("Only mutating strings not undergoing crossover\n");
          break;
      }

***************************************************************************U*/
int PGAGetMutationAndCrossoverFlag (PGAContext *ctx)
{
    PGADebugEntered("PGAGetMutationAndCrossoverFlag");
    PGAFailIfNotSetUp("PGAGetMutationAndCrossoverFlag");

    PGADebugExited("PGAGetMutationAndCrossoverFlag");

    return(!ctx->ga.MutateOnlyNoCross);
}