gplib_main.cpp

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

// *****************
// GPLIB_main.cpp
// Main command structures
// 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"

GPLIB_Environment *GPLIB_Env;

// Constructor, initialisation
GPLIB_Environment::GPLIB_Environment(void) {
  Generation = 1;
  EliteCount = 3;
  TournamentSize = 2;
  SurvivalFract = 15;
  MutantFract = 35;
  WarpedFract = 15;
  RandomFract = 0;
  MutateChance = 5;
  SubstChance = 5;
  PermChance = 7;
  EditChance = 3;
  FlipChance = 4;
  SwapChance = 3;
  ValueMutate = 60;
  TuneLarge = 80;
  RoundError = 0.01f;

  bVerbose = false;
  bPrintProgress = false;

  // -- Setup other stuff

  // Remove buffering from stdout
  setbuf(stdout,NULL);
  Randomise();
  // Welcome the user
  fprintf(stdout,"Welcome to GPLib v%.1f!\n",GPLIB_VER);
  // Setup function list
  SetupFunctions();
  // Set the current environment
  GPLIB_Env = this;
}

// Destructor
GPLIB_Environment::~GPLIB_Environment(void) {
  Entitylist.clear();
  fprintf(stdout,"GPLib Closed Successfully\n");
}

void GPLIB_Environment::Reset(void) {
  int n = (int)Entitylist.size();
  Generation = 1;
  Randomise();
  SetupRandomEntities(n);
  if (bVerbose) fprintf(stderr,"[G] Simulation Reset OK\n");
}

// Setup a new population. Allocate space etc.
void GPLIB_Environment::SetupPopulation(int n) {
  GPLIB_Entity e;
  if (n < 1) {
    fprintf(stderr,"GPLIB Error : Strange entity Count (%d) in SetupPopulation()!\n",n);
    fscanf(stdin,"\n");
    exit(0);
  } 
  SetupRandomEntities(n);
}

// Run this next generation.
void GPLIB_Environment::RunGeneration(void) {

  // Make sure that the population is set up properly
  if (Entitylist.empty()) {
    fprintf(stderr,"GPLIB Error : Calling \"RunGeneration\" with no entities created (population size=0)!  Use \"SetupGeneration(int n)\" first!\n");
    fscanf(stdin,"\n");
    exit(0);
  }
  if (Functions.empty()) {
    fprintf(stderr,"GPLIB Error : Calling \"RunGeneration\" with no function nodes available!  Use \"SetupFunctions()\" first!\n");
    fscanf(stdin,"\n");
    exit(0);
  }

  // Set the global environment
  GPLIB_Env = this;

  // Setup this generation ready to run
  InitialiseGeneration();

  // Calculate the fitness of every individual
  FitnessEvaluation();

  // End of generation
  // Create the next generation by breeding this generation based on fitness
  Breed();

  // Incrememnt the generation counter
  Generation++;
}

// Perform a catastrophe
void GPLIB_Environment::Catastrophe(int frac) {
  if (bVerbose) fprintf(stdout,"[G] Catastrophe (%d%%)\n",frac);
  for (int n=0;n<(int)Entitylist.size();n++) {
    if (Random(100) < frac) {
      Entitylist[n].GenerateRandomSubtree();
    }
  }
}

// Perform an elite consolidation
// Replace weaker members of the population with strongly mutated versions of the top 'num'
void GPLIB_Environment::Consolidate(int num) {
  int source;

  if (bVerbose) fprintf(stdout,"[G] Consolidate (%d)\n",num);

  for (int n=num;n<(int)Entitylist.size();n++) {
    source = Random(num);
    Entitylist[n].CopyFrom(&Entitylist[source]);
    do {
      Entitylist[n].Mutate();
    } while (Random(2));
  }
}

// Setup the initial entitylist randomly
void GPLIB_Environment::SetupRandomEntities(int count) {
  int n;
  GPLIB_Entity e;

  Entitylist.clear();
  Entitylist.reserve(count);

  // Create 'count' random individuals
  for (n=0;n<count;n++) {
    e.GenerateRandomSubtree();
    Entitylist.push_back(e);
  }

  if (bVerbose) fprintf(stdout,"[G] Random population setup OK\n");  
}


// Run the fitness evaluation
void GPLIB_Environment::FitnessEvaluation(void) {
  int n;

  if (bVerbose) fprintf(stdout,"[G] Running   ");

  // Loop though all the entities
  for (n=0;n<(int)Entitylist.size();n++) {

    // Setup this entity
    Entitylist[n].SetScore(0);
    CurrentEntity = n;

    // Print out this entity count
    PrintProgress(n+1);

    // Calculate fitness here
    Entitylist[n].CalculateFitness();

    // Keep track of post-evaluation statistics here
    // (e.g. average score, average length, length tally, etc.)
    PostEvaluationStatistics();
  }

  // Write out the results
  PostRunStatistics();
}


// Print off the progress so far
void GPLIB_Environment::PrintProgress(int done) {
  int percent = (done * 100) / (int)Entitylist.size();
  static int old = -1;

  if (percent == old) return;
  if (percent>10) fprintf(stderr,"\b");
  fprintf(stderr,"\b\b%d%%",percent);
  old = percent;
}

// Get the ID of the best entity in the current population
int GPLIB_Environment::GetBestEntity(void) {
  int best=0;
  for (int n=1;n<(int)Entitylist.size();n++) {
    if (Entitylist[n].GetScore() > Entitylist[best].GetScore()) best = n;
  }
  return best;
}

// Setup the initial entitylist based on an entity file or files
void GPLIB_Environment::SetupEntitiesFromFile(string filename, int how_many) {
  int n,pos=0,level=1,cno,isnum=0,count=0;
  float val;
  FILE *fp;
  GPLIB_Node nd;
  char genome[FILENAME_MAX],fn[64];
  GPLIB_Entity e;

  pos=0;
  level=1;
  count=0;

  if ((fp = fopen(filename.c_str(),"r")) == NULL) {
    fprintf(stderr,"GPLIB Error : Could not open entity file %s\n",filename.c_str());
    fscanf(stdin,"\n");
    exit(0);
  }

  SetupRandomEntities(how_many);

  // Get the genome as a char string
  (void)fgets(genome,sizeof(genome),fp);

  // Parse the genome
  do {
    // Read in junk
    while (genome[pos] == ' ' || genome[pos] == '(' || genome[pos] == ')') pos++;
    cno = 0;
    isnum = 0;
    // Read in function name
    while (genome[pos] != ' ' && genome[pos] != '(' && genome[pos] != ')') {
      if (genome[pos] >= '0' && genome[pos] <= '9') {
        if (isnum==0) isnum=1;
      }
      else if (genome[pos] != '.' && genome[pos] != '-') isnum=-1;
      fn[cno++] = genome[pos++];
    }
    fn[cno] = 0;
    // This is a number
    if (isnum==1) {
      val = (float)atof(fn);
      if (val == (float)GPLIB_RoundFloat(val)) nd.func = GPLIB_ILeaf;
      else nd.func = GPLIB_FLeaf;
      nd.value = val;
      level--;
    } 
    // This is not a number
    else {
      nd.func = GetIDByName(fn);
      if (nd.func == -1) {
        fprintf(stderr,"GPLIB Error : Could not ID function \"%s\" in genome file %s\n",fn,filename.c_str());
        fscanf(stdin,"\n");
        exit(0);
      }
      nd.value = 0.0f;
      level += Functions[nd.func]->GetNP() - 1;
    }
    // Setup the actual genome element in entity number 0
    e.genome.push_back(nd);
    // Keep going until we run out of genome
  } while (level>0);
  if (bVerbose) fprintf(stdout,"[G] Genome file \"%s\" loaded OK\n",filename.c_str());
  fclose(fp);

  // Setup a few mutants based on the loaded entity(ies)
  for (n=0;n<how_many/2;n++) {
    Entitylist[n].CopyFrom(&e);
    Entitylist[n].Mutate();
    if (Random(2) == 0) Entitylist[n].Mutate();
  }

  if (bVerbose) fprintf(stdout,"[G] Entities seeded from file OK\n");  
}

// Get a Cauchy-distributed random number
float GPLIB_CauchyRandom(float radius) {
  double r;

  r = (double)rand() / (double)RAND_MAX;
  r -= 0.5;
  r *= 3.14159265359;
  return radius * (float)tan(r);
}

// Round a floating point number
float GPLIB_RoundFloat(float num) {
  int trunc;
  float res;

  trunc = (int)num;
  res = (float)trunc;
  if (res + 0.5f <= num) res += 1.0f;
  return res;
}

// Is a number a proper number, or a NaN value?
bool GPLIB_NotANumber(float n) {
#ifdef _MSC_VER
  return _isnan(n) ? true : false;
#else
  if (n<0 || n>0 || n==0) return false;
  return true;
#endif
}