classifierlist.c

XCS is a new algorithm for artificial intelligent

void subsumeClassifier(struct xClassifier *cl,struct xClassifier **parents,struct xClassifierSet *locset,struct xClassifierSet **pop)
{
  int i,j;
  /*Try first to subsume in parents */
  for(i=2*frand(),j=0; j<2; i=(i+1)%2, j++){ 
    if(parents[i]!=NULL && subsumes(parents[i],cl)){
      parents[i]->num++;
      freeClassifier(cl);
      return;
    }
  }
  
  if(subsumeClassifierToSet(cl, locset))
    return;

  if(subsumeClassifierToSet(cl, *pop))
    return;
 
  addClassifierToSet(cl,pop);
}

/* try to subsume in one set */
int subsumeClassifierToSet(struct xClassifier *cl, struct xClassifierSet *set)
{
  struct xClassifierSet * setp;
  struct xClassifier *subCl[MAX_POP_SIZE];
  int numSub  ;
  
  /*Try to subsume in the set*/
  for(setp=set,numSub=0; setp!=NULL; setp=setp->next){
    if(subsumes(setp->cl,cl)){
      subCl[numSub]=setp->cl;
      numSub++;
    }
  }
  /* if there were classifiers found to subsume, then choose randomly one and subsume */
  if(numSub>0){
    numSub=numSub*frand();
    subCl[numSub]->num++;
    freeClassifier(cl);
    return 1;
  }
  return 0;
}

/* check if classifier cl1 subsumes cl2 */
int subsumes (struct xClassifier *cl1, struct xClassifier * cl2)
{
  int ret=0;

  ret= (cl1->exp >= SUBSUME_EXPERIENCE) && (cl1->acc >= 0.99) && (strcmp(cl1->act,cl2->act)==0)
    && subsumesConditions ((cl1->con), (cl2->con));

  return ret;
}

/* check if the first condition subsumes the second */
int subsumesConditions (char * first, char * second)
{
  int result = (strlen (first) == strlen (second));
  int i = 0;  
  
  while (result && (first[i] != '\0'))
  {
    result &= ((first[i] == '#') || (first[i] == second[i]));
    i++;
  }
  
  return result;
}

/*######################################## crossover & mutation ##############################################*/

/* crosses the two received classifiers (right now: one-point crossover), return if the strings were changed */
int crossover(struct xClassifier **cl)
{
  int sep,len,i,ret=0;
  char ch;
  
  if(frand()<CROSSPX){
    /* crossover will be applied */
    /* get crossing site */
    len=strlen(cl[0]->con);
    sep=frand()*(len-1);
    /* do the cross */
    for(i=sep+1; i<len; i++){
      if((cl[0]->con)[i]!=(cl[1]->con)[i]){
	ret=1;
	ch=(cl[0]->con)[i];
	(cl[0]->con)[i]=(cl[1]->con)[i];
	(cl[1]->con)[i]=ch;
      }
    }
  }
  /* return if the conditions of the classifiers changed */
  return ret;
}

/* mutate one classifier */
int mutation(struct xClassifier *cl)
{
  int mp,len,mttr=0;
  
  len = strlen(cl->con) + strlen(cl->act);
  for(mp=0; mp<len; mp++){
    if(frand()<MUTPMUE){
      mttr=1;
      if(mp<(signed int)strlen(cl->con)){
	mutate(cl->con,mp,0);
      }else{
	mutate(cl->act,mp-strlen(cl->con),1);
      }
    }
  }
  /* return if the condition or action  of the classifier changed */
  return mttr;
}

/* do one mutation (either in the condition (type 0) or in the action (type 1) */
void mutate(char *string,int pos,int type)
{
  if(type==0){
    /* mutate condition -> 0, 1, or DONT_CARE */
    switch(string[pos]){
    case '0':
      if(frand()<0.5)
	string[pos]='1';
      else
	string[pos]=DONT_CARE;
      break;
    case '1':
      if(frand()<0.5)
	string[pos]='0';
      else
	string[pos]=DONT_CARE;
      break;
    case DONT_CARE:
      if(frand()<0.5)
	string[pos]='0';
      else
	string[pos]='1';
      break;
    default:
      printf("Mistake during mutation! string:%s pos:%d\n",string ,pos);
      break;
    }
  }else{
    /* mutate action -> 0, or 1 */
    if(string[pos]=='0')
      string[pos]='1';
    else
      string[pos]='0';
  }
}

/*####################################### adding classifiers to a set ###########################################*/

/* adds only the pointers to the killset, ensures that no pointer is added twice */
void addClassifierToKillSet(struct xClassifier *cl,struct xClassifierSet **killset)
{
  struct xClassifierSet *setp;
  
  for(setp=*killset; setp!=NULL; setp=setp->next){
    if(setp->cl == cl){
      /* Classifier is already in KillSet */
      return;
    }
  }
  /* add the classifier, as it is not already inthe killset */
  assert((setp=( struct xClassifierSet *)calloc(1,sizeof(struct xClassifierSet)))!=NULL);
  setp->cl=cl;
  setp->next=*killset;
  *killset=setp;
}

/* adds the classifier cl to the population, make sure that the same classifier does not exist, yet 
   returns if inserted classifier was deleted */
int addClassifierToSet(struct xClassifier *cl,struct xClassifierSet **clSet)
{
  struct xClassifierSet *setp;
  
  /* Check if classifier exists already. if so, just increase the numeriosity and free the space of the new classifier */
  for(setp=*clSet;setp!=NULL;setp=setp->next){
    if(strcmp(setp->cl->con,cl->con)==0&&strcmp(setp->cl->act,cl->act)==0){
      setp->cl->num++;
      freeClassifier(cl);
      return 1;
    }
  }
  /* classifier does not exist, yet-> add new classifier */
  assert((setp=( struct xClassifierSet *)calloc(1,sizeof(struct xClassifierSet)))!=NULL);
  setp->cl=cl;
  setp->next=*clSet;
  *clSet=setp;
  return 0;
}

/* adds a new Clasifier to the xClassifierSet */
void addNewClassifierToSet(struct xClassifier *cl,struct xClassifierSet **clSet)
{
  struct xClassifierSet *setp;

  /* classifier does not exist, yet-> add new classifier */
  assert((setp=( struct xClassifierSet *)calloc(1,sizeof(struct xClassifierSet)))!=NULL);
  setp->cl=cl;
  setp->next=*clSet;
  *clSet=setp;
}

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

struct xClassifier * deleteStochClassifier(struct xClassifierSet **pop)
{
  struct xClassifierSet *setp,*setpl;
  struct xClassifier *killedp=NULL;
  double sum=0.,asum,meanf=0.;
  int size=0;  
  
  /* get the sum of the fitness and the numeriosity */
  for(setp=*pop; setp!=NULL; setp=setp->next){
    meanf+=setp->cl->fit;
    size+=setp->cl->num;
  }
  meanf/=(double)size;
  
  /* get the delete proportion, which depends on the average fitness */
  for(setp=*pop;setp!=NULL;setp=setp->next){
    sum+=getDelProp(setp->cl,meanf);
    if(sum<0.)
      printf("Sum overflow in deleteStochclassifier!!!\n");
  }

  /* choose the classifier that will be deleted */
  sum=frand()*sum;
  
  /* look for the classifier */
  setp=*pop;
  setpl=*pop;
  asum=getDelProp(setp->cl,meanf);
  while(asum<sum){
    setpl=setp;
    setp=setp->next;
    asum+=getDelProp(setp->cl,meanf);
  }
  
  /* delete the classifier */
  killedp=deleteTypeOfClassifier(setp,setpl,pop);
  
  /* return the pointer to the deleted classifier, to be able to update other sets */
  return killedp;
}

/* deletes the classifier setp from the population pop, setpl points to the classifier that is before setp in the list */
struct xClassifier * deleteTypeOfClassifier(struct xClassifierSet *setp,struct xClassifierSet *setpl,struct xClassifierSet **pop)
{
  struct xClassifier *killedp=NULL;

  /* setp must point to some classifier! */
  assert(setp!=NULL);

  if(setp->cl->num>1){
    /* if the numeriosity is greater than one -> just decrease it */
    setp->cl->num--;
  }else{
    /* if not, delete it and record it in killedp */
    if(setp==setpl){
      *pop=setp->next;
    }else{
      setpl->next=setp->next;
    }
    killedp=setp->cl;
    freeClassifier(setp->cl);
    free(setp);
  }
  /* return a pointer ot a deleted classifier (NULL if the numeriosity was just decreased) */
  return killedp;
}

/* return the delete proportion of one classifier, meanf is the average fitness in the population */
double getDelProp(struct xClassifier *cl, double meanf)
{
  double ret;
  if((cl->fit/cl->num) >= DELTA*meanf || cl->exp <= DELETION_EXPERIENCE)
    /* First case */
    ret=cl->peerssest*(double)cl->num;
  else
    /* Second case: Take the fitness of the classifier into account */
    ret=((cl->peerssest*cl->num*meanf)/(cl->fit/cl->num));
  return ret;
}



/* check if the classifier pointers that are in killset are in uset - delete the pointers if they are inside 
 * the classifiers in killset are already deleted, so do not read their values or try to delete tehm again*/
int updateSet(struct xClassifierSet **uset,struct xClassifierSet *killset)
{
  struct xClassifierSet *setp,*setpl,*killp,*usetp;
  int updated=1;
  
  /* If one of the sets is emoty -> do not do anything */
  if(*uset==NULL || killset==NULL)
    return 0;
  /* check all classifiers in uset */
  setp=*uset;
  while(updated && setp!=NULL){
    setp=*uset;
    setpl=*uset;
    updated=0;
    while(setp!=NULL && !updated){
      for(killp=killset;killp!=NULL;killp=killp->next){
	if(killp->cl == setp->cl){
	  /* If killed classifier found, delete the struct classifier set in uset */
	  updated=1;
	  if(setp==setpl){
	    usetp=*uset;
	    *uset=usetp->next;
	    free(usetp);
	    break;
	  }else{
	    setpl->next=setp->next;
	    free(setp);
	    break;
	  }
	}
      }
      /* check the whole uset again, if one pointer was deleted */
      if(updated)
	break;
      setpl=setp;
      setp=setp->next;
    }
  }
  /* return if the set was updated */
  return updated;
}

/*################################### concrete deletion of a classifier or a whole classifier set #################################*/

/* Frees only the complete xClassifierSet (not the xClassifiers itself)! */
void freeSet(struct xClassifierSet **cls)
{
  struct xClassifierSet *clp;
  
  while(*cls!=NULL)
    {
      clp=(*cls)->next;
      free(*cls);
      *cls=clp;
    }
}

/* Frees the complete xClassifierSet with the corresponding xClassifiers */
void freeClassifierSet(struct xClassifierSet **cls)
{
  struct xClassifierSet *clp;

  while(*cls!=NULL)
    {
      freeClassifier((*cls)->cl);
      clp=(*cls)->next;
      free(*cls);
      *cls=clp;
    }
}

/* Frees one classifier */
void freeClassifier(struct xClassifier *cl)
{
  free(cl->con);
  free(cl->act);
  free(cl);
}


/*############################################### output operations ##################################################*/

/* print the classifiers in a xClassifierSet */
void printClassifierSet(struct xClassifierSet *head)
{
  for(;head!=NULL;head=head->next)
    printClassifier(head->cl);
}

/* print the classifier in a xClassifierSet to the file fp */
void fprintClassifierSet(FILE *fp,struct xClassifierSet *head)
{
  fprintf(fp,"Cond.\tAction\tPredediction\tPredictionError\tFitness  \tNum Experience ActionSetSizeEst. LastGAIteration\n");
  for(;head!=NULL;head=head->next)
    fprintClassifier(fp, head->cl);
}

/* print a single classifier */
void printClassifier(struct xClassifier *c)
{
  printf("%s\t",c->con);
  printf("%s\t",c->act);  
  printf("%f\t%f\t%f\t%f\t", c->pre, c->preer/PAYMENT_RANGE, c->acc, PAYMENT_RANGE*c->fit);
  printf("%d %d %f %d\n", c->num, c->exp, c->peerssest, c->gaIterationTime);
}

/* print a single classifier to the file fp */
void fprintClassifier(FILE *fp,struct xClassifier *c)
{
  fprintf(fp,"%s\t",c->con);
  fprintf(fp,"%s\t",c->act);
  fprintf(fp,"%f\t%f\t%f\t%f\t", c->pre, c->preer/PAYMENT_RANGE, c->acc, PAYMENT_RANGE* c->fit);
  fprintf(fp,"%d %d %f %d\n", c->num, c->exp, c->peerssest, c->gaIterationTime);
}


/*########################################### sorting the classifier list ###################################################*/

/* sort the classifier set cls in numeriosity order or in prdiction order 
 * type 0 = numeriosity order, type 1 = prediction order */
struct xClassifierSet * sortClassifierSet(struct xClassifierSet **cls,int type)
{
  struct xClassifierSet *clsp, *maxcl, *newcls, *newclshead;
  double max;

  max=0.;
  assert((newclshead=( struct xClassifierSet *)calloc(1,sizeof(struct xClassifierSet)))!=NULL);
  newcls=newclshead;
  do{
    max=-100;
    /* check the classifier set cls for the next maximum -> already inserted classifier are referenced by the NULL pointer */
    for( clsp=*cls, maxcl=*cls; clsp->next!=NULL; clsp=clsp->next ) {
      if(clsp->cl!=NULL && ((type==0 && clsp->cl->num>max) || (type==1 && clsp->cl->pre>max))){
	if(type==0)
	  max=clsp->cl->num;
	else if (type==1)
	  max=clsp->cl->pre;
	maxcl=clsp;
      }
    }
    if(max>-100){
      assert((newcls->next=( struct xClassifierSet *)calloc(1,sizeof(struct xClassifierSet)))!=NULL);
      newcls=newcls->next;
      newcls->next=NULL;
      newcls->cl=maxcl->cl;
      /* do not delete the classifier itself, as it will be present in the new, sorted classifier list */
      maxcl->cl=NULL;
    }
  }while(max>-100);
  
  /* set the new xClassifierSet pointer and free the old stuff */
  newcls=newclshead->next;
  free(newclshead);
  freeSet(cls);
  /* return the pointer to the new xClassifierSet */
  return newcls;
}

/*################################## Utilitiy ################################################*/

/* get the abs value of value */
double absDouble(double value)
{
  if(value>=0.)
    return value;
  else
    return value*(-1.);
}