Context Navigation

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

Last change on this file since 277 was 247, checked in by Maciej Komosinski, 10 years ago
Sources support both 32-bit and 64-bit, and more compilers
Property svn:eol-style set to `native`
File size: 15.4 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: