1 /* ************************************************************************* *
2 bugsx - (C) Copyright 1990-1997 Joshua R. Smith (jrs@media.mit.edu)
3 http://physics.www.media.mit.edu/~jrs
4
5 (C) Copyright 1995-1997 Robert Gasch (Robert_Gasch@peoplesoft.com)
6 http://www.peoplesoft.com/peoplepages/g/robert_gasch/index.htm
7
8 Permission to use, copy, modify and distribute this software for any
9 purpose and without fee is hereby granted, provided that this copyright
10 notice appear in all copies as well as supporting documentation. All
11 work developed as a consequence of the use of this program should duly
12 acknowledge such use.
13
14 No representations are made about the suitability of this software for
15 any purpose. This software is provided "as is" without express or implied
16 warranty.
17
18 See the GNU General Public Licence for more information.
19 * ************************************************************************* */
20
21
22
23
24 /***************************************************************************
25 * BUGS software
26 * Copyright 1990 Joshua R. Smith
27 * file: breed.c 5/10/90
28 *
29 * This is a simple interactive genetic design system. You can grow
30 * creatures (graphs of Fourier Series, at this point) on the screen and
31 * specify which are fit enough to reproduce by clicking. When you've
32 * choosen the ones you want to reproduce, click breed. Breeder varies
33 * their genetic material and displays a new generation for you to
34 * inspect. As of now, breeder uses only the three most basic variation
35 * mechanisms: reproduction, crossover, and mutation. Reproduction
36 * means that only the fit will affect the next generation. Those which
37 * are not fit do not reproduce and therefore do not affect the next
38 * generation. In crossover, pairs of parents from the breeding (ie fit)
39 * subpopulation are choosen. We then choose a random chromosome locus
40 * (a locus is an index into the array holding the genes, ie an index
41 * into the chromosome), snip both Chromosomes at that point, and cross
42 * the strands; that is, we glue the first piece from the first parent
43 * onto the second piece from the second parent and the first piece
44 * from the second parent onto the second piece from the first parent.
45 * Got it? Or wait... Did I get that backwards? No. Just Kidding.
46 * During crossover, mutation can also occur. If an allele (chromosome
47 * array element value) is to be mutated, we just add some noise-- a
48 * gaussian random variable with a specified STD.
49 *
50 * Crossover and mutation do not happen every time. There are variables
51 * specifying the probabilities of these events. Right now, these and
52 * many other useful parameters are in the file Curves.h. To experiment
53 * with them, modify the values set in Curves.h and make to recompile.
54 * Only breed.c should need to be recompiled.
55 * (At some point in the near future, useful parameters will appear in
56 * the control panel so you'll be able to tinker with them without
57 * recompiling. At a later date, all or some parameters may be specified
58 * BY THE GENETIC MATERIAL ITSELF! Then things will really get
59 * interesting. If some variation mechanism is counter-productive in a
60 * particular application, the probability of that variation should
61 * diminish and perhaps vanish. Further down the road, hopefully the
62 * genes will code (some of) the variation mecahisms. Then new ones will
63 * be able to develop as required by the problem, the changing search
64 * space or the environment--whatever you want to call it.
65 *
66 *
67 * This file is where the action is. The main routine, which sets up the
68 * interactive system and then lets it go, is in this file. Also, all the
69 * genetic operators are implemented here. Once again, parameters to
70 * tweak are in Curves.h. The embryological stuff (routine to graph
71 * polynomials) is in the file Grow.c.
72 *
73 * To run, type 'b' (the letter b). This is a command script which
74 * executes 'breed' (compiled program) and passes it the time
75 * as a seed for the random number generator. Hint: if you want
76 * everything to go faster, shrink the population window. The smaller
77 * it is, the faster everything goes.
78 *
79 * Acknowledgements: the code for the user interface was largely
80 * appropriated from GED, written by Mike McDougall, Rob Allen, me, and
81 * others at Williams College. The Gaussian noise generator was written
82 * by Donald House and translated by Rob Allen. And of course the idea
83 * for the program was inspired by Richard Dawkins' Blind Watchmaker.
84 * This program was originally written as a project in Donald House's AI
85 * course. Thanks to Duane Bailey and Don House for supervision and
86 * funding over the summer of 1990.
87 *
88 ***************************************************************************/
89
90
91 #include "bugsx.h"
92
93 extern Display *mydisplay;
94 extern WinType main_win, /* main window */
95 menu[], /* menu items */
96 draw_win[]; /* windows we draw in */
97 extern unsigned long fg, bg; /* foreground, background */
98 extern Population G_Population[]; /* Array of Organisms */
99 extern Population G_Kids_Pop[]; /* Next generation */
100 extern double G_fit_thresh, /* fitness threshold */
101 G_pCross, /* probability of crossover */
102 G_pMutation, /* probability of mutation */
103 G_mutation_std, /* gauss fn STD used to mutate*/
104 G_weight[], /* weight for each term */
105 G_sum_weights; /* Sum of weights -- yscaling */
106 extern int G_size_pop, /* # organisms in population */
107 G_size_breeding_pop, /* # organisms reproducing */
108 G_generation, /* # generations so far */
109 G_switch_default, /* switches start on or off */
110 G_show_genes, /* display gene window */
111 G_current_width, /* Current size of pixwin */
112 G_current_height,
113 G_org_height, /* Size in pixels of organism */
114 G_org_width,
115 G_x_scale, /* These are used for scaling */
116 G_y_scale, /* curves. */
117 G_x_trans,
118 G_y_trans,
119 selected[],
120 extend_print,
121 verbose;
122 extern long seed;
123
124
125 /* ************************************************************************ */
126 /* ************************ initialize the system *********************** */
127 /* ************************************************************************ */
init()128 void init ()
129 {
130
131 G_size_pop = INIT_POP;
132 G_fit_thresh = INIT_FIT_THRESH;
133 G_switch_default= INIT_SWITCH_DEF;
134 G_show_genes = INIT_SHOW_GENES;
135 G_pCross = pCROSS;
136 G_pMutation = pMUTATION;
137 G_mutation_std = MUTATION_STD;
138 G_generation = 0;
139 seed = time (NULL);
140 }
141
142
143
144
145
146 /* ************************************************************************ */
147 /* ****** set organism's genes to random values between -.5 and +.5 ******* */
148 /* *** 6/4/90, changed max and min gene values from -.5,.+5 to -1.0,+1.0 ** */
149 /* ************************************************************************ */
randomize_org(org,name,size_chrom)150 void randomize_org (org, name, size_chrom)
151 Organism *org;
152 int name, size_chrom;
153 {
154 int i;
155
156 org->name = name;
157 org->size_chrom = size_chrom;
158
159 for (i=0; i<size_chrom; i++)
160 {
161 org->X_Chrom[i] = (2.0*drand48())-1.0;
162 org->Y_Chrom[i] = (2.0*drand48())-1.0;
163 G_weight[i] = dpow (WEIGHT_BASE, i);
164 G_sum_weights += G_weight[i];
165 }
166
167 org->fitness = 0.0;
168 org->mom = 0;
169 org->dad = 0;
170 G_sum_weights = 0.0;
171 }
172
173
174
175 /* ************************************************************************ */
176 /* *********************** initialize the population ********************* */
177 /* ************************************************************************ */
randomize_pop()178 void randomize_pop()
179 {
180 int i;
181
182 for (i=0; i<G_size_pop; i++)
183 if (!selected[i])
184 randomize_org (&G_Population[i], i, INIT_CHROM);
185 }
186
187
188
189
190 /* ************************************************************************ */
191 /* * get a uniformly distributed random # between low && high (inclusive) * */
192 /* ************************************************************************ */
rnd(low,high)193 int rnd (low, high)
194 int low, high;
195 {
196 double alpha;
197 int beta;
198
199 alpha = drand48(); /* alpha is a uniform rand dist var on [0.0, 1.0) */
200 beta = (int) (low + ((high-low+1)*alpha));
201 return (beta+low);
202 }
203
204
205
206 /* ************************************************************************ */
207 /* *********** get a boolean value with specified probability ************* */
208 /* ************************************************************************ */
flip(p)209 int flip (p)
210 double p;
211 {
212 int result;
213
214 if (p == 1.0)
215 result = 1;
216 else
217 {
218 if (drand48() <= p)
219 result = 1;
220 else
221 result = 0;
222 }
223 return(result);
224 }
225
226
227
228 /* ************************************************************************ */
229 /* ********** copy genetic material from one organism to another ********** */
230 /* ************************************************************************ */
copy_org(org1,org2)231 void copy_org (org1, org2)
232 Organism *org1, *org2;
233 {
234 int i;
235
236 org2->name = org1->name;
237 org2->size_chrom = org1->size_chrom;
238 for (i=0; i<org1->size_chrom; i++)
239 {
240 org2->X_Chrom[i] = org1->X_Chrom[i];
241 org2->Y_Chrom[i] = org1->Y_Chrom[i];
242 }
243 org2->mom = org1->mom;
244 org2->dad = org1->dad;
245 }
246
247
248
249
250 /* ************************************************************************ */
251 /* ************************ copy entire population ************************ */
252 /* ************************************************************************ */
copy_pop(pop1,pop2,size_pop)253 void copy_pop(pop1, pop2, size_pop)
254 Population *pop1, *pop2;
255 int size_pop;
256 {
257 int i;
258
259 for (i=0; i<size_pop; i++)
260 copy_org (&pop1[i], &pop2[i]);
261 }
262
263
264
265 /* ************************************************************************ */
266 /* *************************** erase an organism ************************** */
267 /* ************************************************************************ */
erase_org(org)268 void erase_org (org)
269 Organism *org;
270 {
271 int i;
272
273 for (i=0; i<org->size_chrom; i++)
274 {
275 org->X_Chrom[i] = 0.0;
276 org->Y_Chrom[i] = 0.0;
277 org->size_chrom = 0;
278 org->fitness = 0.0;
279 }
280 }
281
282
283
284 /* ************************************************************************ */
285 /* ***************** pick out a single eligible individual **************** */
286 /* ************************************************************************ */
select_org(size_pop)287 int select_org (size_pop)
288 int size_pop;
289 {
290 return (rnd(0,size_pop-1));
291 }
292
293
294
295
296 /* ************************************************************************ */
297 /* ******************************** mutate ******************************** */
298 /* ************************************************************************ */
mutation(allele)299 double mutation(allele)
300 double allele;
301 {
302 if (flip(G_pMutation)==1)
303 allele = noise(allele, G_mutation_std);
304 return(allele);
305 }
306
307
308
309
310 /* ************************************************************************ */
311 /* ************************** crossover == sex **************************** */
312 /* ************************************************************************ */
313 /* * Note: if we removed possibility of combining chromosomes of different* */
314 /* ** lengths and it were still possible for chrom length to change then ** */
315 /* ************************ we'd have... speciation! ********************* */
316 /* * Should try to have GENES specify how genetic material is recombined.* */
317 /* ************************************************************************ */
318 /* ************************************************************************ */
319 /* ************************************************************************ */
320 /* This is how Crossover works: choose a crossover point, i_cross.
321 * p1 = p1a.p1b p2 = p2a.p2b.
322 *
323 * Then the children c1 and c2, are:
324 * c1 = p1a.p2b c2 = p2a.p1b
325 * ************************************************************************ */
crossover(parent1,parent2,child1,child2,first_born_name)326 void crossover (parent1, parent2, child1, child2, first_born_name)
327 Organism *parent1, *parent2, *child1, *child2;
328 int first_born_name;
329 {
330 int i, i_cross, short_chrom, long_chrom;
331
332 if (extend_print)
333 {
334 printf("Mom: \n");
335 print_org(parent1);
336 printf("Dad: \n");
337 print_org(parent2);
338 }
339 child1->name = first_born_name;
340 child2->name = first_born_name+1;
341
342 /* *** use size of smaller chromosome as max crossover locus *** */
343 if (parent1->size_chrom > parent2->size_chrom)
344 {
345 long_chrom = parent1->size_chrom;
346 short_chrom = parent2->size_chrom;
347 }
348 else
349 {
350 long_chrom = parent2->size_chrom;
351 short_chrom = parent1->size_chrom;
352 }
353
354 /* *** Now we vary X and Y Chroms completely seperately. *** */
355 /* *** They don't cross over at the same points or at the *** */
356 /* *** same points or at the same times. Also, we don't *** */
357 /* *** use any inter chromosomal variation operators like *** */
358 /* *** segregation and translocation. *** */
359
360 /* *** X_CHROM *** */
361 /* *** Crossover occurs with p(G_pCross) *** */
362 if (flip(G_pCross)==1)
363 /* *** pick crossover locus *** */
364 i_cross = rnd(0,short_chrom-1);
365 else
366 /* *** INCORRECT if diff Chrom sizes *** */
367 i_cross = short_chrom;
368
369 /* *** Copy first part of Chroms directly to children *** */
370 for (i=0; i<i_cross; i++)
371 {
372 child1->X_Chrom[i] = mutation(parent1->X_Chrom[i]);
373 child2->X_Chrom[i] = mutation(parent2->X_Chrom[i]);
374 }
375
376 /* *** parent2 to child 1 (a cross) *** */
377 for (i=i_cross; i<short_chrom; i++)
378 child1->X_Chrom[i] = mutation(parent2->X_Chrom[i]);
379
380 /* *** parent1 to child 2 (a cross) *** */
381 for (i=i_cross; i<long_chrom; i++)
382 child2->X_Chrom[i] = mutation(parent1->X_Chrom[i]);
383
384
385 /* *** Y_CHROM *** */
386 /* *** Crossover occurs with p(G_pCross) *** */
387 if (flip(G_pCross)==1)
388 /* *** pick crossover locus *** */
389 i_cross = rnd(0,short_chrom-1);
390 else
391 /* *** INCORRECT if diff Chrom sizes *** */
392 i_cross = short_chrom;
393
394 /* *** Copy first part of Chroms directly to children *** */
395 for (i=0; i<i_cross; i++)
396 {
397 child1->Y_Chrom[i] = mutation(parent1->Y_Chrom[i]);
398 child2->Y_Chrom[i] = mutation(parent2->Y_Chrom[i]);
399 }
400
401 /* *** parent2 to child 1 (a cross) *** */
402 for (i=i_cross; i<short_chrom; i++)
403 child1->Y_Chrom[i] = mutation(parent2->Y_Chrom[i]);
404
405 /* *** parent1 to child 2 (a cross) *** */
406 for (i=i_cross; i<long_chrom; i++)
407 child2->Y_Chrom[i] = mutation(parent1->Y_Chrom[i]);
408
409 child1->size_chrom = parent2->size_chrom;
410 child2->size_chrom = parent1->size_chrom;
411 child1->fitness = 0.0;
412 child2->fitness = 0.0;
413 child1->mom = parent1->name;
414 child2->mom = parent1->name;
415 child1->dad = parent2->name;
416 child2->dad = parent2->name;
417
418 if (extend_print)
419 {
420 printf("Fred: \n");
421 print_org(child1);
422 printf("Jane: \n");
423 print_org(child2);
424 }
425 }
426
427
428
429 /* ************************************************************************ */
430 /* ************************** mix up the genes **************************** */
431 /* ************************************************************************ */
breed()432 void breed()
433 {
434 int i, size_eligible_pop, Mom, Dad;
435
436 /* *** Isolate the breeding subpopulation *** */
437 size_eligible_pop = 0;
438 for (i=0; i<G_size_pop; i++)
439 {
440 /* *** Set fitness values *** */
441 G_Population[i].fitness = fitness(i);
442 if (fitness(i))
443 size_eligible_pop++;
444 set_toggle_to_default(i);
445 }
446 if (size_eligible_pop<2)
447 size_eligible_pop = G_size_pop;
448 else
449 {
450 size_eligible_pop = 0;
451 for (i=0; i<G_size_pop; i++)
452 {
453 if (G_Population[i].fitness > G_fit_thresh)
454 {
455 if (extend_print)
456 {
457 printf("Copying %d to %d \n",
458 i, size_eligible_pop);
459 printf("original %d: \n", i);
460 print_org(&G_Population[i]);
461 printf("\n");
462 printf("original %d: \n", size_eligible_pop);
463 print_org(&G_Population[size_eligible_pop]);
464 printf("\n");
465 }
466 /* *** This is a tiny optimization *** */
467 /* *** don't copy to same place *** */
468 if (i != size_eligible_pop)
469 copy_org(&G_Population[i],
470 &G_Population[size_eligible_pop]);
471 if (extend_print)
472 {
473 printf("%d after copy: \n", size_eligible_pop);
474 print_org(&G_Population[size_eligible_pop]);
475 printf("\n");
476 }
477 /* *** Increment once per FIT organism *** */
478 size_eligible_pop++;
479 }
480 G_Population[i].fitness = 0.0;
481 }
482 }
483 /* *** Each couple has two kids. Nuclear families! *** */
484 for (i=0; i<G_size_pop; i+=2)
485 {
486 Dad = select_org (size_eligible_pop);
487 do
488 {
489 Mom = select_org(size_eligible_pop);
490 }
491 while (Mom == Dad);
492 crossover(&G_Population[Mom], &G_Population[Dad],
493 &G_Kids_Pop[i], &G_Kids_Pop[i+1], i);
494 }
495
496 /* *** Now the kids grow up - make new generation the current one *** */
497 copy_pop(G_Kids_Pop, G_Population, G_size_pop);
498
499 /* *** Here we actually put the kids on the screen *** */
500 grow_pop();
501 }
502
503
504
505
506 /* ************************************************************************ */
507 /* *** calculate fitness - in this case by checking for selected windows ** */
508 /* ************************************************************************ */
fitness(i)509 int fitness(i)
510 int i;
511 {
512 #ifdef DEBUG
513 if (selected [i])
514 printf ("%d is fit ...\n", i);
515 #endif
516 return (selected [i]);
517 }
518
519
520
521
522 /* ************************************************************************ */
523 /* ********** set the fitness indicator back to default (FALSE) *********** */
524 /* ************************************************************************ */
set_toggle_to_default(i)525 void set_toggle_to_default(i)
526 int i;
527 {
528 if (selected[i])
529 {
530 XFillRectangle (mydisplay, draw_win[i].win, draw_win[i].gc,
531 0, 0, draw_win[i].width, draw_win[i].height);
532 XSetForeground (mydisplay, draw_win[i].gc, fg);
533 selected[i]=FALSE;
534 }
535 }
536
537
538
539
540 /* ************************************************************************ */
541 /* ******************** print the entire population *********************** */
542 /* ************************************************************************ */
print_pop()543 void print_pop()
544 {
545 int i;
546
547 for (i=0; i<G_size_pop; i++)
548 print_org (&G_Population[i]);
549 printf("\n");
550 }
551
552
553
554 /* ************************************************************************ */
555 /* ************************** print an organism *************************** */
556 /* ************************************************************************ */
print_org(org)557 void print_org (org)
558 Organism* org;
559 {
560 int i;
561
562 printf("%d of %d and %d:\n",org->name, org->mom, org->dad);
563 for (i=0; i<org->size_chrom; i++)
564 {
565 printf(" (%1.3g, %1.3g)",
566 org->X_Chrom[i], org->Y_Chrom[i]);
567 if ((i+1)%4 == 0)
568 printf ("\n");
569 }
570 printf("\t%g", org->fitness);
571 printf("\n");
572 }
573
574