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

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

Improved comments, removed unnecessary TODO regarding "Rr" modifiers

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