classifierlist.c

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

/**
 * Calculates the specificity of the classifier
 */
int getSpecificity(struct xClassifier *cl)
{
  return cl->con->size;
}


/**
 * Calculates the specificity of each bit in the conditions of the population.
 * The array specPos is assumed to be set to 0!
 */
void getPosSpecificity(struct xClassifierSet *cll, double *specPos)
{
  struct xCList *l;
  
  for( ; cll!=NULL; cll=cll->next) {
    for(l = cll->cl->con->l; l!=NULL; l=l->next)
      specPos[l->pos] += cll->cl->num;
  }
}


/**
 * Apply mutation to classifier 'cl'.
 * If niche mutation is applied, 'situation' is considered to constrain mutation. 
 * returns if the condition was changed.
 */
int mutation(struct xClassifier *cl, char *situation, struct XCS *xcs)
{
  int mp, len, mttr=0;
  struct xCondition *con;
  struct xCList *l, *ll=NULL, *newl;

  len = getConditionLength();
  con = cl->con;
  l = con->l;
  for(mp=0; mp<len; mp++) {
    if(urand() < xcs->muGA) {
      for(; l!=NULL && l->pos < mp; l=l->next) /* move to position */
	ll=l;
      if(l!=NULL && l->pos==mp) { /* mutate specified position */
	if(mutate(&(l->c), situation[l->pos], xcs->doGeneralizationMutation, xcs->doNicheMutation)) {
	  mttr = 1;
	  if(l->c == DONT_CARE) {/* remove don't care entry!!! */
	    con->size --; /* generalizing */
	    if(ll==NULL) {/* remove first */
	      con->l = con->l->next;
	    }else{
	      ll->next=ll->next->next;
	    }
	    l->next=NULL;
	    free(l);
	    if(ll==NULL) {
	      l = con->l;
	    }else{
	      l = ll->next;
	    }
	  }
	}
      }else{ /* add position */
	assert((newl=(struct xCList *)calloc(1,sizeof(struct xCList)))!=0);
	newl->c = DONT_CARE;
	newl->pos = mp;
	newl->next = l;
	if( ! mutate(&(newl->c), situation[mp], xcs->doGeneralizationMutation, xcs->doNicheMutation) ) {
	  /* still a don't care symbol -> delete it! */
	  free(newl);
	}else{
	  con->size++;
	  mttr=1;
	  if(ll==NULL) { /* add before first one */
	    con->l=newl;
	  }else{
	    ll->next=newl;
	  }
	  ll = newl;
	}
      }
    }
  }
  len = con->size;
  
  /* possibly mutate action */
  if( urand() < xcs->muGA ) {
    mttr=1;
    mutateAction(&(cl->act));
  }
  
  /* return if the condition or action of the classifier changed */
  return mttr;
}

/**
 * Mutates one position in the condition of a classifier.
 * returns if the position really changed (for the GERERALIZATION_MUTATION) 
 */
int mutate(char *c, char s, int doGeneralizationMutation, int doNicheMutation)
{
  int changed=1;
  /* mutate condition -> 0, 1, or DONT_CARE */
  switch(*c) {
  case '0':
    if(doGeneralizationMutation || doNicheMutation ) {
      /* generalize */
      (*c)=DONT_CARE;
    }else{
      if(urand()<0.5)
	(*c)='1';
      else
	(*c)=DONT_CARE;
    }
    break;
  case '1':
    if(doGeneralizationMutation || doNicheMutation ) {
      (*c)=DONT_CARE;
      /* generalize */
    }else{
      if(urand()<0.5)
	(*c)='0';
      else
	(*c)=DONT_CARE;
    }
    break;
  case DONT_CARE:
    if(!doGeneralizationMutation) {
      /* specialize */
      if(doNicheMutation){
	(*c)=s;
      }else{
	if(urand()<0.5)
	  (*c)='0';
	else
	  (*c)='1';
      }
    }else{
      changed=0;
    }
    break;
  default:
    printf("Mistake during mutation! condition:%c char:%c\n",*c ,s);
    break;
  }
  return changed;
}

/**
 * Mutates the action to another action uniformly randomly chosen.
 */
void mutateAction(int *action)
{
  int i;

  do{
    i = (int)(urand() * getNumberOfActions());
  }while(*action == i);
  *action = i;
}


/*############################ offspring insertion #####################################*/


/**
 * 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 XCS *xcs)
{
  struct xClassifier *killedp;

  len+=2;
  if(xcs->doGASubsumption){
    subsumeClassifier(cl[0], parents, *set, pop, xcs->maxPopSize, xcs->thetaSub);
    subsumeClassifier(cl[1], parents, *set, pop, xcs->maxPopSize, xcs->thetaSub);
  }else{
    addClassifierToSet(cl[0], pop);
    addClassifierToSet(cl[1], pop);
  }
  
  while(len > xcs->maxPopSize) {
    len--;
    killedp=deleteClassifier(pop, xcs);
    
    /* record the deleted classifier to update other sets */
    if(killedp!=NULL) {
      addClassifierToPointerSet(killedp,killset);
      /* update the set */
      updateSet(set, *killset);
    }
  }
}


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


/**
 * Action set subsumption as described in the algorithmic describtion of XCS 
 */
void doActionSetSubsumption(struct xClassifierSet **aset, struct xClassifierSet **pop, struct xClassifierSet **killset, int thetaSub)
{
  struct xClassifier *subsumer=NULL;
  struct xClassifierSet *setp, *setpl;
  
  /* Find the most general subsumer */
  for(setp=*aset; setp!=NULL; setp=setp->next) {
    if(isSubsumer(setp->cl, thetaSub)) {
      if(subsumer==NULL || isMoreGeneral(setp->cl->con, subsumer->con)) {
	subsumer = setp->cl;
      }
    }
  }

  /* If a subsumer was found, subsume all classifiers that are more specific. */
  if(subsumer!=NULL) {
    for(setp=*aset, setpl=*aset; setp!=NULL; setp=setp->next) {
      while(isMoreGeneral(subsumer->con, setp->cl->con)) {
	subsumer->num += setp->cl->num;
	if(setpl==setp) {
	  *aset=setp->next;
	  deleteClassifierPointerFromSet(pop, setp->cl);
	  freeClassifier(setp->cl);
	  addClassifierToPointerSet(setp->cl, killset);
	  free(setp);
	  setp=*aset;
	  setpl=*aset;
	}else{
	  setpl->next=setp->next;
	  deleteClassifierPointerFromSet(pop, setp->cl);
	  freeClassifier(setp->cl);
	  addClassifierToPointerSet(setp->cl, killset);
	  free(setp);
	  setp=setpl;
	}
      }
      setpl=setp;
    }
  }
}

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

  addClassifierToSet(cl,pop);
}

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

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

  ret= cl1->act==cl2->act && isSubsumer(cl1, thetaSub) && isMoreGeneral( cl1->con, cl2->con);

  return ret;
}

/** 
 * Returns if the classifier satisfies the criteria for being a subsumer.
 */
int isSubsumer(struct xClassifier *cl, int thetaSub)
{
  return cl->exp > thetaSub && cl->acc == 1.;
}

/**
 * Check if the first condition is more general than the second.
 */
int isMoreGeneral (struct xCondition *first, struct xCondition *second)
{
  struct xCList *l1, *l2;
  int ret=0;

  for(l1=first->l, l2=second->l; l1!=NULL && l2!=NULL; l1=l1->next, l2=l2->next) {
    while(l2->pos < l1->pos) {
      ret = 1; /* definitely more specific */
      l2=l2->next;
      if(l2==NULL) /* since l1 still specifies we know that the first condition is not more general! */
	return 0;
    }
    if(l1->pos < l2->pos || l1->c != l2->c)
      return 0;
    /* if we came here, both pointers must point to the same position in the condition */
  }
  if(l1!=NULL) /* since l1 still specifies we know that the first condition is not more general!*/
    return 0;

  return ret;
}


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


/**
 * Adds only the pointers to the pointerset, ensures that no pointer is added twice,
 * returns if the pointer was added 
 */
int addClassifierToPointerSet(struct xClassifier *cl,struct xClassifierSet **pointerset)
{
  struct xClassifierSet *setp;
  
  for(setp=*pointerset; setp!=NULL; setp=setp->next) {
    if(setp->cl == cl){
      /* Classifier is already in Set */
      return 0;
    }
  }
  /* add the classifier, as it is not already in the pointerset */
  assert((setp=( struct xClassifierSet *)calloc(1,sizeof(struct xClassifierSet)))!=NULL);
  setp->cl=cl;
  setp->next=*pointerset;
  *pointerset=setp;
  return 1;
}

/**
 * Adds the classifier cl to the population, makes 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 numerosity 
   * and free the space of the new classifier */
  for(setp=*clSet;setp!=NULL;setp=setp->next) {
    if(isEqualXC(setp->cl->con,cl->con) && setp->cl->act==cl->act) {
      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 the new Clasifier cl to the xClassifierSet 'clSet'. 
 */
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 #############################################*/


/**
 * Deletes a classifier from the population and returns the pointer to the deleted classifier.
 */
struct xClassifier * deleteClassifier(struct xClassifierSet **pop, struct XCS *xcs) {
  struct xClassifier *killedp = NULL;

  killedp=deleteStochClassifier(pop, xcs->delta, xcs->thetaDel, xcs->deletionType);

  return killedp;
}


/**
 * Deletes one Classifier at Random considering the delection type chosen (random, action-set-size estimate
 * based, fitness based, or both). 
 */
struct xClassifier * deleteStochClassifier(struct xClassifierSet **pop, double delta, int thetaDel, int delType)
{
  struct xClassifierSet *setp,*setpl;
  struct xClassifier *killedp=NULL;
  double sum=0., choicep, meanf=0., meane=0.;
  int size=0;

  /* get the sum of the fitness and the numerosity */
  for(setp=*pop; setp!=NULL; setp=setp->next){
    meanf+=setp->cl->fit;
    meane+= setp->cl->preer*setp->cl->num;
    size+=setp->cl->num;
  }
  meanf/=(double)size;
  meane/=(double)size;