galistgenome.cpp

遗传算法工具箱C++

      bro.tail();		// move to the end of the list
    }
    bro.insert(list);		// stick the clone onto the end
    delete list;
    bro.head();			// set iterator to head of list
    nc += 1;
  }

  return nc;
}







// Partial match crossover for list genomes.  We need two versions of this
// routine:  one for lists whose nodes are pointers to objects (each genome
// points to the same objects as all of the other genomes) and one for
// lists whose nodes contain independent objects (each node has its own copy
// of the object).
//   This version of the partial match crossover uses objects that are multiply
// instantiated - each list genome contains its own objects in its nodes.
// The operator== method must be defined on the object for this implementation
// to work!  In this case, the 'object' is an int, so we're OK.  If you are 
// putting your own objects in the nodes, be sure you have operator== defined
// for your object.  You must also have operator!= defined for your object.  We
// do not do any assignments, so operator= and/or copy is not required.
//   We assume that none of the nodes will return a NULL pointer.  Also assume
// that the cross site has been selected properly.
//   First we make a copy of the mother.  Then we loop through the match 
// section and try to swap each element in the child's match section with its
// partner (as defined by the current node in the father's match section).
//   Mirroring will work the same way - just swap mom & dad and you're all set.
//   The parents should be the same size as the child (and they should contain
// the same nodes, but in any order).  We do not check for this!!
template <class T> int
GAListGenome<T>::
PartialMatchCrossover(const GAGenome& p1, const GAGenome& p2,
		     GAGenome* c1, GAGenome* c2){
  const GAListGenome<T> &mom=DYN_CAST(const GAListGenome<T> &, p1);
  const GAListGenome<T> &dad=DYN_CAST(const GAListGenome<T> &, p2);

  if(mom.size() != dad.size()){
    GAErr(GA_LOC, mom.className(), "cross", gaErrBadParentLength);
    return 0;
  }

  int a = GARandomInt(0, mom.size());
  int b = GARandomInt(0, dad.size());
  if(b<a) SWAP(a,b);
  T* index;
  int i,j,nc=0;

  if(c1){
    GAListGenome<T> &sis=DYN_CAST(GAListGenome<T> &, *c1);
    sis.GAList<T>::copy(mom);
    GAListIter<T> diter(dad);
    index = diter.warp(a);
    for(i=a; i<b; i++, index=diter.next()){
      if(*sis.head() == *index){
	sis.swap(i,0);
      }
      else{
	for(j=1; (j<sis.size()) && (*sis.next() != *index); j++);
	sis.swap(i,j);  // no op if j>size
      }
    }
    sis.head();         // set iterator to head of list
    nc += 1;
  }

  if(c2){
    GAListGenome<T> &bro=DYN_CAST(GAListGenome<T> &, *c2);
    bro.GAList<T>::copy(dad);
    GAListIter<T> miter(mom);
    index = miter.warp(a);
    for(i=a; i<b; i++, index=miter.next()){
      if(*bro.head() == *index){
	bro.swap(i,0);
      }
      else{
	for(j=1; (j<bro.size()) && (*bro.next() != *index); j++);
	bro.swap(i,j);  // no op if j>size
      }
    }
    bro.head();         // set iterator to head of list
    nc += 2;
  }

  return nc;
}





// Order crossover for lists.  As described in Goldberg's book.
//   We assume that we'll never get a NULL pointer while iterating through the
// list.  Also we assume that the lists are the same size and non-NULL.
template <class T> int
GAListIsHole(const GAListGenome<T> &child, const GAListGenome<T> &parent,
	     int index, int a, int b){
  GAListIter<T> citer(child), piter(parent);
  citer.warp(index);
  piter.warp(a);
  for(int i=a; i<b; i++){
    if(*citer.current() == *piter.current()) return 1;
    piter.next();
  }
  return 0;
}

template <class T> int
GAListGenome<T>::
OrderCrossover(const GAGenome& p1, const GAGenome& p2,
	       GAGenome* c1, GAGenome* c2){
  const GAListGenome<T> &mom=DYN_CAST(const GAListGenome<T> &, p1);
  const GAListGenome<T> &dad=DYN_CAST(const GAListGenome<T> &, p2);

  if(mom.size() != dad.size()){
    GAErr(GA_LOC, mom.className(), "cross", gaErrBadParentLength);
    return 0;
  }

  int a = GARandomInt(0, mom.size());
  int b = GARandomInt(0, dad.size());
  if(b<a) SWAP(a,b);
  int i,j, index, nc=0;

  if(c1){
    GAListGenome<T> &sis=DYN_CAST(GAListGenome<T> &, *c1);
    sis.GAList<T>::copy(mom);
    GAListIter<T> siter(sis);
    GAListIter<T> diter(dad);

// Move all the 'holes' into the crossover section and maintain the ordering of
// the non-hole elements.
    for(i=0, index=b; i<sis.size(); i++, index++){
      if(index >= sis.size()) index=0;
      if(GAListIsHole(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(GAListIsHole(sis,dad,j,a,b));
      sis.swap(index,j);
    }

// Now put the 'holes' in the proper order within the crossover section.
    for(i=a, sis.warp(a), diter.warp(a);
	i<b; i++, sis.next(), diter.next()){
      if(*sis.current() != *diter.current()){
	siter.warp(i);
	for(j=i+1; j<b; j++)
	  if(*siter.next() == *diter.current()){
	    sis.swap(i,j);
	    sis.warp(siter);	// move iterator back to previous location
	    break;
	  }
      }
    }

    sis.head();		// set iterator to head of list
    nc += 1;
  }

  if(c2){
    GAListGenome<T> &bro=DYN_CAST(GAListGenome<T> &, *c2);
    bro.GAList<T>::copy(dad);
    GAListIter<T> biter(bro);
    GAListIter<T> miter(mom);

// Move all the 'holes' into the crossover section and maintain the ordering of
// the non-hole elements.
    for(i=0, index=b; i<bro.size(); i++, index++){
      if(index >= bro.size()) index=0;
      if(GAListIsHole(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(GAListIsHole(bro,mom,j,a,b));
      bro.swap(index,j);
    }

// Now put the 'holes' in the proper order within the crossover section.
    for(i=a, bro.warp(a), miter.warp(a);
	i<b; i++, bro.next(), miter.next()){
      if(*bro.current() != *miter.current()){
	biter.warp(i);
	for(j=i+1; j<b; j++)
	  if(*biter.next() == *miter.current()){
	    bro.swap(i,j);
	    bro.warp(biter);	// move iterator back to previous location
	    break;
	  }
      }
    }
    bro.head();		// set iterator to head of list
    nc += 1;
  }

  return nc;
}











template <class T> int
GAListGenome<T>::
CycleCrossover(const GAGenome& p1, const GAGenome& p2,
	       GAGenome* c1, GAGenome* c2){
  const GAListGenome<T> &mom=DYN_CAST(const GAListGenome<T> &, p1);
  const GAListGenome<T> &dad=DYN_CAST(const GAListGenome<T> &, p2);

  if(mom.size() != dad.size()){
    GAErr(GA_LOC, mom.className(), "cross", gaErrBadParentLength);
    return 0;
  }

  GAMask mask;
  mask.size(mom.size());
  mask.clear();
  int i, nc=0;

  if(c1){
    GAListGenome<T> &sis=DYN_CAST(GAListGenome<T> &, *c1);
    sis.GAList<T>::copy(mom);
    GAListIter<T> diter(dad);

// Cycle through mom & dad to get the cyclic part of the crossover.
    mask[0] = 1;
    diter.head();
    while(*diter.current() != *sis.head()){
      for(i=0; i<sis.size(); i++, sis.next()){
	if(*sis.current() == *diter.current()){
	  mask[i] = 1;
	  diter.warp(i);
	  break;
	}
      }
    }

// Now fill in the rest of the sis with dad's contents that we didn't use
// in the cycle.
    sis.head();
    diter.head();
    for(i=0; i<sis.size(); i++){
      if(mask[i] == 0) *sis.current() = *diter.current();
      sis.next(); diter.next();
    }
    sis.head();		// set iterator to head of list
    nc += 1;
  }

  if(c2){
    GAListGenome<T> &bro=DYN_CAST(GAListGenome<T> &, *c2);
    bro.GAList<T>::copy(dad);
    GAListIter<T> miter(mom);

// Cycle through mom & dad to get the cyclic part of the crossover.
    mask[0] = 1;
    miter.head();
    while(*miter.current() != *bro.head()){
      for(i=0; i<bro.size(); i++, bro.next()){
	if(*bro.current() == *miter.current()){
	  mask[i] = 1;
	  miter.warp(i);
	  break;
	}
      }
    }

// Now fill in the rest of the bro with dad's contents that we didn't use
// in the cycle.
    bro.head();
    miter.head();
    for(i=0; i<bro.size(); i++){
      if(mask[i] == 0) *bro.current() = *miter.current();
      bro.next(); miter.next();
    }
    bro.head();		// set iterator to head of list
    nc += 1;
  }

  return nc;
}

#endif