classifierlist.c

XCS is a new algorithm for artificial intelligent

/*
/       (XCS)
/	------------------------------------
/	Learning Classifier System based on accuracy
/
/     by Martin Butz
/     University of Wuerzburg / University of Illinois at Urbana/Champaign
/     [e-mail]
/     Last modified: 10-17-99
/
/     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 "classifierList.h"

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

void createRandomCondition(char *con, int condLength)
{
  int j,cro;
  for(j=0; j<condLength; j++){
    cro=frand()*2;
    if(cro==2)
      con[j]=DONT_CARE;
    else
      con[j]='0'+cro;
  }
}

/* Creates a condition that matches mstring and chooses DON'T-CARE with probability DONTCARE_PROBABILITY */
void createMatchingCondition(char *con,char *mstring)
{
  int j;
  for(j=0;j<(signed int)strlen(mstring);j++){
    if(frand()<DONTCARE_PROBABILITY)
      con[j]=DONT_CARE;
    else
      con[j]=mstring[j];
  }
}


void createRandomAction(char *act, int actLength)
{
  int j,cro;  
  
  for(j=0; j<actLength; j++){
    cro=frand()*2;
    act[j]='0'+cro;
  }
}

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

/* Set all the classifier values to the average values of the population, record the size of the population */
void setInitialMeanVariables(struct xClassifierSet *set,struct xClassifier *cl,int itTime)
{
  double pre=0., err=0., fit=0., acc=0., peerssest=0.;
  int popSize=0;

  if(set==NULL){
    setInitialVariables(cl,itTime);
    return;
  }

  for(;set!=NULL;set=set->next){
    pre+=set->cl->pre*set->cl->num;
    err+=set->cl->preer*set->cl->num;
    acc+=set->cl->acc*set->cl->num;
    fit+=set->cl->fit;
    peerssest+=set->cl->peerssest*set->cl->num;
    popSize+=set->cl->num;
  }
  cl->pre=pre/popSize;
  cl->preer=err/popSize;
  cl->acc=acc/popSize;
  cl->fit=fit/popSize;
  cl->num=1;
  cl->exp=1;
  cl->peerssest=peerssest/popSize;
  cl->gaIterationTime=itTime;
}





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

/* Get MatchSet that matches state
 * 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 */
struct xClassifierSet * getMatchSet(char *state, struct xClassifierSet **pop, struct xClassifierSet **killset, int itTime)
{
  struct xClassifierSet *mset=NULL, *poplocal;
  struct xClassifier *killedp;
  int setsize=0, popSize=0;
  double meanpre=0.,meanprepop=0.;  
  
  for(poplocal= *pop; poplocal!=NULL;poplocal=poplocal->next){
    /* Calculate the mean prediction probability and the population size to detect loops */
    meanprepop+=poplocal->cl->pre*poplocal->cl->num;
    popSize+=poplocal->cl->num;

    if(match(state,poplocal->cl->con)){

      /* Calculate the mean prdiction prob. and the match set size to detect loops */
      meanpre+=(poplocal->cl->pre*poplocal->cl->num);
      setsize+=poplocal->cl->num;

      /* Add matching classifier to the matchset */
      addNewClassifierToSet(poplocal->cl, &mset); 
    }
  }

  /* Create a covering classifier, if no classifier matched state or the meanpre is under a threshold */
  if(mset == NULL || meanpre / (double)setsize < ((double)PRE_INI * (double)PREDICTION_THRESHOLD)){
    /* Delete classifier if population is to big and record it in killset */
    if(popSize>=MAX_POP_SIZE){
      killedp=deleteStochClassifier(pop);
      if(killedp!=NULL){
	addClassifierToKillSet(killedp,killset);
      }
      updateSet(&mset, *killset);
    }
    if(mset == NULL){
      addNewClassifierToSet( createCoverMatch(state, *pop, itTime), &mset);
      addNewClassifierToSet( mset->cl, pop);
    }else{
      /* Create a covering classifier, if a loop is detected 
       * (if the av. prediction of the matchset is smaller than a prediction threshold */
      if( meanpre / (double)setsize < ((double)PRE_INI * (double)PREDICTION_THRESHOLD)) {
	if(!addClassifierToSet( createCoverMatch(state, *pop, itTime), &mset) )
	  /* if the classifier was not yet in the match set, insert it into the population, too */
	  addNewClassifierToSet( mset->cl, pop);

	/* Maybe classifier of the current match set was deleted ->make sure that all classifiers in the match set exist */
	updateSet(&mset, *killset);
      }
    }
  }
  /* return the match set */
  return mset;
}

/* returns 1 if m matches c */
int match(char *m, char *c)
{
  for(;*c!='\0'&&*m!='\0'&&(*m==DONT_CARE||*c==DONT_CARE||*c==*m);m++,c++);
  if (*m=='\0'||*c=='\0')
    return 1;	
  else
    return 0;	
}


/* creates a matching classifier, deletes a classifier, if necessary, and adds the new classifier to the population 
 * the created classifier matches state */
struct xClassifier * createCoverMatch(char *state, struct xClassifierSet *pop, int itTime)
{
  struct xClassifier *cl; 

  /* get memory for the new classifier */
  assert((cl=( struct xClassifier *)calloc(1,sizeof(struct xClassifier)))!=NULL);
  assert((cl->con=(char *)calloc(strlen(state)+1,sizeof(char)))!=NULL);
  assert((cl->act=(char *)calloc(ACTION_LENGTH+1,sizeof(char)))!=NULL);

  /* set all the parameters of a classifier */
  createMatchingCondition(cl->con,state);
  createRandomAction(cl->act, ACTION_LENGTH);
  /* set the values to the mean vlaues of the population */
  setInitialMeanVariables(pop,cl,itTime);

  /* reduce prediction error and fitness */
  cl->preer*=0.25;
  cl->fit*=FITNESS_REDUCTION_IN_NEW_CLASSIFIERS;

  return cl;
}




/*############################################## 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*/

struct xClassifierSet * getActionSet(char *action, struct xClassifierSet *ms)
{
  struct xClassifierSet *aset=NULL, *setp;
  int setsize=0;
  
  /* MatchSet must not be NULL (should never occur, due to covering) */
  assert(ms!=NULL);

  /* insert all classifiers with action == 'action' to the new xClassifierSet */
  for(; ms!=NULL; ms=ms->next){
    if(strcmp(action, ms->cl->act)==0){
      ms->cl->exp++;
      setsize += ms->cl->num;
      addNewClassifierToSet(ms->cl, &aset);
    }else{/*CLassifiers in M/A!*/
      if(DECREASE_FITNESS_IN_M_NOT_A)
	ms->cl->fit*= FITNESS_REDUCTION_IN_M_NOT_A; /* Reduce fitness if not in action set (currently unused ) */
    }
  }
  
  /* adjust the Peer Set Size ESTimation, using averages or the Widrow-Hoff delta rule */
  for(setp=aset; setp!=NULL; setp=setp->next){
    if((double)setp->cl->exp < 1./BETA){
      setp->cl->peerssest=(setp->cl->peerssest*((double)(setp->cl->exp-1))+(double)setsize)/(double)setp->cl->exp; 
    }else{
      setp->cl->peerssest+=BETA*((double)setsize-setp->cl->peerssest);
    } 
  }
  /* return the action set */
  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) */
void adjustActionSet(struct xClassifierSet *aset,double maxP,double reward)
{
  double P;
  struct xClassifierSet *setp;  
  
  /* First update the fitness */
  updateFitness(aset);
  
  /* Then update the prediction error and the prediction */
  P=reward+GAMMA*maxP;
  for(setp=aset;setp!=NULL;setp=setp->next){
    if((double)setp->cl->exp<1./BETA){
      /* !first adjustments! -> simply calcualte the average */
      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;
    }else{
      /* normal adjustment -> use widrow hoff delta rule */
      setp->cl->preer+=(BETA*((absDouble(P-setp->cl->pre))-setp->cl->preer));
      setp->cl->pre+=(BETA*(P-setp->cl->pre));
    }
  }
}

/* update the fitnesses of a action set (the previous a.s. in multi-step envs or the current a.s. in single-step envs.) */
void updateFitness(struct xClassifierSet *aset)
{
  struct xClassifierSet *setp;
  double ksum;

  /* 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 */
  ksum=0.;
  for(setp=aset;setp!=NULL;setp=setp->next){
    if(setp->cl->preer <= MINIMUM_ERROR*PAYMENT_RANGE)
      setp->cl->acc=1.0;/* *(double)setp->cl->num;*/
    else{
      setp->cl->acc=exp(log(FALL_OFF_RATE)*(setp->cl->preer-(MINIMUM_ERROR*PAYMENT_RANGE))/(MINIMUM_ERROR*PAYMENT_RANGE))*(double)setp->cl->num*KAPPA_MULTIPLIER;
    }
    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){
    /* update the values */
    setp->cl->fit = setp->cl->fit + 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)
{
  struct xClassifierSet *setp;
  struct xClassifier *cl[2], *parents[2];
  double fitsum=0., avPre, avPreer, avFit;
  int i, len, meangait=0, mssum=0, changed=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,&meangait,&mssum,itTime);
  
  /* do not do a GA if the average number of time-steps in the set since the last GA
   * is less or equal than MEAN_LAST_GATIME */
  if((double)meangait/(double)mssum <= MEAN_LAST_GATIME)
    return;
  
  /* select two classifiers (roulette wheel selection) and copy them */
  selectTwoClassifiers(cl, parents, *set, fitsum, itTime);
  
  /* do a crossover on the two selected classifiers */
  changed=crossover(cl);

  /* if the strings have changed -> reduce fitness and set the values accordingly */
  if(changed){
    avPre = (cl[0]->pre+cl[1]->pre)/2.;
    avPreer = (cl[0]->preer+cl[1]->preer)/2.;
    avFit = (cl[0]->fit+cl[1]->fit)/2.;

    for(i=0; i<2; i++){
      cl[i]->pre=avPre;
      cl[i]->preer = avPreer * PRE_ERROR_REDUCTION_IN_NEW_CLASSIFIERS;
      cl[i]->fit *= avFit * FITNESS_REDUCTION_IN_NEW_CLASSIFIERS;
    }
  }

  /* Do mutation and reduce fitness if mutated */
  for(i=0;i<2;i++)
    if(mutation(cl[i])&&!changed)
      if(DECREASE_FITNESS_IF_MUTATED)
	cl[i]->fit*=FITNESS_REDUCTION_IN_NEW_CLASSIFIERS;

  /* 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 */
  for(i=0; i<2; i++)
    insertDiscoveredClassifier(cl[i], parents, set, pop, killset, len);
}


/* Calculate all necessary sums in the set for the discovery component */
void getDiscoversSums(struct xClassifierSet *set,double *sum,int *meangait,int *mssum,int itTime)
{
  struct xClassifierSet *setp;

  *sum=0.;
  *meangait=0;
  *mssum=0;  
  for(setp=set;setp!=NULL;setp=setp->next){
    (*sum)+=setp->cl->fit;
    (*meangait)+=(itTime-setp->cl->gaIterationTime)*setp->cl->num;
    (*mssum)+=setp->cl->num;
  }
}

/* select two classifiers and copy them for applying the GA */
void selectTwoClassifiers(struct xClassifier **cl, struct xClassifier **parents, struct xClassifierSet *set,double fitsum, int itTime)
{
  int i;
  struct xClassifier *clp;

  for(i=0;i<2;i++){
    clp=selectClassifierUsingRWS(set,fitsum);
    parents[i]=clp;
    assert((cl[i]=(struct xClassifier *)calloc(1,sizeof(struct xClassifier)))!=NULL);
    clp->gaIterationTime=itTime;
    assert((cl[i]->con=(char *)calloc(strlen(clp->con)+1,sizeof(char)))!=NULL);
    assert((cl[i]->act=(char *)calloc(strlen(clp->act)+1,sizeof(char)))!=NULL);
    strcpy(cl[i]->con,clp->con);
    strcpy(cl[i]->act,clp->act);
    cl[i]->pre=clp->pre;
    cl[i]->preer=clp->preer;
    cl[i]->acc=clp->acc;
    cl[i]->fit=clp->fit/(double)clp->num;;
    cl[i]->num=1;
    cl[i]->exp=1;
    cl[i]->peerssest=clp->peerssest;
    cl[i]->gaIterationTime=itTime;  
  }
}

/* select classifier for the discovery mechanism using roulette wheel selection */
struct xClassifier * selectClassifierUsingRWS(struct xClassifierSet *set,double fitsum)
{
  struct xClassifierSet *setp;
  double choicep;  

  choicep=frand()*fitsum;
  setp=set;
  fitsum=setp->cl->fit;
  while(choicep>fitsum && setp!=NULL){
    setp=setp->next;
    fitsum+=setp->cl->fit;
  }
  assert(setp!=NULL);
  return setp->cl;
}

/* insert a discovered classifier into the population and respects the population size */
void insertDiscoveredClassifier(struct xClassifier *cl, struct xClassifier **parents, struct xClassifierSet **set,
				struct xClassifierSet **pop, struct xClassifierSet **killset, int len)
{
  struct xClassifier *killedp;
  struct xClassifierSet *setp;

  if(len>=MAX_POP_SIZE){
    killedp=deleteStochClassifier(pop);
    /* record the deleted classifier to update other sets */
    if(killedp!=NULL){
      addClassifierToKillSet(killedp,killset);
      /* update the set and the parents incase a classifier was deleted there */
      updateSet(set, *killset);
      for(setp=*killset; setp!=NULL; setp=setp->next){
	if(parents[0] == setp->cl)
	  parents[0]=NULL;
	if(parents[1]==setp->cl)
	  parents[1]=NULL;
      }
    }
  }
  subsumeClassifier(cl, parents, *set, pop);
}







/*################################## subsumption deletion ########################################################*/