source: cpp/f4/geno_f4.cpp @ 32

Last change on this file since 32 was 4, checked in by Maciej Komosinski, 16 years ago

added f4, a genetic representation that describes development of an organism

File size: 18.3 KB
RevLine 
[4]1/*
2 *  geno_f4.cpp - f4 genetic operators.
3 *
4 *  f4genotype - f4 format genotype conversions for FramSticks
5 *
6 *  Copyright (C) 1999,2000  Adam Rotaru-Varga (adam_rotaru@yahoo.com)
7 *  Copyright (C) 2001-2004  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 02111-1307 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
38static 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
55Geno_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_COUNT-1];
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_COUNT-1) FramMessage("Geno_f4","Constructor","Mutation names init error",3);
72}
73
74int 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, retrycount-1 );
97
98    if (res2==GENOPER_OK) return GENOPER_REPAIR;
99    return res2;
100  }
101  // no errors:
102  return GENOPER_OK;
103}
104
105
106int 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
120int 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
136int 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_COUNT-1+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 50-50, 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_COUNT-1+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
350void 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
375void 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
405void 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
415void 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
431int 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;
472retm1v:
473  return res;
474}
475
476
477int 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/*
495int 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);
551retm:
552  delete root;
553  return res;
554}
555*/
556
557
558int 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 = (1-chg) * (float)g1->count();
568  smin = (int)(size*0.9f-1);
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 = (1-chg) * (float)g2->count();
575  smin = (int)(size*0.9f-1);
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
593int 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.25-0.75
602  // adam: seems 0.1-0.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
620unsigned 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
Note: See TracBrowser for help on using the repository browser.