source: trunk/optimizer/src/pgapack/gekco/pgapack/source/duplcate.c @ 815

/*
 *  
 *  ********************************************************************* 
 *  (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: duplicate.c: This file contains the routines that have to do with
*                        testing for duplicate strings
*
*     Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
*              Brian P. Walenz
*****************************************************************************/

#include "pgapack.h"

/*U****************************************************************************
  PGADuplicate - determines if a specified string is a duplicate of one
  already in an existing population

  Category: Generation

  Inputs:
     ctx  - context variable
     p    - string index
     pop1 - symbolic constant of the population containing string p
     pop2 - symbolic constant of the (possibly partial) population containing
            strings to compare string p against
     n    - the number of strings in pop2 to compare string p against
            (indexed 0,...,n-1)

  Outputs:
     Returns PGA_TRUE if PGAGetNoDuplicates() returns PGA_TRUE and
     string p in population pop1 is a duplicate of at least one strings
     0,...,n-1 in population pop2.  Otherwise returns PGA_FALSE

  Example:
     Change any string in PGA_NEWPOP that is an exact copy of a string
     in PGA_OLDPOP.

     PGAContext *ctx;
     int b, n;
     :
     n  = PGAGetPopsize(ctx);
     for (b=0; b<n; b++)
         if (PGADuplicate(ctx, b, PGA_NEWPOP, PGA_OLDPOP, n))
             PGAChange(ctx, b, PGA_NEWPOP);


     Check if the best string in population PGA_OLDPOP is a duplicate of any
     of the strings in the first half of population PGA_NEWPOP.

     PGAContext *ctx;
     int b, n;
     :
     b  = PGAGetBestIndex(ctx, PGA_OLDPOP);
     n  = PGAGetPopsize(ctx) / 2;
     if (PGADuplicate(ctx, b, PGA_OLDPOP, PGA_NEWPOP, n))
         printf("A duplicate!\n");

****************************************************************************U*/
int PGADuplicate(PGAContext *ctx, int p, int pop1, int pop2, int n)
{
    int p2, fp;
    int RetVal = PGA_FALSE;
    
    PGADebugEntered("PGADuplicate");
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "p = ",
                  PGA_INT, (void *) &p );
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "pop1 = ",
                  PGA_INT, (void *) &pop1 );
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "pop2 = ",
                  PGA_INT, (void *) &pop2 );
    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "n  = ",
                  PGA_INT, (void *) &n );
    
    if (ctx->ga.NoDuplicates == PGA_TRUE) {
        if (ctx->fops.Duplicate) {
            fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
            for (p2 = 1; p2 <= n; p2++)
                if ((*ctx->fops.Duplicate)(&ctx, &fp, &pop1, &p2, &pop2)) {
                    RetVal = PGA_TRUE;
                    p2 = n+1;
                }
        } else {
            for (p2 = 0; p2 < n; p2++)
                if ((*ctx->cops.Duplicate)(ctx, p, pop1, p2, pop2)) {
                    RetVal = PGA_TRUE;
                    p2 = n;
                }
        }
    }
    
    PGADebugExited("PGADuplicate");
    
    return(RetVal);
}


/*U****************************************************************************
  PGAChange - Repeatedly apply mutation to a string (with an increasing
  mutation rate) until one or more mutations have occurred.  This routine is
  usually used with PGADuplicate to modify a duplicate string.  It is not
  intended to replace PGAMutation

  Category: Generation

  Inputs:
     ctx  - context variable
     p    - string index
     pop  - symbolic constant of the population containing string p

  Outputs:
     Mutates string p in population pop via side effect.

  Example:
     Change any string in PGA_NEWPOP that is an exact copy of a string
     in PGA_OLDPOP.  To be complete, we should check the population again
     if any changes are made; for simplicity, we don't.

     PGAContext *ctx;
     int b, n;
     :
     n  = PGAGetPopsize(ctx);
     for (b=0; b<n; b++)
         if (PGADuplicate(ctx, b, PGA_NEWPOP, PGA_OLDPOP, n))
             PGAChange(ctx, b, PGA_NEWPOP);

****************************************************************************U*/
void PGAChange( PGAContext *ctx, int p, int pop )
{
    int    changed = PGA_FALSE;
    int    fp, nflips;
    double mr;

    PGADebugEntered("PGAChange");

    mr = ctx->ga.MutationProb;

    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR, "PGAChange", " mr = ",
                   PGA_DOUBLE, (void *) &mr );

    while (( changed == PGA_FALSE ) && (mr <= 1.0)) {
        if (ctx->fops.Mutation) {
            fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
            nflips = (*ctx->fops.Mutation)(&ctx, &fp, &pop, &mr);
        } else {
            nflips = (*ctx->cops.Mutation)( ctx, p, pop, mr );
        }

        if ( nflips > 0 )
        {
        
            /***********************************************/ 
            /***********************************************/ 
            /*************** BUG THAT WAS FOUND ************/ 
            /**** EHW and SNS ADDITION *********************/
            /***********************************************/ 
            /***********************************************/ 
            PGASetEvaluationUpToDateFlag(ctx,p,pop,PGA_FALSE); 
            /***********************************************/ 
            /***********************************************/ 
            changed = PGA_TRUE;

        }
        else
            mr = 1.1*mr;
    }

    if (changed == PGA_FALSE) {
        PGAError(ctx, "Could not change string:", PGA_WARNING, PGA_VOID, NULL);
        PGAPrintString(ctx, stderr, p, pop);
    }

    PGADebugExited("PGAChange");
}

/*U****************************************************************************
   PGASetNoDuplicatesFlag - A boolean flag to indicate if duplicate strings are
   allowed in the population. Valid choices are PGA_TRUE and PGA_FALSE.  The
   default is PGA_FALSE -- allow duplicates.

   Category: Generation

   Inputs:
      ctx  - context variable
      flag - PGA_TRUE or PGA_FALSE

   Outputs:
      None

   Example:
      Set the NoDuplicates flag to require that all strings are unique.

      PGAContext *ctx;
      :
      PGASetNoDuplicatesFlag(ctx,PGA_TRUE);

****************************************************************************U*/
void PGASetNoDuplicatesFlag( PGAContext *ctx, int no_dup)
{
    PGADebugEntered("PGASetNoDuplicatesFlag");

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

    PGADebugExited("PGASetNoDuplicatesFlag");
}

/*U***************************************************************************
   PGAGetNoDuplicatesFlag - Returns PGA_TRUE if duplicates are not allowed,
   else returns PGA_FALSE.

   Category: Generation

   Inputs:
      ctx - context variable

   Outputs:
      The value of the NoDuplicates flag.

   Example:
      PGAContext *ctx;
      int nodups;
      :
      nodups = PGAGetNoDuplicatesFlag(ctx);
      switch (nodups) {
      case PGA_TRUE:
          printf("Duplicate strings not allowed in population\n");
          break;
      case PGA_FALSE:
          printf("Duplicate strings allowed in population\n");
          break;
      }

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

    PGAFailIfNotSetUp("PGAGetNoDuplicatesFlag");

    PGADebugExited("PGAGetNoDuplicatesFlag");

    return(ctx->ga.NoDuplicates);
}