ga1dbinstrgenome.cpp

遗传算法工具箱C++

       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){
    GA1DBinaryStringGenome &sis = (c1 ? 
				   DYN_CAST(GA1DBinaryStringGenome&, *c1) : 
				   DYN_CAST(GA1DBinaryStringGenome&, *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;
}





// Pick a point in the parents then grab alternating chunks for each child.
//   A word about crossover site mapping.  If a genome has width 10, the
// cross site can assume a value of 0 to 10, inclusive.  A site of 0 means
// that all of the material comes from the father.  A site of 10 means that
// all of the material comes from the mother.  A site of 3 means that bits
// 0-2 come from the mother and bits 3-9 come from the father.
int
GA1DBinaryStringGenome::
OnePointCrossover(const GAGenome& p1, const GAGenome& p2,
		  GAGenome* c1, GAGenome* c2){
  const GA1DBinaryStringGenome &mom=
    DYN_CAST(const GA1DBinaryStringGenome &, p1);
  const GA1DBinaryStringGenome &dad=
    DYN_CAST(const GA1DBinaryStringGenome &, p2);

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

  if(c1 && c2){
    GA1DBinaryStringGenome &sis=DYN_CAST(GA1DBinaryStringGenome &, *c1);
    GA1DBinaryStringGenome &bro=DYN_CAST(GA1DBinaryStringGenome &, *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 n;
      }
      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 n;
    }
    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);
  
    n = 2;
  }
  else if(c1 || c2){
    GA1DBinaryStringGenome &sis = (c1 ? 
				   DYN_CAST(GA1DBinaryStringGenome&, *c1) : 
				   DYN_CAST(GA1DBinaryStringGenome&, *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 n;
      }
      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);
    }

    n = 1;
  }

  return n;
}







// Two point crossover for one dimension binary strings.  The first part is
// taken from the mother, the second from the father, and the third from the
// mother.  If the child is resizable then we resize before copying the parts.
//   The rules for doing resizable crossover apply here as well as for the
// single point crossover (see comments for 1Pt for details).
int
GA1DBinaryStringGenome::
TwoPointCrossover(const GAGenome& p1, const GAGenome& p2,
		  GAGenome* c1, GAGenome* c2){
  const GA1DBinaryStringGenome &mom=
    DYN_CAST(const GA1DBinaryStringGenome &, p1);
  const GA1DBinaryStringGenome &dad=
    DYN_CAST(const GA1DBinaryStringGenome &, p2);

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

  if(c1 && c2){
    GA1DBinaryStringGenome &sis=DYN_CAST(GA1DBinaryStringGenome &, *c1);
    GA1DBinaryStringGenome &bro=DYN_CAST(GA1DBinaryStringGenome &, *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 n;
      }
      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){
      GAErr(GA_LOC, mom.className(), "two-point cross", gaErrSameBehavReqd);
      return n;
    }
    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]);

    n = 2;
  }
  else if(c1 || c2){
    GA1DBinaryStringGenome &sis = (c1 ? 
				   DYN_CAST(GA1DBinaryStringGenome&, *c1) : 
				   DYN_CAST(GA1DBinaryStringGenome&, *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 n;
      }
      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]);
    }

    n = 1;
  }

  return n;
}





//   Even and odd crossovers take alternating bits from the mother and father.
// For even crossover, we take every even bit from the mother and every odd bit
// from the father (the first bit is the 0th bit, so it is even).  Odd
// crossover is just the opposite.  
int
GA1DBinaryStringGenome::
EvenOddCrossover(const GAGenome& p1, const GAGenome& p2, 
		 GAGenome* c1, GAGenome* c2){
  const GA1DBinaryStringGenome &mom=
    DYN_CAST(const GA1DBinaryStringGenome &, p1);
  const GA1DBinaryStringGenome &dad=
    DYN_CAST(const GA1DBinaryStringGenome &, p2);

  int n=0;
  int i;

  if(c1 && c2){
    GA1DBinaryStringGenome &sis=DYN_CAST(GA1DBinaryStringGenome &, *c1);
    GA1DBinaryStringGenome &bro=DYN_CAST(GA1DBinaryStringGenome &, *c2);

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

    n = 2;
  }
  else if(c1 || c2){
    GA1DBinaryStringGenome &sis = (c1 ?
				   DYN_CAST(GA1DBinaryStringGenome&, *c1) : 
				   DYN_CAST(GA1DBinaryStringGenome&, *c2));

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

    n = 1;
  }

  return n;
}