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

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

Crossing over with less bloat, but still biologically-inspired
File size: 14.8 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2018  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#include <frams/util/sstring.h>
6#include <vector>
7#include <frams/param/param.h>
8#include "fB_conv.h"
9#include "fB_general.h"
10#include "fB_oper.h"
11#include "../fH/fH_oper.h"
12
13#define FIELDSTRUCT Geno_fB
14
15static ParamEntry GENOfBparam_tab[] =
16{
17        { "Genetics: fB", 3, FB_MUT_COUNT + FB_XOVER_COUNT, },
18        { "Genetics: fB: Mutation", },
19        { "Genetics: fB: Crossover", },
20        { "fB_mut_substitution", 1, 0, "Substitution", "f 0 1 0.6", FIELD(mutationprobs[FB_SUBSTITUTION]), "Probability of mutation by changing single random letter in genotype", },
21        { "fB_mut_insertion", 1, 0, "Insertion", "f 0 1 0.095", FIELD(mutationprobs[FB_INSERTION]), "Probability of mutation by inserting characters in random place of genotype", },
22        { "fB_mut_nclassins", 1, 0, "Insertion of neuron class definition", "f 0 1 0.005", FIELD(mutationprobs[FB_NCLASSINS]), "Probability of mutation by inserting neuron class definition in random place of genotype", },
23        { "fB_mut_deletion", 1, 0, "Deletion", "f 0 1 0.1", FIELD(mutationprobs[FB_DELETION]), "Probability of mutation by deleting random characters in genotype", },
24        { "fB_mut_duplication", 1, 0, "Duplication", "f 0 1 0.0", FIELD(mutationprobs[FB_DUPLICATION]), "Probability of mutation by copying single *gene* of genotype and appending it to the beginning of this genotype", },
25        { "fB_mut_translocation", 1, 0, "Translocation", "f 0 1 0.15", FIELD(mutationprobs[FB_TRANSLOCATION]), "Probability of mutation by replacing two substrings in genotype", },
26        { "fB_cross_gene_transfer", 2, 0, "Horizontal gene transfer", "f 0 1 0.0", FIELD(crossoverprobs[FB_GENE_TRANSFER]), "Probability of crossing over by transferring single genes from both parents to beginning of each other", },
27        { "fB_cross_crossover", 2, 0, "Crossing over", "f 0 1 1.0", FIELD(crossoverprobs[FB_CROSSING_OVER]), "Probability of crossing over by random distribution of genes from both parents to both children", },
28        { 0, },
29};
30
31#undef FIELDSTRUCT
32
33Geno_fB::Geno_fB()
34{
35        par.setParamTab(GENOfBparam_tab);
36        par.select(this);
37        par.setDefault();
38        supported_format = 'B';
39}
40
41bool Geno_fB::hasStick(SString genotype)
42{
43        for (int i = 0; i < fB_GenoHelpers::geneCount(genotype); i++)
44        {
45                int start, end;
46                SString gene = fB_GenoHelpers::getGene(i, genotype, start, end);
47                int endoffset = 0;
48                if (gene.indexOf("zz", 0) != -1) endoffset = 2;
49                if (gene.len() - endoffset < 3)
50                {
51                        return true; // genes with length < 3 are always sticks
52                }
53                else if (gene[2] >= 'a' && gene[2] <= 'i')
54                {
55                        return true; // gene within this range is stick
56                }
57        }
58        return false;
59}
60
61int Geno_fB::checkValidity(const char *geno, const char *genoname)
62{
63        // load genotype
64        SString genotype(geno);
65        SString line;
66        int pos = 0;
67        // if there is no genotype to load, then return error
68        if (!genotype.getNextToken(pos, line, '\n'))
69        {
70                return pos + 1;
71        }
72        // extract dimensions
73        int dims = 0;
74        if (!ExtValue::parseInt(line.c_str(), dims, true, false))
75        {
76                return 1;
77        }
78        // extract next token in order to check if next line starts with "aa"
79        int genstart = genotype.indexOf("aa", 0);
80        if (genstart != pos)
81        {
82                return pos + 1;
83        }
84        // check if rest of characters are lowercase
85        for (int i = genstart; i < genotype.len(); i++)
86        {
87                if (!islower(genotype[i]))
88                {
89                        if (genotype[i] == '"')
90                        {
91                                SString neuclassdef;
92                                int nextid = i + 1;
93                                if (!genotype.getNextToken(nextid, neuclassdef, '"'))
94                                {
95                                        return i + 1;
96                                }
97                                Neuro *neu = new Neuro();
98                                neu->setDetails(neuclassdef);
99
100                                bool isclass = neu->getClass() ? true : false;
101                                delete neu;
102                                if (!isclass)
103                                {
104                                        return i + 1;
105                                }
106                                i = nextid;
107                        }
108                        else
109                        {
110                                return i + 1;
111                        }
112                }
113        }
114        if (!hasStick(genotype))
115        {
116                return 1;
117        }
118        return GENOPER_OK;
119}
120
121int Geno_fB::validate(char *&geno, const char *genoname)
122{
123        // load genotype
124        SString genotype(geno);
125        SString strdims;
126        int pos = 0;
127        if (!genotype.getNextToken(pos, strdims, '\n'))
128        {
129                return GENOPER_OPFAIL;
130        }
131        // parse dimension
132        int dims = 0;
133        if (!ExtValue::parseInt(strdims.c_str(), dims, true, false))
134        {
135                return GENOPER_OPFAIL;
136        }
137        SString line;
138        bool fix = false;
139        int genstart = genotype.indexOf("aa", 0);
140        // if there is no "aa" codon in the beginning of a genotype, then add it
141        if (genstart != pos)
142        {
143                genotype = strdims + "\naa" + genotype.substr(pos);
144                fix = true;
145        }
146        for (int i = pos; i < genotype.len(); i++)
147        {
148                // if character is not alphabetic - error
149                if (!isalpha(genotype[i]))
150                {
151                        if (genotype[i] == '"')
152                        {
153                                SString neuclassdef;
154                                int nextid = i + 1;
155                                if (!genotype.getNextToken(nextid, neuclassdef, '"'))
156                                {
157                                        return i + 1;
158                                }
159                                Neuro *neu = new Neuro();
160                                neu->setDetails(neuclassdef);
161
162                                bool isclass = neu->getClass() ? true : false;
163                                delete neu;
164                                if (!isclass)
165                                {
166                                        return i + 1;
167                                }
168                                i = nextid;
169                        }
170                        else
171                        {
172                                return GENOPER_OPFAIL;
173                        }
174                }
175                // if character is uppercase, then convert it to lowercase
176                else if (isupper(genotype[i]))
177                {
178                        genotype.directWrite()[i] = tolower(genotype[i]);
179                        fix = true;
180                }
181        }
182        // if the genotype does not contain any stick - add it
183        if (!hasStick(genotype))
184        {
185                genotype = SString("aaazz") + genotype;
186        }
187        // if there were any changes - save them
188        if (fix)
189        {
190                free(geno);
191                geno = strdup(genotype.c_str());
192        }
193        return GENOPER_OK;
194}
195
196SString Geno_fB::detokenizeSequence(std::list<SString> tokenlist)
197{
198        SString res = "";
199        for (std::list<SString>::iterator it = tokenlist.begin(); it != tokenlist.end(); it++)
200        {
201                res += (*it);
202        }
203        return res;
204}
205
206std::list<SString> Geno_fB::tokenizeSequence(SString genotype)
207{
208        std::list<SString> res;
209        int i = 0;
210        while (i < genotype.len())
211        {
212                // if character is not alphabetic - error
213                if (isalpha(genotype[i]))
214                {
215                        SString el = "";
216                        el += genotype[i];
217                        res.push_back(el);
218                        i++;
219                }
220                else
221                {
222                        SString neuclassdef;
223                        i++;
224                        genotype.getNextToken(i, neuclassdef, '"');
225                        SString ndef = "\"";
226                        ndef += neuclassdef;
227                        ndef += "\"";
228                        res.push_back(ndef);
229                }
230        }
231        return res;
232}
233
234int Geno_fB::mutate(char *&geno, float &chg, int &method)
235{
236        SString genotype(geno);
237        SString strdims;
238        int pos = 0;
239        genotype.getNextToken(pos, strdims, '\n');
240        SString line;
241        genotype.getNextToken(pos, line, '\n');
242        method = roulette(mutationprobs, FB_MUT_COUNT);
243        switch (method)
244        {
245        case FB_SUBSTITUTION:
246        {
247                std::list<SString> tokenized = tokenizeSequence(line);
248                int rndid = randomN(tokenized.size()); // select random letter from genotype
249                // increment/decrement character - when overflow happens, this method
250                // uses reflect method
251                std::list<SString>::iterator it = tokenized.begin();
252                std::advance(it, rndid);
253                SString t = (*it);
254                if ((*it).len() == 1)
255                {
256                        if (randomN(2) == 0)
257                        {
258                                if ((*it)[0] == 'a') (*it).directWrite()[0] = 'b';
259                                else (*it).directWrite()[0] = (*it)[0] - 1;
260                        }
261                        else
262                        {
263                                if ((*it)[0] == 'z') (*it).directWrite()[0] = 'y';
264                                else (*it).directWrite()[0] = (*it)[0] + 1;
265                        }
266                        chg = 1.0 / line.len();
267                }
268                else
269                {
270                        // first method needs to extract quotes
271                        SString def = (*it);
272                        def = def.substr(1, def.len() - 2);
273                        Geno_fH::mutateNeuronProperties(def);
274                        SString res = "\"";
275                        res += def;
276                        res += "\"";
277                        (*it) = res;
278                        chg = (double)def.len() / line.len();
279                }
280                line = detokenizeSequence(tokenized);
281                break;
282        }
283        case FB_NCLASSINS:
284        {
285                std::list<SString> tokenized = tokenizeSequence(line);
286                std::list<SString>::iterator it = tokenized.begin();
287                int rndid = randomN(tokenized.size()); // select random insertion point
288                std::advance(it, rndid);
289                NeuroClass *cls = getRandomNeuroClass();
290                if (cls)
291                {
292                        SString classdef = cls->getName();
293                        Geno_fH::mutateNeuronProperties(classdef);
294                        SString res = "\"";
295                        res += classdef;
296                        res += "\"";
297                        tokenized.insert(it, res);
298                        chg = (double)classdef.len() / line.len();
299                        line = detokenizeSequence(tokenized);
300                        break;
301                }
302        }
303        /* no break */
304        case FB_INSERTION:
305        {
306                chg = 1.0 / line.len();
307                std::list<SString> tokenized = tokenizeSequence(line);
308                int rndid = randomN(tokenized.size()); // select random insertion point
309                std::list<SString>::iterator it = tokenized.begin();
310                std::advance(it, rndid);
311                SString letter = "a";
312                letter.directWrite()[0] = 'a' + randomN(26);
313                tokenized.insert(it, letter);
314                line = detokenizeSequence(tokenized);
315                break;
316        }
317        case FB_DELETION:
318        {
319                chg = 1.0 / line.len();
320                std::list<SString> tokenized = tokenizeSequence(line);
321                std::list<SString>::iterator it = tokenized.begin();
322                int rndid = randomN(tokenized.size()); // select random deletion point
323                std::advance(it, rndid);
324                tokenized.erase(it);
325                line = detokenizeSequence(tokenized);
326                break;
327        }
328        case FB_DUPLICATION:
329        {
330                int rndgene = randomN(fB_GenoHelpers::geneCount(line));
331                int start, end;
332                SString gene = fB_GenoHelpers::getGene(rndgene, line, start, end);
333                if (gene.indexOf("zz", 0) == -1) gene += "zz";
334                chg = (float)gene.len() / line.len();
335                line = gene + line;
336                break;
337        }
338        case FB_TRANSLOCATION:
339        {
340                std::list<SString> tokenized = tokenizeSequence(line);
341                std::vector<unsigned int> cuts(4);
342                for (int i = 0; i < 4; i++)
343                {
344                        cuts[i] = randomN(tokenized.size());
345                }
346                std::sort(cuts.begin(), cuts.end());
347                std::vector<std::list<SString>::iterator> iters(4);
348                for (int i = 0; i < 4; i++)
349                {
350                        iters[i] = tokenized.begin();
351                        std::advance(iters[i], cuts[i]);
352                }
353
354                std::list<SString> res;
355                res.insert(res.end(), tokenized.begin(), iters[0]);
356                res.insert(res.end(), iters[2], iters[3]);
357                res.insert(res.end(), iters[1], iters[2]);
358                res.insert(res.end(), iters[0], iters[1]);
359                res.insert(res.end(), iters[3], tokenized.end());
360
361//              SString first = line.substr(cuts[0], cuts[1] - cuts[0]);
362//              SString second = line.substr(cuts[2], cuts[3] - cuts[2]);
363//              SString result = line.substr(0, cuts[0]) + second +
364//                      line.substr(cuts[1], cuts[2] - cuts[1]) + first + line.substr(cuts[3]);
365                line = detokenizeSequence(res);
366                chg = (float)(cuts[3] - cuts[2] + cuts[1] - cuts[0]) / line.len();
367                break;
368        }
369        }
370        SString result = strdims + "\n" + line;
371        free(geno);
372        geno = strdup(result.c_str());
373        return GENOPER_OK;
374}
375
376int Geno_fB::crossOver(char *&g1, char *&g2, float& chg1, float& chg2)
377{
378        SString p1(g1);
379        SString p2(g2);
380
381        int dims1 = 0, dims2 = 0;
382        int pos = 0;
383        SString strdims;
384        p1.getNextToken(pos, strdims, '\n');
385        ExtValue::parseInt(strdims.c_str(), dims1, true, false);
386        SString parent1;
387        p1.getNextToken(pos, parent1, '\n');
388
389        pos = 0;
390        p2.getNextToken(pos, strdims, '\n');
391        ExtValue::parseInt(strdims.c_str(), dims2, true, false);
392
393        if (dims1 != dims2)
394        {
395                return GENOPER_OPFAIL;
396        }
397
398        SString parent2;
399        p2.getNextToken(pos, parent2, '\n');
400
401        SString child1 = "";
402        SString child2 = "";
403
404        switch (roulette(crossoverprobs, FB_XOVER_COUNT))
405        {
406        case FB_GENE_TRANSFER:
407        {
408                // get random gene from first parent
409                int choice = randomN(fB_GenoHelpers::geneCount(parent1));
410                int start, end;
411                SString gene = fB_GenoHelpers::getGene(choice, parent1, start, end);
412                // add this gene to the beginning of the second parent genotype
413                child2 = gene + parent2;
414                chg2 = (float)parent2.len() / (float)child2.len();
415                // do the same for second parent
416                choice = randomN(fB_GenoHelpers::geneCount(parent2));
417                gene = fB_GenoHelpers::getGene(choice, parent2, start, end);
418                child1 = gene + parent1;
419                chg1 = (float)parent1.len() / (float)child1.len();
420                break;
421        }
422//      case FB_CROSSING_OVER:
423//      {
424//              // iterate through all genes of the first parent and assign them
425//              // randomly to children
426//              for (int i = 0; i < fB_GenoHelpers::geneCount(parent1); i++)
427//              {
428//                      int start, end;
429//                      SString gene = fB_GenoHelpers::getGene(i, parent1, start, end);
430//                      if (randomN(2) == 0)
431//                      {
432//                              child1 += gene;
433//                              chg1 += 1.0f;
434//                      }
435//                      else
436//                      {
437//                              child2 += gene;
438//                      }
439//              }
440//              chg1 /= fB_GenoHelpers::geneCount(parent1);
441//
442//              // do the same with second parent
443//              for (int i = 0; i < fB_GenoHelpers::geneCount(parent2); i++)
444//              {
445//                      int start, end;
446//                      SString gene = fB_GenoHelpers::getGene(i, parent2, start, end);
447//                      if (randomN(2) == 0)
448//                      {
449//                              child1 += gene;
450//                      }
451//                      else
452//                      {
453//                              child2 += gene;
454//                              chg2 += 1.0f;
455//                      }
456//              }
457//              chg2 /= fB_GenoHelpers::geneCount(parent2);
458//              break;
459//      }
460        case FB_CROSSING_OVER:
461        {
462                // get maximal count of genes from both parents
463                int maxgenecount = max(fB_GenoHelpers::geneCountNoNested(parent1),
464                                fB_GenoHelpers::geneCountNoNested(parent2));
465
466                // while there are genes in at least one genotype
467                for (int i = 0; i < maxgenecount; i++)
468                {
469                        SString to1 = "", to2 = "";
470                        int start = 0, end = 0;
471
472                        // if both parents have genes available, then distribute them
473                        if (i < fB_GenoHelpers::geneCountNoNested(parent1) &&
474                                        i < fB_GenoHelpers::geneCountNoNested(parent2))
475                        {
476                                if (randomN(2) == 0)
477                                {
478                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
479                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
480                                        chg1 += 1.0f;
481                                        chg2 += 1.0f;
482                                }
483                                else
484                                {
485                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
486                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
487                                }
488                        }
489                        else if (i < fB_GenoHelpers::geneCountNoNested(parent1))
490                        {
491                                if (randomN(2) == 0)
492                                {
493                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
494                                        chg1 += 1.0f;
495                                }
496                                else
497                                {
498                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent1, start, end);
499                                }
500                        }
501                        else // if (i < fB_GenoHelpers::geneCountNoNested(parent2))
502                        {
503                                if (randomN(2) == 0)
504                                {
505                                        to1 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
506                                }
507                                else
508                                {
509                                        to2 = fB_GenoHelpers::getNonNestedGene(i, parent2, start, end);
510                                        chg2 += 1.0f;
511                                }
512                        }
513                        child1 += to1;
514                        child2 += to2;
515                }
516
517                chg1 /= fB_GenoHelpers::geneCountNoNested(parent1);
518                chg2 /= fB_GenoHelpers::geneCountNoNested(parent2);
519                break;
520        }
521        }
522
523        free(g1);
524        free(g2);
525        if (child1.len() > 0 && child2.len() == 0)
526        {
527                child1 = strdims + "\n" + child1;
528                g1 = strdup(child1.c_str());
529                g2 = strdup("");
530        }
531        else if (child2.len() > 0 && child1.len() == 0)
532        {
533                child2 = strdims + "\n" + child2;
534                g1 = strdup(child2.c_str());
535                g2 = strdup("");
536        }
537        else
538        {
539                child1 = strdims + "\n" + child1;
540                child2 = strdims + "\n" + child2;
541                g1 = strdup(child1.c_str());
542                g2 = strdup(child2.c_str());
543        }
544        return GENOPER_OK;
545}
546
547uint32_t Geno_fB::style(const char *geno, int pos)
548{
549        char ch = geno[pos];
550        if (isdigit(ch))
551        {
552                while (pos > 0)
553                {
554                        pos--;
555                        if (isdigit(geno[pos]) == 0)
556                        {
557                                return GENSTYLE_CS(0, GENSTYLE_INVALID);
558                        }
559                }
560                return GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD);
561        }
562        if (islower(ch) == 0)
563        {
564                return GENSTYLE_CS(0, GENSTYLE_INVALID);
565        }
566        uint32_t style = GENSTYLE_CS(GENCOLOR_TEXT, GENSTYLE_NONE);
567        if (ch == 'a' && pos > 0 && (geno[pos - 1] == 'a' || geno[pos - 1] == '\n'))
568        {
569                style = GENSTYLE_RGBS(0, 200, 0, GENSTYLE_BOLD);
570        }
571        else if (ch == 'z' && pos > 0 && geno[pos - 1] == 'z')
572        {
573                style = GENSTYLE_RGBS(200, 0, 0, GENSTYLE_BOLD);
574        }
575        return style;
576}
Note: See TracBrowser for help on using the repository browser.