source: cpp/f4/geno_f4.cpp @ 100

/*
 *  geno_f4.cpp - f4 genetic operators.
 *
 *  f4genotype - f4 format genotype conversions for FramSticks
 *
 *  Copyright (C) 1999,2000  Adam Rotaru-Varga (adam_rotaru@yahoo.com)
 *  Copyright (C) 2001-2004  Maciej Komosinski
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 */

#include "geno_f4.h"
#include "nonstd.h"
#include "sstring.h"
#include "framsg.h"

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>


#define FIELDSTRUCT Geno_f4

static ParamEntry GENO4param_tab[]=
{
 {"Genetics: f4",1,F4_COUNT+F4_ADD_COUNT,},
 {"f4_mut_add", 0, 0, "Add node", "f 0 100 50", FIELD(prob[F4_ADD]),"mutation: probability of adding a node", },
 {"f4_mut_add_div", 0, 0, "- add division", "f 0 100 20", FIELD(probadd[F4_ADD_DIV]),"add node mutation: probability of adding a division", },
 {"f4_mut_add_conn", 0, 0, "- add connection", "f 0 100 15", FIELD(probadd[F4_ADD_CONN]),"add node mutation: probability of adding a neural connection", },
 {"f4_mut_add_neupar", 0, 0, "- add neuron property", "f 0 100 5", FIELD(probadd[F4_ADD_NEUPAR]),"add node mutation: probability of adding a neuron property/modifier", },
 {"f4_mut_add_rep", 0, 0, "- add repetition", "f 0 100 10",FIELD(probadd[F4_ADD_REP]),"add node mutation: probability of adding a repetition", },
 {"f4_mut_add_simp", 0, 0, "- add simple node", "f 0 100 50",FIELD(probadd[F4_ADD_SIMP]),"add node mutation: probability of adding a random, simple gene", },
 {"f4_mut_del", 0, 0, "Delete node", "f 0 100 20", FIELD(prob[F4_DEL]),"mutation: probability of deleting a node", },
 {"f4_mut_mod", 0, 0, "Modify node", "f 0 100 30", FIELD(prob[F4_MOD]),"mutation: probability of changing a node", },
 {0,},
};

#undef FIELDSTRUCT


Geno_f4::Geno_f4()
{
   supported_format='4';
   par.setParamTab(GENO4param_tab);
   par.select(this);
   par.setDefault();

   mutation_method_names=new char*[F4_COUNT+F4_ADD_COUNT-1];
   int index=0;
   mutation_method_names[index++]="added division";
   mutation_method_names[index++]="added neural connection";
   mutation_method_names[index++]="added neuron property";
   mutation_method_names[index++]="added repetition gene";
   mutation_method_names[index++]="added a simple node";
   mutation_method_names[index++]="deleted a node";
   mutation_method_names[index++]="modified a node";
   if (index!=F4_COUNT+F4_ADD_COUNT-1) FramMessage("Geno_f4","Constructor","Mutation names init error",3);
}

int Geno_f4::ValidateRec(f4_node * geno, int retrycount) const
{
  // ! the genotype is geno->child (not geno) !
  // build from it with repair on

  f4_Cells cells( geno->child, 1);
  cells.simulate();  //we should simulate?!

  // errors not fixed:
  if (GENOPER_OPFAIL == cells.geterror())
  {
    if (cells.geterrorpos() >= 0) return 1+cells.geterrorpos();
    return GENOPER_OPFAIL;
  }
  // errors can be fixed
  if (GENOPER_REPAIR == cells.geterror())
  {
    cells.repairGeno(geno, 1);
    // note: geno might have been fixed
    // check again
    int res2 = GENOPER_OK;
    if (retrycount>0)
      res2 = ValidateRec( geno, retrycount-1 );

    if (res2==GENOPER_OK) return GENOPER_REPAIR;
    return res2;
  }
  // no errors:
  return GENOPER_OK;
}


int Geno_f4::validate(char *& geno)
{
  // convert geno to tree, then try to validate 20 times
  f4_node root;
  if (f4_processrec(geno, 0, &root) || root.childCount()!=1) return GENOPER_OK; // cannot repair
  if (ValidateRec( &root, 20 )==GENOPER_REPAIR) // if repaired, make it back to string
  {
    geno[0]=0;
    root.child->sprintAdj(geno);
  }
  return GENOPER_OK;
}


int Geno_f4::checkValidity(const char * geno)
{
  f4_node root;
  int res = f4_processrec(geno, 0, &root);
  if (res) return res;  // errorpos, >0
  if (root.childCount()!=1) return 1; //earlier: GENOPER_OPFAIL
  f4_Cells cells( root.child, 0);
  cells.simulate();
  if (cells.geterror()==GENOPER_OPFAIL || cells.geterror()==GENOPER_REPAIR)
  {
    if (cells.geterrorpos() >= 0) return 1+cells.geterrorpos();
      else return 1; //earlier: GENOPER_OPFAIL;
  } else return GENOPER_OK;
}


int Geno_f4::MutateOne(f4_node *& g,int &method) const
{
  // ! the genotype is g->child (not g) !

  // codes that can be changed (apart being added/deleted)
  #define MUT_CHAN_CODES "<[#"
  #define ADD_SIMPLE_CODES ",XlLcCrRaAiIsSmMfFwWeEN@|"
  #define REP_MAXCOUNT 19

  f4_node * n1, * n2, * n3, * n4, * n5;
  int i, j;

  // do the mutation
  // pick a random node
  n1 = g->child->randomNode();
  //DB( printf("%c\n", n1->name); )

  switch(roulette(prob,F4_COUNT))
  {
    case F4_ADD:
    {
      // add a node
      switch(method=roulette(probadd,F4_ADD_COUNT))
      {
        case F4_ADD_DIV:
        {
          // add division ('<')
          n3 = n1->parent;
          n3->removeChild(n1);
          n2 = new f4_node('<', n3, n3->pos );
          n2->addChild(n1);
          // new cell is stick or neuron
          // "X>" or "N>"
          double pr = rnd01;
          pr -= 0.5;
          if (pr<0) n3 = new f4_node('X', n2, n2->pos);
          else
          {
            pr -= 0.5;
            if (pr<0)
            {
              // if neuron, make muscle and add a link
              n3 = new f4_node('N', n2, n2->pos);
              if (randomN(2) == 0)
                n4 = new f4_node('|', n3, n2->pos);
              else
                n4 = new f4_node('@', n3, n2->pos);
              n5 = new f4_node('[', n4, n2->pos);
              linkNodeMakeRandom(n5);
            }
          }
          new f4_node('>', n3, n3->pos);
          n1->parent = n2;
          // now with 50% chance swap children
          if (randomN(2) == 0)
          {
            n3 = n2->child;
            n2->child = n2->child2;
            n2->child2 = n3;
          }
        }
        break;
        case F4_ADD_CONN:
        {
          // add link
          n1->parent->removeChild(n1);
          n2 = new f4_node('[', n1->parent, n1->parent->pos);
          linkNodeMakeRandom(n2);
          n2->addChild(n1);
          n1->parent = n2;
        }
        break;
        case F4_ADD_NEUPAR:
        {
          // add neuron modifier
          n1->parent->removeChild(n1);
          n2 = new f4_node(':', n1->parent, n1->parent->pos);
          nparNodeMakeRandom(n2);
          n2->addChild(n1);
          n1->parent = n2;
        }
        break;
        case F4_ADD_REP:
        {
          // add repetition ('#')
          // repeated code (left child) is the original, right child is empty, count is 2
          n3 = n1->parent;
          n3->removeChild(n1);
          n2 = new f4_node('#', n3, n3->pos );
          n2->i1 = 2;
          n2->addChild(n1);
          new f4_node('>', n2, n2->pos);
          n1->parent = n2;
        }
        break;
        case F4_ADD_SIMP:
        {
          // add simple node
          // choose a simple node from ADD_SIMPLE_CODES
          n1->parent->removeChild(n1);
          n2 = new f4_node(ADD_SIMPLE_CODES[randomN(strlen(ADD_SIMPLE_CODES))], n1->parent, n1->parent->pos );
          n2->addChild(n1);
          n1->parent = n2;
        }
        break;
      }
    }
    break;

    case F4_DEL:
    {
      method=F4_ADD_COUNT-1+F4_DEL;
      // delete a node
      // must pick a node with parent, and at least one child
      // already picked a node, but repeat may be needed
      for (i=0; i<10; i++) {
        if ((NULL != n1->parent) && (g != n1->parent))
          if (NULL != n1->child)
            break;
        // try a new one
        n1 = g->child->randomNode();
      }
      if ((NULL != n1->parent) && (g != n1->parent))
      {
        switch (n1->childCount())
        {
         case 0: break;
         case 1:  // one child
         {
            n2 = n1->parent;
            n2->removeChild(n1);
            if (NULL != n1->child) {
              n1->child->parent = n2;
              n2->addChild(n1->child);
              n1->child = NULL;
            }
            if (NULL != n1->child2) {
              n1->child2->parent = n2;
              n2->addChild(n1->child2);
              n1->child2 = NULL;
            }
            // destroy n1
            n1->parent=NULL;
            delete n1;
         }
         break;

         case 2:  // two children
         {
            // two children
            n2 = n1->parent;
            n2->removeChild(n1);
            // n1 has two children. pick one randomly 50-50, destroy other
            if (randomN(2) == 0)
            {
              n1->child->parent = n2;
              n2->addChild(n1->child);
              n1->child = NULL;
              n1->child2->parent = NULL;
            } else
            {
              n1->child2->parent = n2;
              n2->addChild(n1->child2);
              n1->child2 = NULL;
              n1->child->parent = NULL;
            }
            // destroy n1
            n1->parent=NULL;
            delete n1;
         }
         break;
        }
      } else return GENOPER_OPFAIL;
    }
    break;
    case F4_MOD:
    {
      method=F4_ADD_COUNT-1+F4_MOD;
      // change a node
      // the only nodes that are modifiable are MUT_CHAN_CODES
      // try to get a modifiable node
      // already picked a node, but repeat may be needed
      i=0;
      while (1)
      {
        if (strchr(MUT_CHAN_CODES, n1->name)) break;
        // try a new one
        n1 = g->child->randomNode();
        i++;
        if (i>=20) return GENOPER_OPFAIL;
      }
      switch (n1->name) {
        case '<':
          // swap children
          n2 = n1->child; n1->child = n1->child2; n1->child2 = n2;
          break;
        case '[':
          linkNodeChangeRandom(n1);
          break;
        case '#':
          repeatNodeChangeRandom(n1);
          break;
      }
    }
    break;

    default: //no mutations allowed?
    return GENOPER_OPFAIL;
  }

  return GENOPER_OK;
}

// make a random [ node
void Geno_f4::linkNodeMakeRandom(f4_node * nn) const
{
  int i;
  float prob1;

  i = 0;
  // 35% chance one of *GTS
  prob1 = 1.0f / RAND_MAX * rand();
  prob1 -= 0.35f;
  if (prob1 < 0)
  {
    // '*', 'G', 'T', or 'S', 1/4 chance each
    i = 1 + (int)(3.999f / RAND_MAX * rand());
  }
  nn->i1 = i;
  nn->l1 = 0;
  if (0 == i) {
     // relative input link
     nn->l1 = (int)(4.0f * (1.0f /  RAND_MAX * rand() - 0.5f));
  }
  // weight
  nn->f1 = 10.0f * (1.0f / RAND_MAX * rand() - 0.5f);
}

// change a [ node
void Geno_f4::linkNodeChangeRandom(f4_node * nn) const      //rewritten by M.K. - should work as before (not tested)
{
  int i;
  float prob2;

  double probs[3]={0.1, 0.3, 0.6};
  // 10% change type
  // 30% change link
  // 60% change weight

  switch (roulette(probs,3))
  {
     case 0: // change type
          i = 0;
          // * G, 10% chance each
          prob2 = rnd01 - 0.10f;
          if (prob2 < 0) i=1; else {prob2 -= 0.10f; if (prob2 < 0) i=2;}
          nn->i1 = i;
          break;
     case 1: // change link
          if (0 == nn->i1) // relative input link
             nn->l1 += (int)(2.0f * (rnd01 - 0.5f));
          break;
     case 2: // change weight
          nn->f1 += 1.0f * (rnd01 - 0.5f);
          break;
  }
}

// make a random : node
void Geno_f4::nparNodeMakeRandom(f4_node * nn) const
{
  int sign = (int)( 2.0f / RAND_MAX * rand() );
  int param = (int)( 3.0f / RAND_MAX * rand() );
  if (param>2) param=2;
  nn->l1 = sign;
  nn->i1 = "!=/"[param];
}

// change a repeat # node
void Geno_f4::repeatNodeChangeRandom(f4_node * nn) const
{
  int count;
  float prob1;

  // change count
  count = nn->i1;
  prob1 = 1.0f / RAND_MAX * rand();
  if (prob1 < 0.5f) count++;
               else count--;
  if (count<1) count=1;
  if (count>REP_MAXCOUNT) count=REP_MAXCOUNT;
  nn->i1 = count;
}


int Geno_f4::MutateOneValid(f4_node *& g,int &method) const
// mutate one, until a valid genotype is obtained
{
  // ! the genotype is g->child (not g) !
  int i, res;
  f4_node * gcopy = NULL;
  // try this max 20 times:
  //   copy, mutate, then validate

  for (i=0; i<20; i++)
  {
    gcopy = g->duplicate();

    res = MutateOne(gcopy,method);

    if (GENOPER_OK != res)
    {
      // mutation failed, try again
      delete gcopy;
      continue;  // for
    }
    // try to validate it
    res = ValidateRec(gcopy, 10);
    // accept if it is OK, or was repaired
    if (GENOPER_OK == res)
     //(GENOPER_REPAIR == res)
    {
      // destroy the original one
      g->destroy();
      // make it the new one
      *g = *gcopy;
      gcopy->child=NULL;
      gcopy->child2=NULL;
      delete gcopy;
      res = GENOPER_OK;
      goto retm1v;
    }
    delete gcopy;
  }
  // attempts failed
  res = GENOPER_OPFAIL;
retm1v:
  return res;
}


int Geno_f4::mutate(char *& g, float & chg,int &method)
{
  f4_node *root=new f4_node;
  if (f4_processrec(g, 0, root) || root->childCount()!=1)
     {delete root; return GENOPER_OPFAIL;} // could not convert or bad: fail
  // mutate one node, set chg as this percent
  chg = 1.0/float(root->child->count());
  if (MutateOneValid(root,method)!=GENOPER_OK)
     {delete root; return GENOPER_OPFAIL;}
  // OK, convert back to string
  g[0]=0;
  root->child->sprintAdj(g);
  delete root;
  return GENOPER_OK;
}


/*
int Geno_f4::MutateMany(char *& g, float & chg)
// check if original is valid, then
// make a number of mutations
{
  int res, n, i;
  int totNodes = 0;
  int maxToMut = 0;

  // convert to tree
  f4_node * root;
  root = new f4_node();
  res = f4_processrec(g, 0, root);
  if (res) {
    // could not convert, fail
    goto retm;
  }
  if (1 != root->childCount()) {
    res = GENOPER_OPFAIL;
    goto retm;
  }

  // check if original is valid
  res = ValidateRec( root, 20 );
  // might have been repaired!
  if (GENOPER_REPAIR==res) {
    res = GENOPER_OK;
  }
  if (GENOPER_OK != res) {
    goto retm;
  }

  // decide number of nodes to mutate
  // decide maximum number of nodes to mutate: 0.25*nodes, min 2
  totNodes = root->child->count();
  maxToMut = (int)( 0.25f * totNodes);
  if (maxToMut<2) maxToMut=2;
  if (maxToMut>totNodes) maxToMut=totNodes;

  // decide number of nodes to mutate
  n = (int)( 0.5f + 1.0f/RAND_MAX * rand() * maxToMut );
  if (n<1) n=1;
  if (n>totNodes) n=totNodes;
  // set chg as this percent
  chg = ((float)n) / ((float)totNodes);
  for (i=0; i<n; i++)
  {
    res = MutateOneValid(root);
    if (GENOPER_OK != res)
    {
      res = GENOPER_OPFAIL;
      goto retm;
    }
  }
  // OK, convert back to string
  g[0]=0;
  root->child->sprintAdj(g);
retm:
  delete root;
  return res;
}
*/


int Geno_f4::CrossOverOne(f4_node * g1, f4_node * g2, float chg) const
{
  // ! the genotypes are g1->child and g2->child (not g1 g2) !
  // single offspring in g1
  int smin, smax;
  float size;
  f4_node * n1, * n2, * n1p, * n2p;

  // determine desired size
  size = (1-chg) * (float)g1->count();
  smin = (int)(size*0.9f-1);
  smax = (int)(size*1.1f+1);
  // get a random node with desired size
  n1 = g1->child->randomNodeWithSize(smin, smax);

  // determine desired size
  size = (1-chg) * (float)g2->count();
  smin = (int)(size*0.9f-1);
  smax = (int)(size*1.1f+1);
  // get a random node with desired size
  n2 = g2->child->randomNodeWithSize(smin, smax);

  // exchange the two nodes:
  n1p = n1->parent;
  n2p = n2->parent;
  n1p->removeChild(n1);
  n1p->addChild(n2);
  n2p->removeChild(n2);
  n2p->addChild(n1);
  n1->parent = n2p;
  n2->parent = n1p;

  return GENOPER_OK;
}

int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2)
{
  f4_node root1, root2, *copy1, *copy2;

  // convert genotype strings into tree structures
  if (f4_processrec(g1,0,&root1) || (root1.childCount()!=1)) return GENOPER_OPFAIL;
  if (f4_processrec(g2,0,&root2) || (root2.childCount()!=1)) return GENOPER_OPFAIL;

  // decide amounts of crossover, 0.25-0.75
  // adam: seems 0.1-0.9 -- MacKo
  chg1 = 0.1f + 0.8f*rnd01;
  chg2 = 0.1f + 0.8f*rnd01;

  copy1 = root1.duplicate();
  if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) {delete copy1; copy1=NULL;}
  copy2 = root2.duplicate();
  if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) {delete copy2; copy2=NULL;}

  g1[0]=0;
  g2[0]=0;
  if (copy1) {copy1->child->sprintAdj(g1); delete copy1;}
  if (copy2) {copy2->child->sprintAdj(g2); delete copy2;}
  if (g1[0] || g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL;
}



unsigned long Geno_f4::style(const char *g, int pos)
{
  char ch = g[pos];
  // style categories
  #define STYL4CAT_MODIFIC "LlRrCcQqAaIiSsMmFfWwEe,"
  #define STYL4CAT_NEUMOD "[]|@*GTS:+-/!="
  #define STYL4CAT_DIGIT "0123456789."
  #define STYL4CAT_REST "XN<># "
  if (!strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_DIGIT STYL4CAT_REST, ch))
    return GENSTYLE_CS(0,GENSTYLE_INVALID);
  unsigned long style=GENSTYLE_CS(0,GENSTYLE_STRIKEOUT); //default, should be changed below
  if (strchr("X ", ch))              style=GENSTYLE_CS(0,GENSTYLE_NONE);
  if (strchr("N", ch))               style=GENSTYLE_RGBS(0,200,0,GENSTYLE_NONE);  
  if (strchr("<", ch))               style=GENSTYLE_RGBS(0,0,200,GENSTYLE_BOLD);  
  if (strchr(">", ch))               style=GENSTYLE_RGBS(0,0,100,GENSTYLE_NONE);  
  if (strchr(STYL4CAT_DIGIT, ch))     style=GENSTYLE_RGBS(100,100,100,GENSTYLE_NONE);
  if (strchr(STYL4CAT_MODIFIC, ch))   style=GENSTYLE_RGBS(100,100,100,GENSTYLE_NONE);
  if (strchr(STYL4CAT_NEUMOD, ch))    style=GENSTYLE_RGBS(0,150,0,GENSTYLE_NONE);
  return style;
}