ga3dbinstrgenome.cpp

遗传算法工具箱C++

  if(x + w > nx) w = nx - x;
  if(y + h > ny) h = ny - y;
  if(z + d > nz) d = nz - z;

  for(unsigned int k=0; k<d; k++)
    for(unsigned int j=0; j<h; j++)
      GABinaryString::randomize((z+k)*ny*nx + (y+j)*nx + x, w);
  _evaluated = gaFalse;
}


void
GA3DBinaryStringGenome::
move(unsigned int x, unsigned int y, unsigned int z,
     unsigned int srcx, unsigned int srcy, unsigned int srcz,
     unsigned int w, unsigned int h, unsigned int d)
{
  if(srcx + w > nx) w = nx - srcx;
  if(x + w > nx) w = nx - x;
  if(srcy + h > ny) h = ny - srcy;
  if(y + h > ny) h = ny - y;
  if(srcz + d > nz) d = nz - srcz;
  if(z + d > nz) d = nz - z;

  if(srcz<z){
    if(srcy<y){
      for(int k=d-1; k>=0; k--)
	for(int j=h-1; j>=0; j--)
	  GABinaryString::move((z+k)*ny*nx + (y+j)*nx + x,
			       (srcz+k)*ny*nx + (srcy+j)*nx + srcx, w);
    }
    else{
      for(int k=d-1; k>=0; k--)
	for(unsigned int j=0; j<h; j++)
	  GABinaryString::move((z+k)*ny*nx + (y+j)*nx + x,
			       (srcz+k)*ny*nx + (srcy+j)*nx + srcx, w);
    }
  }
  else{
    if(srcy<y){
      for(unsigned int k=0; k<d; k++)
	for(int j=h-1; j>=0; j--)
	  GABinaryString::move((z+k)*ny*nx + (y+j)*nx + x,
			       (srcz+k)*ny*nx + (srcy+j)*nx + srcx, w);
    }
    else{
      for(unsigned int k=0; k<d; k++)
	for(unsigned int j=0; j<h; j++)
	  GABinaryString::move((z+k)*ny*nx + (y+j)*nx + x,
			       (srcz+k)*ny*nx + (srcy+j)*nx + srcx, w);
    }
  }
  _evaluated = gaFalse;
}


int
GA3DBinaryStringGenome::
equal(const GA3DBinaryStringGenome& orig,
      unsigned int x, unsigned int y, unsigned int z,
      unsigned int srcx, unsigned int srcy, unsigned int srcz,
      unsigned int w, unsigned int h, unsigned int d) const
{
  unsigned int eq = 0;
  for(unsigned int k=0; k<d; k++)
    for(unsigned int j=0; j<h; j++)
      eq += GABinaryString::equal(orig,
				  (z+k)*ny*nx + (y+j)*nx + x,
				  (srcz+k)*ny*nx + (srcy+j)*nx + srcx, 
				  w);
  return eq==d*h ? 1 : 0;
}


int 
GA3DBinaryStringGenome::equal(const GAGenome & c) const
{
  if(this == &c) return 1;
  const GA3DBinaryStringGenome& b = DYN_CAST(const GA3DBinaryStringGenome&, c);
  if(nx != b.nx || ny != b.ny || nz != b.nz) return 0;
  int val=0;
  for(unsigned int k=0; k<nz && val==0; k++)
    for(unsigned int j=0; j<ny && val==0; j++)
      val = GABinaryString::equal(b,k*ny*nx,k*ny*nx,nx) ? 0 : 1;
  return(val ? 0 : 1);
}








/* ----------------------------------------------------------------------------
   Operators
---------------------------------------------------------------------------- */
/* ----------------------------------------------------------------------------
3D Binary String Genome
  The order for looping through indices is depth-then-height-then-width
(ie depth loops before a single height increment, height loops before a single
width increment)
---------------------------------------------------------------------------- */
void 
GA3DBinaryStringGenome::UniformInitializer(GAGenome & c)
{
  GA3DBinaryStringGenome &child=DYN_CAST(GA3DBinaryStringGenome &, c);
  child.resize(GAGenome::ANY_SIZE,GAGenome::ANY_SIZE,GAGenome::ANY_SIZE);
  for(int i=child.width()-1; i>=0; i--)
    for(int j=child.height()-1; j>=0; j--)
      for(int k=child.depth()-1; k>=0; k--)
	child.gene(i,j,k, GARandomBit());
}


void 
GA3DBinaryStringGenome::UnsetInitializer(GAGenome & c)
{
  GA3DBinaryStringGenome &child=DYN_CAST(GA3DBinaryStringGenome &, c);
  child.resize(GAGenome::ANY_SIZE,GAGenome::ANY_SIZE,GAGenome::ANY_SIZE);
  child.unset(0, 0, 0, child.width(), child.height(), child.depth());
}


void 
GA3DBinaryStringGenome::SetInitializer(GAGenome & c)
{
  GA3DBinaryStringGenome &child=DYN_CAST(GA3DBinaryStringGenome &, c);
  child.resize(GAGenome::ANY_SIZE,GAGenome::ANY_SIZE,GAGenome::ANY_SIZE);
  child.set(0, 0, 0, child.width(), child.height(), child.depth());
}


int 
GA3DBinaryStringGenome::FlipMutator(GAGenome & c, float pmut)
{
  GA3DBinaryStringGenome &child=DYN_CAST(GA3DBinaryStringGenome &, c);
  register int n, m, i, j, k, d;
  if(pmut <= 0.0) return(0);

  float nMut = pmut * STA_CAST(float,child.size());
  if(nMut < 1.0){		// we have to do a flip test on each bit
    nMut = 0;
    for(i=child.width()-1; i>=0; i--){
      for(j=child.height()-1; j>=0; j--){
	for(k=child.depth()-1; k>=0; k--){
	  if(GAFlipCoin(pmut)){
	    child.gene(i, j, k, ((child.gene(i,j,k) == 0) ? 1 : 0));
	    nMut++;
	  }
	}
      }
    }
  }
  else{				// only flip the number of bits we need to flip
    for(n=0; n<nMut; n++){
      m = GARandomInt(0, child.size()-1);
      d = child.height() * child.depth();
      i = m / d;
      j = (m % d) / child.depth();
      k = (m % d) % child.depth();
      child.gene(i, j, k, ((child.gene(i,j,k) == 0) ? 1 : 0));
    }
  }
  return(STA_CAST(int,nMut));
}


float
GA3DBinaryStringGenome::BitComparator(const GAGenome& a, const GAGenome& b){
  const GA3DBinaryStringGenome &sis=DYN_CAST(const GA3DBinaryStringGenome&, a);
  const GA3DBinaryStringGenome &bro=DYN_CAST(const GA3DBinaryStringGenome&, b);
  if(sis.size() != bro.size()) return -1;
  if(sis.size() == 0) return 0;
  float count = 0.0;
  for(int i=sis.width()-1; i>=0; i--)
    for(int j=sis.height()-1; j>=0; j--)
      for(int k=sis.depth()-1; k>=0; k--)
	count += ((sis.gene(i,j,k) == bro.gene(i,j,k)) ? 0 : 1);
  return count/sis.size();
}













// Make sure our bitmask is big enough, generate a mask, then use it to 
// extract the information from each parent to stuff the two children.
// We don't deallocate any space for the masks under the assumption that we'll
// have to use them again in the future.
//   For now we'll implement this only for fixed length genomes.  If you use
// this crossover method on genomes of different sizes it might break!
int
GA3DBinaryStringGenome::
UniformCrossover(const GAGenome& p1, const GAGenome& p2,
		 GAGenome* c1, GAGenome* c2){
  const GA3DBinaryStringGenome &mom=
    DYN_CAST(const GA3DBinaryStringGenome &, p1);
  const GA3DBinaryStringGenome &dad=
    DYN_CAST(const GA3DBinaryStringGenome &, p2);

  int i,j,k, nc=0;;

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

    if(sis.width() == bro.width() && sis.height() == bro.height() &&
       sis.depth() == bro.depth() &&
       mom.width() == dad.width() && mom.height() == dad.height() &&
       mom.depth() == dad.depth() &&
       sis.width() == mom.width() && sis.height() == mom.height() &&
       sis.depth() == mom.depth()){
      for(i=sis.width()-1; i>=0; i--){
	for(j=sis.height()-1; j>=0; j--){
	  for(k=sis.depth()-1; k>=0; k--){
	    if(GARandomBit()){
	      sis.gene(i,j,k, mom.gene(i,j,k));
	      bro.gene(i,j,k, dad.gene(i,j,k));
	    }
	    else{
	      sis.gene(i,j,k, dad.gene(i,j,k));
	      bro.gene(i,j,k, mom.gene(i,j,k));
	    }
	  }
	}
      }
    }
    else{
      GAMask mask;
      int maxx = GAMax(sis.width(), bro.width());
      int minx = GAMin(mom.width(), dad.width());
      int maxy = GAMax(sis.height(), bro.height());
      int miny = GAMin(mom.height(), dad.height());
      int maxz = GAMax(sis.depth(), bro.depth());
      int minz = GAMin(mom.depth(), dad.depth());
      mask.size(maxx*maxy*maxz);
      for(i=0; i<maxx; i++)
	for(j=0; j<maxy; j++)
	  for(k=0; k<maxz; k++)
	    mask[i*maxy*maxz+j*maxz+k] = GARandomBit();
      minx = GAMin(sis.width(), minx);
      miny = GAMin(sis.height(), miny);
      minz = GAMin(sis.depth(), minz);
      for(i=minx-1; i>=0; i--)
	for(j=miny-1; j>=0; j--)
	  for(k=minz-1; k>=0; k--)
	    sis.gene(i,j,k, (mask[i*miny*minz+j*minz+k] ?
			     mom.gene(i,j,k) : dad.gene(i,j,k)));
      minx = GAMin(bro.width(), minx);
      miny = GAMin(bro.height(), miny);
      minz = GAMin(bro.depth(), minz);
      for(i=minx-1; i>=0; i--)
	for(j=miny-1; j>=0; j--)
	  for(k=minz-1; k>=0; k--)
	    bro.gene(i,j,k, (mask[i*miny*minz+j*minz+k] ?
			     dad.gene(i,j,k) : mom.gene(i,j,k)));
    }

    nc = 2;
  }
  else if(c1 || c2){
    GA3DBinaryStringGenome &sis = (c1 ? 
				   DYN_CAST(GA3DBinaryStringGenome&, *c1) : 
				   DYN_CAST(GA3DBinaryStringGenome&, *c2));
    
    if(mom.width() == dad.width() && mom.height() == dad.height() &&
       mom.depth() == dad.depth() &&
       sis.width() == mom.width() && sis.height() == mom.height() &&
       sis.depth() == mom.depth()){
      for(i=sis.width()-1; i>=0; i--)
	for(j=sis.height()-1; j>=0; j--)
	  for(k=sis.depth()-1; k>=0; k--)
	    sis.gene(i,j,k, (GARandomBit() ? mom.gene(i,j,k):dad.gene(i,j,k)));
    }
    else{
      int minx = GAMin(mom.width(), dad.width());
      int miny = GAMin(mom.height(), dad.height());
      int minz = GAMin(mom.depth(), dad.depth());
      minx = GAMin(sis.width(), minx);
      miny = GAMin(sis.height(), miny);
      minz = GAMin(sis.depth(), minz);
      for(i=minx-1; i>=0; i--)
	for(j=miny-1; j>=0; j--)
	  for(k=minz-1; k>=0; k--)
	    sis.gene(i,j,k, (GARandomBit() ? mom.gene(i,j,k):dad.gene(i,j,k)));
    }

    nc = 1;
  }

  return nc;
}



// For even crossover we take the even bits from the mother (for the daughter)
// and the odd bits from the father.  Just the opposite for the son.
//   This is designed only for genomes that are the same length.  If the child
// is not the same length as the parent, or if the children are not the same
// size, we don't do the crossover.
//   In the interest of speed we do not do any checks for size.  Do not use 
// this crossover method when the parents and children may be different sizes.
// It might break!
int
GA3DBinaryStringGenome::
EvenOddCrossover(const GAGenome& p1, const GAGenome& p2,
		 GAGenome* c1, GAGenome* c2){
  const GA3DBinaryStringGenome &mom=
    DYN_CAST(const GA3DBinaryStringGenome &, p1);
  const GA3DBinaryStringGenome &dad=
    DYN_CAST(const GA3DBinaryStringGenome &, p2);

  int nc=0;
  int i,j,k;

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

    if(sis.width() == bro.width() && sis.height() == bro.height() &&
       sis.depth() == bro.depth() &&
       mom.width() == dad.width() && mom.height() == dad.height() &&
       mom.depth() == dad.depth() &&
       sis.width() == mom.width() && sis.height() == mom.height() &&
       sis.depth() == mom.depth()){
      int count=0;
      for(i=sis.width()-1; i>=0; i--){
	for(j=sis.height()-1; j>=0; j--){
	  for(k=sis.depth()-1; k>=0; k--){
	    if(count%2 == 0){
	      sis.gene(i,j,k, mom.gene(i,j,k));
	      bro.gene(i,j,k, dad.gene(i,j,k));
	    }
	    else{
	      sis.gene(i,j,k, dad.gene(i,j,k));
	      bro.gene(i,j,k, mom.gene(i,j,k));
	    }
	    count++;
	  }
	}
      }
    }
    else{
      int minx = GAMin(mom.width(), dad.width());
      int miny = GAMin(mom.height(), dad.height());
      int minz = GAMin(mom.depth(), dad.depth());
      minx = GAMin(sis.width(), minx);
      miny = GAMin(sis.height(), miny);
      minz = GAMin(sis.depth(), minz);