ga1darraygenome.cpp

遗传算法工具箱C++

// $Header$
/* ----------------------------------------------------------------------------
  array1.C
  mbwall 25feb95
  Copyright (c) 1995 Massachusetts Institute of Technology
                     all rights reserved

 DESCRIPTION:
  Source file for the 1D array genome.
---------------------------------------------------------------------------- */
#ifndef _ga_array1_C_
#define _ga_array1_C_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "garandom.h"
#include "GA1DArrayGenome.h"
#include "GAMask.h"

template <class T> int 
GA1DArrayIsHole(const GA1DArrayGenome<T>&, const GA1DArrayGenome<T>&,
		int, int, int);


/* ----------------------------------------------------------------------------
1DArrayGenome
---------------------------------------------------------------------------- */
template <class T> const char *
GA1DArrayGenome<T>::className() const {return "GA1DArrayGenome";}
template <class T> int
GA1DArrayGenome<T>::classID() const {return GAID::ArrayGenome;}

// 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).
// Besides, we default to the no-initialization initializer by calling the
// default genome constructor.
template <class T> 
GA1DArrayGenome<T>::
GA1DArrayGenome(unsigned int length, GAGenome::Evaluator f, void * u) :
GAArray<T>(length),
GAGenome(DEFAULT_1DARRAY_INITIALIZER, 
	 DEFAULT_1DARRAY_MUTATOR,
	 DEFAULT_1DARRAY_COMPARATOR) {
  evaluator(f);
  userData(u);
  nx=minX=maxX=length;
  crossover(DEFAULT_1DARRAY_CROSSOVER);
}


// This is the copy initializer.  We set everything to the default values, then
// copy the original.  The Array creator takes care of zeroing the data.
template <class T> 
GA1DArrayGenome<T>::
GA1DArrayGenome(const GA1DArrayGenome<T> & orig) : 
GAArray<T>(orig.sz), GAGenome() {
  GA1DArrayGenome<T>::copy(orig);
}


// Delete whatever we own.
template <class T>
GA1DArrayGenome<T>::~GA1DArrayGenome() { }


// 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 Array takes care of the resize in its copy method.
template <class T> void
GA1DArrayGenome<T>::copy(const GAGenome & orig){
  if(&orig == this) return;
  const GA1DArrayGenome<T>* c = DYN_CAST(const GA1DArrayGenome<T>*, &orig);
  if(c) {
    GAGenome::copy(*c);
    GAArray<T>::copy(*c);
    nx = c->nx; minX = c->minX; maxX = c->maxX;
  }
}


template <class T> GAGenome *
GA1DArrayGenome<T>::clone(GAGenome::CloneMethod flag) const {
  GA1DArrayGenome<T> *cpy = new GA1DArrayGenome<T>(nx);
  if(flag == CONTENTS){ 
    cpy->copy(*this);
  }
  else{
    cpy->GAGenome::copy(*this);
    cpy->maxX = maxX; cpy->minX = minX;
  }
  return cpy;
}


//   Resize the genome.
//   A negative value for the length means that we should randomly set the
// length of the genome (if the resize behaviour is resizeable).  If
// someone tries to randomly set the length and the resize behaviour is fixed
// length, then we don't do anything.
//   We pay attention to the values of minX and maxX - they determine what kind
// of resizing we are allowed to do.  If a resize is requested with a length
// less than the min length specified by the behaviour, we set the minimum 
// to the length.  If the length is longer than the max length specified by
// the behaviour, we set the max value to the length.
//   We return the total size (in bits) of the genome after resize. 
//   We don't do anything to the new contents!
template <class T> int
GA1DArrayGenome<T>::resize(int len)
{
  if(len == STA_CAST(int,nx)) return nx;

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

  nx = GAArray<T>::size(len);
  _evaluated = gaFalse;
  return this->sz;
}


#ifdef GALIB_USE_STREAMS
// We don't define this one apriori.  Do it in a specialization.
template <class T> int
GA1DArrayGenome<T>::read(STD_ISTREAM &) {
  GAErr(GA_LOC, className(), "read", gaErrOpUndef);
  return 1;
}


// When we write the data to a stream we do it with spaces between elements.
// Also, there is no newline at the end of the stream of digits.
template <class T> int
GA1DArrayGenome<T>::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.
template <class T> int
GA1DArrayGenome<T>::
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) GA1DArrayGenome<T>::resize(upper);
  if(nx < lower) GA1DArrayGenome<T>::resize(lower);
  return resizeBehaviour();
}

template <class T> int
GA1DArrayGenome<T>::resizeBehaviour() const {
  int val = maxX;
  if(maxX == minX) val = FIXED_SIZE;
  return val;
}

template <class T> int 
GA1DArrayGenome<T>::equal(const GAGenome & c) const {
  const GA1DArrayGenome<T> & b = DYN_CAST(const GA1DArrayGenome<T> &, c);
  return((this == &c) ? 1 : ((nx != b.nx) ? 0 : GAArray<T>::equal(b,0,0,nx)));
}









/* ----------------------------------------------------------------------------
1DArrayAlleleGenome

  These genomes contain an allele set.  When we create a new genome, it owns
its own, independent allele set.  If we clone a new genome, the new one gets a
link to our allele set (so we don't end up with zillions of allele sets).  Same
is true for the copy constructor.
  The array may have a single allele set or an array of allele sets, depending
on which creator was called.  Either way, the allele set cannot be changed 
once the array is created.
---------------------------------------------------------------------------- */
template <class T> const char *
GA1DArrayAlleleGenome<T>::className() const {return "GA1DArrayAlleleGenome";}
template <class T> int
GA1DArrayAlleleGenome<T>::classID() const {return GAID::ArrayAlleleGenome;}

template <class T> 
GA1DArrayAlleleGenome<T>::
GA1DArrayAlleleGenome(unsigned int length, const GAAlleleSet<T> & s,
		      GAGenome::Evaluator f, void * u) :
GA1DArrayGenome<T>(length, f, u){
  naset = 1;
  aset = new GAAlleleSet<T>[1];
  aset[0] = s;

  initializer(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_INITIALIZER);
  mutator(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_MUTATOR);
  comparator(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_COMPARATOR);
  crossover(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_CROSSOVER);
}

template <class T> 
GA1DArrayAlleleGenome<T>::
GA1DArrayAlleleGenome(const GAAlleleSetArray<T> & sa,
		      GAGenome::Evaluator f, void * u) :
GA1DArrayGenome<T>(sa.size(), f, u) {
  naset = sa.size();
  aset = new GAAlleleSet<T>[naset];
  for(int i=0; i<naset; i++)
    aset[i] = sa.set(i);

  initializer(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_INITIALIZER);
  mutator(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_MUTATOR);
  comparator(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_COMPARATOR);
  crossover(GA1DArrayAlleleGenome<T>::DEFAULT_1DARRAY_ALLELE_CROSSOVER);
}


// The copy constructor creates a new genome whose allele set refers to the
// original's allele set.
template <class T> 
GA1DArrayAlleleGenome<T>::
GA1DArrayAlleleGenome(const GA1DArrayAlleleGenome<T>& orig) : 
GA1DArrayGenome<T>(orig.sz) {
  naset = 0;
  aset = (GAAlleleSet<T>*)0;
  GA1DArrayAlleleGenome<T>::copy(orig);
}


// Delete the allele set
template <class T>
GA1DArrayAlleleGenome<T>::~GA1DArrayAlleleGenome(){
  delete [] aset;
}


// This implementation of clone does not make use of the contents/attributes
// capability because this whole interface isn't quite right yet...  Just 
// clone the entire thing, contents and all.
template <class T> GAGenome *
GA1DArrayAlleleGenome<T>::clone(GAGenome::CloneMethod) const {
  return new GA1DArrayAlleleGenome<T>(*this);
}


template <class T> void 
GA1DArrayAlleleGenome<T>::copy(const GAGenome& orig){
  if(&orig == this) return;
  const GA1DArrayAlleleGenome<T> * c = 
    DYN_CAST(const GA1DArrayAlleleGenome<T>*, &orig);
  if(c) {
    GA1DArrayGenome<T>::copy(*c);
    if(naset != c->naset){
      delete [] aset;
      naset = c->naset;
      aset = new GAAlleleSet<T>[naset];
    }
    for(int i=0; i<naset; i++)
      aset[i].link(c->aset[i]);
  }
}


// If we resize to a larger length then we need to set the contents to a valid
// value (ie one of our alleles).
template <class T> int
GA1DArrayAlleleGenome<T>::resize(int len){
  unsigned int oldx = this->nx;
  GA1DArrayGenome<T>::resize(len);
  if(this->nx > oldx){
    for(unsigned int i=oldx; i<this->nx; i++)
      this->a[i] = aset[i % naset].allele();
  }
  return len;
}



// Define these so they can easily be specialized as needed.
#ifdef GALIB_USE_STREAMS
template <class T> int
GA1DArrayAlleleGenome<T>::read(STD_ISTREAM& is){
  return GA1DArrayGenome<T>::read(is);
}

template <class T> int
GA1DArrayAlleleGenome<T>::write(STD_OSTREAM& os) const {
  return GA1DArrayGenome<T>::write(os);
}
#endif

template <class T> int
GA1DArrayAlleleGenome<T>::equal(const GAGenome & c) const {
  return GA1DArrayGenome<T>::equal(c);
}











/* ----------------------------------------------------------------------------
   Operator definitions
---------------------------------------------------------------------------- */
// The random initializer sets the elements of the array based on the alleles
// set.  We choose randomly the allele for each element.
template <class ARRAY_TYPE> void 
GA1DArrayAlleleGenome<ARRAY_TYPE>::UniformInitializer(GAGenome & c)
{
  GA1DArrayAlleleGenome<ARRAY_TYPE> &child=
    DYN_CAST(GA1DArrayAlleleGenome<ARRAY_TYPE> &, c);
  child.resize(GAGenome::ANY_SIZE); // let chrom resize if it can
  for(int i=child.length()-1; i>=0; i--)
    child.gene(i, child.alleleset(i).allele());
}


// Random initializer for order-based genome.  Loop through the genome
// and assign each element the next allele in the allele set.  Once each
// element has been initialized, scramble the contents by swapping elements.
// This assumes that there is only one allele set for the array.
template <class ARRAY_TYPE> void 
GA1DArrayAlleleGenome<ARRAY_TYPE>::OrderedInitializer(GAGenome & c)
{
  GA1DArrayAlleleGenome<ARRAY_TYPE> &child=
    DYN_CAST(GA1DArrayAlleleGenome<ARRAY_TYPE> &, c);
  child.resize(GAGenome::ANY_SIZE); // let chrom resize if it can
  int length = child.length()-1;
  int n=0;
  int i;
  for(i=length; i>=0; i--){
    child.gene(i, child.alleleset().allele(n++));
    if(n >= child.alleleset().size()) n = 0;
  }
  for(i=length; i>=0; i--)
    child.swap(i, GARandomInt(0, length));
}


// Randomly pick elements in the array then set the element to any of the 
// alleles in the allele set for this genome.  This will work for any number
// of allele sets for a given array.
template <class ARRAY_TYPE> int 
GA1DArrayAlleleGenome<ARRAY_TYPE>::FlipMutator(GAGenome & c, float pmut)
{
  GA1DArrayAlleleGenome<ARRAY_TYPE> &child=
    DYN_CAST(GA1DArrayAlleleGenome<ARRAY_TYPE> &, 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--){