1  /*


2  * geno_f4.cpp  f4 genetic operators.


3  *


4  * f4genotype  f4 format genotype conversions for FramSticks


5  *


6  * Copyright (C) 1999,2000 Adam RotaruVarga (adam_rotaru@yahoo.com)


7  * Copyright (C) 20012004 Maciej Komosinski


8  *


9  * This library is free software; you can redistribute it and/or


10  * modify it under the terms of the GNU Lesser General Public


11  * License as published by the Free Software Foundation; either


12  * version 2.1 of the License, or (at your option) any later version.


13  *


14  * This library is distributed in the hope that it will be useful,


15  * but WITHOUT ANY WARRANTY; without even the implied warranty of


16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU


17  * Lesser General Public License for more details.


18  *


19  * You should have received a copy of the GNU Lesser General Public


20  * License along with this library; if not, write to the Free Software


21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021111307 USA


22  *


23  */


24 


25  #include "geno_f4.h"


26  #include "nonstd.h"


27  #include "sstring.h"


28  #include "framsg.h"


29 


30  #include <stdio.h>


31  #include <stdlib.h>


32  #include <math.h>


33  #include <string.h>


34 


35 


36  #define FIELDSTRUCT Geno_f4


37 


38  static ParamEntry GENO4param_tab[]=


39  {


40  {"Genetics: f4",1,F4_COUNT+F4_ADD_COUNT,},


41  {"f4_mut_add", 0, 0, "Add node", "f 0 100 50", FIELD(prob[F4_ADD]),"mutation: probability of adding a node", },


42  {"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", },


43  {"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", },


44  {"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", },


45  {"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", },


46  {"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", },


47  {"f4_mut_del", 0, 0, "Delete node", "f 0 100 20", FIELD(prob[F4_DEL]),"mutation: probability of deleting a node", },


48  {"f4_mut_mod", 0, 0, "Modify node", "f 0 100 30", FIELD(prob[F4_MOD]),"mutation: probability of changing a node", },


49  {0,},


50  };


51 


52  #undef FIELDSTRUCT


53 


54 


55  Geno_f4::Geno_f4()


56  {


57  supported_format='4';


58  par.setParamTab(GENO4param_tab);


59  par.select(this);


60  par.setDefault();


61 


62  mutation_method_names=new char*[F4_COUNT+F4_ADD_COUNT1];


63  int index=0;


64  mutation_method_names[index++]="added division";


65  mutation_method_names[index++]="added neural connection";


66  mutation_method_names[index++]="added neuron property";


67  mutation_method_names[index++]="added repetition gene";


68  mutation_method_names[index++]="added a simple node";


69  mutation_method_names[index++]="deleted a node";


70  mutation_method_names[index++]="modified a node";


71  if (index!=F4_COUNT+F4_ADD_COUNT1) FramMessage("Geno_f4","Constructor","Mutation names init error",3);


72  }


73 


74  int Geno_f4::ValidateRec(f4_node * geno, int retrycount) const


75  {


76  // ! the genotype is geno>child (not geno) !


77  // build from it with repair on


78 


79  f4_Cells cells( geno>child, 1);


80  cells.simulate(); //we should simulate?!


81 


82  // errors not fixed:


83  if (GENOPER_OPFAIL == cells.geterror())


84  {


85  if (cells.geterrorpos() >= 0) return 1+cells.geterrorpos();


86  return GENOPER_OPFAIL;


87  }


88  // errors can be fixed


89  if (GENOPER_REPAIR == cells.geterror())


90  {


91  cells.repairGeno(geno, 1);


92  // note: geno might have been fixed


93  // check again


94  int res2 = GENOPER_OK;


95  if (retrycount>0)


96  res2 = ValidateRec( geno, retrycount1 );


97 


98  if (res2==GENOPER_OK) return GENOPER_REPAIR;


99  return res2;


100  }


101  // no errors:


102  return GENOPER_OK;


103  }


104 


105 


106  int Geno_f4::validate(char *& geno)


107  {


108  // convert geno to tree, then try to validate 20 times


109  f4_node root;


110  if (f4_processrec(geno, 0, &root)  root.childCount()!=1) return GENOPER_OK; // cannot repair


111  if (ValidateRec( &root, 20 )==GENOPER_REPAIR) // if repaired, make it back to string


112  {


113  geno[0]=0;


114  root.child>sprintAdj(geno);


115  }


116  return GENOPER_OK;


117  }


118 


119 


120  int Geno_f4::checkValidity(const char * geno)


121  {


122  f4_node root;


123  int res = f4_processrec(geno, 0, &root);


124  if (res) return res; // errorpos, >0


125  if (root.childCount()!=1) return 1; //earlier: GENOPER_OPFAIL


126  f4_Cells cells( root.child, 0);


127  cells.simulate();


128  if (cells.geterror()==GENOPER_OPFAIL  cells.geterror()==GENOPER_REPAIR)


129  {


130  if (cells.geterrorpos() >= 0) return 1+cells.geterrorpos();


131  else return 1; //earlier: GENOPER_OPFAIL;


132  } else return GENOPER_OK;


133  }


134 


135 


136  int Geno_f4::MutateOne(f4_node *& g,int &method) const


137  {


138  // ! the genotype is g>child (not g) !


139 


140  // codes that can be changed (apart being added/deleted)


141  #define MUT_CHAN_CODES "<[#"


142  #define ADD_SIMPLE_CODES ",XlLcCrRaAiIsSmMfFwWeEN@"


143  #define REP_MAXCOUNT 19


144 


145  f4_node * n1, * n2, * n3, * n4, * n5;


146  int i, j;


147 


148  // do the mutation


149  // pick a random node


150  n1 = g>child>randomNode();


151  //DB( printf("%c\n", n1>name); )


152 


153  switch(roulette(prob,F4_COUNT))


154  {


155  case F4_ADD:


156  {


157  // add a node


158  switch(method=roulette(probadd,F4_ADD_COUNT))


159  {


160  case F4_ADD_DIV:


161  {


162  // add division ('<')


163  n3 = n1>parent;


164  n3>removeChild(n1);


165  n2 = new f4_node('<', n3, n3>pos );


166  n2>addChild(n1);


167  // new cell is stick or neuron


168  // "X>" or "N>"


169  double pr = rnd01;


170  pr = 0.5;


171  if (pr<0) n3 = new f4_node('X', n2, n2>pos);


172  else


173  {


174  pr = 0.5;


175  if (pr<0)


176  {


177  // if neuron, make muscle and add a link


178  n3 = new f4_node('N', n2, n2>pos);


179  if (randomN(2) == 0)


180  n4 = new f4_node('', n3, n2>pos);


181  else


182  n4 = new f4_node('@', n3, n2>pos);


183  n5 = new f4_node('[', n4, n2>pos);


184  linkNodeMakeRandom(n5);


185  }


186  }


187  new f4_node('>', n3, n3>pos);


188  n1>parent = n2;


189  // now with 50% chance swap children


190  if (randomN(2) == 0)


191  {


192  n3 = n2>child;


193  n2>child = n2>child2;


194  n2>child2 = n3;


195  }


196  }


197  break;


198  case F4_ADD_CONN:


199  {


200  // add link


201  n1>parent>removeChild(n1);


202  n2 = new f4_node('[', n1>parent, n1>parent>pos);


203  linkNodeMakeRandom(n2);


204  n2>addChild(n1);


205  n1>parent = n2;


206  }


207  break;


208  case F4_ADD_NEUPAR:


209  {


210  // add neuron modifier


211  n1>parent>removeChild(n1);


212  n2 = new f4_node(':', n1>parent, n1>parent>pos);


213  nparNodeMakeRandom(n2);


214  n2>addChild(n1);


215  n1>parent = n2;


216  }


217  break;


218  case F4_ADD_REP:


219  {


220  // add repetition ('#')


221  // repeated code (left child) is the original, right child is empty, count is 2


222  n3 = n1>parent;


223  n3>removeChild(n1);


224  n2 = new f4_node('#', n3, n3>pos );


225  n2>i1 = 2;


226  n2>addChild(n1);


227  new f4_node('>', n2, n2>pos);


228  n1>parent = n2;


229  }


230  break;


231  case F4_ADD_SIMP:


232  {


233  // add simple node


234  // choose a simple node from ADD_SIMPLE_CODES


235  n1>parent>removeChild(n1);


236  n2 = new f4_node(ADD_SIMPLE_CODES[randomN(strlen(ADD_SIMPLE_CODES))], n1>parent, n1>parent>pos );


237  n2>addChild(n1);


238  n1>parent = n2;


239  }


240  break;


241  }


242  }


243  break;


244 


245  case F4_DEL:


246  {


247  method=F4_ADD_COUNT1+F4_DEL;


248  // delete a node


249  // must pick a node with parent, and at least one child


250  // already picked a node, but repeat may be needed


251  for (i=0; i<10; i++) {


252  if ((NULL != n1>parent) && (g != n1>parent))


253  if (NULL != n1>child)


254  break;


255  // try a new one


256  n1 = g>child>randomNode();


257  }


258  if ((NULL != n1>parent) && (g != n1>parent))


259  {


260  switch (n1>childCount())


261  {


262  case 0: break;


263  case 1: // one child


264  {


265  n2 = n1>parent;


266  n2>removeChild(n1);


267  if (NULL != n1>child) {


268  n1>child>parent = n2;


269  n2>addChild(n1>child);


270  n1>child = NULL;


271  }


272  if (NULL != n1>child2) {


273  n1>child2>parent = n2;


274  n2>addChild(n1>child2);


275  n1>child2 = NULL;


276  }


277  // destroy n1


278  n1>parent=NULL;


279  delete n1;


280  }


281  break;


282 


283  case 2: // two children


284  {


285  // two children


286  n2 = n1>parent;


287  n2>removeChild(n1);


288  // n1 has two children. pick one randomly 5050, destroy other


289  if (randomN(2) == 0)


290  {


291  n1>child>parent = n2;


292  n2>addChild(n1>child);


293  n1>child = NULL;


294  n1>child2>parent = NULL;


295  } else


296  {


297  n1>child2>parent = n2;


298  n2>addChild(n1>child2);


299  n1>child2 = NULL;


300  n1>child>parent = NULL;


301  }


302  // destroy n1


303  n1>parent=NULL;


304  delete n1;


305  }


306  break;


307  }


308  } else return GENOPER_OPFAIL;


309  }


310  break;


311  case F4_MOD:


312  {


313  method=F4_ADD_COUNT1+F4_MOD;


314  // change a node


315  // the only nodes that are modifiable are MUT_CHAN_CODES


316  // try to get a modifiable node


317  // already picked a node, but repeat may be needed


318  i=0;


319  while (1)


320  {


321  if (strchr(MUT_CHAN_CODES, n1>name)) break;


322  // try a new one


323  n1 = g>child>randomNode();


324  i++;


325  if (i>=20) return GENOPER_OPFAIL;


326  }


327  switch (n1>name) {


328  case '<':


329  // swap children


330  n2 = n1>child; n1>child = n1>child2; n1>child2 = n2;


331  break;


332  case '[':


333  linkNodeChangeRandom(n1);


334  break;


335  case '#':


336  repeatNodeChangeRandom(n1);


337  break;


338  }


339  }


340  break;


341 


342  default: //no mutations allowed?


343  return GENOPER_OPFAIL;


344  }


345 


346  return GENOPER_OK;


347  }


348 


349  // make a random [ node


350  void Geno_f4::linkNodeMakeRandom(f4_node * nn) const


351  {


352  int i;


353  float prob1;


354 


355  i = 0;


356  // 35% chance one of *GTS


357  prob1 = 1.0f / RAND_MAX * rand();


358  prob1 = 0.35f;


359  if (prob1 < 0)


360  {


361  // '*', 'G', 'T', or 'S', 1/4 chance each


362  i = 1 + (int)(3.999f / RAND_MAX * rand());


363  }


364  nn>i1 = i;


365  nn>l1 = 0;


366  if (0 == i) {


367  // relative input link


368  nn>l1 = (int)(4.0f * (1.0f / RAND_MAX * rand()  0.5f));


369  }


370  // weight


371  nn>f1 = 10.0f * (1.0f / RAND_MAX * rand()  0.5f);


372  }


373 


374  // change a [ node


375  void Geno_f4::linkNodeChangeRandom(f4_node * nn) const //rewritten by M.K.  should work as before (not tested)


376  {


377  int i;


378  float prob2;


379 


380  double probs[3]={0.1, 0.3, 0.6};


381  // 10% change type


382  // 30% change link


383  // 60% change weight


384 


385  switch (roulette(probs,3))


386  {


387  case 0: // change type


388  i = 0;


389  // * G, 10% chance each


390  prob2 = rnd01  0.10f;


391  if (prob2 < 0) i=1; else {prob2 = 0.10f; if (prob2 < 0) i=2;}


392  nn>i1 = i;


393  break;


394  case 1: // change link


395  if (0 == nn>i1) // relative input link


396  nn>l1 += (int)(2.0f * (rnd01  0.5f));


397  break;


398  case 2: // change weight


399  nn>f1 += 1.0f * (rnd01  0.5f);


400  break;


401  }


402  }


403 


404  // make a random : node


405  void Geno_f4::nparNodeMakeRandom(f4_node * nn) const


406  {


407  int sign = (int)( 2.0f / RAND_MAX * rand() );


408  int param = (int)( 3.0f / RAND_MAX * rand() );


409  if (param>2) param=2;


410  nn>l1 = sign;


411  nn>i1 = "!=/"[param];


412  }


413 


414  // change a repeat # node


415  void Geno_f4::repeatNodeChangeRandom(f4_node * nn) const


416  {


417  int count;


418  float prob1;


419 


420  // change count


421  count = nn>i1;


422  prob1 = 1.0f / RAND_MAX * rand();


423  if (prob1 < 0.5f) count++;


424  else count;


425  if (count<1) count=1;


426  if (count>REP_MAXCOUNT) count=REP_MAXCOUNT;


427  nn>i1 = count;


428  }


429 


430 


431  int Geno_f4::MutateOneValid(f4_node *& g,int &method) const


432  // mutate one, until a valid genotype is obtained


433  {


434  // ! the genotype is g>child (not g) !


435  int i, res;


436  f4_node * gcopy = NULL;


437  // try this max 20 times:


438  // copy, mutate, then validate


439 


440  for (i=0; i<20; i++)


441  {


442  gcopy = g>duplicate();


443 


444  res = MutateOne(gcopy,method);


445 


446  if (GENOPER_OK != res)


447  {


448  // mutation failed, try again


449  delete gcopy;


450  continue; // for


451  }


452  // try to validate it


453  res = ValidateRec(gcopy, 10);


454  // accept if it is OK, or was repaired


455  if (GENOPER_OK == res)


456  //(GENOPER_REPAIR == res)


457  {


458  // destroy the original one


459  g>destroy();


460  // make it the new one


461  *g = *gcopy;


462  gcopy>child=NULL;


463  gcopy>child2=NULL;


464  delete gcopy;


465  res = GENOPER_OK;


466  goto retm1v;


467  }


468  delete gcopy;


469  }


470  // attempts failed


471  res = GENOPER_OPFAIL;


472  retm1v:


473  return res;


474  }


475 


476 


477  int Geno_f4::mutate(char *& g, float & chg,int &method)


478  {


479  f4_node *root=new f4_node;


480  if (f4_processrec(g, 0, root)  root>childCount()!=1)


481  {delete root; return GENOPER_OPFAIL;} // could not convert or bad: fail


482  // mutate one node, set chg as this percent


483  chg = 1.0/float(root>child>count());


484  if (MutateOneValid(root,method)!=GENOPER_OK)


485  {delete root; return GENOPER_OPFAIL;}


486  // OK, convert back to string


487  g[0]=0;


488  root>child>sprintAdj(g);


489  delete root;


490  return GENOPER_OK;


491  }


492 


493 


494  /*


495  int Geno_f4::MutateMany(char *& g, float & chg)


496  // check if original is valid, then


497  // make a number of mutations


498  {


499  int res, n, i;


500  int totNodes = 0;


501  int maxToMut = 0;


502 


503  // convert to tree


504  f4_node * root;


505  root = new f4_node();


506  res = f4_processrec(g, 0, root);


507  if (res) {


508  // could not convert, fail


509  goto retm;


510  }


511  if (1 != root>childCount()) {


512  res = GENOPER_OPFAIL;


513  goto retm;


514  }


515 


516  // check if original is valid


517  res = ValidateRec( root, 20 );


518  // might have been repaired!


519  if (GENOPER_REPAIR==res) {


520  res = GENOPER_OK;


521  }


522  if (GENOPER_OK != res) {


523  goto retm;


524  }


525 


526  // decide number of nodes to mutate


527  // decide maximum number of nodes to mutate: 0.25*nodes, min 2


528  totNodes = root>child>count();


529  maxToMut = (int)( 0.25f * totNodes);


530  if (maxToMut<2) maxToMut=2;


531  if (maxToMut>totNodes) maxToMut=totNodes;


532 


533  // decide number of nodes to mutate


534  n = (int)( 0.5f + 1.0f/RAND_MAX * rand() * maxToMut );


535  if (n<1) n=1;


536  if (n>totNodes) n=totNodes;


537  // set chg as this percent


538  chg = ((float)n) / ((float)totNodes);


539  for (i=0; i<n; i++)


540  {


541  res = MutateOneValid(root);


542  if (GENOPER_OK != res)


543  {


544  res = GENOPER_OPFAIL;


545  goto retm;


546  }


547  }


548  // OK, convert back to string


549  g[0]=0;


550  root>child>sprintAdj(g);


551  retm:


552  delete root;


553  return res;


554  }


555  */


556 


557 


558  int Geno_f4::CrossOverOne(f4_node * g1, f4_node * g2, float chg) const


559  {


560  // ! the genotypes are g1>child and g2>child (not g1 g2) !


561  // single offspring in g1


562  int smin, smax;


563  float size;


564  f4_node * n1, * n2, * n1p, * n2p;


565 


566  // determine desired size


567  size = (1chg) * (float)g1>count();


568  smin = (int)(size*0.9f1);


569  smax = (int)(size*1.1f+1);


570  // get a random node with desired size


571  n1 = g1>child>randomNodeWithSize(smin, smax);


572 


573  // determine desired size


574  size = (1chg) * (float)g2>count();


575  smin = (int)(size*0.9f1);


576  smax = (int)(size*1.1f+1);


577  // get a random node with desired size


578  n2 = g2>child>randomNodeWithSize(smin, smax);


579 


580  // exchange the two nodes:


581  n1p = n1>parent;


582  n2p = n2>parent;


583  n1p>removeChild(n1);


584  n1p>addChild(n2);


585  n2p>removeChild(n2);


586  n2p>addChild(n1);


587  n1>parent = n2p;


588  n2>parent = n1p;


589 


590  return GENOPER_OK;


591  }


592 


593  int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2)


594  {


595  f4_node root1, root2, *copy1, *copy2;


596 


597  // convert genotype strings into tree structures


598  if (f4_processrec(g1,0,&root1)  (root1.childCount()!=1)) return GENOPER_OPFAIL;


599  if (f4_processrec(g2,0,&root2)  (root2.childCount()!=1)) return GENOPER_OPFAIL;


600 


601  // decide amounts of crossover, 0.250.75


602  // adam: seems 0.10.9  MacKo


603  chg1 = 0.1f + 0.8f*rnd01;


604  chg2 = 0.1f + 0.8f*rnd01;


605 


606  copy1 = root1.duplicate();


607  if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) {delete copy1; copy1=NULL;}


608  copy2 = root2.duplicate();


609  if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) {delete copy2; copy2=NULL;}


610 


611  g1[0]=0;


612  g2[0]=0;


613  if (copy1) {copy1>child>sprintAdj(g1); delete copy1;}


614  if (copy2) {copy2>child>sprintAdj(g2); delete copy2;}


615  if (g1[0]  g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL;


616  }


617 


618 


619 


620  unsigned long Geno_f4::style(const char *g, int pos)


621  {


622  char ch = g[pos];


623  // style categories


624  #define STYL4CAT_MODIFIC "LlRrCcQqAaIiSsMmFfWwEe,"


625  #define STYL4CAT_NEUMOD "[]@*GTS:+/!="


626  #define STYL4CAT_DIGIT "0123456789."


627  #define STYL4CAT_REST "XN<># "


628  if (!strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_DIGIT STYL4CAT_REST, ch))


629  return GENSTYLE_CS(0,GENSTYLE_INVALID);


630  unsigned long style=GENSTYLE_CS(0,GENSTYLE_STRIKEOUT); //default, should be changed below


631  if (strchr("X ", ch)) style=GENSTYLE_CS(0,GENSTYLE_NONE);


632  if (strchr("N", ch)) style=GENSTYLE_RGBS(0,200,0,GENSTYLE_NONE);


633  if (strchr("<", ch)) style=GENSTYLE_RGBS(0,0,200,GENSTYLE_BOLD);


634  if (strchr(">", ch)) style=GENSTYLE_RGBS(0,0,100,GENSTYLE_NONE);


635  if (strchr(STYL4CAT_DIGIT, ch)) style=GENSTYLE_RGBS(100,100,100,GENSTYLE_NONE);


636  if (strchr(STYL4CAT_MODIFIC, ch)) style=GENSTYLE_RGBS(100,100,100,GENSTYLE_NONE);


637  if (strchr(STYL4CAT_NEUMOD, ch)) style=GENSTYLE_RGBS(0,150,0,GENSTYLE_NONE);


638  return style;


639  }


640 


641 

