gplib_tree.cpp

遗传规划算法 智能算法：遗传规划

// *****************
// GPLIB_tree.cpp
// Tree operations
// Colin Frayn
// December 2006
// *****************

// GPLib v2.0, A Genetic programming Library for C++
// Copyright (C) 2006  Colin Frayn
// 
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.


#include "GPLib.h"

extern GPLIB_Environment *GPLIB_Env;
GPLIB_EntityParent *GPLIB_CurrentEntity;

// Get the specified sub-branch from a genome without removal
// and return the location of the start-point
int GPLIB_EntityParent::GetBranchByPos(int start, int pos) {
  int n=start+1,level=1,prog;

  // Split the genome
  while (pos>1) {
    prog = genome[n++].func;
    level--;
    if (GPLIB_IsFunc(prog)) level += GPLIB_Env->Functions[prog]->GetNP();
    if (level == 0) {pos--;level=1;}
  }
  if (pos>1 || n >= (int)genome.size()) {
    fprintf(stderr,"GPLIB Error : Error splitting genome (%d,%d)\n",start,pos);
    GPLIB_Env->PrintGenome(genome,stderr);
    fscanf(stdin,"\n");
    exit(0);
  }
  return n;
}


// Generate a random subtree and return the length
void GPLIB_EntityParent::GenerateRandomSubtree(void) {
  int level=1,prog,n,count=0;
  float val=0.0f;
  GPLIB_Node nd;

  genome.clear();

  do {
    val = 0.0f;
    // This subtree is getting too large - terminate it with a leaf
    if ((count+level >= GPLIB_MaxSubTree) || (Random(100) < GPLIB_LEAF_NODE_PROB)) {
      if (GPLIB_Env->FuncByNParam[0].empty() || Random(100) >= GPLIB_LEAF_NODE_FUNC) {
        n = Random(100);
        // Is this a value leaf?
        if (n < (GPLIB_LEAF_NODE_FLOAT+GPLIB_LEAF_NODE_INT)) {
          // Add a float leaf
          if (n < GPLIB_LEAF_NODE_FLOAT) {
            prog = GPLIB_FLeaf;
            // If the leaf is already a value then just swap the type.  Otherwise, generate a new one.
            val = FRandom(GPLIB_LEAF_NODE_MAX - GPLIB_LEAF_NODE_MIN) + (float)GPLIB_LEAF_NODE_MIN;
          }
          // Add an integer leaf
          else {
            prog = GPLIB_ILeaf;
            // If the leaf is already a value then just swap the type.  Otherwise, generate a new one.
            val = (float)(Random(1 + GPLIB_LEAF_NODE_MAX - GPLIB_LEAF_NODE_MIN) + GPLIB_LEAF_NODE_MIN);
          }
        }
        // Otherwise add in a parameter
        else {
          prog = -(1+Random(GPLIB_Env->CountVariables()));
        }
      }
      // Otherwise add a randomly chosen leaf function
      else {
        n = Random(GPLIB_Env->LeafWeight);
        prog=0;
        while (GPLIB_Env->Functions[GPLIB_Env->FuncByNParam[0][prog]]->GetWeight() < n) {
          n -= GPLIB_Env->Functions[GPLIB_Env->FuncByNParam[0][prog++]]->GetWeight();
        }
        prog = GPLIB_Env->FuncByNParam[0][prog];
      }
      level--;
    }
    // Not too deep yet - Generate a random function
    else {
      n = Random(GPLIB_Env->TotalWeight);
      prog=0;
      while (GPLIB_Env->Functions[prog]->GetWeight() < n) {
        n -= GPLIB_Env->Functions[prog++]->GetWeight();
      }
      level += GPLIB_Env->Functions[prog]->GetNP() - 1;
    }
    nd.func = prog;
    nd.value = val;
    genome.push_back(nd);
    count++;
  } while (level>0);
}


// Print out a tree in function readable format
void GPLIB_Environment::PrintGenome(vector <GPLIB_Node> genome, FILE *fp) {
  int n=0,level=0,bracket[GPLIB_MaxGenome],prog;

  fprintf(fp,"(");
  bracket[0] = 1;

  do {
    prog = genome[n].func;  
    if (GPLIB_IsFunc(prog)) { 
      fprintf(fp,"%s",Functions[prog]->Name.c_str());
      if (GPLIB_Env->Functions[prog]->GetNP()>0) {
        fprintf(fp," ");
        level++;
        bracket[level] = Functions[prog]->GetNP();
        fprintf(fp,"(");
      }
    }
    else {
      if (prog == GPLIB_ILeaf) fprintf(fp,"%d",(int)genome[n].value);
      else if (prog == GPLIB_FLeaf) fprintf(fp,"%f",genome[n].value);
      else fprintf(fp,"%s",strVariables[-(prog+1)].c_str());
    }

    if (!GPLIB_IsFunc(prog) || Functions[prog]->GetNP()==0) {
      fprintf(fp,")");
      while (--bracket[level] == 0 && level>0) {
        level--;
        fprintf(fp,")");
      }
      if (level>0 && bracket[level]>0) fprintf(fp,"(");
    }
    n++;
  } while (level>0);
  fprintf(fp,"\n");
}


// Split a genome, finding the end of the subtree starting at the specified point
int GPLIB_EntityParent::SplitGenome(int pos) {
  int level=1,n=pos,prog=GPLIB_FLeaf;

  do {
    prog = genome[n].func;
    n++;
    level--;
    if (GPLIB_IsFunc(prog)) level += GPLIB_Env->Functions[prog]->GetNP();
  } while (level>0);  
  if (n<pos || level<0) {
    fprintf(stderr,"GPLIB Error : Error splitting genome [%d][%d][%d]\n",n,pos,level);
    fscanf(stdin,"\n");
    exit(0);
  }
  return n;
}


// Check a genome is legal
// Currently not used
void GPLIB_Environment::CheckGenome(vector<GPLIB_Node> genome, int caller) {
  int prog,level=1,n;
  int length = (int)genome.size();
  string strDebug;

  // Loop through the genome
  for (n=0;n<length;n++) {
    prog = genome[n].func; 
    if (prog == GPLIB_ILeaf) strDebug.push_back('I');
    else if (prog == GPLIB_FLeaf) strDebug.push_back('F');
    else strDebug.push_back((char)(prog+48));
    // Illegal function in genome
    if (prog >= (int)Functions.size()) {
      fprintf(stderr,"GPLIB Error : CheckGenome() [1] : Caller=%d, Prog=%d\n",caller,prog);    
      PrintGenome(genome,stderr);
      fprintf(stderr,"%s",strDebug.c_str());
      fscanf(stdin,"\n");
      exit(0);
    }
    // Illegal parameter
    if (prog < 0 && prog != GPLIB_ILeaf && prog != GPLIB_FLeaf && -(prog+1) > CountVariables()) {
      fprintf(stderr,"GPLIB Error : CheckGenome() [2] : Caller=%d, Prog=%d\n",caller,prog);    
      fscanf(stdin,"\n");
      exit(0);
    }
    level--;
    if (GPLIB_IsFunc(prog)) level += Functions[prog]->GetNP();
  }

  // Bracketing error
  if (level != 0) {
    fprintf(stderr,"GPLIB Error : CheckGenome() [3] : Caller=%d, Lev=%d, Len=%d\n",caller,level,length);   
    PrintGenome(genome,stderr);
    fprintf(stderr,"%s",strDebug.c_str());
    fscanf(stdin,"\n");
    exit(0);
  }
}



//  ----- Sort out the function lists -----

// Setup the array of functions
void GPLIB_Environment::SetupFunctions(void) {
  int n,NP;

  // Setup the list of functions so that we have pointers to all the functions
  Functions.clear();
  SetupFunctionArray();

  // Check the functions
  for (n=0;n<(int)Functions.size();n++) {
    if (Functions[n]->GetNP() > GPLIB_MaxParam) {
      fprintf(stderr,"GPLIB Error : Illegal parameter count for function \"%s\" (%d > %d)\n",Functions[n]->Name.c_str(),Functions[n]->GetNP(),GPLIB_MaxParam);
    }
  }

  TotalWeight = LeafWeight = 0;

  // Get the array of parameter counts - do not edit
  for (n=0;n<(int)Functions.size();n++) {
    // Get Number of Parameters
    NP = Functions[n]->GetNP();
    // Get weightings list
    TotalWeight += Functions[n]->GetWeight();
    if (NP == 0) LeafWeight += Functions[n]->GetWeight();
    // Setup FuncByNParam lists
    FuncByNParam[NP].push_back(n);
  }
}


// Execute a function call
float GPLIB_GPFunction::Execute(GPLIB_EntityParent *ent, int pos) {
  int prog;
  GPLIB_CurrentEntity = ent;
  prog = ent->genome[pos].func;
  if (!GPLIB_IsFunc(prog)) {
    fprintf(stderr,"GPLIB Error : (Execute) - Function type is leaf function!\n");
    fscanf(stdin,"\n");
    exit(0);
  }
  return FunctionBody(pos);
}


// Run a sufunction call with the given number
float GPLIB_GPFunction::RunSubFunction(int pos, int PNo) {
  int prog,branch;

  if (PNo > NP || PNo < 1) {
    fprintf(stderr,"GPLIB Error : Illegal RunSubFunction in %s (PNo=%d)\n",Name.c_str(),PNo);
    fscanf(stdin,"\n");
    exit(0);
  }
  branch = GPLIB_CurrentEntity->GetBranchByPos(pos,PNo);
  prog = (GPLIB_CurrentEntity->genome[branch]).func;
  if (GPLIB_IsFunc(prog)) return GPLIB_Env->Functions[prog]->Execute(GPLIB_CurrentEntity,branch);
  if (prog == GPLIB_ILeaf || prog == GPLIB_FLeaf) return (GPLIB_CurrentEntity->genome[branch]).value;
  return GPLIB_Env->GetXVal(-(prog+1),GPLIB_Env->GetCurrentDatum());
}

// Get a function ID given the function's name
int GPLIB_Environment::GetIDByName(string Name) {
  int n;

  for (n=0;n<(int)Functions.size();n++) {
    if (Name == Functions[n]->Name) return n;
  }
  return -1;
}