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 | // Copyright (C) 1999,2000 Adam Rotaru-Varga (adam_rotaru@yahoo.com), GNU LGPL |
---|
6 | // Copyright (C) since 2001 Maciej Komosinski |
---|
7 | // 2018, Grzegorz Latosinski, added support for new API for neuron types and their properties |
---|
8 | |
---|
9 | |
---|
10 | // This representation has a tendency to bloat - adding a small penalty to fitness such as "this.velocity - 0.000000001*String.len(this.genotype);" |
---|
11 | // may help, but it would be better to improve the source code to make genetic operators neutral in terms of genotype length. Adding such a penalty |
---|
12 | // removes "work in progress" changes in genotypes thus promoting immediate, straightforward improvements while hindering slower, multifaceted progress. |
---|
13 | // TODO getting rid of redundancy (having valid genotypes with a lot of "junk code") in this representation looks like a good idea. |
---|
14 | // |
---|
15 | // Note: symbols after the last > are ignored, for example /*4*/<X>N:N>blablaN:N[2:-0.5]XXXwhatever but since they are not parsed into the f4_Node tree, they will be lost after any mutation. |
---|
16 | // |
---|
17 | // TODO the behavior of neuron input indexes during mutation seems badly implemented (see also TREAT_BAD_CONNECTIONS_AS_INVALID_GENO). Are they kept properly maintained when nodes are added and removed? This could be done well because during mutation we operate on the tree structure with cross-references between nodes (so they should not be affected by local changes in the tree), and then convert the tree back to string. Yet, the f4_Node.conn_from is an integer and these fields in nodes do not seem to be maintained on tree node adding/removal... change these integer offsets to references to node objects? But actually, do the offsets that constitute relative connection references concern the f4_Node tree structure (and all these sophisticated calculations of offsets during mutation are useful) or rather they concern the f4_Cells development? verify all situations in f4_Cell::oneStep(), case '['. |
---|
18 | // TODO add simplifying sequences of modifiers (so capital and small letter cancel out, like in f1) - but seems like each single modifier is a separate f4_Node? and perhaps we don't want to use the repair mechanism for this... maybe mutations, when they add/modify/remove a modifier node, should be "cleaning" the tree by removing nodes when they encounter contradictory modifiers on the same subpath, and also limit the number of modifiers of each type just like in f1? To avoid squences like ...<X>llmlIilImmimiimmimifmfl<fifmmimilimmmiimiliffmfliIfififlliflimfliffififmiffmfliflifmIlimimiflimfiffmllliflmimifllifliliflifmIlimimiflimfiffmllliflmimifllfmIlimimiflimfiffmllliflmimiflliflimimmiflimfliffmiflifmfiffllIlififliffififmiffmfliflifIliflimimflimflfflimimifllfflifllfflimlififfiiffifIr<r<... |
---|
19 | // TODO add support for properties of (any class of) neurons - not just sigmoid/force/intertia (':' syntax) for N |
---|
20 | // TODO add mapping genotype character ranges for neural [connections] |
---|
21 | |
---|
22 | |
---|
23 | #include "f4_oper.h" |
---|
24 | #include <frams/util/sstring.h> |
---|
25 | #include <common/log.h> |
---|
26 | |
---|
27 | #include <stdio.h> |
---|
28 | #include <stdlib.h> |
---|
29 | #include "common/nonstd_math.h" |
---|
30 | #include <string.h> |
---|
31 | |
---|
32 | |
---|
33 | const char *Geno_f4::all_modifiers = F14_MODIFIERS ","; //comma in f4 is handled the same way (simple node, F4_ADD_SIMP) as modifiers |
---|
34 | |
---|
35 | // codes that can be changed (apart from being added/deleted) |
---|
36 | #define F4_MUT_CHANGE_CODES "<[#" |
---|
37 | |
---|
38 | #define FIELDSTRUCT Geno_f4 |
---|
39 | |
---|
40 | static ParamEntry geno_f4_paramtab[] = |
---|
41 | { |
---|
42 | { "Genetics: f4", 1, F4_COUNT + F4_ADD_COUNT + F4_MODNEU_COUNT + 2, }, |
---|
43 | { "f4_mut_add", 0, 0, "Add node", "f 0 100 50", FIELD(prob[F4_ADD]), "Mutation: probability of adding a node", }, |
---|
44 | { "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", }, |
---|
45 | { "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", }, |
---|
46 | { "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", }, |
---|
47 | { "f4_mut_add_rep", 0, 0, "- add repetition '#'", "f 0 100 10", FIELD(probadd[F4_ADD_REP]), "Add node mutation: probability of adding the '#' repetition gene", }, |
---|
48 | { "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", }, |
---|
49 | |
---|
50 | { "f4_mut_del", 0, 0, "Delete node", "f 0 100 20", FIELD(prob[F4_DEL]), "Mutation: probability of deleting a node", }, |
---|
51 | |
---|
52 | { "f4_mut_mod", 0, 0, "Modify node", "f 0 100 30", FIELD(prob[F4_MOD]), "Mutation: probability of changing a node", }, |
---|
53 | { "f4_mut_modneu_conn", 0, 0, "- neuron input: modify source", "f 0 100 60", FIELD(probmodneu[F4_MODNEU_CONN]), "Neuron input mutation: probability of changing its source neuron", }, |
---|
54 | { "f4_mut_modneu_weight", 0, 0, "- neuron input: modify weight", "f 0 100 40", FIELD(probmodneu[F4_MODNEU_WEIGHT]), "Neuron input mutation: probability of changing its weight", }, |
---|
55 | |
---|
56 | { "f4_mut_max_rep", 1, 0, "Maximum number for '#' repetitions", "d 2 20 6", FIELD(mut_max_rep), "Maximum allowed number of repetitions for the '#' repetition gene", }, |
---|
57 | { "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: " F14_MODIFIERS ")", }, |
---|
58 | { 0, }, |
---|
59 | }; |
---|
60 | |
---|
61 | #undef FIELDSTRUCT |
---|
62 | |
---|
63 | |
---|
64 | Geno_f4::Geno_f4() |
---|
65 | { |
---|
66 | supported_format = '4'; |
---|
67 | par.setParamTab(geno_f4_paramtab); |
---|
68 | par.select(this); |
---|
69 | par.setDefault(); |
---|
70 | |
---|
71 | mutation_method_names = new const char*[F4_COUNT + F4_ADD_COUNT - 1]; |
---|
72 | int index = 0; |
---|
73 | mutation_method_names[index++] = "added division"; |
---|
74 | mutation_method_names[index++] = "added neural connection"; |
---|
75 | mutation_method_names[index++] = "added neuron property"; |
---|
76 | mutation_method_names[index++] = "added repetition gene"; |
---|
77 | mutation_method_names[index++] = "added a simple node"; |
---|
78 | mutation_method_names[index++] = "deleted a node"; |
---|
79 | mutation_method_names[index++] = "modified a node"; |
---|
80 | if (index != F4_COUNT + F4_ADD_COUNT - 1) logMessage("Geno_f4", "Constructor", LOG_CRITICAL, "Mutation names init error"); |
---|
81 | } |
---|
82 | |
---|
83 | void Geno_f4::setDefaults() |
---|
84 | { |
---|
85 | excluded_modifiers = F14_MODIFIERS_RARE F14_MODIFIERS_VISUAL; |
---|
86 | } |
---|
87 | |
---|
88 | int Geno_f4::ValidateRec(f4_Node *geno, int retrycount) const |
---|
89 | { |
---|
90 | // ! the genotype is geno->child (not geno) ! |
---|
91 | // build from it with repair on |
---|
92 | |
---|
93 | f4_Cells cells(geno->child, 1); |
---|
94 | cells.simulate(); //we should simulate?! |
---|
95 | |
---|
96 | // errors not fixed: |
---|
97 | if (cells.getErrorCode() == GENOPER_OPFAIL) |
---|
98 | { |
---|
99 | if (cells.getErrorPos() >= 0) return 1 + cells.getErrorPos(); |
---|
100 | return GENOPER_OPFAIL; |
---|
101 | } |
---|
102 | // errors can be fixed |
---|
103 | if (cells.getErrorCode() == GENOPER_REPAIR) |
---|
104 | { |
---|
105 | cells.repairGeno(geno, 1); |
---|
106 | // note: geno might have been fixed |
---|
107 | // check again |
---|
108 | int res2 = GENOPER_OK; |
---|
109 | if (retrycount > 0) |
---|
110 | res2 = ValidateRec(geno, retrycount - 1); |
---|
111 | |
---|
112 | if (res2 == GENOPER_OK) return GENOPER_REPAIR; |
---|
113 | return res2; |
---|
114 | } |
---|
115 | // no errors: |
---|
116 | return GENOPER_OK; |
---|
117 | } |
---|
118 | |
---|
119 | |
---|
120 | int Geno_f4::validate(char *& geno, const char *genoname) |
---|
121 | { |
---|
122 | // convert geno to a tree, then try to validate |
---|
123 | f4_Node root; |
---|
124 | if (f4_processRecur(geno, 0, &root) || root.childCount() != 1) return GENOPER_OK; // cannot repair |
---|
125 | |
---|
126 | const int VALIDATE_TRIALS = 20; |
---|
127 | if (ValidateRec(&root, VALIDATE_TRIALS) == GENOPER_REPAIR) // if repaired, make it back to string |
---|
128 | { |
---|
129 | geno[0] = 0; |
---|
130 | root.child->sprintAdj(geno); |
---|
131 | } |
---|
132 | return GENOPER_OK; |
---|
133 | } |
---|
134 | |
---|
135 | |
---|
136 | int Geno_f4::checkValidity(const char* geno, const char *genoname) |
---|
137 | { |
---|
138 | f4_Node root; |
---|
139 | int res = f4_processRecur(geno, 0, &root); |
---|
140 | if (res) return res; // errorpos, >0 |
---|
141 | if (root.childCount() != 1) return 1; //earlier: GENOPER_OPFAIL |
---|
142 | f4_Cells cells(root.child, 0); |
---|
143 | cells.simulate(); |
---|
144 | if (cells.getErrorCode() == GENOPER_OPFAIL || cells.getErrorCode() == GENOPER_REPAIR) |
---|
145 | { |
---|
146 | if (cells.getErrorPos() >= 0) return 1 + cells.getErrorPos(); |
---|
147 | else return 1; //earlier: GENOPER_OPFAIL; |
---|
148 | } |
---|
149 | else return GENOPER_OK; |
---|
150 | } |
---|
151 | |
---|
152 | |
---|
153 | int Geno_f4::MutateOne(f4_Node *& g, int &method) const |
---|
154 | { |
---|
155 | // ! the genotype is g->child (not g) ! |
---|
156 | |
---|
157 | // do the mutation |
---|
158 | // pick a random node |
---|
159 | f4_Node *node_mutated = g->child->randomNode(); |
---|
160 | //DB( printf("%c\n", node_mutated->name); ) |
---|
161 | |
---|
162 | switch (roulette(prob, F4_COUNT)) |
---|
163 | { |
---|
164 | case F4_ADD: |
---|
165 | { |
---|
166 | // add a node |
---|
167 | switch (method = roulette(probadd, F4_ADD_COUNT)) |
---|
168 | { |
---|
169 | case F4_ADD_DIV: |
---|
170 | { |
---|
171 | // add division ('<') |
---|
172 | f4_Node *node_mutated_parent = node_mutated->parent; |
---|
173 | node_mutated_parent->removeChild(node_mutated); |
---|
174 | f4_Node *node_new_div = new f4_Node('<', node_mutated_parent, node_mutated_parent->pos); |
---|
175 | node_new_div->addChild(node_mutated); |
---|
176 | // new cell is stick or neuron |
---|
177 | // "X>" or "N>" |
---|
178 | constexpr double STICK_OR_NEURON = 0.5; // hardcoded probability... could be parametrized, but in a general case (unknown fitness goal) 0.5 makes sense? |
---|
179 | f4_Node *node_new = NULL; //stick or neuron or neural connection |
---|
180 | if (rndDouble(1) < STICK_OR_NEURON) |
---|
181 | node_new = new f4_Node('X', node_new_div, node_new_div->pos); |
---|
182 | else |
---|
183 | { |
---|
184 | // make neuron |
---|
185 | NeuroClass *rndclass = GenoOperators::getRandomNeuroClass(Model::SHAPETYPE_BALL_AND_STICK); |
---|
186 | if (rndclass == NULL) //no active neurons? |
---|
187 | { |
---|
188 | node_new = new f4_Node('X', node_new_div, node_new_div->pos); |
---|
189 | } |
---|
190 | else |
---|
191 | { |
---|
192 | f4_Node *node_new_neuron = new f4_Node(rndclass->getName().c_str(), node_new_div, node_new_div->pos); |
---|
193 | node_new_neuron->neuclass = rndclass; |
---|
194 | node_new = node_new_neuron; //can be changed below if all goes well and we add a new connection too |
---|
195 | if (probadd[F4_ADD_CONN] > 0) //user wants to add connections |
---|
196 | { |
---|
197 | if (rndclass->getPreferredInputs() != 0) //neuron also wants connections? |
---|
198 | { |
---|
199 | int node_new_neuron_index, other_neuron_index; |
---|
200 | bool ok = findConnectionNeuronIndexes(g, node_new_neuron, true, node_new_neuron_index, other_neuron_index); //node_new_neuron_index==-1 should never happen, we just added node_new_neuron we are looking for |
---|
201 | if (ok) //we can create a new connection |
---|
202 | { |
---|
203 | node_new = new f4_Node('[', node_new_neuron, node_new_div->pos); |
---|
204 | connectionNodeChangeRandom(node_new, node_new_neuron_index, other_neuron_index); |
---|
205 | } |
---|
206 | } |
---|
207 | else if (rndclass->getPreferredOutput() > 0) //neuron also wants connections? |
---|
208 | { |
---|
209 | // Not so easy: we would need to add a '[' node as a child not of node_new_neuron, but of other neuron that would get an input from node_new_neuron (and need to properly calculate relative connection reference). |
---|
210 | // The "false" argument in findConnectionNeuronIndexes() below is not suffient, because we also need to access (find) the f4_Node of the other neuron. |
---|
211 | // A similar logic is implemented in F4_ADD_CONN below, but let's not complicate this F4_ADD_DIV mutation anymore. |
---|
212 | // The disadvantage is that the node_new_neuron added here which is a neuron that provides output (e.g., a receptor, N, etc.) will not get connected immediately here even when there are already existing neurons wanting inputs (e.g., muscles, N, etc.). |
---|
213 | //bool ok = findConnectionNeuronIndexes(g, ... , false, ..., ...); |
---|
214 | } |
---|
215 | } |
---|
216 | } |
---|
217 | } |
---|
218 | new f4_Node('>', node_new, node_new->pos); //adds to node_new |
---|
219 | node_mutated->parent = node_new_div; |
---|
220 | // now, swap children with 50% chance |
---|
221 | if (rndUint(2) == 0) |
---|
222 | { |
---|
223 | node_mutated_parent = node_new_div->child; |
---|
224 | node_new_div->child = node_new_div->child2; |
---|
225 | node_new_div->child2 = node_mutated_parent; |
---|
226 | } |
---|
227 | } |
---|
228 | break; |
---|
229 | case F4_ADD_CONN: |
---|
230 | { |
---|
231 | // add connection |
---|
232 | |
---|
233 | // the probability that a randomly selected node will be a neuron and additionally this neuron will accept inputs is low, |
---|
234 | // so we disregard randomly picked node_mutated and build a list of all valid candidate nodes here, then randomly select one from them. |
---|
235 | |
---|
236 | vector<f4_Node*> candidate_nodes; //neurons that accept input(s) |
---|
237 | for (int i = 0; i < g->count(); i++) |
---|
238 | { |
---|
239 | f4_Node *node = g->ordNode(i); |
---|
240 | f4_Node *node_parent = node->parent; |
---|
241 | if (node_parent == NULL || node_parent->neuclass == NULL) continue; |
---|
242 | int prefinputs = node_parent->neuclass->getPreferredInputs(); |
---|
243 | if (prefinputs == -1 || |
---|
244 | prefinputs > 0) //would be nice if we could easily and quickly check if the parent already has its preferred inputs used, so that we do not produce an invalid mutation here... it is possible through the f4_Cell.n_conns field, but only during organism development |
---|
245 | candidate_nodes.push_back(node); |
---|
246 | } |
---|
247 | |
---|
248 | if (candidate_nodes.size() == 0) |
---|
249 | return GENOPER_OPFAIL; |
---|
250 | |
---|
251 | node_mutated = candidate_nodes[rndUint((unsigned int)candidate_nodes.size())]; |
---|
252 | f4_Node *node_mutated_parent = node_mutated->parent; |
---|
253 | |
---|
254 | int node_mutated_parent_index, other_neuron_index; |
---|
255 | bool ok = findConnectionNeuronIndexes(g, node_mutated_parent, true, node_mutated_parent_index, other_neuron_index); //node_mutated_parent_index==-1 should never happen, we earlier selected the neuron we are now looking for |
---|
256 | if (!ok) |
---|
257 | return GENOPER_OPFAIL; |
---|
258 | |
---|
259 | node_mutated->parent->removeChild(node_mutated); //this subtree will be reconnected below, as a child to node_new_conn |
---|
260 | f4_Node *node_new_conn = new f4_Node('[', node_mutated->parent, node_mutated->parent->pos); |
---|
261 | node_new_conn->addChild(node_mutated); |
---|
262 | node_mutated->parent = node_new_conn; // node_mutated_parent is the neuron, node_mutated->parent is '[' |
---|
263 | connectionNodeChangeRandom(node_new_conn, node_mutated_parent_index, other_neuron_index); |
---|
264 | } |
---|
265 | break; |
---|
266 | case F4_ADD_NEUPAR: |
---|
267 | { |
---|
268 | // add neuron modifier |
---|
269 | node_mutated->parent->removeChild(node_mutated); |
---|
270 | f4_Node *n2 = new f4_Node(':', node_mutated->parent, node_mutated->parent->pos); |
---|
271 | nparNodeMakeRandom(n2); |
---|
272 | n2->addChild(node_mutated); |
---|
273 | node_mutated->parent = n2; |
---|
274 | } |
---|
275 | break; |
---|
276 | case F4_ADD_REP: |
---|
277 | { |
---|
278 | // add repetition ('#') |
---|
279 | // repeated code (left child) is the original, right child is empty, count is set to 2 |
---|
280 | f4_Node *n3 = node_mutated->parent; |
---|
281 | n3->removeChild(node_mutated); |
---|
282 | f4_Node *n2 = new f4_Node('#', n3, n3->pos); |
---|
283 | n2->reps = 2; |
---|
284 | n2->addChild(node_mutated); |
---|
285 | new f4_Node('>', n2, n2->pos); |
---|
286 | node_mutated->parent = n2; |
---|
287 | } |
---|
288 | break; |
---|
289 | case F4_ADD_SIMP: |
---|
290 | { |
---|
291 | // add simple node |
---|
292 | // choose a simple node from ADD_SIMPLE_CODES |
---|
293 | node_mutated->parent->removeChild(node_mutated); |
---|
294 | //f4_Node *n2 = new f4_Node(ADD_SIMPLE_CODES[rndUint(strlen(ADD_SIMPLE_CODES))], n1->parent, n1->parent->pos); |
---|
295 | int modifierid = GenoOperators::getRandomChar(all_modifiers, excluded_modifiers.c_str()); |
---|
296 | f4_Node *n2 = new f4_Node(all_modifiers[modifierid], node_mutated->parent, node_mutated->parent->pos); |
---|
297 | n2->addChild(node_mutated); |
---|
298 | node_mutated->parent = n2; |
---|
299 | } |
---|
300 | break; |
---|
301 | } |
---|
302 | } |
---|
303 | break; |
---|
304 | |
---|
305 | case F4_DEL: |
---|
306 | { |
---|
307 | method = F4_ADD_COUNT - 1 + F4_DEL; |
---|
308 | // delete a node |
---|
309 | // must pick a node with parent, and at least one child |
---|
310 | // already picked a node, but repeat may be needed |
---|
311 | for (int i = 0; i < 10; i++) |
---|
312 | { |
---|
313 | if ((node_mutated->parent != NULL) && (g != node_mutated->parent)) |
---|
314 | if (node_mutated->child != NULL) |
---|
315 | break; |
---|
316 | // try a new one |
---|
317 | node_mutated = g->child->randomNode(); |
---|
318 | } |
---|
319 | if ((node_mutated->parent != NULL) && (g != node_mutated->parent)) |
---|
320 | { |
---|
321 | switch (node_mutated->childCount()) |
---|
322 | { |
---|
323 | case 0: break; |
---|
324 | case 1: // one child |
---|
325 | { |
---|
326 | f4_Node *node_mutated_parent = node_mutated->parent; |
---|
327 | node_mutated_parent->removeChild(node_mutated); |
---|
328 | if (node_mutated->child != NULL) |
---|
329 | { |
---|
330 | node_mutated->child->parent = node_mutated_parent; |
---|
331 | node_mutated_parent->addChild(node_mutated->child); |
---|
332 | node_mutated->child = NULL; |
---|
333 | } |
---|
334 | if (node_mutated->child2 != NULL) |
---|
335 | { |
---|
336 | node_mutated->child2->parent = node_mutated_parent; |
---|
337 | node_mutated_parent->addChild(node_mutated->child2); |
---|
338 | node_mutated->child2 = NULL; |
---|
339 | } |
---|
340 | // destroy n1 |
---|
341 | node_mutated->parent = NULL; |
---|
342 | delete node_mutated; |
---|
343 | } |
---|
344 | break; |
---|
345 | |
---|
346 | case 2: // two children |
---|
347 | { |
---|
348 | // two children |
---|
349 | f4_Node *n2 = node_mutated->parent; |
---|
350 | n2->removeChild(node_mutated); |
---|
351 | // n1 has two children. pick one randomly 50-50, destroy other |
---|
352 | if (rndUint(2) == 0) |
---|
353 | { |
---|
354 | node_mutated->child->parent = n2; |
---|
355 | n2->addChild(node_mutated->child); |
---|
356 | node_mutated->child = NULL; |
---|
357 | node_mutated->child2->parent = NULL; |
---|
358 | } |
---|
359 | else |
---|
360 | { |
---|
361 | node_mutated->child2->parent = n2; |
---|
362 | n2->addChild(node_mutated->child2); |
---|
363 | node_mutated->child2 = NULL; |
---|
364 | node_mutated->child->parent = NULL; |
---|
365 | } |
---|
366 | // destroy n1 |
---|
367 | node_mutated->parent = NULL; |
---|
368 | delete node_mutated; |
---|
369 | } |
---|
370 | break; |
---|
371 | } |
---|
372 | } |
---|
373 | else return GENOPER_OPFAIL; |
---|
374 | } |
---|
375 | break; |
---|
376 | case F4_MOD: |
---|
377 | { |
---|
378 | method = F4_ADD_COUNT - 1 + F4_MOD; |
---|
379 | // change a node |
---|
380 | // the only nodes that are modifiable are F4_MUT_CHANGE_CODES |
---|
381 | // try to get a modifiable node |
---|
382 | // already picked a node, but repeat may be needed |
---|
383 | int i = 0; |
---|
384 | while (1) |
---|
385 | { |
---|
386 | if (strchr(F4_MUT_CHANGE_CODES, node_mutated->name[0])) break; |
---|
387 | // try a new one |
---|
388 | node_mutated = g->child->randomNode(); |
---|
389 | i++; |
---|
390 | if (i >= 20) return GENOPER_OPFAIL; |
---|
391 | } |
---|
392 | switch (node_mutated->name[0]) |
---|
393 | { |
---|
394 | case '<': |
---|
395 | { |
---|
396 | // swap children |
---|
397 | f4_Node *n2 = node_mutated->child; |
---|
398 | node_mutated->child = node_mutated->child2; |
---|
399 | node_mutated->child2 = n2; |
---|
400 | } |
---|
401 | break; |
---|
402 | case '[': |
---|
403 | { |
---|
404 | switch (roulette(probmodneu, F4_MODNEU_COUNT)) |
---|
405 | { |
---|
406 | case F4_MODNEU_CONN: |
---|
407 | { |
---|
408 | f4_Node *neuron = node_mutated; //we start in '[' node and follow up parents until we find the neuron with these connections |
---|
409 | while (neuron != NULL && neuron->neuclass == NULL) neuron = neuron->parent; |
---|
410 | if (neuron == NULL) |
---|
411 | return GENOPER_OPFAIL; //did not find a neuron on the way up tree |
---|
412 | |
---|
413 | |
---|
414 | int neuron_index, other_neuron_index; |
---|
415 | bool ok = findConnectionNeuronIndexes(g, neuron, true, neuron_index, other_neuron_index); //neuron_index==-1 should never happen, we know the neuron is in the tree |
---|
416 | if (!ok) |
---|
417 | return GENOPER_OPFAIL; |
---|
418 | |
---|
419 | connectionNodeChangeRandom(node_mutated, neuron_index, other_neuron_index); |
---|
420 | break; |
---|
421 | } |
---|
422 | case F4_MODNEU_WEIGHT: |
---|
423 | node_mutated->conn_weight = GenoOperators::getMutatedNeuronConnectionWeight(node_mutated->conn_weight); |
---|
424 | break; |
---|
425 | } |
---|
426 | } |
---|
427 | break; |
---|
428 | |
---|
429 | case '#': |
---|
430 | { |
---|
431 | repeatNodeChangeRandom(node_mutated); |
---|
432 | } |
---|
433 | break; |
---|
434 | } |
---|
435 | } |
---|
436 | break; |
---|
437 | |
---|
438 | default: //no mutations allowed? |
---|
439 | return GENOPER_OPFAIL; |
---|
440 | } |
---|
441 | return GENOPER_OK; |
---|
442 | } |
---|
443 | |
---|
444 | // find all neurons and the needle |
---|
445 | vector<NeuroClass*> Geno_f4::findAllNeuronsAndNode(f4_Node * const & g, f4_Node* const &needle_neuron, int &found_index) |
---|
446 | { |
---|
447 | found_index = -1; // not found (for example, needle_neuron is not a neuroclass node or not added to the "g" tree) |
---|
448 | vector<NeuroClass*> neulist; |
---|
449 | for (int i = 0; i < g->count(); i++) |
---|
450 | { |
---|
451 | f4_Node *node = g->ordNode(i); |
---|
452 | if (node->neuclass != NULL) |
---|
453 | { |
---|
454 | neulist.push_back(node->neuclass); |
---|
455 | if (node == needle_neuron) |
---|
456 | found_index = int(neulist.size()) - 1; |
---|
457 | } |
---|
458 | } |
---|
459 | return neulist; |
---|
460 | } |
---|
461 | |
---|
462 | bool Geno_f4::findConnectionNeuronIndexes(f4_Node * const &g, f4_Node *neuron, bool other_has_output, int &neuron_index, int &other_neuron_index) |
---|
463 | { |
---|
464 | vector<NeuroClass*> neulist = findAllNeuronsAndNode(g, neuron, neuron_index); |
---|
465 | if (neuron_index == -1) |
---|
466 | return false; |
---|
467 | |
---|
468 | other_neuron_index = other_has_output ? |
---|
469 | GenoOperators::getRandomNeuroClassWithOutput(neulist) //find an existing neuron that provides an output |
---|
470 | : |
---|
471 | GenoOperators::getRandomNeuroClassWithInput(neulist); //find an existing neuron that accepts input(s) |
---|
472 | return other_neuron_index >= 0; |
---|
473 | } |
---|
474 | |
---|
475 | // change a [ node |
---|
476 | void Geno_f4::connectionNodeChangeRandom(f4_Node *nn, int nn_index, int other_index) const |
---|
477 | { |
---|
478 | // relative input connection to some existing neuron |
---|
479 | nn->conn_from = nn_index - other_index; |
---|
480 | //nn->conn_from = (int)(4.0f * (rndDouble(1) - 0.5)); //in very old times - did not care about neuron input/output preferences |
---|
481 | |
---|
482 | nn->conn_weight = GenoOperators::getMutatedNeuronConnectionWeight(nn->conn_weight); |
---|
483 | } |
---|
484 | |
---|
485 | |
---|
486 | // make a random : node |
---|
487 | void Geno_f4::nparNodeMakeRandom(f4_Node *nn) const |
---|
488 | { |
---|
489 | unsigned int prop = rndUint(3); //random neuron property |
---|
490 | nn->prop_symbol = "!=/"[prop]; |
---|
491 | nn->prop_increase = rndUint(2) == 1; |
---|
492 | } |
---|
493 | |
---|
494 | // change a repeat # node |
---|
495 | void Geno_f4::repeatNodeChangeRandom(f4_Node *nn) const |
---|
496 | { |
---|
497 | if (rndDouble(1) < 0.5) nn->reps++; else nn->reps--; // change count |
---|
498 | if (nn->reps < 1) nn->reps = 1; |
---|
499 | if (nn->reps > mut_max_rep) nn->reps = mut_max_rep; |
---|
500 | } |
---|
501 | |
---|
502 | |
---|
503 | int Geno_f4::MutateOneValid(f4_Node *& g, int &method) const |
---|
504 | // mutate one, until a valid genotype is obtained |
---|
505 | { |
---|
506 | // ! the genotype is g->child (not g) ! |
---|
507 | int i, res; |
---|
508 | f4_Node *gcopy = NULL; |
---|
509 | const int TRY_MUTATE = 20; |
---|
510 | // try this at most TRY_MUTATE times: copy, mutate, then validate |
---|
511 | for (i = 0; i < TRY_MUTATE; i++) |
---|
512 | { |
---|
513 | gcopy = g->duplicate(); |
---|
514 | |
---|
515 | res = MutateOne(gcopy, method); |
---|
516 | |
---|
517 | if (GENOPER_OK != res) |
---|
518 | { |
---|
519 | // mutation failed, try again |
---|
520 | delete gcopy; |
---|
521 | continue; // for |
---|
522 | } |
---|
523 | // try to validate it |
---|
524 | res = ValidateRec(gcopy, 10); |
---|
525 | // accept if it is OK, or was repaired |
---|
526 | if (GENOPER_OK == res) |
---|
527 | //(GENOPER_REPAIR == res) |
---|
528 | { |
---|
529 | // destroy the original one |
---|
530 | g->destroy(); |
---|
531 | // make it the new one |
---|
532 | *g = *gcopy; |
---|
533 | gcopy->child = NULL; |
---|
534 | gcopy->child2 = NULL; |
---|
535 | delete gcopy; |
---|
536 | res = GENOPER_OK; |
---|
537 | goto retm1v; |
---|
538 | } |
---|
539 | delete gcopy; |
---|
540 | } |
---|
541 | // attempts failed |
---|
542 | res = GENOPER_OPFAIL; |
---|
543 | retm1v: |
---|
544 | return res; |
---|
545 | } |
---|
546 | |
---|
547 | |
---|
548 | int Geno_f4::mutate(char *& g, float & chg, int &method) |
---|
549 | { |
---|
550 | f4_Node *root = new f4_Node; |
---|
551 | if (f4_processRecur(g, 0, root) || root->childCount() != 1) |
---|
552 | { |
---|
553 | delete root; |
---|
554 | return GENOPER_OPFAIL; |
---|
555 | } // could not convert or bad: fail |
---|
556 | // mutate one node, set chg as this percent |
---|
557 | chg = 1.0 / float(root->child->count()); |
---|
558 | if (MutateOneValid(root, method) != GENOPER_OK) |
---|
559 | { |
---|
560 | delete root; |
---|
561 | return GENOPER_OPFAIL; |
---|
562 | } |
---|
563 | // OK, convert back to string |
---|
564 | g[0] = 0; |
---|
565 | root->child->sprintAdj(g); |
---|
566 | delete root; |
---|
567 | return GENOPER_OK; |
---|
568 | } |
---|
569 | |
---|
570 | |
---|
571 | /* |
---|
572 | int Geno_f4::MutateMany(char *& g, float & chg) |
---|
573 | // check if original is valid, then |
---|
574 | // make a number of mutations |
---|
575 | { |
---|
576 | int res, n, i; |
---|
577 | int totNodes = 0; |
---|
578 | int maxToMut = 0; |
---|
579 | |
---|
580 | // convert to tree |
---|
581 | f4_Node *root; |
---|
582 | root = new f4_Node(); |
---|
583 | res = f4_processrec(g, 0, root); |
---|
584 | if (res) { |
---|
585 | // could not convert, fail |
---|
586 | goto retm; |
---|
587 | } |
---|
588 | if (1 != root->childCount()) { |
---|
589 | res = GENOPER_OPFAIL; |
---|
590 | goto retm; |
---|
591 | } |
---|
592 | |
---|
593 | // check if original is valid |
---|
594 | res = ValidateRec( root, 20 ); |
---|
595 | // might have been repaired! |
---|
596 | if (GENOPER_REPAIR==res) { |
---|
597 | res = GENOPER_OK; |
---|
598 | } |
---|
599 | if (GENOPER_OK != res) { |
---|
600 | goto retm; |
---|
601 | } |
---|
602 | |
---|
603 | // decide number of nodes to mutate |
---|
604 | // decide maximum number of nodes to mutate: 0.25*nodes, min 2 |
---|
605 | totNodes = root->child->count(); |
---|
606 | maxToMut = (int)( 0.25f * totNodes); |
---|
607 | if (maxToMut<2) maxToMut=2; |
---|
608 | if (maxToMut>totNodes) maxToMut=totNodes; |
---|
609 | |
---|
610 | // decide number of nodes to mutate |
---|
611 | n = (int)( 0.5 + rndDouble(1) * maxToMut ); |
---|
612 | if (n<1) n=1; |
---|
613 | if (n>totNodes) n=totNodes; |
---|
614 | // set chg as this percent |
---|
615 | chg = ((float)n) / ((float)totNodes); |
---|
616 | for (i=0; i<n; i++) |
---|
617 | { |
---|
618 | res = MutateOneValid(root); |
---|
619 | if (GENOPER_OK != res) |
---|
620 | { |
---|
621 | res = GENOPER_OPFAIL; |
---|
622 | goto retm; |
---|
623 | } |
---|
624 | } |
---|
625 | // OK, convert back to string |
---|
626 | g[0]=0; |
---|
627 | root->child->sprintAdj(g); |
---|
628 | retm: |
---|
629 | delete root; |
---|
630 | return res; |
---|
631 | } |
---|
632 | */ |
---|
633 | |
---|
634 | |
---|
635 | int Geno_f4::CrossOverOne(f4_Node *g1, f4_Node *g2, float chg) const |
---|
636 | { |
---|
637 | // ! the genotypes are g1->child and g2->child (not g1 g2) ! |
---|
638 | // single offspring in g1 |
---|
639 | int smin, smax; |
---|
640 | float size; |
---|
641 | f4_Node *n1, *n2, *n1p, *n2p; |
---|
642 | |
---|
643 | // determine desired size |
---|
644 | size = (1 - chg) * (float)g1->count(); |
---|
645 | smin = (int)(size * 0.9f - 1); |
---|
646 | smax = (int)(size * 1.1f + 1); |
---|
647 | // get a random node with desired size |
---|
648 | n1 = g1->child->randomNodeWithSize(smin, smax); |
---|
649 | |
---|
650 | // determine desired size |
---|
651 | size = (1 - chg) * (float)g2->count(); |
---|
652 | smin = (int)(size * 0.9f - 1); |
---|
653 | smax = (int)(size * 1.1f + 1); |
---|
654 | // get a random node with desired size |
---|
655 | n2 = g2->child->randomNodeWithSize(smin, smax); |
---|
656 | |
---|
657 | // exchange the two nodes: |
---|
658 | n1p = n1->parent; |
---|
659 | n2p = n2->parent; |
---|
660 | n1p->removeChild(n1); |
---|
661 | n1p->addChild(n2); |
---|
662 | n2p->removeChild(n2); |
---|
663 | n2p->addChild(n1); |
---|
664 | n1->parent = n2p; |
---|
665 | n2->parent = n1p; |
---|
666 | |
---|
667 | return GENOPER_OK; |
---|
668 | } |
---|
669 | |
---|
670 | int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2) |
---|
671 | { |
---|
672 | f4_Node root1, root2, *copy1, *copy2; |
---|
673 | |
---|
674 | // convert genotype strings into tree structures |
---|
675 | if (f4_processRecur(g1, 0, &root1) || (root1.childCount() != 1)) return GENOPER_OPFAIL; |
---|
676 | if (f4_processRecur(g2, 0, &root2) || (root2.childCount() != 1)) return GENOPER_OPFAIL; |
---|
677 | |
---|
678 | // decide amounts of crossover, 0.1-0.9 |
---|
679 | chg1 = 0.1 + rndDouble(0.8); |
---|
680 | chg2 = 0.1 + rndDouble(0.8); |
---|
681 | |
---|
682 | copy1 = root1.duplicate(); |
---|
683 | if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) { delete copy1; copy1 = NULL; } |
---|
684 | copy2 = root2.duplicate(); |
---|
685 | if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) { delete copy2; copy2 = NULL; } |
---|
686 | |
---|
687 | g1[0] = 0; |
---|
688 | g2[0] = 0; |
---|
689 | if (copy1) { copy1->child->sprintAdj(g1); delete copy1; } |
---|
690 | if (copy2) { copy2->child->sprintAdj(g2); delete copy2; } |
---|
691 | if (g1[0] || g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL; |
---|
692 | } |
---|
693 | |
---|
694 | uint32_t Geno_f4::style(const char *g, int pos) |
---|
695 | { |
---|
696 | char ch = g[pos]; |
---|
697 | |
---|
698 | // style categories |
---|
699 | #define STYL4CAT_MODIFIC F14_MODIFIERS "," |
---|
700 | #define STYL4CAT_NEUMOD "/!=" |
---|
701 | #define STYL4CAT_NEUSPECIAL "|@*" |
---|
702 | #define STYL4CAT_DIGIT "+-0123456789.[]" //'+' is only for adjusting old-style properties "/!=" |
---|
703 | #define STYL4CAT_REST ":XN<># " |
---|
704 | |
---|
705 | if (!isalpha(ch) && !strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_NEUSPECIAL STYL4CAT_DIGIT STYL4CAT_REST "\t", ch)) |
---|
706 | { |
---|
707 | return GENSTYLE_CS(0, GENSTYLE_INVALID); |
---|
708 | } |
---|
709 | uint32_t style = GENSTYLE_CS(0, GENSTYLE_STRIKEOUT); //default, should be changed below |
---|
710 | if (strchr("X", ch)) style = GENSTYLE_CS(0, GENSTYLE_BOLD); |
---|
711 | else if (strchr(":", ch)) style = GENSTYLE_CS(0, GENSTYLE_NONE); |
---|
712 | else if (strchr("#", ch)) style = GENSTYLE_RGBS(220, 0, 0, GENSTYLE_BOLD); |
---|
713 | else if (strchr("/=!", ch)) style = GENSTYLE_RGBS(255, 140, 0, GENSTYLE_BOLD); //property... for now, f4 does not supoprt properties in general for any neuron class, like f1 does |
---|
714 | else if (strchr("N@|*", ch)) style = GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); //neuroclass |
---|
715 | else if (strchr("<", ch)) style = GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD); |
---|
716 | else if (strchr(">", ch)) style = GENSTYLE_RGBS(0, 0, 100, GENSTYLE_NONE); |
---|
717 | else if (strchr(STYL4CAT_DIGIT, ch)) style = GENSTYLE_CS(GENCOLOR_NUMBER, GENSTYLE_NONE); |
---|
718 | else if (strchr(STYL4CAT_MODIFIC, ch)) style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE); |
---|
719 | else if (strchr(STYL4CAT_NEUMOD, ch)) style = GENSTYLE_RGBS(0, 150, 0, GENSTYLE_NONE); |
---|
720 | if (isalpha(ch)) |
---|
721 | { |
---|
722 | // allowed neuron formats: |
---|
723 | // N:CLASSNAME |
---|
724 | // N:@ |
---|
725 | // N:| |
---|
726 | // old syntax still supported in coloring, but no longer valid: |
---|
727 | // [SENSOR, WEIGHT] |
---|
728 | // N@ |
---|
729 | // N| |
---|
730 | // ...so must have N: or [ before neuroclass name (or just N, but this is handled above - for N@|* only) |
---|
731 | |
---|
732 | while (pos > 0) |
---|
733 | { |
---|
734 | pos--; |
---|
735 | if (!isalpha(g[pos])) |
---|
736 | { |
---|
737 | if (isupper(g[pos + 1]) && (g[pos] == '[') || (g[pos] == ':' && pos > 0 && g[pos - 1] == 'N')) //we may have sequences like :-/:I (even though they are not valid) - in this example "I" should not be treated as neuron name, hence there must also be a "N" before ":" |
---|
738 | style = GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); // neuroclass |
---|
739 | //(...) else (...) |
---|
740 | // style = GENSTYLE_RGBS(255, 140, 0, GENSTYLE_BOLD); // property - current f4 does not support neuron properties in a general case, only those old-style "/=!" as +! -! += -= +/ -/ |
---|
741 | break; |
---|
742 | } |
---|
743 | } |
---|
744 | } |
---|
745 | return style; |
---|
746 | } |
---|