build/pga/source/utility.c (261 lines of code) (raw):
/*
COPYRIGHT
The following is a notice of limited availability of the code, and disclaimer
which must be included in the prologue of the code and in all source listings
of the code.
(C) COPYRIGHT 2008 University of Chicago
Permission is hereby granted to use, reproduce, prepare derivative works, and
to redistribute to others. This software was authored by:
D. Levine
Mathematics and Computer Science Division
Argonne National Laboratory Group
with programming assistance of participants in Argonne National
Laboratory's SERS program.
GOVERNMENT LICENSE
Portions of this material resulted from work developed under a
U.S. Government Contract and are subject to the following license: the
Government is granted for itself and others acting on its behalf a paid-up,
nonexclusive, irrevocable worldwide license in this computer software to
reproduce, prepare derivative works, and perform publicly and display
publicly.
DISCLAIMER
This computer code material was prepared, in part, as an account of work
sponsored by an agency of the United States Government. Neither the United
States, nor the University of Chicago, nor any of their employees, makes any
warranty express or implied, or assumes any legal liability or responsibility
for the accuracy, completeness, or usefulness of any information, apparatus,
product, or process disclosed, or represents that its use would not infringe
privately owned rights.
*/
/*****************************************************************************
* FILE: utility.c: This file contains routines that perform utility
* functions.
*
* Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
* Brian P. Walenz
*****************************************************************************/
#include <pgapack.h>
/*U****************************************************************************
PGAMean - calculates the mean value of an array of elements
Category: Utility
Inputs:
ctx - context variable
a - array to take the mean of
n - number of elements in array a
Outputs:
The mean of the n elements in array a
Example:
PGAContext *ctx;
double a[100], mean;
:
mean = PGAMean(ctx, a, 100);
****************************************************************************U*/
double PGAMean ( PGAContext *ctx, double *a, int n)
{
int i;
double result;
PGADebugEntered("PGAMean");
result = 0.;
for( i=n-1; i>=0; i-- )
result += a[i];
PGADebugExited("PGAMean");
return (result / (double) n );
}
/*U****************************************************************************
PGAStddev - calculates the standard deviation of an array of elements
Category: Utility
Inputs:
ctx - context variable
a - array to take the standard deviation of
n - number of elements in array a
mean - the mean of the elements in array a
Outputs:
The standard deviation of the n elements in array a
Example:
PGAContext *ctx;
double a[100], mean, sigma;
:
mean = PGAMean(ctx, a, 100);
sigma = PGAStddev(ctx, a, 100, mean);
****************************************************************************U*/
double PGAStddev ( PGAContext *ctx, double *a, int n, double mean)
{
int i;
double result;
PGADebugEntered("PGAStddev");
result = 0;
for(i=n-1; i>=0; i--)
result += (a[i] - mean) * (a[i] - mean);
result = sqrt(result/n);
PGADebugExited("PGAStddev");
return (result);
}
/*U****************************************************************************
PGARound - Mathematically round a double to an integer, using 0.5 as the
cutoff value.
Category: Utility
Inputs:
ctx - context variable
x - the number to be rounded
Outputs:
The rounded number.
Example:
PGAContext *ctx;
int y;
y = PGARound(ctx, -78.6);
****************************************************************************U*/
int PGARound(PGAContext *ctx, double x)
{
double ipart, frac;
PGADebugEntered("PGARound");
frac = modf(x, &ipart);
if (frac <= -0.5)
ipart--;
else if (frac >= 0.5)
ipart++;
PGADebugExited("PGARound");
return ((int)ipart);
}
/*U****************************************************************************
PGACopyIndividual - copies string p1 in population pop1 to position p2 in
population pop2
Category: Generation
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:
String p2 is an exact copy of string p1.
Example:
PGAContext *ctx;
int i,j;
:
PGACopyIndividual(ctx, i, PGA_OLDPOP, j, PGA_NEWPOP);
****************************************************************************U*/
void PGACopyIndividual( PGAContext *ctx, int p1, int pop1, int p2, int pop2)
{
PGAIndividual *source, *dest;
PGADebugEntered("PGACopyIndividual");
source = PGAGetIndividual ( ctx, p1, pop1 );
dest = PGAGetIndividual ( ctx, p2, pop2 );
dest->evalfunc = source->evalfunc;
dest->fitness = source->fitness;
dest->evaluptodate = source->evaluptodate;
(*ctx->cops.CopyString)(ctx, p1, pop1, p2, pop2);
PGADebugExited("PGACopyIndividual");
}
/*U****************************************************************************
PGACheckSum - maps a string to a number to be used a verification check
PGA_DATATYPE_USER is not supported.
Category: Utility
Inputs:
ctx - context variable
p - string index
pop - symbolic constant for the population
Outputs:
An integer representing the "value" of the string.
Example:
PGAContext *ctx;
int p, sum;
:
sum = PGACheckSum(ctx, p, PGA_NEWPOP);
****************************************************************************U*/
int PGACheckSum(PGAContext *ctx, int p, int pop)
{
long stringlen, totalchars, charbits, i, j, checksum, totalbytes, out_bit;
unsigned char *message, specimen;
PGADebugEntered("PGACheckSum");
stringlen = PGAGetStringLength(ctx);
switch (ctx->ga.datatype) {
case PGA_DATATYPE_BINARY:
totalbytes = ctx->ga.tw * sizeof(PGABinary);
break;
case PGA_DATATYPE_INTEGER:
totalbytes = stringlen * sizeof(PGAInteger);
break;
case PGA_DATATYPE_REAL:
totalbytes = stringlen * sizeof(PGAReal);
break;
case PGA_DATATYPE_CHARACTER:
totalbytes = stringlen * sizeof(PGACharacter);
break;
default:
totalbytes = 0;
PGAError(ctx, "PGACheckSum: User datatype checksum may be invalid.",
PGA_WARNING, PGA_VOID, NULL);
break;
}
message = (unsigned char *)PGAGetIndividual(ctx, p, pop)->chrom;
totalchars = totalbytes / sizeof(unsigned char);
charbits = sizeof(unsigned char) * 8;
checksum = 0;
for (i = 0; i < totalchars; i++) {
specimen = *(message + i);
for (j = 0; j < charbits; j++) {
out_bit = (checksum & 0x80000000) == 1;
checksum = (checksum << 1) + ((specimen & 0x80) == 0x80);
if (out_bit)
checksum ^= 0x04c11db7;
specimen <<= 1;
}
}
PGADebugExited("PGACheckSum");
return (checksum);
}
/*U***************************************************************************
PGAGetWorstIndex - returns the index of the string with the worst
evaluation function value in population pop
Category: Utility
Inputs:
ctx - context variable
pop - symbolic constant of the population to find the worst string in
Outputs:
Index of the string with the worst evaluation function value
Example:
PGAContext *ctx;
int worst;
:
worst = PGAGetWorstIndex(ctx,PGA_OLDPOP);
***************************************************************************U*/
int PGAGetWorstIndex(PGAContext *ctx, int pop)
{
int p, worst_indx = 0;
double eval, worst_eval;
PGADebugEntered("PGAGetWorstIndex");
for (p = 0; p < ctx->ga.PopSize; p++)
if (!PGAGetEvaluationUpToDateFlag(ctx, p, pop))
PGAError(ctx, "PGAGetWorstIndex: Evaluate function not up to "
"date:", PGA_FATAL, PGA_INT, (void *) &p);
worst_eval = PGAGetEvaluation(ctx, 0, pop);
switch (PGAGetOptDirFlag(ctx)) {
case PGA_MAXIMIZE:
for (p = 1; p < ctx->ga.PopSize; p++) {
eval = PGAGetEvaluation(ctx, p, pop);
if (eval < worst_eval) {
worst_indx = p;
worst_eval = eval;
}
}
break;
case PGA_MINIMIZE:
for (p = 1; p < ctx->ga.PopSize; p++) {
eval = PGAGetEvaluation(ctx, p, pop);
if (eval > worst_eval) {
worst_indx = p;
worst_eval = eval;
}
}
break;
}
PGADebugExited("PGAGetWorstIndex");
return (worst_indx);
}
/*U***************************************************************************
PGAGetBestIndex - returns the index of the string with the best evaluation
function value in population pop
Category: Utility
Inputs:
ctx - context variable
pop - symbolic constant of the population to find the best string in
Outputs:
Index of the string with the best evaluation function value
Example:
PGAContext *ctx;
int best;
:
best = PGAGetBestIndex(ctx,PGA_OLDPOP);
***************************************************************************U*/
int PGAGetBestIndex(PGAContext *ctx, int pop)
{
int p, Best_indx = 0;
double eval, Best_eval;
PGADebugEntered("PGAGetBestIndex");
for (p = 0; p < ctx->ga.PopSize; p++)
if (!PGAGetEvaluationUpToDateFlag(ctx, p, pop))
PGAError(ctx, "PGAGetBestIndex: Evaluate function not up to "
"date:", PGA_FATAL, PGA_INT, (void *) &p);
Best_eval = PGAGetEvaluation(ctx, 0, pop);
switch (PGAGetOptDirFlag(ctx)) {
case PGA_MAXIMIZE :
for (p = 1; p < ctx->ga.PopSize; p++) {
eval = PGAGetEvaluation(ctx, p, pop);
if (eval > Best_eval) {
Best_indx = p;
Best_eval = eval;
}
}
break;
case PGA_MINIMIZE :
for (p = 1; p < ctx->ga.PopSize; p++) {
eval = PGAGetEvaluation(ctx, p, pop);
if (eval < Best_eval) {
Best_indx = p;
Best_eval = eval;
}
}
break;
}
PGADebugExited("PGAGetBestIndex");
return (Best_indx);
}
/*I****************************************************************************
PGAGetIndividual - translate string index and population symbolic constant
into pointer to an individual
Inputs:
ctx - context variable
p - string index
pop - symbolic constant of the population the string is in
Outputs:
Address of the PGAIndividual structure for string p in population pop
Example:
PGAIndividual *source;
PGAContext *ctx;
int p;
:
source = PGAGetIndividual ( ctx, p, PGA_NEWPOP );
****************************************************************************I*/
PGAIndividual *PGAGetIndividual ( PGAContext *ctx, int p, int pop)
{
PGAIndividual *ind;
PGADebugEntered("PGAGetIndividual");
#ifdef OPTIMIZE
ind = (pop == PGA_OLDPOP) ? ctx->ga.oldpop : ctx->ga.newpop;
if (p>=0)
ind += p;
else
ind += (p == PGA_TEMP1) ? ctx->ga.PopSize : ctx->ga.PopSize+1;
#else
if (pop == PGA_OLDPOP)
ind = ctx->ga.oldpop;
else
if (pop == PGA_NEWPOP)
ind = ctx->ga.newpop;
else
PGAError(ctx, "PGAGetIndividual: Invalid value of pop:",
PGA_FATAL, PGA_INT, (void *) &pop );
if (p>0 && p<ctx->ga.PopSize)
ind += p;
else
if (p == PGA_TEMP1)
ind += ctx->ga.PopSize;
else
if (p == PGA_TEMP2)
ind += ctx->ga.PopSize + 1;
else
PGAError(ctx, "PGAGetIndividual: Invalid value of p:",
PGA_FATAL, PGA_INT, (void *) &p );
#endif
PGADebugExited("PGAGetIndividual");
return(ind);
}
/*I****************************************************************************
PGAUpdateAverage - Updates the average fitness statistic for reporting.
Inputs:
ctx - context variable
pop - symbolic constant of the population
Outputs:
Example:
**************************************************************************I*/
void PGAUpdateAverage(PGAContext *ctx, int pop)
{
double ThisGensTotal = 0;
int p;
PGADebugEntered("PGAUpdateAverage");
for (p = 0; p < ctx->ga.PopSize; p++)
if (!PGAGetEvaluationUpToDateFlag(ctx, p, pop))
PGAError(ctx, "PGAUpdateOnline: Evaluate function not up to "
"date:", PGA_FATAL, PGA_INT, (void *) &p);
for (p = 0; p < ctx->ga.PopSize; p++)
ThisGensTotal += PGAGetEvaluation(ctx, p, pop);
ctx->rep.Average = ThisGensTotal / (double)ctx->ga.PopSize;
PGADebugExited("PGAUpdateAverage");
}
/*I****************************************************************************
PGAUpdateOnline - Updates the online value based on the results in
the new generation
Inputs:
ctx - context variable
pop - symbolic constant of the population whose statistics to use
Outputs:
Updates an internal field in the context variable
Example:
PGAContext *ctx;
:
PGAUpdateOnline(ctx,PGA_NEWPOP);
**************************************************************************I*/
void PGAUpdateOnline(PGAContext *ctx, int pop)
{
double ThisGensTotal = 0;
int p;
PGADebugEntered("PGAUpdateOnline");
for (p = 0; p < ctx->ga.PopSize; p++)
if (!PGAGetEvaluationUpToDateFlag(ctx, p, pop))
PGAError(ctx, "PGAUpdateOnline: Evaluate function not up to "
"date:", PGA_FATAL, PGA_INT, (void *) &p);
for (p = 0; p < ctx->ga.PopSize; p++)
ThisGensTotal += PGAGetEvaluation(ctx, p, pop);
PGADebugPrint(ctx, PGA_DEBUG_PRINTVAR, "PGAUpdateOnline",
"ThisGensTotal = ", PGA_DOUBLE, (void *) &ThisGensTotal);
ctx->rep.Online = (ctx->rep.Online * ctx->ga.PopSize * (ctx->ga.iter - 1)
+ ThisGensTotal) / ctx->ga.iter / ctx->ga.PopSize;
PGADebugExited("PGAUpdateOnline");
}
/*I****************************************************************************
PGAUpdateOffline - Updates the offline value based on the results in
the new generation
Inputs:
ctx - context variable
pop - symbolic constant of the population whose statistics to use
Outputs:
Updates an internal field in the context variable
Example:
PGAContext *ctx;
:
PGAUpdateOffline(ctx,PGA_NEWPOP);
**************************************************************************I*/
void PGAUpdateOffline(PGAContext *ctx, int pop)
{
int p;
PGADebugEntered("PGAUpdateOffline");
for (p = 0; p < ctx->ga.PopSize; p++)
if (!PGAGetEvaluationUpToDateFlag(ctx, p, pop))
PGAError(ctx, "PGAUpdateOffline: Evaluate function not up to "
"date:", PGA_FATAL, PGA_INT, (void *) &p);
p = PGAGetBestIndex(ctx, pop);
ctx->rep.Offline = ((ctx->ga.iter - 1) * ctx->rep.Offline +
PGAGetEvaluation(ctx, p, pop)) / ctx->ga.iter;
PGADebugExited("PGAUpdateOffline");
}
/*I****************************************************************************
PGAComputeSimilarity - computes the percentage of the population that have
the same evaluation function
Inputs:
ctx - context variable
pop - symbolic constant of the population whose statistics to use
Outputs:
returns a count of the number of population members that have the same
evaluation function value
Example:
PGAContext *ctx;
:
PGAComputeSimilarity(ctx,PGA_NEWPOP);
**************************************************************************I*/
int PGAComputeSimilarity(PGAContext *ctx, PGAIndividual *pop)
{
int max = 0, curr = 1, i;
double prev;
PGADebugEntered("PGAComputeSimilarity");
for(i=0; i < ctx->ga.PopSize; i++)
{
ctx->scratch.dblscratch[i] = (pop + i)->evalfunc;
ctx->scratch.intscratch[i] = i;
}
PGADblHeapSort(ctx, ctx->scratch.dblscratch, ctx->scratch.intscratch,
ctx->ga.PopSize);
prev = ctx->scratch.dblscratch[0];
for(i = 1; i < ctx->ga.PopSize; i++)
{
if (ctx->scratch.dblscratch[i] == prev)
curr++;
else
{
if (curr > max)
max = curr;
curr = 1;
}
}
PGADebugExited("PGAComputeSimilarity");
return(100 * max / ctx->ga.PopSize);
}