ga1dbinstrgenome.cpp

遗传算法工具箱C++

// $Header$
/* ----------------------------------------------------------------------------
  binstr1.C
  mbwall 19apr95
  Copyright (c) 1995 Massachusetts Institute of Technology
                     all rights reserved

 DESCRIPTION:
  Source file for the 1D binary string genome.
---------------------------------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "gaerror.h"
#include "garandom.h"
#include "GA1DBinStrGenome.h"
#include "GAMask.h"

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

/* ----------------------------------------------------------------------------
   Genome class definition
---------------------------------------------------------------------------- */
// Set all the initial values to NULL or zero, then allocate the space we'll
// need (using the resize method).  We do NOT call the initialize method at
// this point - initialization must be done explicitly by the user of the
// genome (eg when the population is created or reset).  If we called the
// initializer routine here then we could end up with multiple initializations
// and/or calls to dummy initializers (for example when the genome is 
// created with a dummy initializer and the initializer is assigned later on).
GA1DBinaryStringGenome::
GA1DBinaryStringGenome(unsigned int len, 
		       GAGenome::Evaluator f, void * u) :
GABinaryString(len),
GAGenome(DEFAULT_1DBINSTR_INITIALIZER, 
	 DEFAULT_1DBINSTR_MUTATOR,
	 DEFAULT_1DBINSTR_COMPARATOR) {
  evaluator(f);
  userData(u);
  crossover(DEFAULT_1DBINSTR_CROSSOVER); // assign the default sexual crossover
  nx=minX=maxX=0;
  resize(len);
}


// This is the copy initializer.  We set everything to the default values, then
// copy the original.  The BinaryStringGenome creator takes care of zeroing
// the data and sz members.
GA1DBinaryStringGenome::
GA1DBinaryStringGenome(const GA1DBinaryStringGenome& orig) :
GABinaryString(orig.GABinaryString::size()),
GAGenome() {
  nx=minX=maxX=0;
  GA1DBinaryStringGenome::copy(orig);
}

GA1DBinaryStringGenome::~GA1DBinaryStringGenome() {
}


// The clone member creates a duplicate (exact or just attributes, depending
// on the flag).  The caller is responsible for freeing the memory that is 
// allocated by this method.
GAGenome*
GA1DBinaryStringGenome::clone(GAGenome::CloneMethod flag) const {
  GA1DBinaryStringGenome *cpy = new GA1DBinaryStringGenome(nx);
  if(flag == CONTENTS){
    cpy->copy(*this);
  }
  else{
    cpy->GAGenome::copy(*this);
    cpy->maxX = maxX; cpy->minX = minX;
  }
  return cpy;
}


// This is the class-specific copy method.  It will get called by the super
// class since the superclass operator= is set up to call ccopy (and that is
// what we define here - a virtual function).  We should check to be sure that
// both genomes are the same class and same dimension.  This function tries
// to be smart about they way it copies.  If we already have data, then we do
// a memcpy of the one we're supposed to copy.  If we don't or we're not the 
// same size as the one we're supposed to copy, then we adjust ourselves.
//   The BinaryStringGenome takes care of the resize in its copy method.
// It also copies the bitstring for us.
void
GA1DBinaryStringGenome::copy(const GAGenome & orig)
{
  if(&orig == this) return;
  const GA1DBinaryStringGenome* c = 
    DYN_CAST(const GA1DBinaryStringGenome*, &orig);
  if(c) {
    GAGenome::copy(*c);
    GABinaryString::copy(*c);
    nx = c->nx; minX = c->minX; maxX = c->maxX;
  }
}


//   Resize the genome.  If someone specifies ANY_RESIZE then we pick a random
// size within the behaviour limits that have been set.  If limits have been
// set and someone passes us something outside the limits, we resize to the
// closest bound.  If the genome is fixed size (ie min limit equals max limit)
// then we resize to the specified value and move the min/max to match it.
int
GA1DBinaryStringGenome::resize(int l)
{
  if(l == STA_CAST(int, nx)) return nx;

  if(l == GAGenome::ANY_SIZE)
    l = GARandomInt(minX, maxX);
  else if(l < 0)
    return nx;			// do nothing
  else if(minX == maxX)
    minX=maxX=l;
  else{
    if(l < STA_CAST(int, minX)) l=minX;
    if(l > STA_CAST(int, maxX)) l=maxX;
  }

  GABinaryString::resize(l);
  if(l > STA_CAST(int, nx))
    for(int i=nx; i<l; i++)
      bit(i, GARandomBit());
  nx = l;
  _evaluated = gaFalse;
  return sz;
}


#ifdef GALIB_USE_STREAMS
// We read data from a stream as a series of 1's and 0's.  We want a continuous
// stream (ie no spaces) but if there are spaces then we can handle them.  We
// ignore all whitespace.  We ignore anything that is not a digit.  If it is a
// zero then we set to zero.  Anything else is a 1.
int
GA1DBinaryStringGenome::read(STD_ISTREAM & is)
{
  static char c;
  unsigned int i=0;

  while(!is.fail() && !is.eof() && i<nx) {
    is >> c;
    if(isdigit(c)) gene(i++, ((c == '0') ? 0 : 1));
  }

  _evaluated = gaFalse;

  if(is.eof() && i < nx){
    GAErr(GA_LOC, className(), "read", gaErrUnexpectedEOF);
    is.clear(STD_IOS_BADBIT | is.rdstate());
    return 1;
  }

  return 0;
}


// When we write the data to a stream we do it without any spaces.  Also, there
// is no newline at the end of the stream of digits.
int
GA1DBinaryStringGenome::write(STD_OSTREAM & os) const
{
  for(unsigned int i=0; i<nx; i++)
    os << gene(i);
  return 0;
}
#endif


//   Set the resize behaviour of the genome.  A genome can be fixed
// length, resizeable with a max and min limit, or resizeable with no limits
// (other than an implicit one that we use internally).
//   A value of 0 means no resize, a value less than zero mean unlimited 
// resize, and a positive value means resize with that value as the limit.
//   We return the upper limit of the genome's size.
int
GA1DBinaryStringGenome::
resizeBehaviour(unsigned int lower, unsigned int upper)
{
  if(upper < lower){
    GAErr(GA_LOC, className(), "resizeBehaviour", gaErrBadResizeBehaviour);
    return resizeBehaviour();
  }
  minX = lower; maxX = upper;
  if(nx > upper) resize(upper);
  if(nx < lower) resize(lower);
  return resizeBehaviour();
}

int 
GA1DBinaryStringGenome::resizeBehaviour() const {
  int val = maxX;
  if(maxX == minX) val = FIXED_SIZE;
  return val;
}

int 
GA1DBinaryStringGenome::
equal(const GA1DBinaryStringGenome& c,
      unsigned int dest, unsigned int src, unsigned int len) const {
  return GABinaryString::equal(c,dest,src,len);
}

int 
GA1DBinaryStringGenome::equal(const GAGenome & c) const {
  if(this == &c) return 1;
  const GA1DBinaryStringGenome* b = DYN_CAST(const GA1DBinaryStringGenome*,&c);
  int eq = 0;
  if(b) {
    eq = ((nx != b->nx) ? 0 : GABinaryString::equal(*b,0,0,nx));
  }
  return eq;
}










/* ----------------------------------------------------------------------------
   Operators
---------------------------------------------------------------------------- */
//   Set the bits of the genome to random values.  We use the library's
// random bit function so we don't have to worry about machine-specific stuff.
//   We also do a resize so the genome can resize itself (randomly) if it
// is a resizeable genome.
void 
GA1DBinaryStringGenome::UniformInitializer(GAGenome & c)
{
  GA1DBinaryStringGenome &child=DYN_CAST(GA1DBinaryStringGenome &, c);
  child.resize(GAGenome::ANY_SIZE); // let chrom resize if it can
  for(int i=child.length()-1; i>=0; i--)
    child.gene(i, GARandomBit()); // initial values are all random
}


//   Unset all of the bits in the genome.
void 
GA1DBinaryStringGenome::UnsetInitializer(GAGenome & c)
{
  GA1DBinaryStringGenome &child=DYN_CAST(GA1DBinaryStringGenome &, c);
  child.resize(GAGenome::ANY_SIZE); // let chrom resize if it can
  child.unset(0, child.length());
}


//   Set all of the bits in the genome.
void 
GA1DBinaryStringGenome::SetInitializer(GAGenome & c)
{
  GA1DBinaryStringGenome &child=DYN_CAST(GA1DBinaryStringGenome &, c);
  child.resize(GAGenome::ANY_SIZE); // let chrom resize if it can
  child.set(0, child.length());
}


// This function gets called a lot (especially for the simple ga) so it must
// be as streamlined as possible.  If the mutation probability is small, then
// we must call random on each bit in the string.  Otherwise, can can simply
// mutate a known number of bits (based on the mutation rate).  We don't check
// to see how many bits we flip, nor do we keep track of which ones got flipped
// so this can result in an actual mutation that is lower than that specified,
// but the bigger the genome and the smaller the mutation probability, the
// better the chance that it will match the desired mutation rate.
//   If nMut is greater than 1, then we round up, so a mutation of 2.2 would
// be 3 mutations, and 2.9 would be 3 as well.  nMut of 3 would be 3 mutations.
int 
GA1DBinaryStringGenome::FlipMutator(GAGenome & c, float pmut)
{
  GA1DBinaryStringGenome &child=DYN_CAST(GA1DBinaryStringGenome &, c);
  register int n, i;
  if(pmut <= 0.0) return(0);

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


// Return a number from 0 to 1 to indicate how similar two genomes are.  For 
// the binary strings we compare bits.  We count the number of bits that are
// the same then divide by the number of bits.  If the genomes are different
// length then we return a -1 to indicate that we cannot calculate the 
// similarity.
//   Normal hamming distance makes use of population information - this is not
// a hamming measure!  This is a similarity measure of two individuals, not
// two individuals relative to the rest of the population.  This comparison is
// independent of the population!  (you can do Hamming measure in the scaling
// object)
float
GA1DBinaryStringGenome::BitComparator(const GAGenome& a, const GAGenome& b){
  const GA1DBinaryStringGenome &sis=DYN_CAST(const GA1DBinaryStringGenome&, a);
  const GA1DBinaryStringGenome &bro=DYN_CAST(const GA1DBinaryStringGenome&, 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();
}














// 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.  This operator can be 
// used on genomes of different lengths, but the crossover is truncated to the
// shorter of the parents and child.
int
GA1DBinaryStringGenome::
UniformCrossover(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() &&