/*
C code for the H-IFF GA test function. 

This version does not include the resource-based fitness sharing. 

If this is useful to you please let me know and I can forward anything 
else you need/ answer any questions you might have. 

I would be interested to know if you end-up using it in your work
 - please send me an email.

Have fun. 
love, 
Richard.
richardw@cs.brandeis.edu
www.cs.brandeis.edu/~richardw
*/
  

/*============ HIFF test function and test examples ===========*/ 

/* compile line:   cc -o testhiff hiff_func.c -lm              */ 

#include <stdio.h> 
#include <math.h> 
#include <sys/time.h> 

#define NUMGENES 16  /* must equal K^P */ 
#define K 2          /* sub-blocks per block */ 
#define P 4          /* num of hierarchical levels eg N=16 so P=4 */ 
#define Rc 2         /* ratio of block contributions - originally 2 */ 
#define NONVALUE -1  /* null value for transform function (usually shown as "-") */ 
#define SHUFFLE 0    /* 0-ordinary HIFF, 1-shuffled HIFF */ 
  
  

/*=============================================================*/ 

double H(double *genes); 
double f(double b); 
double t(double* block, int first); 
void printme(); 
void make_shuffle(); 
int random_index(); 
void init_random(); 

/*================ a few test examples ========================*/ 
  

double testme[NUMGENES]; 
int order[NUMGENES]; 

main(){ 

  int i; 

  init_random(); 
  make_shuffle(); 

  for(i=0;i<NUMGENES;i++)  testme[i]=0; 
  printme(); /* perfect= 80 */ 

  for(i=0;i<NUMGENES-1;i+=2) {testme[i]=0;testme[i+1]=1;}; 
  printme();  /* useless= 16 */ 

  for(i=1;i<NUMGENES;i++)  testme[i]=0; testme[0]=1; 
  printme();  /* all but one= 50 */ 

  for(i=0;i<NUMGENES/K;i++) testme[i]=0; 
  for(i=NUMGENES/K;i<NUMGENES;i++) testme[i]=1; 
  printme();  /* half and half= 64 */ 

  for(i=0;i<NUMGENES-1;i+=2) {testme[i]=0;testme[i+1]=1;};testme[0]=NONVALUE; 
  printme();  /* useless and one null = 15*/ 
} 

void printme() 
{ 
  int i; 
  for(i=0;i<NUMGENES;i++)  printf("%d",(int)(testme[i])); 
  printf ("  value = %f \n",H(testme)); 
} 
  

void make_shuffle() 
{ 
  int index, tmp, i; 
  for (i=0; i<NUMGENES; i++) order[i] = i; 
  if (SHUFFLE) 
    for (i=0; i<NUMGENES; i++) 
      { 
  index = random_index(); 
  tmp = order[i]; 
  order[i] = order[index]; 
  order[index] = tmp; 
      } 
  for (i=0; i<NUMGENES; i++) {printf("%d ", order[i]);} printf("\n"); 
} 

int random_index() 
{ 
 return (int)floor(drand48()*NUMGENES); 
} 

void init_random(void)  { 
   struct timeval tp; 
   struct timezone tzp; 
   gettimeofday(&tp, &tzp); 
   srand48(tp.tv_usec); 
} 

/*============================= H-IFF ======================================*/ 
  

/* 
H-IFF is defined using the main function H, and the two base functions f 
and t. 
H is a generalised construction for Hierarchical functions using 
base-functions f and t  - H works for any number of sub-blocks per block 
(K)(also good for any size alphabet). 
H-IFF is H with K=2 (ie. 2 subblocks per block= pairs of bits in the 
first level) and with Rc=2 (ratio of contributions) and with appropriate 
base functions f and t. 
The versions of f and t given below make H calculate H-IFF. 
The original H-IFF doubles bonus at each level ie Rc=2. (ratio of 
contributions). 
P is the number of levels in the heirarchy; NUMGENES must be 2^P 
(assuming K=2). 
If using no null values in candidates, ie not Messy GA, then evaluation 
at level 0 simply adds a constant==NUMGENES. 
This version has no resource-based fitness-sharing. And does not shuffle 
bits. 

the only tricky data structure is 'transform', a vector used to store 
intermediate 
transforms of the genes as we progress up levels in the hierarchy. 
For a 16 bit example string, transform will have the following 
contents.. 

 level  transformed_string  contents_of_transform 
   0    1111100100000100    1111100100000100    - initial example string 
   1    11--00-0            11--00-000000100    - pairs transformed -comment 1 
   2    1-0-                1-0-00-000000100    - pairs of pairs -comment 2 
   3    --                  --0-00-000000100    - no blocks of 8 arecorrect 
   4    -                   --0-00-000000100    - all 16 bits transformed into a single symbol, 
                                            (which is null because the string was not optimal) 

comment 1: after pairs are transformed the 16 bits are reduced to 8 bits. 
           the last 8 bits in block remain unchanged from level 0 
            but we only care about the first 8 bits 
comment 2: now we only care about the first 4 entries in block 
*/ 
  

double H(double *genes) 
{ 
        double bonus=1, F=0, transform[NUMGENES]; 
        int last=NUMGENES, level, b; 
        for (b=0; b<last; b++) 
          {transform[b]=genes[order[b]]; /* transcribe genes */ 
           F+=f(transform[b])*bonus; /* add bonus for each non-null gene */ 
          }; 
        for (level=1; level<=P; level++) 
          {last=last/K; /* num of symbols reduces by factor of K */ 
           bonus=bonus*Rc; /* bonus increases by factor of Rc */ 
           for (b=0; b<last; b++) 
                {transform[b]=t(transform,b*K); 
                /* t transforms K symbols into one symbol */ 
                 F+=f(transform[b])*bonus; 
                 /* and sum fitness contributions of transforms */ 
                 } 
          } 
        return F; 
} 
  
  

/*================= base functions for H-IFF ======================*/ 

double t(double* transform, int first) 
  /* base transform function 
     H-equal is implemented here ie. 'reduce to same if equal else null' 

     simply checks whether 
     transform[first]==transform[first+1]==...==transform[first+k] 
     H-IFF is H-equal for K=2 (and binary alphabet) 
     (H-equal also works for any other size alphabet) */ 
{       int s=0, i; 
        for(i=first+1;i<first+K;i++) 
                s+=(transform[first]==transform[i]); 
        /* this could be more efficient i.e. break loop at first inequality */ 
        if (s==(K-1)) return transform[first]; 
        /* i.e there are K-1 other bits in the block that are equal to the first */ 
        return NONVALUE; 
} 
  

double f(double b) 
  /* base fitness function 
     H-equal ie. '1 if not null'*/ 
{ 
        if (b!=NONVALUE) return 1; 
        return 0; 
} 

/*=================================================================*/