ga1darraygenome.cpp

遗传算法工具箱C++

      if(GAFlipCoin(pmut)){
	child.gene(i, child.alleleset(i).allele());
	nMut++;
      }
    }
  }
  else{				// only flip the number of bits we need to flip
    for(n=0; n<nMut; n++){
      i = GARandomInt(0, child.length()-1);
      child.gene(i, child.alleleset(i).allele());
    }
  }
  return(STA_CAST(int,nMut));
}


// Randomly swap elements in the array.
template <class ARRAY_TYPE> int 
GA1DArrayGenome<ARRAY_TYPE>::SwapMutator(GAGenome & c, float pmut)
{
  GA1DArrayGenome<ARRAY_TYPE> &child=DYN_CAST(GA1DArrayGenome<ARRAY_TYPE>&, c);
  register int n, i;
  if(pmut <= 0.0) return(0);

  float nMut = pmut * STA_CAST(float,child.length());
  int length = child.length()-1;
  if(nMut < 1.0){		// we have to do a flip test on each bit
    nMut = 0;
    for(i=length; i>=0; i--){
      if(GAFlipCoin(pmut)){
	child.swap(i, GARandomInt(0, length));
	nMut++;
      }
    }
  }
  else{				// only flip the number of bits we need to flip
    for(n=0; n<nMut; n++)
      child.swap(GARandomInt(0, length), GARandomInt(0, length));
  }
  return(STA_CAST(int,nMut));
}


// The comparator is supposed to return a number that indicates how similar
// two genomes are, so here we just compare elements and return a number that
// indicates how many elements match.  If they are different lengths then we
// return -1 to indicate that we could not calculate the differences.
//   This assumes that there is an operator == defined for the object in the
// elements of the array.
template <class ARRAY_TYPE> float
GA1DArrayGenome<ARRAY_TYPE>::
ElementComparator(const GAGenome& a, const GAGenome& b)
{
  const GA1DArrayGenome<ARRAY_TYPE>& sis=
    DYN_CAST(const GA1DArrayGenome<ARRAY_TYPE>&, a);
  const GA1DArrayGenome<ARRAY_TYPE>& bro=
    DYN_CAST(const GA1DArrayGenome<ARRAY_TYPE>&, b);

  if(sis.length() != bro.length()) return -1;
  if(sis.length() == 0) return 0;
  float count = 0.0;
  for(int i=sis.length()-1; i>=0; i--)
    count += ((sis.gene(i) == bro.gene(i)) ? 0 : 1);
  return count/sis.length();
}














#define SWAP(a,b) {unsigned int tmp=a; a=b; b=tmp;}

// Randomly take bits from each parent.  For each bit we flip a coin to see if
// that bit should come from the mother or the father.  If strings are 
// different lengths then we need to use the mask to get things right.
template <class T> int
GA1DArrayGenome<T>::
UniformCrossover(const GAGenome& p1, const GAGenome& p2,
		 GAGenome* c1, GAGenome* c2){
  const GA1DArrayGenome<T> &mom=DYN_CAST(const GA1DArrayGenome<T> &, p1);
  const GA1DArrayGenome<T> &dad=DYN_CAST(const GA1DArrayGenome<T> &, p2);

  int n=0;
  int i;

  if(c1 && c2){
    GA1DArrayGenome<T> &sis=DYN_CAST(GA1DArrayGenome<T> &, *c1);
    GA1DArrayGenome<T> &bro=DYN_CAST(GA1DArrayGenome<T> &, *c2);

    if(sis.length() == bro.length() &&
       mom.length() == dad.length() &&
       sis.length() == mom.length()){
      for(i=sis.length()-1; i>=0; i--){
	if(GARandomBit()){
	  sis.gene(i, mom.gene(i));
	  bro.gene(i, dad.gene(i));
	}
	else{
	  sis.gene(i, dad.gene(i));
	  bro.gene(i, mom.gene(i));
	}
      }
    }
    else{
      GAMask mask;
      int start;
      int max = (sis.length() > bro.length()) ? sis.length() : bro.length();
      int min = (mom.length() < dad.length()) ? mom.length() : dad.length();
      mask.size(max);
      for(i=0; i<max; i++)
	mask[i] = GARandomBit();
      start = (sis.length() < min) ? sis.length()-1 : min-1;
      for(i=start; i>=0; i--)
	sis.gene(i, (mask[i] ? mom.gene(i) : dad.gene(i)));
      start = (bro.length() < min) ? bro.length()-1 : min-1;
      for(i=start; i>=0; i--)
	bro.gene(i, (mask[i] ? dad.gene(i) : mom.gene(i)));
    }
    n = 2;
  }
  else if(c1 || c2){
    GA1DArrayGenome<T> &sis = (c1 ? 
			       DYN_CAST(GA1DArrayGenome<T> &, *c1) : 
			       DYN_CAST(GA1DArrayGenome<T> &, *c2));

    if(mom.length() == dad.length() && sis.length() == mom.length()){
      for(i=sis.length()-1; i>=0; i--)
	sis.gene(i, (GARandomBit() ? mom.gene(i) : dad.gene(i)));
    }
    else{
      int min = (mom.length() < dad.length()) ? mom.length() : dad.length();
      min = (sis.length() < min) ? sis.length() : min;
      for(i=min-1; i>=0; i--)
	sis.gene(i, (GARandomBit() ? mom.gene(i) : dad.gene(i)));
    }
    n = 1;
  }

  return n;
}





// Single point crossover for 1D array genomes.  Pick a single point then
// copy genetic material from each parent.  We must allow for resizable genomes
// so be sure to check the behaviours before we do the crossovers.  If resizing
// is allowed then the children will change depending on where the site is
// located.  It is also possible to have a mixture of resize behaviours, but
// we won't worry about that at this point.  If this happens we just say that
// we cannot handle that and post an error message.
template <class T> int
GA1DArrayGenome<T>::
OnePointCrossover(const GAGenome& p1, const GAGenome& p2, 
		  GAGenome* c1, GAGenome* c2){
  const GA1DArrayGenome<T> &mom=DYN_CAST(const GA1DArrayGenome<T> &, p1);
  const GA1DArrayGenome<T> &dad=DYN_CAST(const GA1DArrayGenome<T> &, p2);

  int nc=0;
  unsigned int momsite, momlen;
  unsigned int dadsite, dadlen;

  if(c1 && c2){
    GA1DArrayGenome<T> &sis=DYN_CAST(GA1DArrayGenome<T> &, *c1);
    GA1DArrayGenome<T> &bro=DYN_CAST(GA1DArrayGenome<T> &, *c2);

    if(sis.resizeBehaviour() == GAGenome::FIXED_SIZE &&
       bro.resizeBehaviour() == GAGenome::FIXED_SIZE){
      if(mom.length() != dad.length() || 
	 sis.length() != bro.length() ||
	 sis.length() != mom.length()){
	GAErr(GA_LOC, mom.className(), "one-point cross", gaErrSameLengthReqd);
	return nc;
      }
      momsite = dadsite = GARandomInt(0, mom.length());
      momlen = dadlen = mom.length() - momsite;
    }
    else if(sis.resizeBehaviour() == GAGenome::FIXED_SIZE ||
	    bro.resizeBehaviour() == GAGenome::FIXED_SIZE){
      GAErr(GA_LOC, mom.className(), "one-point cross", gaErrSameBehavReqd);
      return nc;
    }
    else{
      momsite = GARandomInt(0, mom.length());
      dadsite = GARandomInt(0, dad.length());
      momlen = mom.length() - momsite;
      dadlen = dad.length() - dadsite;
      sis.resize(momsite+dadlen);
      bro.resize(dadsite+momlen);
    }
    
    sis.copy(mom, 0, 0, momsite);
    sis.copy(dad, momsite, dadsite, dadlen);
    bro.copy(dad, 0, 0, dadsite);
    bro.copy(mom, dadsite, momsite, momlen);
  
    nc = 2;
  }
  else if(c1 || c2){
    GA1DArrayGenome<T> &sis = (c1 ? 
			       DYN_CAST(GA1DArrayGenome<T> &, *c1) : 
			       DYN_CAST(GA1DArrayGenome<T> &, *c2));

    if(sis.resizeBehaviour() == GAGenome::FIXED_SIZE){
      if(mom.length() != dad.length() || sis.length() != mom.length()){
	GAErr(GA_LOC, mom.className(), "one-point cross", gaErrSameLengthReqd);
	return nc;
      }
      momsite = dadsite = GARandomInt(0, mom.length());
      momlen = dadlen = mom.length() - momsite;
    }
    else{
      momsite = GARandomInt(0, mom.length());
      dadsite = GARandomInt(0, dad.length());
      momlen = mom.length() - momsite;
      dadlen = dad.length() - dadsite;
      sis.resize(momsite+dadlen);
    }
    
    if(GARandomBit()){
      sis.copy(mom, 0, 0, momsite);
      sis.copy(dad, momsite, dadsite, dadlen);
    }
    else{
      sis.copy(dad, 0, 0, dadsite);
      sis.copy(mom, dadsite, momsite, momlen);
    }

    nc = 1;
  }

  return nc;
}











// Two point crossover for the 1D array genome.  Similar to the single point
// crossover, but here we pick two points then grab the sections based upon 
// those two points.
//   When we pick the points, it doesn't matter where they fall (one is not
// dependent upon the other).  Make sure we get the lesser one into the first
// position of our site array.
template <class T> int
GA1DArrayGenome<T>::
TwoPointCrossover(const GAGenome& p1, const GAGenome& p2, 
		  GAGenome* c1, GAGenome* c2){
  const GA1DArrayGenome<T> &mom=DYN_CAST(const GA1DArrayGenome<T> &, p1);
  const GA1DArrayGenome<T> &dad=DYN_CAST(const GA1DArrayGenome<T> &, p2);

  int nc=0;
  unsigned int momsite[2], momlen[2];
  unsigned int dadsite[2], dadlen[2];

  if(c1 && c2){
    GA1DArrayGenome<T> &sis=DYN_CAST(GA1DArrayGenome<T> &, *c1);
    GA1DArrayGenome<T> &bro=DYN_CAST(GA1DArrayGenome<T> &, *c2);

    if(sis.resizeBehaviour() == GAGenome::FIXED_SIZE &&
       bro.resizeBehaviour() == GAGenome::FIXED_SIZE){
      if(mom.length() != dad.length() || 
	 sis.length() != bro.length() ||
	 sis.length() != mom.length()){
	GAErr(GA_LOC, mom.className(), "two-point cross", gaErrSameLengthReqd);
	return nc;
      }
      momsite[0] = GARandomInt(0, mom.length());
      momsite[1] = GARandomInt(0, mom.length());
      if(momsite[0] > momsite[1]) SWAP(momsite[0], momsite[1]);
      momlen[0] = momsite[1] - momsite[0];
      momlen[1] = mom.length() - momsite[1];
      
      dadsite[0] = momsite[0];
      dadsite[1] = momsite[1];
      dadlen[0] = momlen[0];
      dadlen[1] = momlen[1];
    }
    else if(sis.resizeBehaviour() == GAGenome::FIXED_SIZE ||
	    bro.resizeBehaviour() == GAGenome::FIXED_SIZE){
      return nc;
    }
    else{
      momsite[0] = GARandomInt(0, mom.length());
      momsite[1] = GARandomInt(0, mom.length());
      if(momsite[0] > momsite[1]) SWAP(momsite[0], momsite[1]);
      momlen[0] = momsite[1] - momsite[0];
      momlen[1] = mom.length() - momsite[1];
      
      dadsite[0] = GARandomInt(0, dad.length());
      dadsite[1] = GARandomInt(0, dad.length());
      if(dadsite[0] > dadsite[1]) SWAP(dadsite[0], dadsite[1]);
      dadlen[0] = dadsite[1] - dadsite[0];
      dadlen[1] = dad.length() - dadsite[1];
      
      sis.resize(momsite[0]+dadlen[0]+momlen[1]);
      bro.resize(dadsite[0]+momlen[0]+dadlen[1]);
    }

    sis.copy(mom, 0, 0, momsite[0]);
    sis.copy(dad, momsite[0], dadsite[0], dadlen[0]);
    sis.copy(mom, momsite[0]+dadlen[0], momsite[1], momlen[1]);
    bro.copy(dad, 0, 0, dadsite[0]);
    bro.copy(mom, dadsite[0], momsite[0], momlen[0]);
    bro.copy(dad, dadsite[0]+momlen[0], dadsite[1], dadlen[1]);

    nc = 2;
  }
  else if(c1 || c2){
    GA1DArrayGenome<T> &sis = (c1 ?
			       DYN_CAST(GA1DArrayGenome<T> &, *c1) :
			       DYN_CAST(GA1DArrayGenome<T> &, *c2));

    if(sis.resizeBehaviour() == GAGenome::FIXED_SIZE){
      if(mom.length() != dad.length() || sis.length() != mom.length()){
	GAErr(GA_LOC, mom.className(), "two-point cross", gaErrSameLengthReqd);
	return nc;
      }
      momsite[0] = GARandomInt(0, mom.length());
      momsite[1] = GARandomInt(0, mom.length());
      if(momsite[0] > momsite[1]) SWAP(momsite[0], momsite[1]);
      momlen[0] = momsite[1] - momsite[0];
      momlen[1] = mom.length() - momsite[1];
      
      dadsite[0] = momsite[0];
      dadsite[1] = momsite[1];
      dadlen[0] = momlen[0];
      dadlen[1] = momlen[1];
    }
    else{
      momsite[0] = GARandomInt(0, mom.length());
      momsite[1] = GARandomInt(0, mom.length());
      if(momsite[0] > momsite[1]) SWAP(momsite[0], momsite[1]);
      momlen[0] = momsite[1] - momsite[0];
      momlen[1] = mom.length() - momsite[1];
      
      dadsite[0] = GARandomInt(0, dad.length());
      dadsite[1] = GARandomInt(0, dad.length());
      if(dadsite[0] > dadsite[1]) SWAP(dadsite[0], dadsite[1]);
      dadlen[0] = dadsite[1] - dadsite[0];
      dadlen[1] = dad.length() - dadsite[1];

      sis.resize(momsite[0]+dadlen[0]+momlen[1]);
    }

    if(GARandomBit()){
      sis.copy(mom, 0, 0, momsite[0]);
      sis.copy(dad, momsite[0], dadsite[0], dadlen[0]);
      sis.copy(mom, momsite[0]+dadlen[0], momsite[1], momlen[1]);
    }
    else{
      sis.copy(dad, 0, 0, dadsite[0]);
      sis.copy(mom, dadsite[0], momsite[0], momlen[0]);
      sis.copy(dad, dadsite[0]+momlen[0], dadsite[1], dadlen[1]);
    }

    nc = 1;
  }

  return nc;
}







// Even and odd crossover for the array works just like it does for the 
// binary strings.  For even crossover we take the 0th element and every other
// one after that from the mother.  The 1st and every other come from the
// father.  For odd crossover, we do just the opposite.
template <class T> int