classifierlist.c

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

  /* get the delete proportion, which depends on the average fitness */
  for(setp=*pop; setp!=NULL; setp=setp->next) {
    sum += ((double)setp->cl->num * getDelPropMikro(setp->cl, meanf, meane, delta, thetaDel, delType));
  }

  /* choose the classifier that will be deleted */
  choicep=urand()*sum;
  
  /* look for the classifier */
  setp=*pop;
  setpl=*pop;
  sum= ((double)setp->cl->num * getDelPropMikro(setp->cl,meanf, meane, delta, thetaDel, delType));
  while(sum < choicep) {
    setpl=setp;
    setp=setp->next;
    sum += ((double)setp->cl->num * getDelPropMikro(setp->cl,meanf, meane, delta, thetaDel, delType));
  }
  
  /* 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 numerosity is greater than one -> just decrease it */
    setp->cl->num--;
    /*setp->cl->peerssest--;*/
  }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 numerosity was just decreased) */
  return killedp;
}

/**
 * Returns the delete proportion of one classifier, meanf is the average fitness in the population,
 * the deletion type determines which classifier properties are considered for deletion. 
 */
double getDelPropMikro(struct xClassifier *cl, double meanf, double meane, double delta, int thetaDel, int delType)
{
  double ret = 1;

  if((delType==1 || delType==2) && cl->exp >= thetaDel && (cl->fit/cl->num) < delta * meanf)
    ret *= meanf / (cl->fit / (double)cl->num);
  
  if(delType%2 == 1 ) {
    ret *= cl->peerssest;
  }
  
  if((delType==4 || delType == 5)) /* && cl-> exp >= thetaDel && cl->preer > meane)*/
    ret *= cl->preer/meane;
  
  return ret;
}


/** 
 * Check if the classifier pointers that are in killset are in uset - delete the pointers,
 * if they are inside. Note that the classifiers in killset are already deleted, so do not 
 * read their values or try to delete them again here!
 */
int updateSet(struct xClassifierSet **uset,struct xClassifierSet *killset)
{
  struct xClassifierSet *setp,*setpl,*killp,*usetp;
  int updated=1;
  
  /* If one of the sets is empty -> 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) {/* first entry in set */
	    usetp=*uset;
	    *uset=usetp->next;
	    free(usetp);
	    break;
	  }else{
	    setpl->next=setp->next;
	    free(setp);
	    setp = *uset;
	    setpl= *uset;
	    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;
}

/**
 * Deletes the classifier pointer from the specified set 
 * and returns if the pointer was found and deleted. 
 */
int deleteClassifierPointerFromSet(struct xClassifierSet **set, struct xClassifier *clp)
{
  struct xClassifierSet *setp, *setpl;
  for(setp=*set, setpl=*set; setp!=NULL; setp=setp->next){
    if(setp->cl==clp){
      if(setpl==setp){
	*set=(*set)->next;
	free(setp);
      }else{
	setpl->next=setp->next;
	free(setp);
      }
      return 1;
    }
    setpl=setp;
  }
  return 0;
}


/*############# 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)
{
  emptyXCondition(cl->con);
  free(cl->con);
  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.\t\tAction\tPrediction\tPredictionError\tAccuracy\tFitness  \tNum Exp ASSE. LastGA\n");
  for(;head!=NULL;head=head->next)
    fprintClassifier(fp, head->cl);
}

/**
 * print a single classifier 
 */
void printClassifier(struct xClassifier *c)
{
  printXC(stdout, c->con);
  printf(" %d\t",c->act);  
  printf("%4.2f\t%4.2f\t%4.2f\t%4.2f\t", c->pre, c->preer, c->acc, c->fit);
  printf("%d %d %4.2f\t%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)
{
  printXC(fp, c->con);
  fprintf(fp," %d\t",c->act);
  fprintf(fp,"%f\t%f\t%f\t%f\t", c->pre, c->preer, c->acc, 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 numerosity, prediction, fitness, or error order. 
 * type 0 = numerosity order, type 1 = prediction order, type 2 = fitness order, type 3=error 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=-100000;
    /* check the classifier set cls for the next maximum -> already inserted classifier are referenced by the NULL pointer */
    for( clsp=*cls, maxcl=NULL; clsp!=NULL; clsp=clsp->next ) {
      if(clsp->cl!=NULL && (maxcl==NULL || ((type==0 && clsp->cl->num>max) || (type==1 && clsp->cl->pre>max) || (type==2 && clsp->cl->fit/clsp->cl->num > max) || (type==3 && -1.*(clsp->cl->preer) > max)))) {
	if(type==0)
	  max=clsp->cl->num;
	else if (type==1)
	  max=clsp->cl->pre;
	else if (type==2)
	  max=clsp->cl->fit/clsp->cl->num;
	else if(type==3)
	  max=-1.*(clsp->cl->preer);
	maxcl=clsp;
      }
    }
    if(max>-100000) {
      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>-100000);
  
  /* 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.);
}


/*############################### Operation on Condition Part ##########################*/


/**
 * Adds specified position 'c' add position pos to condition con. 
 */
int addXCPos(struct xCondition *con, int pos, char c)
{
  struct xCList *l, *ll=NULL;

  for(l=con->l; l!=NULL; l=l->next) {
    if(l->pos>=pos) {
      if(l->pos == pos)
	return 0; /* position is already specified */
      else 
	break; /* position is further than the one to be inserted */
    }
    ll=l;
  }
  /* position will be added */
  con->size ++;
  if(ll==NULL) { /* add before first one */
    assert((con->l = (struct xCList *)calloc(1,sizeof(struct xCList)))!=0);
    con->l->next = l;
    l=con->l;
  }else{ /* add one more */
    assert((ll->next = (struct xCList *)calloc(1,sizeof(struct xCList)))!=0);
    ll->next->next=l;
    l=ll->next;
  }
  l->pos = pos;
  l->c = c;
  return 1;
}

/**
 * Copies the condition. 
 */
struct xCondition * copyXC(struct xCondition *cOld)
{
  struct xCList *cl, *clnew;
  struct xCondition *cNew;

  assert((cNew=(struct xCondition *)calloc(1,sizeof(struct xCondition)))!=NULL);
  cNew->l=NULL;
  cNew->size=0;

  clnew = NULL;
  for(cl=cOld->l; cl!=NULL; cl=cl->next) {
    if(clnew==NULL) { /* add first element in new condition */
      assert((cNew->l = (struct xCList *)calloc(1,sizeof(struct xCList)))!=0);
      clnew = cNew->l;
    }else{ /* add next element in new condition */
      assert((clnew->next = (struct xCList *)calloc(1,sizeof(struct xCList)))!=0);
      clnew = clnew->next;
    }
    /* copy from the old classifier */
    clnew->pos = cl->pos;
    clnew->c = cl->c;
  }
  cNew->size = cOld->size;

  return cNew;
}

/**
 * Checks for equality. 
 */
int isEqualXC(struct xCondition *c1, struct xCondition *c2)
{
  struct xCList *l1, *l2;

  for(l1=c1->l, l2=c2->l; l1!=NULL && l2!=NULL; l1=l1->next, l2=l2->next) {
    if(l1->pos != l2->pos || l1->c != l2->c)
      return 0;
  }
  if(l1==NULL && l2==NULL)
    return 1;
  return 0;
}

/**
 * prints the condition in standard form 
 */
void printXC(FILE *fp, struct xCondition *con)
{
  struct xCList *l, *lh;
  int i=0;
  int length;

  for(l=con->l; l!=NULL; l=l->next) {
    for( ; i<l->pos; i++)
      fprintf(fp, "#");
    fprintf(fp, "%c", l->c);
    if(l->c == DONT_CARE)
	fprintf(fp, "MISTAKE - SPURIOUS DONTCARE SPECIFICATION");      
    for(lh = l->next; lh!=NULL; lh=lh->next) {
      if(lh->pos <= l->pos)
	fprintf(fp, "MISTAKE - DOUBLE POS SPECIFICATION");
    }
    i++;
  }
  length = getConditionLength();
  for( ; i<length; i++)
    fprintf(fp, "#");
}

/**
 * Empties the condition and sets its length to zero.
 */
void emptyXCondition(struct xCondition *con)
{
  struct xCList *cl, *clHelp;
  for(cl=con->l; cl!=NULL; ) {
    clHelp=cl;
    cl=cl->next;
    clHelp->next=NULL;
    free(clHelp);
  }
  con->l = NULL;
}

/**
 * Resets the specificity size parameter of the condition.
 */
void resetXCSize(struct xCondition *con)
{
  int i=0;
  struct xCList *l;
  for(l=con->l; l!=NULL; l=l->next)
    i++;
  con->size = i;
}