gplib_entity.cpp

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

// *****************
// GPLIB_entity.cpp
// EntityParent class member functions
// 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;

// Breed two entities by genetic crossover
void GPLIB_EntityParent::GenerateOffspring(GPLIB_EntityParent *ent1, GPLIB_EntityParent *ent2) {
  int c1,c2,l[2],pick,split1,split2,n;

  // Reset the genome
  genome.clear();

  // Work out where to merge the two gene sequences together
  c1 = Random((int)ent1->genome.size());
  c2 = Random((int)ent2->genome.size());

  // Get the genome sections spanning the crossover points
  split1 = ent1->SplitGenome(c1);
  split2 = ent2->SplitGenome(c2);

  // Replace subtree of one parent with subtree of other parent
  // Pick the shortest subtree (to minimise genome length explosion)
  l[0] = c1 + (split2-c2) + ((int)ent1->genome.size() - split1);
  l[1] = c2 + (split1-c1) + ((int)ent2->genome.size() - split2);

  // Pick a parent at random, but if the chosen child would have a long genome string
  // and the other wouldn't then swap choice
  pick = Random(2);
  if (l[pick] >= GPLIB_IdealMaxLength && l[1-pick]<l[pick]) pick = 1-pick;

  // Setup the new child genome
  if (pick==0) {
    for (n=0;n<c1;n++) genome.push_back(ent1->genome[n]);
    for (n=0;n<(split2 - c2);n++) genome.push_back(ent2->genome[n+c2]);
    for (n=0;n<((int)ent1->genome.size() - split1);n++) genome.push_back(ent1->genome[n+split1]);
  }
  else {
    for (n=0;n<c2;n++) genome.push_back(ent2->genome[n]);
    for (n=0;n<(split1 - c1);n++) genome.push_back(ent1->genome[n+c1]);
    for (n=0;n<((int)ent2->genome.size() - split2);n++) genome.push_back(ent2->genome[n+split2]);
  }

  // Check for mutations
  if (Random(100) < GPLIB_Env->MutateChance) Mutate();
}

// Generate a mutant entity based on an existing genome
void GPLIB_EntityParent::Mutate(void) {
  int type,pos,prog,newf,end,n;
  GPLIB_Entity entTmp;

  // Work out what kind of edit we're doing
  type = Random(GPLIB_Env->PermChance + GPLIB_Env->EditChance + GPLIB_Env->FlipChance + GPLIB_Env->SwapChance + GPLIB_Env->SubstChance);

  // Find the location
  pos = Random((int)genome.size());

  // If the chosen location is a value terminal then
  // there is a chance of a simple value mutation
  if (!GPLIB_IsFunc(genome[pos].func) && Random(100)>GPLIB_Env->ValueMutate) {
    ValueMutation(pos);
    return;
  }

  // Substitution (replace a node with a new random subtree)
  if (type < GPLIB_Env->SubstChance) {
    // If the genome is already too long then quit
    if ((int)genome.size() >= GPLIB_IdealMaxLength) return;
    end = SplitGenome(pos);
    entTmp.GenerateRandomSubtree();
    for (n=end;n<(int)genome.size();n++) entTmp.genome.push_back(genome[n]);
    genome.erase(genome.begin()+pos,genome.end());
    for (n=0;n<(int)entTmp.genome.size();n++) genome.push_back(entTmp.genome[n]);
    return;
  }
  type -= GPLIB_Env->SubstChance;

  // Permutation (swap over the operands of a function node)
  if (type < GPLIB_Env->PermChance) {
    prog = genome[pos].func;
    if (GPLIB_IsFunc(prog) && GPLIB_Env->Functions[prog]->GetNP() > 1) SwapSubtrees(pos);
    return;
  }
  type -= GPLIB_Env->PermChance;

  // Edit (prune out redundant genome information).  Applies to whole genome.
  if (type < GPLIB_Env->EditChance) {
    EditGenome();
    return;
  }
  type -= GPLIB_Env->EditChance;

  // Swap a randomly chosen node with another of the same parameter count
  if (type < GPLIB_Env->SwapChance) {
    prog = genome[pos].func;
    // Deal with value terminal generation
    if (!GPLIB_IsFunc(prog) || (GPLIB_Env->Functions[prog]->GetNP()==0 && (Random(100) >= GPLIB_LEAF_NODE_FUNC))) {
      // Make an integer / floating point value leaf?
      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) {
          genome[pos].func = GPLIB_FLeaf;
          // If the leaf is already a value then just swap the type.  Otherwise, generate a new one.
          if (prog != GPLIB_ILeaf) genome[pos].value = FRandom(GPLIB_LEAF_NODE_MAX - GPLIB_LEAF_NODE_MIN) + (float)GPLIB_LEAF_NODE_MIN;
        }
        // Add an integer leaf
        else {
          genome[pos].func = GPLIB_ILeaf;
          // If the leaf is already a value then just swap the type.  Otherwise, generate a new one.
          if (prog != GPLIB_FLeaf) genome[pos].value = (float)(Random(1 + GPLIB_LEAF_NODE_MAX - GPLIB_LEAF_NODE_MIN) + GPLIB_LEAF_NODE_MIN);
        }
      }
      // Otherwise add in a parameter
      else {
        genome[pos].func = -(1+Random(GPLIB_Env->CountVariables()));
      }
    }
    else {
      newf = Random((int)GPLIB_Env->FuncByNParam[GPLIB_Env->Functions[prog]->GetNP()].size());
      genome[pos].func = GPLIB_Env->FuncByNParam[GPLIB_Env->Functions[prog]->GetNP()][newf];
    }
    return;
  }
  type -= GPLIB_Env->SwapChance;

  // Test for two adjacent functions of identical parameter count.  Flip them.
  if (type < GPLIB_Env->FlipChance) {
    CheckPermute(pos);
    return;
  }
  type -= GPLIB_Env->FlipChance;

  // Add more mutations here
}

// Prune out unwanted stuff from the genome
void GPLIB_EntityParent::EditGenome(void) {
  int n=0,prog,edit;
  float val;

  // Loop through source genome
  while (0 && n<(int)genome.size()) {
    prog = genome[n].func;
    if (!GPLIB_IsFunc(prog)) {n++;continue;}
    edit = GPLIB_Env->Functions[prog]->EditCheck(this,n);
    switch(edit) {
      case GPLIB_NOP:
        break;
      case GPLIB_SNIP:
        SnipSubTree(n);
        genome[n].func  = GPLIB_FLeaf;
        genome[n].value = 0.0f;
        break;
      case GPLIB_SIMPLIFY:
        val = GPLIB_Env->Functions[prog]->Execute(this,n);
        SnipSubTree(n);
        genome[n].func = GPLIB_FLeaf;
        genome[n].value = val;
        break;
      case GPLIB_FIRST:
        ReplaceWithSubTree(n,1);
        break;
      case GPLIB_SECOND:
        ReplaceWithSubTree(n,2);
        break;
      case GPLIB_THIRD:
        ReplaceWithSubTree(n,3);
        break;
      case GPLIB_FOURTH:
        ReplaceWithSubTree(n,4);
        break;
        // Replace this tree with a sole function call
      default:
        if (edit<0) {
          fprintf(stderr,"GPLIB Error : Illegal Edit (%d)\n",edit);
          fscanf(stdin,"\n");
          exit(0);
        }
        SnipSubTree(n);
        genome[n].func  = edit;
        genome[n].value = 0.0f;
        break;
    }
    n++;
  }
}

// Swap genome subtrees starting from this position
// Arbitrary number of subtrees handled (<=10)
void GPLIB_EntityParent::SwapSubtrees(int pos) {
  int prog,np,level=1,swap[10],used[10],treeno,count,n,nodepos[10],length,l;  
  GPLIB_Node temp[GPLIB_MaxGenome];

  prog = genome[pos].func;
  if (!GPLIB_IsFunc(prog)) np = 0;
  else np = GPLIB_Env->Functions[prog]->GetNP();

  if (np<2) return;

  // Work out the order of the new trees
  if (np > 10) {
    fprintf(stderr,"GPLIB Error : Error in SwapSubTrees (Prog %d, NP %d)!\n",prog,np);
    fscanf(stdin,"\n");
    exit(0);
  } 

  for(n=0;n<np;n++) used[n]=0;
  count = 0;

  while (count<np) {
    do {      
      swap[count] = Random(np);
    } while (used[swap[count]]);
    used[swap[count++]] = 1;
  }

  // Find the subtrees
  count=0;
  treeno = 1;
  nodepos[0] = 0;
  while (treeno<=np) {
    temp[count] = genome[count+pos+1];
    prog = genome[count+pos+1].func;
    level--;
    if (GPLIB_IsFunc(prog)) level += GPLIB_Env->Functions[prog]->GetNP();
    if (level == 0) {
      level = 1;
      if (treeno<np) {
        nodepos[treeno] = count+1;
      }
      treeno++;
    }
    count++;
  }
  length = count;

  // Write out the new sequence into the old genome
  treeno=0;
  count=0;
  l=pos+1;
  level = 1;
  do { 
    genome[l] = temp[(nodepos[swap[treeno]])+count];
    prog = genome[l].func;
    level--;
    if (GPLIB_IsFunc(prog)) level += GPLIB_Env->Functions[prog]->GetNP();
    if (level == 0){
      level = 1;
      count = 0;
      treeno++;
    }
    else count++;
    l++;
  } while (treeno<np);
}

// Execute the code tree corresponding to this entity's genome.
// Pass the entity itself and the remainder of the genome as parameters
float GPLIB_EntityParent::RunEntity() {
  int prog;
  prog = genome[0].func;
  if (!GPLIB_IsFunc(prog)) {
    if (prog == GPLIB_ILeaf || prog == GPLIB_FLeaf) return genome[0].value;
    else return GPLIB_Env->GetXVal(-(prog+1),GPLIB_Env->GetCurrentDatum());
  }
  else return GPLIB_Env->Functions[prog]->Execute(this,0);
}

// Snip out the sub-tree starting at the given point, retaining only
// the root node
void GPLIB_EntityParent::SnipSubTree(int pos) {
  int n,end;

  end = SplitGenome(pos);
  for (n=0;n<((int)genome.size()-end);n++) {
    genome[pos+n+1] = genome[end+n];
  }
}

// Replace the entire tree with only the given sub-tree 
void GPLIB_EntityParent::ReplaceWithSubTree(int pos, int treeno) {
  int n,loc,end,endst;

  end = SplitGenome(pos);
  loc = GetBranchByPos(pos,treeno);
  endst = SplitGenome(loc);
  for (n=0;n<(endst-loc);n++) {
    genome[pos+n] = genome[loc+n];
  }
  for (n=pos+endst-loc;n<(int)genome.size();n++) {
    genome[n] = genome[n+(end-pos)-(endst-loc)];
  }
}

// Check to see if there are two adjacent nodes in the
// genome with an identical parameter count.
// If so then swap them over.
void GPLIB_EntityParent::CheckPermute(int pos) {
  int f1,f2,n1=0,n2=0;
  GPLIB_Node temp;

  // Make sure we're notat the end of the genome
  if (pos >= (int)genome.size()-1) return;

  // Get the details of the two functions
  f1 = genome[pos].func;
  f2 = genome[pos+1].func;
  if (GPLIB_IsFunc(f1)) n1 = GPLIB_Env->Functions[f1]->GetNP();
  if (GPLIB_IsFunc(f2)) n2 = GPLIB_Env->Functions[f2]->GetNP();

  // Check these two functions accept the same number of parameters
  if (n1 != n2) return;

  // Do the swap
  temp = genome[pos];
  genome[pos] = genome[pos+1];
  genome[pos+1] = temp;
}

// Mutate an integer/floating point value, or the variable ID
void GPLIB_EntityParent::ValueMutation(int pos) {
  float d,inv;

  // Round to nearest integer if close
  if (genome[pos].func == GPLIB_FLeaf) {
    d = GPLIB_RoundFloat(genome[pos].value);
    d = (float)fabs(d - genome[pos].value);
    if (d < GPLIB_Env->RoundError) {
      genome[pos].value = GPLIB_RoundFloat(genome[pos].value);
      if (Random(2) == 0) genome[pos].func = GPLIB_ILeaf;
      return;
    }
  }

  // Floating point value
  if (genome[pos].func == GPLIB_FLeaf) {   
    // Check for inverses
    inv = 1.0f / genome[pos].value;
    d = (float)fabs(GPLIB_RoundFloat(inv) - inv);
    if (d < GPLIB_Env->RoundError) {genome[pos].value = 1.0f/GPLIB_RoundFloat(inv);return;}

    // Large change
    if (Random(100) < GPLIB_Env->TuneLarge) genome[pos].value *= (1.0f+GPLIB_CauchyRandom(0.1f));
    // Small change
    else genome[pos].value *= (1.0f+GPLIB_CauchyRandom(0.01f));
  }

  // Integer value
  else if (genome[pos].func == GPLIB_FLeaf) {
    // Large change
    if (Random(100) < GPLIB_Env->TuneLarge) genome[pos].value = GPLIB_RoundFloat(genome[pos].value * (1.0f + GPLIB_CauchyRandom(0.1f)));
    // Small change
    else genome[pos].value = GPLIB_RoundFloat(genome[pos].value * (1.0f + GPLIB_CauchyRandom(0.01f)));
  }

  // Alter variable number
  else {
    genome[pos].func = -(1+Random(GPLIB_Env->CountVariables()));
  }
}