classifierlist.c

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

{
  struct xClassifierSet *setp;
  
  *fitsum=0.;
  *setsum=0;  
  *gaitsum=0;
  for(setp=set;setp!=NULL;setp=setp->next){
    (*fitsum)+=setp->cl->fit;
    (*setsum)+=setp->cl->num;
    (*gaitsum) += setp->cl->gaIterationTime*setp->cl->num;
  }
}

/**
 * Sets the time steps of all classifiers in the set to itTime 
 * (because a GA application is occurring in this set!).
 */
void setTimeStamps(struct xClassifierSet *set, int itTime)
{
  for( ; set!=NULL; set=set->next){
    set->cl->gaIterationTime=itTime;
  }
}


/*############################ selection mechanisms ####################################*/


/**
 * Select two classifiers using the chosen selection mechanism and copy them as offspring. 
 */
void selectTwoClassifiers(struct xClassifier **cl, struct xClassifier **parents, struct xClassifierSet *set, double fitsum, int setsum, struct XCS *xcs, char *situation)
{
  int i; /*,j, length;*/
  struct xClassifier *clp;

  assert(set!=NULL);

  for(i=0;i<2;i++) {
    if(xcs->tournamentSize<=0)
      clp = selectClassifierUsingRWS(set,fitsum);
    else
      if(i==0)
	clp = selectClassifierUsingTournamentSelection(set, setsum, xcs, 0);
      else
	clp = selectClassifierUsingTournamentSelection(set, setsum, xcs, parents[0]);
    parents[i]=clp;
      
    assert((cl[i]=(struct xClassifier *)calloc(1,sizeof(struct xClassifier)))!=NULL);
    cl[i]->con = copyXC(clp->con);
    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 = clp->gaIterationTime;
  }
}

/** 
 * Selects a classifier from 'set' using tournament selection.
 * If 'notMe' is not the NULL pointer and forceDifferentInTournament is set to a value larger 0,
 * this classifier is not selected except if it is the only classifier. 
 */
struct xClassifier * selectClassifierUsingTournamentSelection(struct xClassifierSet *set, int setsum, 
							      struct XCS *xcs, struct xClassifier *notMe)
{
  struct xClassifierSet *setp, *winnerSet=NULL;
  struct xClassifier *winner=NULL;
  double fitness=-1, value;
  int i, j, *sel, size=0;

  assert(set!=NULL);/* there must be at least one classifier in the set */
  if(notMe!=0) {
    if(urand() < xcs->forceDifferentInTournament)
      setsum -= notMe->num; 
    else
      notMe=0; /* picking the same guy is allowed */
  }
  if(setsum<=0) /* only one classifier in set */
    return set->cl;

  if(xcs->tournamentSize>1) {/* tournament with fixed size */
    assert((sel = (int *)calloc(setsum, sizeof(int)))!=NULL);
    for(i=0; i<xcs->tournamentSize; i++) { /* (with replacement) */
      sel[(int)(urand()*setsum)]=1;
    }
    if(i-xcs->tournamentSize != 0 && urand() > i-xcs->tournamentSize) 
      /* possible probabilistic selection of the last guy */
      sel[(int)(urand()*setsum)]=1;

    for(setp=set, i=0; setp!=NULL; setp=setp->next) {
      if(setp->cl != notMe) {
	if(fitness < setp->cl->fit/setp->cl->num) {
	  for(j=0; j<setp->cl->num; j++) {
	    if(sel[i+j]) {
	      freeSet(&winnerSet);
	      addClassifierToPointerSet(setp->cl, &winnerSet);
	      fitness = setp->cl->fit/setp->cl->num;
	      break; /* go to next classifier since this one is already a winner*/
	    }
	  }
	}
	i += setp->cl->num;
      }
    }
    free(sel);
    assert(winnerSet!=NULL);
    size=1;
  }else{
    /* tournament selection with the tournament size approx. equal to tournamentSize*setsum */
    winnerSet=NULL;
    while(winnerSet==NULL) {
      size=0;
      for(setp=set; setp!=NULL; setp=setp->next) {
	if(setp->cl != notMe) { /* do not reselect the same classifier -> this only applies if forcedDifferentInTournament is set!*/
	  value = setp->cl->preer;
	  if(winnerSet==NULL 
	     || (!xcs->doGAErrorBasedSelect && fitness - xcs->selectTolerance <= setp->cl->fit/setp->cl->num)
	     || (xcs->doGAErrorBasedSelect && fitness + xcs->selectTolerance * getPaymentRange() >= value)) {
	    /* if his fitness is worse then do not bother */
	    for(i=0; i<setp->cl->num; i++) {
	      if(urand() < xcs->tournamentSize) {
		/* this classifier is a selection candidate and 
		 * his fitness/error is higher/lower or similar to the other classifier */
		if(winnerSet==NULL) {
		  /* the first guy in the tournament */
		  addClassifierToPointerSet(setp->cl, &winnerSet);
		  if(xcs->doGAErrorBasedSelect) {
		    fitness = value;
		  }else{
		    fitness = setp->cl->fit/setp->cl->num;
		  }
		  size=1;
		}else{
		  /* another guy in the tournament */
		  if( (!xcs->doGAErrorBasedSelect && fitness + xcs->selectTolerance > setp->cl->fit/setp->cl->num)
		      || 
		      (xcs->doGAErrorBasedSelect && fitness - xcs->selectTolerance * getPaymentRange() < value)) {
		    /* both classifiers in tournament have a similar fitness/error */
		    size += addClassifierToPointerSet(setp->cl, &winnerSet);
		  }else{
		    /* new classifier in tournament is clearly better */
		    freeSet(&winnerSet);
		    winnerSet=NULL;
		    addClassifierToPointerSet(setp->cl, &winnerSet);
		    if(xcs->doGAErrorBasedSelect) {
		      fitness = value;
		    }else{
		      fitness = setp->cl->fit/setp->cl->num;
		    }
		    size=1;
		  }
		}
		break; /* go to next classifier since this one is already a winner*/
	      }
	    }
	  }
	}
      }
    }    
  }
  /* choose one of the equally best winners at random */
  size = (int)(urand()*size);
  for(setp=winnerSet; setp!=NULL; setp=setp->next) {
    if(size==0)
      break;
    size--;
  }
  winner = setp->cl;
  freeSet(&winnerSet);
  return winner;
}


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

  choicep=urand()*fitsum;
  setp=set;
  fitsum=setp->cl->fit;
  while(choicep>fitsum){
    setp=setp->next;
    fitsum+=setp->cl->fit;
  }

  return setp->cl;
}


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


/**
 * Determines if crossover is applied and calls then the selected crossover type.
 * returns if the conditions changed */
int crossover(struct xClassifier **cl, int crossoverType, double chi)
{
  int changed=0;

  if(urand()<chi){
    if(crossoverType == 0)
      changed = uniformCrossover(cl);
    else if(crossoverType == 1)
      changed = onePointCrossover(cl);
    else
      changed = twoPointCrossover(cl);
  }
  return changed;
}


/**
 * Crosses the two received classifiers using uniform crossover.
 * returns if the conditions were changed 
 */
int uniformCrossover(struct xClassifier **cl)
{
  int len, changed =0;
  char help;
  struct xCList *l1=NULL, *l2=NULL, *ll1=NULL, *ll2=NULL;

  len=getConditionLength();
  
  for(l1=cl[0]->con->l, l2=cl[1]->con->l; l1!=NULL ; ) {
    while(l2!=NULL && l2->pos < l1->pos) {
      if(urand()<0.5) { /* add l2 to l1 and remove it from l2 */
	changed = 1;
	/*...removing*/
	if(ll2==NULL) { /* first attribute*/
	  cl[1]->con->l = l2->next;
	}else{
	  ll2->next = l2->next;
	}
	/*...adding*/
	if(ll1==NULL) { /* first attribute */
	  cl[0]->con->l = l2;
	  cl[0]->con->l->next = l1;
	  ll1=l2;
	}else{
	  ll1->next = l2;
	  ll1->next->next = l1;
	  ll1=ll1->next;
	}
	/* set l2 */
	if(ll2==NULL) { /* removed first attribute */
	  l2=cl[1]->con->l;
	}else{
	  l2=ll2->next;
	}
      }else{ /* move l2 to the next position without crossing*/
	ll2=l2;
	l2=l2->next;
      }
    }
    if(l2!=NULL && l2->pos == l1->pos) {
      if(urand()<0.5) { /* swap the characters of the two */
	if(l1->c != l2->c) {
	  printf("Attributes are not equal during crossover!?\n");
	  changed=1;
	  help = l1->c;
	  l1->c=l2->c;
	  l2->c=help;
	}
      }
      ll1=l1;
      ll2=l2;
      l1=l1->next;
      l2=l2->next;
    }else if(l2==NULL || l2->pos > l1->pos) {
      if(urand()<0.5) {/* add l1 to l2 and remove it from l1 */
	changed=1;
	/*...removing */
	if(ll1==NULL) {/* first attribute */
	  cl[0]->con->l = l1->next;
	}else{
	  ll1->next = l1->next;
	}
	/*...adding */
	if(ll2==NULL) { /* first attribute */
	  cl[1]->con->l = l1;
	  cl[1]->con->l->next = l2;
	  ll2=l1;
	}else{
	  ll2->next = l1;
	  ll2->next->next = l2;
	  ll2=l1;
	}
	/* set l1 */
	if(ll1==NULL) { /* removed first attribute */
	  l1=cl[0]->con->l;
	}else{
	  l1=ll1->next;
	}
      }else{ /* move l1 to the next position without crossing*/
	ll1=l1;
	l1=l1->next;
      }
    }
  }
  /* finally, possible last elements in l2 might be crossed */
  while(l2!=NULL) { /* l1=NULL now!!! */
    if(urand()<0.5) {/*add l2 to l1 and remove it from l2 */
      changed=1;
      /*...removing*/
      if(ll2==NULL) {/* first attribute*/
	cl[1]->con->l = l2->next;
      }else{
	ll2->next = l2->next;
      }
      /*...adding*/
      if(ll1==NULL) { /* first attribute */
	cl[0]->con->l = l2;
	cl[0]->con->l->next = l1;
	ll1=l2;
      }else{
	ll1->next = l2;
	ll1->next->next = l1;
	ll1=ll1->next;
      }
      /* set l2 */
      if(ll2==NULL) { /* removed first attribute */
	l2=cl[1]->con->l;
      }else{
	l2=ll2->next;
      }
    }else{ /* move l2 to the next position without crossing*/
      ll2=l2;
      l2=l2->next;
    }
  }
  resetXCSize(cl[0]->con);
  resetXCSize(cl[1]->con);
  return changed;
}

/**
 * Crosses the two received classifiers using one-point crossover.
 * returns if the conditions were changed 
 */
int onePointCrossover(struct xClassifier **cl)
{
  int sep,len;
  struct xCList *l1=NULL, *l2=NULL, *ll1=NULL, *ll2=NULL;
  
  /* get crossing site */
  len=getConditionLength();
  sep=urand()*(len-1);
  /* find cross start */
  for(l1=cl[0]->con->l; l1!=NULL; l1=l1->next) {
    if(l1->pos > sep)
      break;
    ll1=l1;
  }
  for(l2=cl[0]->con->l; l2!=NULL; l2=l2->next) {
    if(l2->pos > sep)
      break;
    ll2=l2;
  }
  if( (ll1==NULL && ll2==NULL) || (l1==NULL && l2==NULL))
    return 0;
  /* cross those... */
  if(ll1==NULL) {
    cl[0]->con->l=l2;
  }else{
    ll1->next=l2;
  }
  if(ll2==NULL) {
    cl[1]->con->l=l1;
  }else{
    ll2->next = l1;
  }
  resetXCSize(cl[0]->con);
  resetXCSize(cl[1]->con);
  return 1;
}


/**
 * Crosses the two received classifiers using two-point crossover.
 * returns if the conditions were changed 
 */
int twoPointCrossover(struct xClassifier **cl)
{
  int sep[2],len, h, i;
  struct xCList *l1=NULL, *l2=NULL, *ll1=NULL, *ll2=NULL;

  /* get two crossing sites with sep1<sep2 */
  len=getConditionLength();
  sep[0]=urand()*len;
  sep[1]=urand()*len +1;
  if(sep[0]>sep[1]){
    h=sep[0];
    sep[0]=sep[1];
    sep[1]=h;
  }else if(sep[0]==sep[1]){
    sep[1]++;
  }

  for(i=0; i<2; i++) {  /* I do two crosses starting both times from the beginning... */
    /* find cross start */
    ll1=NULL;
    for(l1=cl[0]->con->l; l1!=NULL; l1=l1->next) {
      if(l1->pos >= sep[i])
	break;
      ll1=l1;
    }
    ll2=NULL;
    for(l2=cl[1]->con->l; l2!=NULL; l2=l2->next) {
      if(l2->pos >= sep[i])
	break;
      ll2=l2;
    }
    /* cross those... */
    if(ll1==NULL) {
      cl[0]->con->l=l2;
    }else{
      ll1->next = l2;
    }
    if(ll2==NULL) {
      cl[1]->con->l=l1;
    }else{
      ll2->next = l1;
    }
  }
  resetXCSize(cl[0]->con);
  resetXCSize(cl[1]->con);
  
  return 1;
}