source: cpp/frams/genetics/f4/oper_f4.cpp @ 286

Last change on this file since 286 was 286, checked in by Maciej Komosinski, 10 years ago

Updated headers
  • Property svn:eol-style set to native
File size: 15.3 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2015  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5// Copyright (C) 1999,2000  Adam Rotaru-Varga (adam_rotaru@yahoo.com), GNU LGPL
6// Copyright (C) since 2001 Maciej Komosinski
7
8#include "oper_f4.h"
9#include <frams/util/sstring.h>
10#include <common/framsg.h>
11
12#include <stdio.h>
13#include <stdlib.h>
14#include "common/nonstd_math.h"
15#include <string.h>
16
17
18#define FIELDSTRUCT Geno_f4
19
20static ParamEntry GENO4param_tab[] =
21{
22        { "Genetics: f4", 1, F4_COUNT + F4_ADD_COUNT, },
23        { "f4_mut_add", 0, 0, "Add node", "f 0 100 50", FIELD(prob[F4_ADD]), "mutation: probability of adding a node", },
24        { "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", },
25        { "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", },
26        { "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", },
27        { "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", },
28        { "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", },
29        { "f4_mut_del", 0, 0, "Delete node", "f 0 100 20", FIELD(prob[F4_DEL]), "mutation: probability of deleting a node", },
30        { "f4_mut_mod", 0, 0, "Modify node", "f 0 100 30", FIELD(prob[F4_MOD]), "mutation: probability of changing a node", },
31        { 0, },
32};
33
34#undef FIELDSTRUCT
35
36
37Geno_f4::Geno_f4()
38{
39        supported_format = '4';
40        par.setParamTab(GENO4param_tab);
41        par.select(this);
42        par.setDefault();
43
44        mutation_method_names = new const char*[F4_COUNT + F4_ADD_COUNT - 1];
45        int index = 0;
46        mutation_method_names[index++] = "added division";
47        mutation_method_names[index++] = "added neural connection";
48        mutation_method_names[index++] = "added neuron property";
49        mutation_method_names[index++] = "added repetition gene";
50        mutation_method_names[index++] = "added a simple node";
51        mutation_method_names[index++] = "deleted a node";
52        mutation_method_names[index++] = "modified a node";
53        if (index != F4_COUNT + F4_ADD_COUNT - 1) FramMessage("Geno_f4", "Constructor", "Mutation names init error", 3);
54}
55
56int Geno_f4::ValidateRec(f4_node * geno, int retrycount) const
57{
58        // ! the genotype is geno->child (not geno) !
59        // build from it with repair on
60
61        f4_Cells cells(geno->child, 1);
62        cells.simulate();  //we should simulate?!
63
64        // errors not fixed:
65        if (GENOPER_OPFAIL == cells.geterror())
66        {
67                if (cells.geterrorpos() >= 0) return 1 + cells.geterrorpos();
68                return GENOPER_OPFAIL;
69        }
70        // errors can be fixed
71        if (GENOPER_REPAIR == cells.geterror())
72        {
73                cells.repairGeno(geno, 1);
74                // note: geno might have been fixed
75                // check again
76                int res2 = GENOPER_OK;
77                if (retrycount > 0)
78                        res2 = ValidateRec(geno, retrycount - 1);
79
80                if (res2 == GENOPER_OK) return GENOPER_REPAIR;
81                return res2;
82        }
83        // no errors:
84        return GENOPER_OK;
85}
86
87
88int Geno_f4::validate(char *& geno)
89{
90        // convert geno to tree, then try to validate 20 times
91        f4_node root;
92        if (f4_processrec(geno, 0, &root) || root.childCount() != 1) return GENOPER_OK; // cannot repair
93        if (ValidateRec(&root, 20) == GENOPER_REPAIR) // if repaired, make it back to string
94        {
95                geno[0] = 0;
96                root.child->sprintAdj(geno);
97        }
98        return GENOPER_OK;
99}
100
101
102int Geno_f4::checkValidity(const char * geno)
103{
104        f4_node root;
105        int res = f4_processrec(geno, 0, &root);
106        if (res) return res;  // errorpos, >0
107        if (root.childCount() != 1) return 1; //earlier: GENOPER_OPFAIL
108        f4_Cells cells(root.child, 0);
109        cells.simulate();
110        if (cells.geterror() == GENOPER_OPFAIL || cells.geterror() == GENOPER_REPAIR)
111        {
112                if (cells.geterrorpos() >= 0) return 1 + cells.geterrorpos();
113                else return 1; //earlier: GENOPER_OPFAIL;
114        }
115        else return GENOPER_OK;
116}
117
118
119int Geno_f4::MutateOne(f4_node *& g, int &method) const
120{
121        // ! the genotype is g->child (not g) !
122
123        // codes that can be changed (apart being added/deleted)
124#define MUT_CHAN_CODES "<[#"
125#define ADD_SIMPLE_CODES ",XlLcCrRaAiIsSmMfFwWeEN@|"
126#define REP_MAXCOUNT 19
127
128        f4_node * n1, *n2, *n3, *n4, *n5;
129
130        // do the mutation
131        // pick a random node
132        n1 = g->child->randomNode();
133        //DB( printf("%c\n", n1->name); )
134
135        switch (roulette(prob, F4_COUNT))
136        {
137        case F4_ADD:
138        {
139                // add a node
140                switch (method = roulette(probadd, F4_ADD_COUNT))
141                {
142                case F4_ADD_DIV:
143                {
144                        // add division ('<')
145                        n3 = n1->parent;
146                        n3->removeChild(n1);
147                        n2 = new f4_node('<', n3, n3->pos);
148                        n2->addChild(n1);
149                        // new cell is stick or neuron
150                        // "X>" or "N>"
151                        double pr = rnd01;
152                        pr -= 0.5;
153                        if (pr < 0) n3 = new f4_node('X', n2, n2->pos);
154                        else
155                        {
156                                pr -= 0.5;
157                                if (pr < 0)
158                                {
159                                        // if neuron, make muscle and add a link
160                                        n3 = new f4_node('N', n2, n2->pos);
161                                        if (randomN(2) == 0)
162                                                n4 = new f4_node('|', n3, n2->pos);
163                                        else
164                                                n4 = new f4_node('@', n3, n2->pos);
165                                        n5 = new f4_node('[', n4, n2->pos);
166                                        linkNodeMakeRandom(n5);
167                                }
168                        }
169                        new f4_node('>', n3, n3->pos);
170                        n1->parent = n2;
171                        // now with 50% chance swap children
172                        if (randomN(2) == 0)
173                        {
174                                n3 = n2->child;
175                                n2->child = n2->child2;
176                                n2->child2 = n3;
177                        }
178                }
179                        break;
180                case F4_ADD_CONN:
181                {
182                        // add link
183                        n1->parent->removeChild(n1);
184                        n2 = new f4_node('[', n1->parent, n1->parent->pos);
185                        linkNodeMakeRandom(n2);
186                        n2->addChild(n1);
187                        n1->parent = n2;
188                }
189                        break;
190                case F4_ADD_NEUPAR:
191                {
192                        // add neuron modifier
193                        n1->parent->removeChild(n1);
194                        n2 = new f4_node(':', n1->parent, n1->parent->pos);
195                        nparNodeMakeRandom(n2);
196                        n2->addChild(n1);
197                        n1->parent = n2;
198                }
199                        break;
200                case F4_ADD_REP:
201                {
202                        // add repetition ('#')
203                        // repeated code (left child) is the original, right child is empty, count is 2
204                        n3 = n1->parent;
205                        n3->removeChild(n1);
206                        n2 = new f4_node('#', n3, n3->pos);
207                        n2->i1 = 2;
208                        n2->addChild(n1);
209                        new f4_node('>', n2, n2->pos);
210                        n1->parent = n2;
211                }
212                        break;
213                case F4_ADD_SIMP:
214                {
215                        // add simple node
216                        // choose a simple node from ADD_SIMPLE_CODES
217                        n1->parent->removeChild(n1);
218                        n2 = new f4_node(ADD_SIMPLE_CODES[randomN(strlen(ADD_SIMPLE_CODES))], n1->parent, n1->parent->pos);
219                        n2->addChild(n1);
220                        n1->parent = n2;
221                }
222                        break;
223                }
224        }
225                break;
226
227        case F4_DEL:
228        {
229                method = F4_ADD_COUNT - 1 + F4_DEL;
230                // delete a node
231                // must pick a node with parent, and at least one child
232                // already picked a node, but repeat may be needed
233                for (int i = 0; i < 10; i++) {
234                        if ((NULL != n1->parent) && (g != n1->parent))
235                                if (NULL != n1->child)
236                                        break;
237                        // try a new one
238                        n1 = g->child->randomNode();
239                }
240                if ((NULL != n1->parent) && (g != n1->parent))
241                {
242                        switch (n1->childCount())
243                        {
244                        case 0: break;
245                        case 1:  // one child
246                        {
247                                n2 = n1->parent;
248                                n2->removeChild(n1);
249                                if (NULL != n1->child) {
250                                        n1->child->parent = n2;
251                                        n2->addChild(n1->child);
252                                        n1->child = NULL;
253                                }
254                                if (NULL != n1->child2) {
255                                        n1->child2->parent = n2;
256                                        n2->addChild(n1->child2);
257                                        n1->child2 = NULL;
258                                }
259                                // destroy n1
260                                n1->parent = NULL;
261                                delete n1;
262                        }
263                                break;
264
265                        case 2:  // two children
266                        {
267                                // two children
268                                n2 = n1->parent;
269                                n2->removeChild(n1);
270                                // n1 has two children. pick one randomly 50-50, destroy other
271                                if (randomN(2) == 0)
272                                {
273                                        n1->child->parent = n2;
274                                        n2->addChild(n1->child);
275                                        n1->child = NULL;
276                                        n1->child2->parent = NULL;
277                                }
278                                else
279                                {
280                                        n1->child2->parent = n2;
281                                        n2->addChild(n1->child2);
282                                        n1->child2 = NULL;
283                                        n1->child->parent = NULL;
284                                }
285                                // destroy n1
286                                n1->parent = NULL;
287                                delete n1;
288                        }
289                                break;
290                        }
291                }
292                else return GENOPER_OPFAIL;
293        }
294                break;
295        case F4_MOD:
296        {
297                method = F4_ADD_COUNT - 1 + F4_MOD;
298                // change a node
299                // the only nodes that are modifiable are MUT_CHAN_CODES
300                // try to get a modifiable node
301                // already picked a node, but repeat may be needed
302                int i = 0;
303                while (1)
304                {
305                        if (strchr(MUT_CHAN_CODES, n1->name)) break;
306                        // try a new one
307                        n1 = g->child->randomNode();
308                        i++;
309                        if (i >= 20) return GENOPER_OPFAIL;
310                }
311                switch (n1->name) {
312                case '<':
313                        // swap children
314                        n2 = n1->child; n1->child = n1->child2; n1->child2 = n2;
315                        break;
316                case '[':
317                        linkNodeChangeRandom(n1);
318                        break;
319                case '#':
320                        repeatNodeChangeRandom(n1);
321                        break;
322                }
323        }
324                break;
325
326        default: //no mutations allowed?
327                return GENOPER_OPFAIL;
328        }
329
330        return GENOPER_OK;
331}
332
333// make a random [ node
334void Geno_f4::linkNodeMakeRandom(f4_node * nn) const
335{
336        int i;
337        float prob1;
338
339        i = 0;
340        // 35% chance one of *GTS
341        prob1 = rnd01;
342        prob1 -= 0.35f;
343        if (prob1 < 0)
344        {
345                // '*', 'G', 'T', or 'S', 1/4 chance each
346                i = 1 + (int)(3.999f * rnd01);
347        }
348        nn->i1 = i;
349        nn->l1 = 0;
350        if (0 == i) {
351                // relative input link
352                nn->l1 = (int)(4.0f * (rnd01 - 0.5f));
353        }
354        // weight
355        nn->f1 = 10.0f * (rnd01 - 0.5f);
356}
357
358// change a [ node
359void Geno_f4::linkNodeChangeRandom(f4_node * nn) const      //rewritten by M.K. - should work as before (not tested)
360{
361        int i;
362        float prob2;
363
364        double probs[3] = { 0.1, 0.3, 0.6 };
365        // 10% change type
366        // 30% change link
367        // 60% change weight
368
369        switch (roulette(probs, 3))
370        {
371        case 0: // change type
372                i = 0;
373                // * G, 10% chance each
374                prob2 = rnd01 - 0.10f;
375                if (prob2 < 0) i = 1; else { prob2 -= 0.10f; if (prob2 < 0) i = 2; }
376                nn->i1 = i;
377                break;
378        case 1: // change link
379                if (0 == nn->i1) // relative input link
380                        nn->l1 += (int)(2.0f * (rnd01 - 0.5f));
381                break;
382        case 2: // change weight
383                nn->f1 += 1.0f * (rnd01 - 0.5f);
384                break;
385        }
386}
387
388// make a random : node
389void Geno_f4::nparNodeMakeRandom(f4_node * nn) const
390{
391        int sign = (int)(2.0f * rnd01);
392        int param = (int)(3.0f * rnd01);
393        if (param > 2) param = 2;
394        nn->l1 = sign;
395        nn->i1 = "!=/"[param];
396}
397
398// change a repeat # node
399void Geno_f4::repeatNodeChangeRandom(f4_node * nn) const
400{
401        int count;
402        float prob1;
403
404        // change count
405        count = nn->i1;
406        prob1 = rnd01;
407        if (prob1 < 0.5f) count++;
408        else count--;
409        if (count<1) count = 1;
410        if (count>REP_MAXCOUNT) count = REP_MAXCOUNT;
411        nn->i1 = count;
412}
413
414
415int Geno_f4::MutateOneValid(f4_node *& g, int &method) const
416// mutate one, until a valid genotype is obtained
417{
418        // ! the genotype is g->child (not g) !
419        int i, res;
420        f4_node * gcopy = NULL;
421        // try this max 20 times:
422        //   copy, mutate, then validate
423
424        for (i = 0; i < 20; i++)
425        {
426                gcopy = g->duplicate();
427
428                res = MutateOne(gcopy, method);
429
430                if (GENOPER_OK != res)
431                {
432                        // mutation failed, try again
433                        delete gcopy;
434                        continue;  // for
435                }
436                // try to validate it
437                res = ValidateRec(gcopy, 10);
438                // accept if it is OK, or was repaired
439                if (GENOPER_OK == res)
440                        //(GENOPER_REPAIR == res)
441                {
442                        // destroy the original one
443                        g->destroy();
444                        // make it the new one
445                        *g = *gcopy;
446                        gcopy->child = NULL;
447                        gcopy->child2 = NULL;
448                        delete gcopy;
449                        res = GENOPER_OK;
450                        goto retm1v;
451                }
452                delete gcopy;
453        }
454        // attempts failed
455        res = GENOPER_OPFAIL;
456retm1v:
457        return res;
458}
459
460
461int Geno_f4::mutate(char *& g, float & chg, int &method)
462{
463        f4_node *root = new f4_node;
464        if (f4_processrec(g, 0, root) || root->childCount() != 1)
465        {
466                delete root; return GENOPER_OPFAIL;
467        } // could not convert or bad: fail
468        // mutate one node, set chg as this percent
469        chg = 1.0 / float(root->child->count());
470        if (MutateOneValid(root, method) != GENOPER_OK)
471        {
472                delete root; return GENOPER_OPFAIL;
473        }
474        // OK, convert back to string
475        g[0] = 0;
476        root->child->sprintAdj(g);
477        delete root;
478        return GENOPER_OK;
479}
480
481
482/*
483int Geno_f4::MutateMany(char *& g, float & chg)
484// check if original is valid, then
485// make a number of mutations
486{
487int res, n, i;
488int totNodes = 0;
489int maxToMut = 0;
490
491// convert to tree
492f4_node * root;
493root = new f4_node();
494res = f4_processrec(g, 0, root);
495if (res) {
496// could not convert, fail
497goto retm;
498}
499if (1 != root->childCount()) {
500res = GENOPER_OPFAIL;
501goto retm;
502}
503
504// check if original is valid
505res = ValidateRec( root, 20 );
506// might have been repaired!
507if (GENOPER_REPAIR==res) {
508res = GENOPER_OK;
509}
510if (GENOPER_OK != res) {
511goto retm;
512}
513
514// decide number of nodes to mutate
515// decide maximum number of nodes to mutate: 0.25*nodes, min 2
516totNodes = root->child->count();
517maxToMut = (int)( 0.25f * totNodes);
518if (maxToMut<2) maxToMut=2;
519if (maxToMut>totNodes) maxToMut=totNodes;
520
521// decide number of nodes to mutate
522n = (int)( 0.5f + rnd01 * maxToMut );
523if (n<1) n=1;
524if (n>totNodes) n=totNodes;
525// set chg as this percent
526chg = ((float)n) / ((float)totNodes);
527for (i=0; i<n; i++)
528{
529res = MutateOneValid(root);
530if (GENOPER_OK != res)
531{
532res = GENOPER_OPFAIL;
533goto retm;
534}
535}
536// OK, convert back to string
537g[0]=0;
538root->child->sprintAdj(g);
539retm:
540delete root;
541return res;
542}
543*/
544
545
546int Geno_f4::CrossOverOne(f4_node * g1, f4_node * g2, float chg) const
547{
548        // ! the genotypes are g1->child and g2->child (not g1 g2) !
549        // single offspring in g1
550        int smin, smax;
551        float size;
552        f4_node * n1, *n2, *n1p, *n2p;
553
554        // determine desired size
555        size = (1 - chg) * (float)g1->count();
556        smin = (int)(size*0.9f - 1);
557        smax = (int)(size*1.1f + 1);
558        // get a random node with desired size
559        n1 = g1->child->randomNodeWithSize(smin, smax);
560
561        // determine desired size
562        size = (1 - chg) * (float)g2->count();
563        smin = (int)(size*0.9f - 1);
564        smax = (int)(size*1.1f + 1);
565        // get a random node with desired size
566        n2 = g2->child->randomNodeWithSize(smin, smax);
567
568        // exchange the two nodes:
569        n1p = n1->parent;
570        n2p = n2->parent;
571        n1p->removeChild(n1);
572        n1p->addChild(n2);
573        n2p->removeChild(n2);
574        n2p->addChild(n1);
575        n1->parent = n2p;
576        n2->parent = n1p;
577
578        return GENOPER_OK;
579}
580
581int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2)
582{
583        f4_node root1, root2, *copy1, *copy2;
584
585        // convert genotype strings into tree structures
586        if (f4_processrec(g1, 0, &root1) || (root1.childCount() != 1)) return GENOPER_OPFAIL;
587        if (f4_processrec(g2, 0, &root2) || (root2.childCount() != 1)) return GENOPER_OPFAIL;
588
589        // decide amounts of crossover, 0.25-0.75
590        // adam: seems 0.1-0.9 -- MacKo
591        chg1 = 0.1f + 0.8f*rnd01;
592        chg2 = 0.1f + 0.8f*rnd01;
593
594        copy1 = root1.duplicate();
595        if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) { delete copy1; copy1 = NULL; }
596        copy2 = root2.duplicate();
597        if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) { delete copy2; copy2 = NULL; }
598
599        g1[0] = 0;
600        g2[0] = 0;
601        if (copy1) { copy1->child->sprintAdj(g1); delete copy1; }
602        if (copy2) { copy2->child->sprintAdj(g2); delete copy2; }
603        if (g1[0] || g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL;
604}
605
606
607
608uint32_t Geno_f4::style(const char *g, int pos)
609{
610        char ch = g[pos];
611        // style categories
612#define STYL4CAT_MODIFIC "LlRrCcQqAaIiSsMmFfWwEe,"
613#define STYL4CAT_NEUMOD "[]|@*GTS:+-/!="
614#define STYL4CAT_DIGIT "0123456789."
615#define STYL4CAT_REST "XN<># "
616        if (!strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_DIGIT STYL4CAT_REST, ch))
617                return GENSTYLE_CS(0, GENSTYLE_INVALID);
618        uint32_t style = GENSTYLE_CS(0, GENSTYLE_STRIKEOUT); //default, should be changed below
619        if (strchr("X ", ch))              style = GENSTYLE_CS(0, GENSTYLE_NONE);
620        if (strchr("N", ch))               style = GENSTYLE_RGBS(0, 200, 0, GENSTYLE_NONE);
621        if (strchr("<", ch))               style = GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD);
622        if (strchr(">", ch))               style = GENSTYLE_RGBS(0, 0, 100, GENSTYLE_NONE);
623        if (strchr(STYL4CAT_DIGIT, ch))     style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
624        if (strchr(STYL4CAT_MODIFIC, ch))   style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
625        if (strchr(STYL4CAT_NEUMOD, ch))    style = GENSTYLE_RGBS(0, 150, 0, GENSTYLE_NONE);
626        return style;
627}
Note: See TracBrowser for help on using the repository browser.