ga1darraygenome.cpp

遗传算法工具箱C++

GA1DArrayGenome<T>::
EvenOddCrossover(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;
  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>=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)));
    }

    nc = 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>=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)));
    }

    nc = 1;
  }

  return nc;
}





// Partial match crossover for the 1D array genome.  This uses the partial
// matching algorithm described in Goldberg's book.
//   Parents and children must be the same size for this crossover to work.  If
// they are not, we post an error message.
//   We make sure that b will be greater than a.
template <class T> int
GA1DArrayGenome<T>::
PartialMatchCrossover(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;
  int a = GARandomInt(0, mom.length());
  int b = GARandomInt(0, dad.length());
  if(b < a) SWAP(a,b);
  int i,j,index;

  if(mom.length() != dad.length()){
    GAErr(GA_LOC, mom.className(), "parial match cross", gaErrBadParentLength);
    return nc;
  }
  
  if(c1 && c2){
    GA1DArrayGenome<T> &sis=DYN_CAST(GA1DArrayGenome<T> &, *c1);
    GA1DArrayGenome<T> &bro=DYN_CAST(GA1DArrayGenome<T> &, *c2);

    sis.GAArray<T>::copy(mom);
    for(i=a, index=a; i<b; i++, index++){
      for(j=0; j<sis.length()-1 && sis.gene(j) != dad.gene(index); j++);
      sis.swap(i,j);
    }
    bro.GAArray<T>::copy(dad);
    for(i=a, index=a; i<b; i++, index++){
      for(j=0; j<bro.length()-1 && bro.gene(j) != mom.gene(index); j++);
      bro.swap(i,j);
    }

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

    const GA1DArrayGenome<T> *parent1, *parent2;
    if(GARandomBit()) { parent1 = &mom; parent2 = &dad; }
    else              { parent1 = &dad; parent2 = &mom; }

    sis.GAArray<T>::copy(*parent1);
    for(i=a, index=a; i<b; i++, index++){
      for(j=0; j<sis.length()-1 && sis.gene(j) != parent2->gene(index); j++);
      sis.swap(i,j);
    }

    nc = 1;
  }

  return nc;
}





// This function determines whether or not an indexed position is a hole that
// we can substitute into.  It does a linear search to find the holes (yuk).
template <class T> int
GA1DArrayIsHole(const GA1DArrayGenome<T> &c, const GA1DArrayGenome<T> &dad,
		int index, int a, int b){
  for(int i=a; i<b; i++)
    if(c.gene(index) == dad.gene(i)) return 1;
  return 0;
}


// Order crossover for the 1D array genome.  This uses the order crossover
// described in Goldberg's book.
//   Parents and children must be the same length.
//   We make sure that b will be greater than a.
//   This implementation isn't terribly smart.  For example, I do a linear
// search rather than caching and doing binary search or smarter hash tables.
//   First we copy the mother into the sister.  Then move the 'holes' into the
// crossover section and maintain the ordering of the non-hole elements.  
// Finally, put the 'holes' in the proper order within the crossover section.
// After we have done the sister, we do the brother.
template <class T> int
GA1DArrayGenome<T>::
OrderCrossover(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;
  int a = GARandomInt(0, mom.length());
  int b = GARandomInt(0, mom.length());
  if(b < a) SWAP(a,b);
  int i,j, index;

  if(mom.length() != dad.length()){
    GAErr(GA_LOC, mom.className(), "order cross", gaErrBadParentLength);
    return nc;
  }
  
  if(c1 && c2){
    GA1DArrayGenome<T> &sis=DYN_CAST(GA1DArrayGenome<T> &, *c1);
    GA1DArrayGenome<T> &bro=DYN_CAST(GA1DArrayGenome<T> &, *c2);

// Copy the parent
    sis.GAArray<T>::copy(mom);

// Move all the 'holes' into the crossover section
    for(i=0, index=b; i<sis.size(); i++, index++){
      if(index >= sis.size()) index=0;
      if(GA1DArrayIsHole(sis,dad,index,a,b)) break;
    }
    
    for(; i<sis.size()-b+a; i++, index++){
      if(index >= sis.size()) index=0;
      j=index;
      do{
	j++;
	if(j >= sis.size()) j=0;
      } while(GA1DArrayIsHole(sis,dad,j,a,b));
      sis.swap(index,j);
    }

// Now put the 'holes' in the proper order within the crossover section.
    for(i=a; i<b; i++){
      if(sis.gene(i) != dad.gene(i)){
	for(j=i+1; j<b; j++)
	  if(sis.gene(j) == dad.gene(i)) sis.swap(i,j);
      }
    }

// Now do the other child
    bro.GAArray<T>::copy(dad);

// Move all the 'holes' into the crossover section
    for(i=0, index=b; i<bro.size(); i++, index++){
      if(index >= bro.size()) index=0;
      if(GA1DArrayIsHole(bro,mom,index,a,b)) break;
    }

    for(; i<bro.size()-b+a; i++, index++){
      if(index >= bro.size()) index=0;
      j=index;
      do{
	j++;
	if(j >= bro.size()) j=0;
      } while(GA1DArrayIsHole(bro,mom,j,a,b));
      bro.swap(index,j);
    }
    
// Now put the 'holes' in the proper order within the crossover section.
    for(i=a; i<b; i++){
      if(bro.gene(i) != mom.gene(i)){
	for(j=i+1; j<b; j++)
	  if(bro.gene(j) == mom.gene(i)) bro.swap(i,j);
      }
    }

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

    const GA1DArrayGenome<T> *parent1, *parent2;
    if(GARandomBit()) { parent1 = &mom; parent2 = &dad; }
    else              { parent1 = &dad; parent2 = &mom; }

    sis.GAArray<T>::copy(*parent1);
    for(i=0, index=b; i<sis.size(); i++, index++){
      if(index >= sis.size()) index=0;
      if(GA1DArrayIsHole(sis,*parent2,index,a,b)) break;
    }
    for(; i<sis.size()-b+a; i++, index++){
      if(index >= sis.size()) index=0;
      j=index;
      do{
	j++;
	if(j >= sis.size()) j=0;
      } while(GA1DArrayIsHole(sis,*parent2,j,a,b));
      sis.swap(index,j);
    }
    for(i=a; i<b; i++){
      if(sis.gene(i) != parent2->gene(i)){
	for(j=i+1; j<b; j++)
	  if(sis.gene(j) == parent2->gene(i)) sis.swap(i,j);
      }
    }

    nc = 1;
  }

  return nc;
}








// Cycle crossover for the 1D array genome.  This is implemented as described 
// in goldberg's book.  The first is picked from mom, then cycle using dad.
// Finally, fill in the gaps with the elements from dad.
//   We allocate space for a temporary array in this routine.  It never frees
// the memory that it uses, so you might want to re-think this if you're really
// memory-constrained (similar to what we do with the uniform crossover when
// the children are resizeable).
//  Allocate space for an array of flags.  We use this to keep track of whether
// the child's contents came from the mother or the father.  We don't free the
// space here, but it is not a memory leak.
//   The first step is to cycle through mom & dad to get the cyclic part of 
// the crossover.  Then fill in the rest of the sis with dad's contents that 
// we didn't use in the cycle.  Finally, do the same thing for the other child.
//   Notice that this implementation makes serious use of the operator= for the
// objects in the array.  It also requires the operator != and == comparators.
template <class T> int
GA1DArrayGenome<T>::
CycleCrossover(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;
  int i, current=0;

  if(mom.length() != dad.length()){
    GAErr(GA_LOC, mom.className(), "cycle cross", gaErrBadParentLength);
    return nc;
  }

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

    mask.size(sis.length());
    mask.clear();

    sis.gene(0, mom.gene(0));
    mask[0] = 1;
    while(dad.gene(current) != mom.gene(0)){
      for(i=0; i<sis.size(); i++){
	if(mom.gene(i) == dad.gene(current)){
	  sis.gene(i, mom.gene(i));
	  mask[i] = 1;
	  current = i;
	  break;
	}
      }
    }

    for(i=0; i<sis.size(); i++)
      if(mask[i] == 0) sis.gene(i, dad.gene(i));

    mask.clear();

    bro.gene(0, dad.gene(0));
    mask[0] = 1;
    while(mom.gene(current) != dad.gene(0)){
      for(i=0; i<bro.size(); i++){
	if(dad.gene(i) == mom.gene(current)){
	  bro.gene(i, dad.gene(i));
	  mask[i] = 1;
	  current = i;
	  break;
	}
      }
    }

    for(i=0; i<bro.size(); i++)
      if(mask[i] == 0) bro.gene(i, mom.gene(i));

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

    const GA1DArrayGenome<T> *parent1, *parent2;
    if(GARandomBit()) { parent1 = &mom; parent2 = &dad; }
    else              { parent1 = &dad; parent2 = &mom; }

    GAMask mask;
    mask.size(sis.length());
    mask.clear();
    
    sis.gene(0, parent1->gene(0));
    mask[0] = 1;
    while(parent2->gene(current) != parent1->gene(0)){
      for(i=0; i<sis.size(); i++){
	if(parent1->gene(i) == parent2->gene(current)){
	  sis.gene(i, parent1->gene(i));
	  mask[i] = 1;
	  current = i;
	  break;
	}
      }
    }
    for(i=0; i<sis.size(); i++)
      if(mask[i] == 0) sis.gene(i, parent2->gene(i));

    nc = 1;
  }

  return nc;
}

#undef SWAP

#endif