gaselector.cpp

遗传算法工具箱C++

			  GAPopulation::SCALED : GAPopulation::RAW));
}

// Make sure we have enough memory to work with.  Set values of choices array
// to appropriate values.

// This is the preselection part.  Figure out how many we should expect of 
// each individual.  An individual with e of 4.3 will get 4 places and have a
// 30% chance of a 5th place.

// This implementation only works if fitness scores are strictly positive or
// strictly negative.
void
GASRSSelector::update() {
  if(n != (unsigned int)(pop->size())){
    delete [] fraction;
    delete [] choices;
    n = pop->size();
    fraction = new float [n];
    choices = new unsigned int [n];
  }

  int i,ne,k=0;

  if(which == GASelectionScheme::RAW){
    if(pop->ave() == 0 || pop->max() == pop->min()){
      for(i=0; (unsigned int)i<n; i++)
	choices[i] = GARandomInt(0, n-1);
    }
    else if((pop->max() >= 0 && pop->min() >= 0) ||
	    (pop->max() <= 0 && pop->min() <= 0)){
      float expected;
      for(i=0; i<pop->size(); i++){
	if(pop->order() == GAPopulation::HIGH_IS_BEST)
	  expected = 
	    pop->individual(i, GAPopulation::RAW).score()/pop->ave();
	else
	  expected = 
	    (-pop->individual(i, GAPopulation::RAW).score()
	     + pop->max() + pop->min())/pop->ave();
	ne = (int)expected;
	fraction[i] = expected - ne;
	while(ne > 0 && k < (int)n){
	  assert(k >= 0 && k < (int)n);
	  choices[k] = i;
	  k++; ne--;
	}
      }
      i=0;
      while(k < pop->size()){
	if(fraction[i] > 0.0 && GAFlipCoin(fraction[i])){
	  assert(k >= 0 && k < (int)n);
	  assert(i >= 0 && i < (int)n);
	  choices[k] = i;
	  fraction[i] -= 1.0;
	  k++;
	}
	i++;
	if(i >= pop->size()) i=0;
      }
    }
    else {
      GAErr(GA_LOC, className(), "update",
	    "objective scores are not strictly negative or strictly positive",
	    "this selection method cannot be used with these scores");
    }
  }
  else {
    if(pop->fitave() == 0 || pop->fitmax() == pop->fitmin()){
      for(i=0; (unsigned int)i<n; i++)
	choices[i] = GARandomInt(0, n-1);
    }
    else if((pop->fitmax() >= 0 && pop->fitmin() >= 0) ||
	    (pop->fitmax() <= 0 && pop->fitmin() <= 0)){
      float expected;
      for(i=0; i<pop->size(); i++){
	if(pop->order() == GAPopulation::HIGH_IS_BEST)
	  expected = 
	    pop->individual(i, GAPopulation::SCALED).fitness()/pop->fitave();
	else
	  expected = 
	    (-pop->individual(i, GAPopulation::SCALED).fitness() 
	     + pop->fitmax() + pop->fitmin()) / pop->fitave();
	ne = (int)expected;
	fraction[i] = expected - ne;
	while(ne > 0 && k < (int)n){
	  assert(k >= 0 && k < (int)n);
	  choices[k] = i;
	  k++; ne--;
	}
      }
      i=0;
      int flag = 1;
      while(k < pop->size() && flag){
	if(i >= pop->size()){
	  i=0;
	  flag = 0;
	}
	if(fraction[i] > 0.0 && GAFlipCoin(fraction[i])){
	  assert(k >= 0 && k < (int)n);
	  assert(i >= 0 && i < (int)n);
	  choices[k] = i;
	  fraction[i] -= 1.0;
	  k++;
	  flag = 1;
	}
	i++;
      }
      if(k < pop->size()){
	for(; k<pop->size(); k++)
	  choices[k] = GARandomInt(0,pop->size()-1);
      }
    }
    else {
      GAErr(GA_LOC, className(), "update",
	    "fitness scores are not strictly negative or strictly positive",
	    "this selection method cannot be used with these scores");
    }
  }
}
#endif


/* ----------------------------------------------------------------------------
DSSelector - deterministic sampling

  This is implemented as described in Goldberg's book.
---------------------------------------------------------------------------- */
#if USE_DS_SELECTOR == 1
GAGenome &
GADSSelector::select() const {
  return pop->individual(choices[GARandomInt(0, pop->size()-1)],
			 (which == SCALED ? 
			  GAPopulation::SCALED : GAPopulation::RAW));
}

// Make sure we have enough memory to work with. Then calc the choices array.

// This is the preselection part.  Figure out how many we should expect of 
// each individual.  An individual with e of 4.3 will get 4 places, an 
// individual with e of 5.9 will get 5 places.  If there are any spaces
// remaining then we fill them with the individuals with highest fractional
// values (don't as *ME* why Goldberg does it this way...)

// This implementation only works if fitness scores are strictly positive or
// strictly negative.
void
GADSSelector::update() {
  if(n != (unsigned int)pop->size()){
    delete [] fraction;
    delete [] choices;
    delete [] idx;
    n = pop->size();
    fraction = new float [n];
    choices = new unsigned int [n];
    idx = new unsigned int [n];
  }

  int i,ne,k=0;

  if(which == GASelectionScheme::RAW){
    if(pop->ave() == 0 || pop->max() == pop->min()){
      for(i=0; (unsigned int)i<n; i++)
	choices[i] = GARandomInt(0, n-1);
    }
    else if((pop->max() >= 0 && pop->min() >= 0) ||
	    (pop->max() <= 0 && pop->min() <= 0)){
      float expected;
      for(i=0; i<pop->size(); i++){
	idx[i] = i;
	if(pop->order() == GAPopulation::HIGH_IS_BEST)
	  expected = 
	    pop->individual(i, GAPopulation::RAW).score()/pop->ave();
	else
	  expected =
	    (-pop->individual(i, GAPopulation::RAW).score()
	     + pop->max() + pop->min())/pop->ave();
	ne = (int)expected;
	fraction[i] = expected - ne;
	
	while(ne > 0 && k < (int)n){
	  assert(k >= 0 && k < (int)n);
	  choices[k] = i;
	  k++; ne--;
	}
      }
      
      GAQuickSort(idx, fraction, 0, n-1);
      for(i=pop->size()-1; k<pop->size(); k++, i--)
	choices[k] = idx[i];
    }
    else{
      GAErr(GA_LOC, className(), "update",
	    "objective scores are not strictly negative or strictly positive",
	    "this selection method cannot be used with these scores");
    }
  }
  else{
    if(pop->fitave() == 0 || pop->fitmax() == pop->fitmin()){
      for(i=0; (unsigned int)i<n; i++)
	choices[i] = GARandomInt(0, n-1);
    }
    else if((pop->fitmax() >= 0 && pop->fitmin() >= 0) ||
	    (pop->fitmax() <= 0 && pop->fitmin() <= 0)){
      float expected;
      for(i=0; i<pop->size(); i++){
	idx[i] = i;
	if(pop->order() == GAPopulation::HIGH_IS_BEST)
	  expected =
	    pop->individual(i, GAPopulation::SCALED).fitness()/pop->fitave();
	else
	  expected =
	    (-pop->individual(i, GAPopulation::SCALED).fitness()
	     + pop->fitmax() + pop->fitmin()) / pop->fitave();
	ne = (int)expected;
	fraction[i] = expected - ne;
	
	while(ne > 0 && k < (int)n){
	  assert(k >= 0 && k < (int)n);
	  choices[k] = i;
	  k++; ne--;
	}
      }
      
      GAQuickSort(idx, fraction, 0, n-1);
      for(i=pop->size()-1; k<pop->size(); k++, i--)
	choices[k] = idx[i];
    }
    else{
      GAErr(GA_LOC, className(), "update",
	    "fitness scores are not strictly negative or strictly positive",
	    "this selection method cannot be used with these scores");
    }
  }
}

static void
GAQuickSort(unsigned int *c, float *s, int l, int r) {
  int i,j; 
  float v;
  unsigned int tc;
  float ts;

  if(r > l){
    v = s[r]; i = l-1; j = r;
    for(;;){
      while(s[++i] < v); // might exceed max array limit here
      while(s[--j] > v && j > 0);
      if(i >= j) break;
      tc = c[i]; c[i] = c[j]; c[j] = tc;
      ts = s[i]; s[i] = s[j]; s[j] = ts;
    }
    tc = c[i]; c[i] = c[r]; c[r] = tc;
    ts = s[i]; s[i] = s[r]; s[r] = ts;
    GAQuickSort(c,s,l,i-1);
    GAQuickSort(c,s,i+1,r);
  }
}

#endif