gp.h

用C++编写的遗传算法

// These definitions are for the different types of creation method
// available to the genetic programming system and are set by the user.
enum GPCreationType {
  // variable tree to maxdepth creation
  GPVariable=0,
  // all branches go to maxdepth creation
  GPGrow,
  // half and half of the the two types shown below. This is the
  // creation method of Koza...
  GPRampedHalf,
  GPRampedVariable,
  // grow branches equal to max depth ofcreation with this
  // parameter being increased as we move through population
  GPRampedGrow,
  // Whatever the user thinks. We haven't implemented this, but the
  // user can in one of his inherited classes
  GPUserDefinedCreation};

// Selection types: tournament selection or probabilistic selection.
enum GPSelectionType {
  GPProbabilisticSelection=0,
  GPTournamentSelection,
  GPUserDefinedSelection};



class GPVariables : public GPObject
{
public:
  GPVariables ();
  ~GPVariables () {};

  GPVariables (const GPVariables& gpo);
  virtual GPObject& duplicate () { return *(new GPVariables(*this)); }

  int PopulationSize,
    NumberOfGenerations,
    CreationType,
    MaximumDepthForCreation,
    MaximumDepthForCrossover,
    SelectionType,
    TournamentSize,
    DemeticGrouping,
    DemeSize,
    AddBestToNewPopulation,
    SteadyState;
  double CrossoverProbability, CreationProbability,
    SwapMutationProbability, ShrinkMutationProbability,
    DemeticMigProbability;

  virtual void printOn (ostream& os);

  virtual int isA () { return GPVariablesID; }
  virtual char* load (istream& is);
  virtual void save (ostream& os);
  virtual GPObject* createObject() { return new GPVariables; }
};



class GPGene : public GPContainer
{
public:
  GPGene () { node=0; }
  GPGene (GPNode& gpo)
    : node(&gpo), GPContainer(gpo.arguments()) {}

  GPGene (const GPGene& gpo)
    : GPContainer (gpo) { node=gpo.node; }
  virtual GPObject& duplicate () { return *(new GPGene(*this)); }

  virtual GPGene* createChild (GPNode& gpo) {
    return new GPGene (gpo); }

  virtual int isA () { return GPGeneID; }
  virtual char* load (istream& is);
  virtual void save (ostream& os);
  void resolveNodeValues (GPNodeSet& ns);
  virtual GPObject* createObject() { return new GPGene; }

  virtual void printOn (ostream& os);

  virtual int isFunction () { return node->isFunction (); }
  virtual int isTerminal () { return node->isTerminal (); }

  GPNode& geneNode () { return *node; }
  GPGene* NthChild (int n) {
    return (GPGene*) GPContainer::Nth (n); }
  GPGene** findNthNode (GPGene** rootPtr, int findFunction,
			int &iLengthCount);

  virtual GPGene** choose (GPGene** rootPtr);

  int countFunctions ();
  GPGene** chooseFunctionNode (GPGene** rootPtr);

  virtual int length ();
  virtual int depth (int depthSoFar=1);

  virtual void create (enum GPCreationType ctype, int allowabledepth, 
		       GPNodeSet& ns);

  friend int operator == (GPGene& pg1, GPGene& pg2);
  virtual int compare (GPGene& g);

  friend GP;

  GPGene& operator = (GPGene& gpo) {
    GPExitSystem ("operator =", "Assignment operator not yet implemented"); 
    return gpo; }

protected:
  // Pointer to Function or Terminal.  It's a good solution (I think)
  // not to have any specific values in this class, but rather
  // pointers to the functions.  You can get all the information you
  // need from them... On the other hand, if we load a gene, we
  // load/save only the node value.  Another function has to be called
  // after the load process to convert this value back to a pointer
  union
  {
    GPNode* node;
    int nodeValue;
  };
};



class GP : public GPContainer
{
public:
  GP () { fitnessValid=0; GPlength=0; GPdepth=0; }
  GP (int trees) : GPContainer (trees) { fitnessValid=0; 
    GPlength=0; GPdepth=0; }

  GP (const GP& gpo) : GPContainer(gpo) { stdFitness=gpo.stdFitness; 
    fitnessValid=gpo.fitnessValid; GPlength=gpo.GPlength; 
    GPdepth=gpo.GPdepth; }
  virtual GPObject& duplicate () { return *(new GP(*this)); }

  virtual GPGene* createGene (GPNode& gpo) {
    return new GPGene (gpo); }

  virtual void printOn (ostream& os);

  GPGene* NthGene (int n) { return (GPGene*) GPContainer::Nth(n); }

  double getFitness () { return stdFitness; }
  virtual int length () { return GPlength; }
  virtual int depth () { return GPdepth; }
  virtual void calcLength ();
  virtual void calcDepth ();

  virtual int compare (GP& gp);
  virtual void create (enum GPCreationType ctype, int allowabledepth, 
		       GPAdfNodeSet& adfNs);

  void shrinkMutation ();
  void swapMutation (GPAdfNodeSet& adfNs);
  virtual void mutate (GPVariables& GPVar, GPAdfNodeSet& adfNs);
  virtual GPContainer& cross (GPContainer* parents, 
			      int maxdepthforcrossover);
  virtual void evaluate ();

  virtual int isA () { return GPID; }
  virtual char* load (istream& is);
  virtual void save (ostream& os);
  void resolveNodeValues (GPAdfNodeSet& adfNs);
  virtual GPObject* createObject() { return new GP; }

  friend GPPopulation;

  GP& operator = (GP& gpo) {
    GPExitSystem ("operator =", "Assignment operator not yet implemented"); 
    return gpo; }

protected:
  // The standardized fitness (positive numbers, and 0.0 is best) and
  // a flag whether the fitness of this GP-object is already
  // calculated or not. The flag must be set to 0 by any operation
  // that changes the GP (for example the crossover and mutation), but
  // not by reproduction. This can save us a lot of time.
  int fitnessValid;
  double stdFitness;

  // Length and depth of GP
  int GPlength, GPdepth;
};



// A structure to simplify the parameter exchange for all the
// selection functions.  It holds the range for which the selection
// has to take place, and a flag that determines whether this is the
// first selection of that particular deme.  This is used to speed up
// the selection process for the probablistic selection.
struct GPPopulationRange
{
  int startIx, endIx;
  int firstSelectionPerDeme;
};



class GPPopulation : public GPContainer
{
public:
  GPPopulation () {}
  GPPopulation (GPVariables& GPVar_, GPAdfNodeSet& adfNs_) : 
    adfNs(&adfNs_), GPVar(GPVar_) {}

  GPPopulation (const GPPopulation& gpo) : GPContainer(gpo), adfNs(gpo.adfNs)
    { GPVar=gpo.GPVar; avgFitness=gpo.avgFitness; 
    avgLength=gpo.avgLength; avgDepth=gpo.avgDepth; }
  virtual GPObject& duplicate () { return *(new GPPopulation(*this)); }

  virtual void printOn (ostream& os);

  GP* NthGP (int n) { return (GP*) GPContainer::Nth (n); }

  virtual int checkForValidCreation (GP& gpo);
  virtual void create ();
  virtual GP* createGP (int numOfTrees) { return new GP (numOfTrees); }

  double totalFitness ();
  long totalLength ();
  long totalDepth ();

  virtual void tournamentSelection (int *selection, int numToSelect,
				    int selectWorst, 
				    GPPopulationRange& range);
  virtual void probabilisticSelection (int *selection, int numToSelect, 
				       int selectWorst, 
				       GPPopulationRange& range);
  virtual void selectIndices (int *selection, int numToSelect, 
			      int selectWorst, GPPopulationRange& range);
  virtual GPContainer* select (int numToSelect, GPPopulationRange& range);
  virtual GPContainer* selectParents (GPPopulationRange& range);
  virtual void calculateStatistics ();
  virtual void evaluate();

  virtual void createGenerationReport (int printLegend, int generation,
				       ostream& fout, ostream& bout);
  GPContainer* evolution (GPPopulationRange& range);
  virtual void generate (GPPopulation& newPop);
  virtual void demeticMigration ();

  virtual int isA () { return GPID; }
  virtual char* load (istream& is);
  virtual void save (ostream& os);
  void setNodeSets (GPAdfNodeSet& adfNs_);
  virtual GPObject* createObject() { return new GPPopulation; }

  // Index to the best and worst of a population. Only valid after a
  // call to calculateStatistics (done by evaluate())
  int bestOfPopulation, worstOfPopulation;

  GPPopulation& operator = (GPPopulation& gpo) {
    GPExitSystem ("operator =", "Assignment operator not yet implemented"); 
    return gpo; }

protected:
  // We have to save the function and terminal sets here, because we
  // need them later
  GPAdfNodeSet* adfNs;

  // These are important variables used for the configuration of the
  // whole GP system
  GPVariables GPVar;

  // Average values: some useful statistics. Calculated by
  // calculateStatistics() (which is called by evaluate())
  double avgFitness, avgLength, avgDepth;

private:
  // These variables are needed only for the probablistic selection
  // method and are calculated anew for every deme or population.  So
  // they need not to be load/saved.  We save the summed inverse
  // fitness and the summed fitness of the deme/population in a static
  // variable and determine whether we have to calculate it again each
  // call depending on variable firstCallPerDeme (parameter to the
  // selection function).
  double invSumFitness;
  double sumFitness;

  int checkForDiversity (GP& gp);
};



#endif