classifierlist.c

Simple GA code (Pascal code from Goldberg, D. E. (1989), Genetic Algorithms in Search, Optimization,

/*
/       (XCS-C 1.2)
/	------------------------------------
/	Learning Classifier System based on accuracy
/
/     by 
/     Martin V. Butz
/     Illinois Genetic Algorithms Laboratory (IlliGAL)
/     University of Illinois at Urbana/Champaign
/     [e-mail]
/
/     Last modified: 09-30-2003
/
/     All actions related to the xClassifier and xClassifierSet.
*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "xcsMacros.h"
#include "env.h"
#include "xcs.h"
#include "classifierList.h"
#include "actionSelection.h"


/**
 * Creates a random classifier set of size maxPopSize.
 */
struct xClassifierSet * createRandomClassifierSet(int condLength, int maxPopSize, double dontCareProb)
{
  struct xClassifierSet *head=NULL;
  struct xClassifier *cl;
  int i=0;
  
  for(i=0;i<maxPopSize;i++){
    assert((cl=( struct xClassifier *)calloc(1,sizeof(struct xClassifier)))!=NULL);
    assert((cl->con=(struct xCondition *)calloc(1,sizeof(struct xCondition)))!=NULL);
    
    createRandomCondition(cl->con, condLength, dontCareProb);
    createRandomAction(&(cl->act));
    setInitialVariables(cl , 0);
    addClassifierToSet(cl, &head);
  }
  return head;
}

/**
 * Creates a random condition of length condLength choosing DONT_CARE with probability dontCareProb.
 */ 
void createRandomCondition(struct xCondition *con, int condLength, double dontCareProb)
{
  int j;

  for(j=0; j<condLength; j++){
    if(urand()>dontCareProb)
      addXCPos(con, j, '0'+(int)(urand()*2.));
  }
}

/**
 * Creates a random action. 
 */
void createRandomAction(int *act)
{
  *act = (int)(urand()* getNumberOfActions());
}

/**
 * Sets all initial varibles of a classifier list ->used by various functions. 
 */
void setInitialVariables(struct xClassifier *cl,int itTime)
{
  cl->pre=PRE_INI;
  cl->preer=PREER_INI;
  cl->acc=FIT_INI;
  cl->fit=FIT_INI;
  cl->num=1;
  cl->exp=1;
  cl->peerssest=1.;
  cl->gaIterationTime=itTime;
}


/*############################## match set operations #################################*/


/**
 * Gets the match-set that matches state from pop.
 * If a classifier was deleted, record its address in killset to be
 * able to update former actionsets.
 * The iteration time 'itTime' is used when creating a new classifier
 * due to covering. Covering occurs when not all possible actions are
 * present in the match set. Thus, it is made sure that all actions
 * are present in the match set.
 */
struct xClassifierSet * getMatchSet(struct XCS *xcs, char *state, struct xClassifierSet **pop, struct xClassifierSet **killset, int itTime)
{
  struct xClassifierSet *mset=NULL, *poppointer;
  struct xClassifier *killedp, *coverCl;
  int popSize=0, setSize=0, *coveredActions, i, representedActions;
  double spec=0.;

  assert((coveredActions = (int *)calloc(getNumberOfActions(),sizeof(int)))!=0);

  for(poppointer= *pop; poppointer!=NULL;poppointer=poppointer->next) {
    /* Calculate the mean prediction probability and the population size to detect loops */
    popSize += poppointer->cl->num;

    if(match(state, poppointer->cl->con)) {
      /* Add matching classifier to the matchset */
      addNewClassifierToSet(poppointer->cl, &mset); 
      setSize+=poppointer->cl->num;
      spec += getSpecificity(poppointer->cl)*poppointer->cl->num;
    }
  }

  /* Create covering classifiers, if not all actions are covered */
  representedActions = nrActionsInSet(mset, coveredActions);
  
  while( representedActions < getNumberOfActions() ) {
    for(i=0; i<getNumberOfActions(); i++){
      /* make sure that all actions are covered! */
      if(coveredActions[i]==0){
 
	coverCl=createNewCoverMatch(state, itTime, mset, i, xcs->dontCareProb);
	addNewClassifierToSet( coverCl, &mset);
	addNewClassifierToSet( coverCl, pop);
	popSize++;
	setSize++;
	coverCl->peerssest=setSize;
      }
    }
    
    /* Delete classifier if population is too big and record it in killset */
    while( popSize > xcs->maxPopSize ) {
      /* PL */
      killedp = deleteClassifier(pop, xcs);
      if(killedp!=NULL) {
	deleteClassifierPointerFromSet(&mset, killedp);
  	addClassifierToPointerSet(killedp, killset);
      }      
      popSize--;
    }
    representedActions = nrActionsInSet(mset, coveredActions);
  }

  free(coveredActions);
  /* return the match set */
  return mset;
}

/**
 * Returns the number of actions in the set and stores which actions are covered 
 * in the array coveredActions.
 */
int nrActionsInSet(struct xClassifierSet *set, int *coveredActions)
{
  int nr,i;

  for(i=0; i<getNumberOfActions(); i++) {
    coveredActions[i]=0;
  }
  for(nr=0; nr<getNumberOfActions() && set!=NULL; set=set->next) {
    if(coveredActions[set->cl->act]==0) {
      coveredActions[set->cl->act]=1;
      nr++;
    }
  }
  return nr;
}

/**
 * returns 1 if m matches c 
 */
int match(char *m, struct xCondition *c)
{
  struct xCList *l;
  
  for(l=c->l; l!=NULL; l=l->next) {
    if(l->c != m[l->pos] && m[l->pos]!='#')
      return 0;
  }
  return 1;
}

/**
 * returns the relation between the two: 0=equal, 1=more general, 2=more specific, 3=both .
 */
int compareStateWithClassifier(char *state, struct xCondition *c)
{
  struct xCList *l;
  int i, moreGeneral=0, moreSpecific=0;
  for(i=0, l=c->l; i<getConditionLength(); i++) {
    if(state[i]=='#') {
      while(l!=NULL && l->pos<i)
	l=l->next;
      if(l!=NULL && l->pos==i)
	moreSpecific=1;
    }else{
      while(l!=NULL && l->pos<i)
	l=l->next;
      if(l==NULL || l->pos>i)
	moreGeneral=1;
    }
  }
  if(moreSpecific==0) {
    if(moreGeneral==0)
      return 0;
    else
      return 1;
  }else{
    if(moreGeneral==0)
      return 2;
    else
      return 3;
  }
  return -1;
}

/**
 * Creates a matching classifier, deletes a classifier, if necessary,
 * and adds the new classifier to the population; the created
 * classifier matches state and has action "action".
 */
struct xClassifier * createNewCoverMatch(char *state, int itTime, struct xClassifierSet *set, 
					 int action, double dontCareProb)
{
  struct xClassifier *cl; 

  /* get memory for the new classifier */
  assert((cl=( struct xClassifier *)calloc(1,sizeof(struct xClassifier)))!=NULL);
  assert((cl->con=(struct xCondition *)calloc(1,sizeof(struct xCondition)))!=NULL);

  /* create condition and action */
  createMatchingCondition(cl->con, state, dontCareProb);
  cl->act = action;

  /* set the parameters to the initial values */
  setInitialVariables(cl, itTime);

  return cl;
}

/**
 * Creates a condition that matches mstring choosing DONT_CARE with probability dontCareProb .
 */
void createMatchingCondition(struct xCondition *con,char *mstring, double dontCareProb)
{
  int j;
  for(j=0;j<(signed int)strlen(mstring);j++){
    if(urand()>dontCareProb)
      addXCPos(con, j, mstring[j]);
  }
}


/*########################### action set operations ####################################*/


/**
 * Get ActionSet out of the set ms (the match set) that only has classifiers that match action,
 * and increase the experience of those classifiers
 * returns the created action set
 */
struct xClassifierSet * getActionSet(int action, struct xClassifierSet *ms)
{
  struct xClassifierSet *aset=NULL;
  
  /* insert all classifiers with action == 'action' to the new xClassifierSet */
  for(; ms!=NULL; ms=ms->next){
    if(action == ms->cl->act){
      addNewClassifierToSet(ms->cl, &aset);
    }
  }
  
  return aset;
}

/**
 * This is the reinforcement component,
 * if maxP equals 0 then there was no previous action set (single-step
 * env or a new trial) updates: experience (always first!), fitness
 * (second or last), prediction (before or after prediction error),
 * prediction error (before or after prediction), peer set size
 * estimate. 
 */
void adjustActionSet(struct XCS *xcs, struct xClassifierSet **aset, double maxP, double reward, 
		     struct xClassifierSet **pop, struct xClassifierSet **killset)
{
  double P, setsize=0;
  struct xClassifierSet *setp;  
  
  for(setp=*aset; setp!=NULL; setp=setp->next){
    setp->cl->exp++;
    if(setp->cl->exp>10000)
      setp->cl->exp=10000;
    setsize += setp->cl->num;
  }
  /* Update the fitness */
  if(DO_FITNESSUPDATE_FIRST)
    updateFitness(*aset, xcs);
  
  /* Update prediction, prediction error and peer set size estimate */
  P=reward+(xcs->gamma)*maxP;
  for(setp=*aset; setp!=NULL; setp=setp->next) {
    if(xcs->doMAM && (double)setp->cl->exp < 1./xcs->beta) {
      /* !first adjustments! -> simply calculate the average */
      if(UPDATEORDER_PRED_PREDERROR){
	setp->cl->pre= (setp->cl->pre* ((double)setp->cl->exp - 1.) + P) / (double)setp->cl->exp;
	setp->cl->preer= (setp->cl->preer* ((double)setp->cl->exp - 1.) + absDouble(P - setp->cl->pre)) / (double)setp->cl->exp;
      }else{
	setp->cl->preer= (setp->cl->preer* ((double)setp->cl->exp - 1.) + absDouble(P - setp->cl->pre)) / (double)setp->cl->exp;
	setp->cl->pre= (setp->cl->pre* ((double)setp->cl->exp - 1.) + P) / (double)setp->cl->exp;
      }
      setp->cl->peerssest=(setp->cl->peerssest*((double)(setp->cl->exp-1))+setsize)/(double)setp->cl->exp; 
    }else{
      /* normal adjustment -> use widrow hoff delta rule */
      if(UPDATEORDER_PRED_PREDERROR){
	setp->cl->pre += (xcs->beta) * (P - setp->cl->pre);
	setp->cl->preer += (xcs->beta) * (absDouble(P - setp->cl->pre) - setp->cl->preer);
      }else{
	setp->cl->preer += (xcs->beta) * (absDouble(P - setp->cl->pre) - setp->cl->preer);
	setp->cl->pre += (xcs->beta) * (P - setp->cl->pre);
      }
      setp->cl->peerssest+= (xcs->beta) * (setsize-setp->cl->peerssest);
    }
  }
  /* Update the fitness */
  if(!DO_FITNESSUPDATE_FIRST)
    updateFitness(*aset, xcs);

  if( xcs->doActionSetSubsumption )
    doActionSetSubsumption(aset, pop, killset, xcs->thetaSub);
}


/**
 * Update the fitnesses of an action set 
 * (the previous [A] in multi-step envs or the current [A] in single-step envs.) 
 */
void updateFitness(struct xClassifierSet *aset, struct XCS *xcs)
{
  struct xClassifierSet *setp;
  double ksum=0, powerSub;
  int i;

  /* If the action set got NULL (due to deletion) return */
  if(aset==NULL)
    return;
  
  /* Calculate the accuracies of all classifiers and get the sum of all accuracies */
  for(setp=aset;setp!=NULL;setp=setp->next) {
    if(setp->cl->preer <= xcs->epsilon0*(double)getPaymentRange()) {
      setp->cl->acc=1.0;
    }else{
      powerSub = setp->cl->preer/(xcs->epsilon0*(double)getPaymentRange());
      setp->cl->acc = powerSub;
      for(i=2; i <= xcs->nu; i++)
	setp->cl->acc *= powerSub;
      setp->cl->acc = xcs->alpha * (1/(setp->cl->acc));
    }
    ksum += setp->cl->acc*(double)setp->cl->num;
  }
  
  /* Update the fitnesses of the classifiers in aset using the relative accuracy values */
  for(setp=aset; setp!=NULL; setp=setp->next) {
    setp->cl->fit += xcs->beta * ((setp->cl->acc * setp->cl->num) / ksum - setp->cl->fit);
  }
}



/*############################### discovery mechanism ##################################*/


/**
 * The discovery conmponent with the genetic algorithm 
 * note: some classifiers in set could be deleted ! 
 */
void discoveryComponent(struct xClassifierSet **set, struct xClassifierSet **pop, struct xClassifierSet **killset, int itTime, char *situation, struct XCS *xcs, double currentReward)
{
  struct xClassifierSet *setp;
  struct xClassifier *cl[2], *parents[2];
  double fitsum=0.;
  int i, len, setsum=0, gaitsum=0;

  /* if the classifier set is empty, return (due to deletion) */
  if(*set==NULL)
    return;
  
  /* get all sums that are needed to do the discovery */
  getDiscoversSums(*set, &fitsum, &setsum, &gaitsum);
  
  /* do not do a GA if the average number of time-steps in the set since the last GA
   * is less or equal than thetaGA */
  if( itTime - (double)gaitsum / (double)setsum < xcs->thetaGA)
    return;
  
  setTimeStamps(*set, itTime);
  
  /* select two classifiers (roulette wheel selection) and copy them */
  selectTwoClassifiers(cl, parents, *set, fitsum, setsum, xcs, situation);
  
  /* Reducing fitness of new classifiers by a given factor */
  cl[0]->fit *= xcs->fitnessReduction; /* reduce fitness of new classifiers */
  cl[1]->fit *= xcs->fitnessReduction; /* reduce fitness of new classifiers */
  
  /* do crossover on the two selected classifiers */
  if(crossover(cl, xcs->crossoverType, xcs->chiGA)) {
    /* if crossover got applied and changed classifiers, average their values */
    cl[0]->pre   = (cl[0]->pre + cl[1]->pre) / 2.; 
    cl[0]->fit   = (cl[0]->fit + cl[1]->fit) / 2.; 

    cl[0]->preer = (cl[0]->preer + cl[1]->preer) / 2.;
    
    cl[1]->pre   = cl[0]->pre;
    cl[1]->preer = cl[0]->preer;
    cl[1]->fit   = cl[0]->fit;
  }

  /* do mutation */
  for(i=0; i<2; i++) {
    mutation(cl[i], situation, xcs);
  }
  
  /* get the length of the population to check if clasifiers have to be deleted */
  for(len=0, setp=*pop; setp!=NULL; setp=setp->next)
    len += setp->cl->num;
  
  /* insert the new two classifiers and delete two if necessary */
  insertDiscoveredClassifier(cl, parents, set, pop, killset, len, xcs);
}

/**
 * Calculate all necessary sums in the set for the discovery component.
 */
void getDiscoversSums(struct xClassifierSet *set, double *fitsum, int *setsum, int *gaitsum)