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

Last change on this file since 671 was 671, checked in by Maciej Komosinski, 7 years ago

Unified property names of f1 and f4; improved docs; 3.141 -> M_PI

  • Property svn:eol-style set to native
File size: 15.4 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2017  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/log.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) logMessage("Geno_f4", "Constructor", 3, "Mutation names init error");
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, const char *genoname)
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, const char *genoname)
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                {
235                        if ((NULL != n1->parent) && (g != n1->parent))
236                                if (NULL != n1->child)
237                                        break;
238                        // try a new one
239                        n1 = g->child->randomNode();
240                }
241                if ((NULL != n1->parent) && (g != n1->parent))
242                {
243                        switch (n1->childCount())
244                        {
245                        case 0: break;
246                        case 1:  // one child
247                        {
248                                n2 = n1->parent;
249                                n2->removeChild(n1);
250                                if (NULL != n1->child)
251                                {
252                                        n1->child->parent = n2;
253                                        n2->addChild(n1->child);
254                                        n1->child = NULL;
255                                }
256                                if (NULL != n1->child2)
257                                {
258                                        n1->child2->parent = n2;
259                                        n2->addChild(n1->child2);
260                                        n1->child2 = NULL;
261                                }
262                                // destroy n1
263                                n1->parent = NULL;
264                                delete n1;
265                        }
266                                break;
267
268                        case 2:  // two children
269                        {
270                                // two children
271                                n2 = n1->parent;
272                                n2->removeChild(n1);
273                                // n1 has two children. pick one randomly 50-50, destroy other
274                                if (randomN(2) == 0)
275                                {
276                                        n1->child->parent = n2;
277                                        n2->addChild(n1->child);
278                                        n1->child = NULL;
279                                        n1->child2->parent = NULL;
280                                }
281                                else
282                                {
283                                        n1->child2->parent = n2;
284                                        n2->addChild(n1->child2);
285                                        n1->child2 = NULL;
286                                        n1->child->parent = NULL;
287                                }
288                                // destroy n1
289                                n1->parent = NULL;
290                                delete n1;
291                        }
292                                break;
293                        }
294                }
295                else return GENOPER_OPFAIL;
296        }
297                break;
298        case F4_MOD:
299        {
300                method = F4_ADD_COUNT - 1 + F4_MOD;
301                // change a node
302                // the only nodes that are modifiable are MUT_CHAN_CODES
303                // try to get a modifiable node
304                // already picked a node, but repeat may be needed
305                int i = 0;
306                while (1)
307                {
308                        if (strchr(MUT_CHAN_CODES, n1->name)) break;
309                        // try a new one
310                        n1 = g->child->randomNode();
311                        i++;
312                        if (i >= 20) return GENOPER_OPFAIL;
313                }
314                switch (n1->name)
315                {
316                case '<':
317                        // swap children
318                        n2 = n1->child; n1->child = n1->child2; n1->child2 = n2;
319                        break;
320                case '[':
321                        linkNodeChangeRandom(n1);
322                        break;
323                case '#':
324                        repeatNodeChangeRandom(n1);
325                        break;
326                }
327        }
328                break;
329
330        default: //no mutations allowed?
331                return GENOPER_OPFAIL;
332        }
333
334        return GENOPER_OK;
335}
336
337// make a random [ node
338void Geno_f4::linkNodeMakeRandom(f4_node * nn) const
339{
340        int i;
341        float prob1;
342
343        i = 0;
344        // 35% chance one of *GTS
345        prob1 = rnd01;
346        prob1 -= 0.35f;
347        if (prob1 < 0)
348        {
349                // '*', 'G', 'T', or 'S', 1/4 chance each
350                i = 1 + (int)(3.999f * rnd01);
351        }
352        nn->i1 = i;
353        nn->l1 = 0;
354        if (0 == i)
355        {
356                // relative input link
357                nn->l1 = (int)(4.0f * (rnd01 - 0.5f));
358        }
359        // weight
360        nn->f1 = 10.0f * (rnd01 - 0.5f);
361}
362
363// change a [ node
364void Geno_f4::linkNodeChangeRandom(f4_node * nn) const      //rewritten by M.K. - should work as before (not tested)
365{
366        int i;
367        float prob2;
368
369        double probs[3] = { 0.1, 0.3, 0.6 };
370        // 10% change type
371        // 30% change link
372        // 60% change weight
373
374        switch (roulette(probs, 3))
375        {
376        case 0: // change type
377                i = 0;
378                // * G, 10% chance each
379                prob2 = rnd01 - 0.10f;
380                if (prob2 < 0) i = 1; else { prob2 -= 0.10f; if (prob2 < 0) i = 2; }
381                nn->i1 = i;
382                break;
383        case 1: // change link
384                if (0 == nn->i1) // relative input link
385                        nn->l1 += (int)(2.0f * (rnd01 - 0.5f));
386                break;
387        case 2: // change weight
388                nn->f1 += 1.0f * (rnd01 - 0.5f);
389                break;
390        }
391}
392
393// make a random : node
394void Geno_f4::nparNodeMakeRandom(f4_node * nn) const
395{
396        int sign = (int)(2.0f * rnd01);
397        int param = (int)(3.0f * rnd01);
398        if (param > 2) param = 2;
399        nn->l1 = sign;
400        nn->i1 = "!=/"[param];
401}
402
403// change a repeat # node
404void Geno_f4::repeatNodeChangeRandom(f4_node * nn) const
405{
406        int count;
407        float prob1;
408
409        // change count
410        count = nn->i1;
411        prob1 = rnd01;
412        if (prob1 < 0.5f) count++;
413        else count--;
414        if (count < 1) count = 1;
415        if (count > REP_MAXCOUNT) count = REP_MAXCOUNT;
416        nn->i1 = count;
417}
418
419
420int Geno_f4::MutateOneValid(f4_node *& g, int &method) const
421// mutate one, until a valid genotype is obtained
422{
423        // ! the genotype is g->child (not g) !
424        int i, res;
425        f4_node * gcopy = NULL;
426        // try this max 20 times:
427        //   copy, mutate, then validate
428
429        for (i = 0; i < 20; i++)
430        {
431                gcopy = g->duplicate();
432
433                res = MutateOne(gcopy, method);
434
435                if (GENOPER_OK != res)
436                {
437                        // mutation failed, try again
438                        delete gcopy;
439                        continue;  // for
440                }
441                // try to validate it
442                res = ValidateRec(gcopy, 10);
443                // accept if it is OK, or was repaired
444                if (GENOPER_OK == res)
445                        //(GENOPER_REPAIR == res)
446                {
447                        // destroy the original one
448                        g->destroy();
449                        // make it the new one
450                        *g = *gcopy;
451                        gcopy->child = NULL;
452                        gcopy->child2 = NULL;
453                        delete gcopy;
454                        res = GENOPER_OK;
455                        goto retm1v;
456                }
457                delete gcopy;
458        }
459        // attempts failed
460        res = GENOPER_OPFAIL;
461retm1v:
462        return res;
463}
464
465
466int Geno_f4::mutate(char *& g, float & chg, int &method)
467{
468        f4_node *root = new f4_node;
469        if (f4_processrec(g, 0, root) || root->childCount() != 1)
470        {
471                delete root;
472                return GENOPER_OPFAIL;
473        } // could not convert or bad: fail
474        // mutate one node, set chg as this percent
475        chg = 1.0 / float(root->child->count());
476        if (MutateOneValid(root, method) != GENOPER_OK)
477        {
478                delete root;
479                return GENOPER_OPFAIL;
480        }
481        // OK, convert back to string
482        g[0] = 0;
483        root->child->sprintAdj(g);
484        delete root;
485        return GENOPER_OK;
486}
487
488
489/*
490int Geno_f4::MutateMany(char *& g, float & chg)
491// check if original is valid, then
492// make a number of mutations
493{
494int res, n, i;
495int totNodes = 0;
496int maxToMut = 0;
497
498// convert to tree
499f4_node * root;
500root = new f4_node();
501res = f4_processrec(g, 0, root);
502if (res) {
503// could not convert, fail
504goto retm;
505}
506if (1 != root->childCount()) {
507res = GENOPER_OPFAIL;
508goto retm;
509}
510
511// check if original is valid
512res = ValidateRec( root, 20 );
513// might have been repaired!
514if (GENOPER_REPAIR==res) {
515res = GENOPER_OK;
516}
517if (GENOPER_OK != res) {
518goto retm;
519}
520
521// decide number of nodes to mutate
522// decide maximum number of nodes to mutate: 0.25*nodes, min 2
523totNodes = root->child->count();
524maxToMut = (int)( 0.25f * totNodes);
525if (maxToMut<2) maxToMut=2;
526if (maxToMut>totNodes) maxToMut=totNodes;
527
528// decide number of nodes to mutate
529n = (int)( 0.5f + rnd01 * maxToMut );
530if (n<1) n=1;
531if (n>totNodes) n=totNodes;
532// set chg as this percent
533chg = ((float)n) / ((float)totNodes);
534for (i=0; i<n; i++)
535{
536res = MutateOneValid(root);
537if (GENOPER_OK != res)
538{
539res = GENOPER_OPFAIL;
540goto retm;
541}
542}
543// OK, convert back to string
544g[0]=0;
545root->child->sprintAdj(g);
546retm:
547delete root;
548return res;
549}
550*/
551
552
553int Geno_f4::CrossOverOne(f4_node * g1, f4_node * g2, float chg) const
554{
555        // ! the genotypes are g1->child and g2->child (not g1 g2) !
556        // single offspring in g1
557        int smin, smax;
558        float size;
559        f4_node * n1, *n2, *n1p, *n2p;
560
561        // determine desired size
562        size = (1 - chg) * (float)g1->count();
563        smin = (int)(size*0.9f - 1);
564        smax = (int)(size*1.1f + 1);
565        // get a random node with desired size
566        n1 = g1->child->randomNodeWithSize(smin, smax);
567
568        // determine desired size
569        size = (1 - chg) * (float)g2->count();
570        smin = (int)(size*0.9f - 1);
571        smax = (int)(size*1.1f + 1);
572        // get a random node with desired size
573        n2 = g2->child->randomNodeWithSize(smin, smax);
574
575        // exchange the two nodes:
576        n1p = n1->parent;
577        n2p = n2->parent;
578        n1p->removeChild(n1);
579        n1p->addChild(n2);
580        n2p->removeChild(n2);
581        n2p->addChild(n1);
582        n1->parent = n2p;
583        n2->parent = n1p;
584
585        return GENOPER_OK;
586}
587
588int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2)
589{
590        f4_node root1, root2, *copy1, *copy2;
591
592        // convert genotype strings into tree structures
593        if (f4_processrec(g1, 0, &root1) || (root1.childCount() != 1)) return GENOPER_OPFAIL;
594        if (f4_processrec(g2, 0, &root2) || (root2.childCount() != 1)) return GENOPER_OPFAIL;
595
596        // decide amounts of crossover, 0.25-0.75
597        // adam: seems 0.1-0.9 -- MacKo
598        chg1 = 0.1f + 0.8f*rnd01;
599        chg2 = 0.1f + 0.8f*rnd01;
600
601        copy1 = root1.duplicate();
602        if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) { delete copy1; copy1 = NULL; }
603        copy2 = root2.duplicate();
604        if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) { delete copy2; copy2 = NULL; }
605
606        g1[0] = 0;
607        g2[0] = 0;
608        if (copy1) { copy1->child->sprintAdj(g1); delete copy1; }
609        if (copy2) { copy2->child->sprintAdj(g2); delete copy2; }
610        if (g1[0] || g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL;
611}
612
613
614
615uint32_t Geno_f4::style(const char *g, int pos)
616{
617        char ch = g[pos];
618        // style categories
619#define STYL4CAT_MODIFIC "LlRrCcQqAaIiSsMmFfWwEe,"
620#define STYL4CAT_NEUMOD "[]|@*GTS:+-/!="
621#define STYL4CAT_DIGIT "0123456789."
622#define STYL4CAT_REST "XN<># "
623        if (!strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_DIGIT STYL4CAT_REST, ch))
624                return GENSTYLE_CS(0, GENSTYLE_INVALID);
625        uint32_t style = GENSTYLE_CS(0, GENSTYLE_STRIKEOUT); //default, should be changed below
626        if (strchr("X ", ch))              style = GENSTYLE_CS(0, GENSTYLE_NONE);
627        if (strchr("N", ch))               style = GENSTYLE_RGBS(0, 200, 0, GENSTYLE_NONE);
628        if (strchr("<", ch))               style = GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD);
629        if (strchr(">", ch))               style = GENSTYLE_RGBS(0, 0, 100, GENSTYLE_NONE);
630        if (strchr(STYL4CAT_DIGIT, ch))     style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
631        if (strchr(STYL4CAT_MODIFIC, ch))   style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
632        if (strchr(STYL4CAT_NEUMOD, ch))    style = GENSTYLE_RGBS(0, 150, 0, GENSTYLE_NONE);
633        return style;
634}
Note: See TracBrowser for help on using the repository browser.