source: cpp/frams/genetics/fB/fB_oper.cpp

Last change on this file was 1298, checked in by Maciej Komosinski, 3 weeks ago

Introduced overloads for rndUint() with size_t and int arguments to avoid numerous type casts in sources
File size: 17.8 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2023  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5//TODO parsing quotes/neurons seems too relaxed, for example the genotype aag"S""acalaaaafbc is considered valid
6//TODO Same with numbers: "----1.23" is valid
7//TODO reconsider: Horizontal gene transfer - copying a single random gene from each parent to the beginning of the other parent: should the gene be copied (seems to cause bloat!) or rather moved?
8//Neurons ("N") can grow even without using quotes and providing neuron classname in the genotype, for example aaaaabbccvaaapdgfddaalaandwddbaajt (this works likely as designed, but investigate and reconsider); also valid neuron definitions inside the genotype are sometimes not expressed
9
10#include <frams/util/sstring.h>
11#include <vector>
12#include <algorithm>
13#include <frams/param/param.h>
14#include "fB_conv.h"
15#include "fB_general.h"
16#include "fB_oper.h"
17#include "../fH/fH_oper.h"
18
19#define FIELDSTRUCT Geno_fB
20
21static ParamEntry geno_fB_paramtab[] =
22{
23        { "Genetics: fB", 3, FB_MUT_COUNT + FB_XOVER_COUNT, },
24        { "Genetics: fB: Mutation", },
25        { "Genetics: fB: Crossover", },
26        { "fB_mut_substitute", 1, 0, "Substitution", "f 0 100 1", FIELD(mutationprobs[FB_SUBSTITUTION]), "Relative probability of changing a single random character (or a neuron) in the genotype", },
27        { "fB_mut_insert", 1, 0, "Insertion", "f 0 100 3", FIELD(mutationprobs[FB_INSERTION]), "Relative probability of inserting a random character in a random place of the genotype", },
28        { "fB_mut_insert_neuron", 1, 0, "Insertion of a neuron", "f 0 100 3", FIELD(mutationprobs[FB_INSERTION_NEURON]), "Relative probability of inserting a neuron in a random place of genotype", },
29        { "fB_mut_delete", 1, 0, "Deletion", "f 0 100 4", FIELD(mutationprobs[FB_DELETION]), "Relative probability of deleting a random character (or a neuron) in the genotype", },
30        { "fB_mut_duplicate", 1, 0, "Duplication", "f 0 100 0", FIELD(mutationprobs[FB_DUPLICATION]), "Relative probability of copying a single *gene* of the genotype and appending it to the beginning of this genotype", },
31        { "fB_mut_translocate", 1, 0, "Translocation", "f 0 100 4", FIELD(mutationprobs[FB_TRANSLOCATION]), "Relative probability of swapping two substrings in the genotype", },
32        { "fB_cross_gene_transfer", 2, 0, "Horizontal gene transfer", "f 0 100 0", FIELD(crossoverprobs[FB_GENE_TRANSFER]), "Relative probability of crossing over by copying a single random gene from each parent to the beginning of the other parent", },
33        { "fB_cross_crossover", 2, 0, "Crossing over", "f 0 100 100", FIELD(crossoverprobs[FB_CROSSING_OVER]), "Relative probability of crossing over by a random distribution of genes from both parents to both children", },
34        { 0, },
35};
36
37#undef FIELDSTRUCT
38
39Geno_fB::Geno_fB()
40{
41        par.setParamTab(geno_fB_paramtab);
42        par.select(this);
43        par.setDefault();
44        supported_format = 'B';
45}
46
47bool Geno_fB::hasStick(const SString &genotype)
48{
49        for (int i = 0; i < fB_GenoHelpers::geneCount(genotype); i++)
50        {
51                int start, end;
52                SString gene = fB_GenoHelpers::getGene(i, genotype, start, end);
53                int endoffset = 0;
54                if (gene.indexOf("zz", 0) != -1) endoffset = 2;
55                if (gene.length() - endoffset < 3)
56                {
57                        return true; // genes with length < 3 are always sticks
58                }
59                else if (gene[2] >= 'a' && gene[2] <= 'i')
60                {
61                        return true; // gene within this range is stick
62                }
63        }
64        return false;
65}
66
67int Geno_fB::checkValidity(const char *geno, const char *genoname)
68{
69        // load genotype
70        SString genotype(geno);
71        SString line;
72        int pos = 0;
73        // if there is no genotype to load, then return error
74        if (!genotype.getNextToken(pos, line, '\n'))
75        {
76                return pos + 1;
77        }
78        // extract dimensions
79        int dims = 0;
80        if (!ExtValue::parseInt(line.c_str(), dims, true, false))
81        {
82                return 1;
83        }
84        // extract next token in order to check if next line starts with "aa"
85        int genstart = genotype.indexOf("aa", 0);
86        if (genstart != pos)
87        {
88                return pos + 1;
89        }
90        // check if rest of characters are lowercase
91        for (int i = genstart; i < genotype.length(); i++)
92        {
93                if (!islower(genotype[i]))
94                {
95                        if (genotype[i] == '"')
96                        {
97                                SString neuclassdef;
98                                int nextid = i + 1;
99                                if (!genotype.getNextToken(nextid, neuclassdef, '"'))
100                                {
101                                        return i + 1;
102                                }
103                                Neuro *neu = new Neuro();
104                                neu->setDetails(neuclassdef);
105
106                                bool isclass = neu->getClass() ? true : false;
107                                delete neu;
108                                if (!isclass)
109                                {
110                                        return i + 1;
111                                }
112                                i = nextid;
113                        }
114                        else
115                        {
116                                return i + 1;
117                        }
118                }
119        }
120        if (!hasStick(genotype))
121        {
122                return 1;
123        }
124        return GENOPER_OK;
125}
126
127int Geno_fB::validate(char *&geno, const char *genoname)
128{
129        // load genotype
130        SString genotype(geno);
131        SString strdims;
132        int pos = 0;
133        if (!genotype.getNextToken(pos, strdims, '\n'))
134        {
135                return GENOPER_OK;
136        }
137        // parse dimension
138        int dims = 0;
139        if (!ExtValue::parseInt(strdims.c_str(), dims, true, false))
140        {
141                return GENOPER_OK;
142        }
143        SString line;
144        bool fix = false;
145        int genstart = genotype.indexOf("aa", 0);
146        // if there is no "aa" codon in the beginning of a genotype, then add it
147        if (genstart != pos)
148        {
149                genotype = strdims + "\naa" + genotype.substr(pos);
150                fix = true;
151        }
152        for (int i = pos; i < genotype.length(); i++)
153        {
154                // if character is not alphabetic - error
155                if (!isalpha(genotype[i]))
156                {
157                        if (genotype[i] == '"')
158                        {
159                                SString neuclassdef;
160                                int nextid = i + 1;
161                                if (!genotype.getNextToken(nextid, neuclassdef, '"'))
162                                {
163                                        return i + 1;
164                                }
165                                Neuro *neu = new Neuro();
166                                neu->setDetails(neuclassdef);
167
168                                bool isclass = neu->getClass() ? true : false;
169                                delete neu;
170                                if (!isclass)
171                                {
172                                        return i + 1;
173                                }
174                                i = nextid;
175                        }
176                        else
177                        {
178                                return GENOPER_OK;
179                        }
180                }
181                // if character is uppercase, then convert it to lowercase
182                else if (isupper(genotype[i]))
183                {
184                        genotype.directWrite()[i] = tolower(genotype[i]);
185                        fix = true;
186                }
187        }
188        // if the genotype does not contain any stick - add it
189        if (!hasStick(genotype))
190        {
191                genotype = SString("aaazz") + genotype;
192        }
193        // if there were any changes - save them
194        if (fix)
195        {
196                free(geno);
197                geno = strdup(genotype.c_str());
198        }
199        return GENOPER_OK;
200}
201
202SString Geno_fB::detokenizeSequence(std::list<SString> *tokenlist)
203{
204        SString res = "";
205        for (std::list<SString>::iterator it = tokenlist->begin(); it != tokenlist->end(); it++)
206        {
207                res += (*it);
208        }
209        return res;
210}
211
212std::list<SString> Geno_fB::tokenizeSequence(const SString &genotype)
213{
214        std::list<SString> res;
215        int i = 0;
216        while (i < genotype.length())
217        {
218                // if character is not alphabetic - error
219                if (isalpha(genotype[i]))
220                {
221                        SString el = "";
222                        el += genotype[i];
223                        res.push_back(el);
224                        i++;
225                }
226                else
227                {
228                        SString neuclassdef;
229                        i++;
230                        genotype.getNextToken(i, neuclassdef, '"');
231                        SString ndef = "\"";
232                        ndef += neuclassdef;
233                        ndef += "\"";
234                        res.push_back(ndef);
235                }
236        }
237        return res;
238}
239
240int Geno_fB::mutate(char *&geno, float &chg, int &method)
241{
242        SString genotype(geno);
243        SString strdims;
244        int pos = 0;
245        genotype.getNextToken(pos, strdims, '\n');
246        SString line;
247        genotype.getNextToken(pos, line, '\n');
248        method = roulette(mutationprobs, FB_MUT_COUNT);
249        switch (method)
250        {
251        case FB_SUBSTITUTION:
252        {
253                std::list<SString> tokenized = tokenizeSequence(line);
254                int rndid = rndUint(tokenized.size()); // select random letter from genotype
255                // increment/decrement character - when overflow happens, this method
256                // uses the "reflect" approach
257                std::list<SString>::iterator it = tokenized.begin();
258                std::advance(it, rndid);
259                SString t = (*it);
260                if ((*it).length() == 1)
261                {
262                        if (rndUint(2) == 0)
263                        {
264                                if ((*it)[0] == 'a') (*it).directWrite()[0] = 'b';
265                                else (*it).directWrite()[0] = (*it)[0] - 1;
266                        }
267                        else
268                        {
269                                if ((*it)[0] == 'z') (*it).directWrite()[0] = 'y';
270                                else (*it).directWrite()[0] = (*it)[0] + 1;
271                        }
272                        chg = 1.0 / line.length();
273                }
274                else
275                {
276                        // first method needs to extract quotes
277                        SString def = (*it);
278                        def = def.substr(1, def.length() - 2);
279                        Geno_fH::mutateNeuronProperties(def);
280                        SString res = "\"";
281                        res += def;
282                        res += "\"";
283                        (*it) = res;
284                        chg = (double)def.length() / line.length();
285                }
286                line = detokenizeSequence(&tokenized);
287                break;
288        }
289        case FB_INSERTION_NEURON:
290        {
291                std::list<SString> tokenized = tokenizeSequence(line);
292                std::list<SString>::iterator it = tokenized.begin();
293                int rndid = rndUint(tokenized.size()); // select random insertion point
294                std::advance(it, rndid);
295                NeuroClass *cls = getRandomNeuroClass(Model::SHAPETYPE_BALL_AND_STICK);
296                if (cls)
297                {
298                        SString classdef = cls->getName();
299                        Geno_fH::mutateNeuronProperties(classdef);
300                        SString res = "\"";
301                        res += classdef;
302                        res += "\"";
303                        tokenized.insert(it, res);
304                        chg = (double)classdef.length() / line.length();
305                        line = detokenizeSequence(&tokenized);
306                        break;
307                }
308        }
309        [[fallthrough]];
310        case FB_INSERTION:
311        {
312                chg = 1.0 / line.length();
313                std::list<SString> tokenized = tokenizeSequence(line);
314                int rndid = rndUint(tokenized.size()); // select random insertion point
315                std::list<SString>::iterator it = tokenized.begin();
316                std::advance(it, rndid);
317                SString letter = "a";
318                letter.directWrite()[0] = 'a' + rndUint(26);
319                tokenized.insert(it, letter);
320                line = detokenizeSequence(&tokenized);
321                break;
322        }
323        case FB_DELETION:
324        {
325                chg = 1.0 / line.length();
326                std::list<SString> tokenized = tokenizeSequence(line);
327                std::list<SString>::iterator it = tokenized.begin();
328                int rndid = rndUint(tokenized.size()); // select random deletion point
329                std::advance(it, rndid);
330                tokenized.erase(it);
331                line = detokenizeSequence(&tokenized);
332                break;
333        }
334        case FB_DUPLICATION:
335        {
336                int rndgene = rndUint(fB_GenoHelpers::geneCount(line));
337                int start, end;
338                SString gene = fB_GenoHelpers::getGene(rndgene, line, start, end);
339                if (gene.indexOf("zz", 0) == -1) gene += "zz";
340                chg = (float)gene.length() / line.length();
341                line = gene + line;
342                break;
343        }
344        case FB_TRANSLOCATION:
345        {
346                std::list<SString> tokenized = tokenizeSequence(line);
347                std::vector<unsigned int> cuts(4);
348                for (int i = 0; i < 4; i++)
349                {
350                        cuts[i] = rndUint(tokenized.size());
351                }
352                std::sort(cuts.begin(), cuts.end());
353                std::vector<std::list<SString>::iterator> iters(4);
354                for (int i = 0; i < 4; i++)
355                {
356                        iters[i] = tokenized.begin();
357                        std::advance(iters[i], cuts[i]);
358                }
359
360                std::list<SString> res;
361                res.insert(res.end(), tokenized.begin(), iters[0]);
362                res.insert(res.end(), iters[2], iters[3]);
363                res.insert(res.end(), iters[1], iters[2]);
364                res.insert(res.end(), iters[0], iters[1]);
365                res.insert(res.end(), iters[3], tokenized.end());
366
367                //              SString first = line.substr(cuts[0], cuts[1] - cuts[0]);
368                //              SString second = line.substr(cuts[2], cuts[3] - cuts[2]);
369                //              SString result = line.substr(0, cuts[0]) + second +
370                //                      line.substr(cuts[1], cuts[2] - cuts[1]) + first + line.substr(cuts[3]);
371                line = detokenizeSequence(&res);
372                chg = (float)(cuts[3] - cuts[2] + cuts[1] - cuts[0]) / line.length();
373                break;
374        }
375        }
376        SString result = strdims + "\n" + line;
377        free(geno);
378        geno = strdup(result.c_str());
379        return GENOPER_OK;
380}
381
382int Geno_fB::crossOver(char *&g1, char *&g2, float& chg1, float& chg2)
383{
384        SString p1(g1);
385        SString p2(g2);
386
387        int dims1 = 0, dims2 = 0;
388        int pos = 0;
389        SString strdims;
390        p1.getNextToken(pos, strdims, '\n');
391        ExtValue::parseInt(strdims.c_str(), dims1, true, false);
392        SString parent1;
393        p1.getNextToken(pos, parent1, '\n');
394
395        pos = 0;
396        p2.getNextToken(pos, strdims, '\n');
397        ExtValue::parseInt(strdims.c_str(), dims2, true, false);
398
399        if (dims1 != dims2)
400        {
401                return GENOPER_OPFAIL;
402        }
403
404        SString parent2;
405        p2.getNextToken(pos, parent2, '\n');
406
407        SString child1 = "";
408        SString child2 = "";
409
410        switch (roulette(crossoverprobs, FB_XOVER_COUNT))
411        {
412        case FB_GENE_TRANSFER:
413        {
414                // get a random gene from the first parent
415                int choice = rndUint(fB_GenoHelpers::geneCount(parent1));
416                int start, end;
417                SString gene = fB_GenoHelpers::getGene(choice, parent1, start, end);
418                // add this gene to the beginning of the second parent genotype
419                child2 = gene + parent2;
420                chg2 = (float)parent2.length() / (float)child2.length();
421                // do the same for the second parent
422                choice = rndUint(fB_GenoHelpers::geneCount(parent2));
423                gene = fB_GenoHelpers::getGene(choice, parent2, start, end);
424                child1 = gene + parent1;
425                chg1 = (float)parent1.length() / (float)child1.length();
426                break;
427        }
428        //      case FB_CROSSING_OVER:
429        //      {
430        //              // iterate through all genes of the first parent and assign them
431        //              // randomly to children
432        //              for (int i = 0; i < fB_GenoHelpers::geneCount(parent1); i++)
433        //              {
434        //                      int start, end;
435        //                      SString gene = fB_GenoHelpers::getGene(i, parent1, start, end);
436        //                      if (rndUint(2) == 0)
437        //                      {
438        //                              child1 += gene;
439        //                              chg1 += 1.0f;
440        //                      }
441        //                      else
442        //                      {
443        //                              child2 += gene;
444        //                      }
445        //              }
446        //              chg1 /= fB_GenoHelpers::geneCount(parent1);
447        //
448        //              // do the same with second parent
449        //              for (int i = 0; i < fB_GenoHelpers::geneCount(parent2); i++)
450        //              {
451        //                      int start, end;
452        //                      SString gene = fB_GenoHelpers::getGene(i, parent2, start, end);
453        //                      if (rndUint(2) == 0)
454        //                      {
455        //                              child1 += gene;
456        //                      }
457        //                      else
458        //                      {
459        //                              child2 += gene;
460        //                              chg2 += 1.0f;
461        //                      }
462        //              }
463        //              chg2 /= fB_GenoHelpers::geneCount(parent2);
464        //              break;
465        //      }
466        case FB_CROSSING_OVER:
467        {
468                // get maximal count of genes from both parents
469                int maxgenecount = std::max(fB_GenoHelpers::geneCountNoNested(parent1),
470                        fB_GenoHelpers::geneCountNoNested(parent2));
471
472                // while there are genes in at least one genotype
473                for (int i = 0; i < maxgenecount; i++)
474                {
475                        SString to1 = "", to2 = "";
476                        int start = 0, end = 0;
477
478                        // if both parents have genes available, then distribute them
479                        if (i < fB_GenoHelpers::geneCountNoNested(parent1) &&
480                                i < fB_GenoHelpers::geneCountNoNested(parent2))
481                        {
482                                if (rndUint(2) == 0)
483                                {
484                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
485                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
486                                        chg1 += 1.0f;
487                                        chg2 += 1.0f;
488                                }
489                                else
490                                {
491                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
492                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
493                                }
494                        }
495                        else if (i < fB_GenoHelpers::geneCountNoNested(parent1))
496                        {
497                                if (rndUint(2) == 0)
498                                {
499                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
500                                        chg1 += 1.0f;
501                                }
502                                else
503                                {
504                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
505                                }
506                        }
507                        else // if (i < fB_GenoHelpers::geneCountNoNested(parent2))
508                        {
509                                if (rndUint(2) == 0)
510                                {
511                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
512                                }
513                                else
514                                {
515                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
516                                        chg2 += 1.0f;
517                                }
518                        }
519                        child1 += to1;
520                        child2 += to2;
521                }
522
523                chg1 /= fB_GenoHelpers::geneCountNoNested(parent1);
524                chg2 /= fB_GenoHelpers::geneCountNoNested(parent2);
525                break;
526        }
527        }
528
529        free(g1);
530        free(g2);
531        if (child1.length() > 0 && child2.length() == 0)
532        {
533                child1 = strdims + "\n" + child1;
534                g1 = strdup(child1.c_str());
535                g2 = strdup("");
536        }
537        else if (child2.length() > 0 && child1.length() == 0)
538        {
539                child2 = strdims + "\n" + child2;
540                g1 = strdup(child2.c_str());
541                g2 = strdup("");
542        }
543        else
544        {
545                child1 = strdims + "\n" + child1;
546                child2 = strdims + "\n" + child2;
547                g1 = strdup(child1.c_str());
548                g2 = strdup(child2.c_str());
549        }
550        return GENOPER_OK;
551}
552
553uint32_t Geno_fB::style(const char *geno, int pos)
554{
555        char ch = geno[pos];
556        if (isdigit(ch))
557        {
558                while (pos > 0)
559                {
560                        pos--;
561                        if (isdigit(geno[pos]) == 0) //going left we encountered some non-digit character
562                        {
563                                return GENSTYLE_CS(GENCOLOR_NUMBER, GENSTYLE_NONE); //so 'ch' is any digit in the genotype (neural property value etc.); for simplicity, digits as parts of neuroclass name or property name also get included here
564                        }
565                }
566                return GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD); //only digits up to the beginning, so this is the dimensionality value
567        }
568        if (ch == '-' || ch == '.')
569                return GENSTYLE_CS(GENCOLOR_NUMBER, GENSTYLE_NONE);
570        if (ch == '"')
571                return GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); //quotes encompass neuron definitions. To further distinguish the text inside quotes from the text outside quotes, we would need to determine the number of '"' from the beginning, i.e. linear search through the entire genotype. We don't want to do it - it would mean the complexity of len(geno)^2 if performed for each symbol in the genotype independently, like this function does. Below we perform an approximate partial scan.
572        if (isupper(ch) || strchr("@|*", ch))
573                return GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); //neuroclass
574        if (strchr(":,=", ch))
575                return GENSTYLE_RGBS(150, 0, 150, GENSTYLE_NONE); //these symbols occur exclusively inside "...neuron...", so let's make the entire neuron section "...neuron..." more visually uniform by using the same violet color as the neuroclass name and quotes have
576        if (islower(ch)) //how to color the current lower-case letter?
577        {
578                static const int SCAN_RANGE = 8; //how many characters before the current one to scan to discover some context and find out if we are likely in the neuroclass name or the property name. Reduces computational complexity. Example genotype fragments: abcabc"T:r=0.9, ry=4.088, rz=1.213"abcabc or abc"N:in=0.0, fo=0.17, si=999.0"abc
579                int i = pos;
580                while (i > 0 && pos - i < SCAN_RANGE)
581                {
582                        i--; //go back one char
583                        if (isupper(geno[i]))
584                                return GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); //neuroclass
585                        if (geno[i] == ',' || geno[i] == ':') //this is what must occur before property name starts
586                                return GENSTYLE_RGBS(255, 140, 0, GENSTYLE_BOLD); //property
587                        if (!(isalpha(geno[i]) || isspace(geno[i]))) //going left we encountered any char that is not a letter or space
588                                break;
589                }
590        }
591
592        uint32_t style = GENSTYLE_CS(GENCOLOR_TEXT, GENSTYLE_NONE); //if the current character did not fall into any of the above cases, assume default black style
593        if (ch == 'a' && (geno[pos + 1] == 'a' || (pos > 0 && geno[pos - 1] == 'a'))) //start codon, "aa"
594        {
595                style = GENSTYLE_RGBS(0, 200, 0, GENSTYLE_BOLD);
596        }
597        else if (ch == 'z' && (geno[pos + 1] == 'z' || (pos > 0 && geno[pos - 1] == 'z'))) //stop codon, "zz"
598        {
599                style = GENSTYLE_RGBS(200, 0, 0, GENSTYLE_BOLD);
600        }
601        return style;
602}
Note: See TracBrowser for help on using the repository browser.