1 /*
2 COPYRIGHT
3
4 The following is a notice of limited availability of the code, and disclaimer
5 which must be included in the prologue of the code and in all source listings
6 of the code.
7
8 (C) COPYRIGHT 2008 University of Chicago
9
10 Permission is hereby granted to use, reproduce, prepare derivative works, and
11 to redistribute to others. This software was authored by:
12
13 D. Levine
14 Mathematics and Computer Science Division
15 Argonne National Laboratory Group
16
17 with programming assistance of participants in Argonne National
18 Laboratory's SERS program.
19
20 GOVERNMENT LICENSE
21
22 Portions of this material resulted from work developed under a
23 U.S. Government Contract and are subject to the following license: the
24 Government is granted for itself and others acting on its behalf a paid-up,
25 nonexclusive, irrevocable worldwide license in this computer software to
26 reproduce, prepare derivative works, and perform publicly and display
27 publicly.
28
29 DISCLAIMER
30
31 This computer code material was prepared, in part, as an account of work
32 sponsored by an agency of the United States Government. Neither the United
33 States, nor the University of Chicago, nor any of their employees, makes any
34 warranty express or implied, or assumes any legal liability or responsibility
35 for the accuracy, completeness, or usefulness of any information, apparatus,
36 product, or process disclosed, or represents that its use would not infringe
37 privately owned rights.
38 */
39
40 /*****************************************************************************
41 * File: binary.c: This file contains routines specific to the binary
42 * datatype.
43 *
44 * Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
45 * Brian P. Walenz
46 *****************************************************************************/
47
48 #include "pgapack.h"
49
50 /*U****************************************************************************
51 PGASetBinaryAllele - sets a binary allele to the specified value.
52
53 Category: Fitness & Evaluation
54
55 Inputs:
56 ctx - context variable
57 p - string index
58 pop - symbolic constant of the population the string is in
59 i - allele index
60 val - binary value (either 1 or 0) to set the allele to
61
62 Outputs:
63 The allele is changed by side-effect.
64
65 Example:
66 Copies the alleles from member p in PGA_OLDPOP to member q PGA_NEWPOP.
67 Assumes strings are of the same length.
68
69 PGAContext *ctx;
70 int p, q, i;
71 :
72 for (i=PGAGetStringLength(ctx)-1; i>=0; i--)
73 PGASetBinaryAllele(ctx, q, PGA_NEWPOP, i,
74 PGAGetBinaryAllele(ctx, p, PGA_OLDPOP, i))
75
76 ****************************************************************************U*/
PGASetBinaryAllele(PGAContext * ctx,int p,int pop,int i,int val)77 void PGASetBinaryAllele ( PGAContext *ctx, int p, int pop, int i, int val )
78 {
79 int windex; /* index of the computer word allele i is in */
80 int bix; /* bit position in word chrom[windex] of allele i */
81 PGAIndividual *ind;
82 PGABinary *chrom;
83
84 PGADebugEntered("PGASetBinaryAllele");
85 PGACheckDataType("PGAGetBinaryAllele", PGA_DATATYPE_BINARY);
86
87 INDEX( windex,bix,i,WL );
88 ind = PGAGetIndividual ( ctx, p, pop );
89 chrom = (PGABinary *)ind->chrom;
90 if ( val == 0 )
91 UNSET( bix, chrom[windex] );
92 else
93 SET( bix, chrom[windex] );
94
95 PGADebugExited("PGASetBinaryAllele");
96 }
97
98 /*U****************************************************************************
99 PGAGetBinaryAllele - returns the value of a (binary) allele in a
100 PGA_DATATYPE_BINARY string
101
102 Category: Fitness & Evaluation
103
104 Inputs:
105 ctx - context variable
106 p - string index
107 pop - symbolic constant of the population the string is in
108 i - allele index
109
110 Outputs:
111 The value of the ith allele of string p in population pop.
112
113 Example:
114 Copies the alleles from member p in PGA_OLDPOP to member q PGA_NEWPOP.
115 Assumes the strings are of the same length.
116
117 PGAContext *ctx;
118 int p, q, i;
119 :
120 for (i=PGAGetStringLength(ctx)-1; i>=0; i--)
121 PGASetBinaryAllele(ctx, q, PGA_NEWPOP, i,
122 PGAGetBinaryAllele(ctx, p, PGA_OLDPOP, i))
123
124 ****************************************************************************U*/
PGAGetBinaryAllele(PGAContext * ctx,int p,int pop,int i)125 int PGAGetBinaryAllele ( PGAContext *ctx, int p, int pop, int i )
126 {
127
128 int windex; /* index of the computer word allele i is in */
129 int bix; /* bit position in word chrom[windex] of allele i */
130 PGAIndividual *ind;
131 PGABinary *chrom;
132
133 PGADebugEntered("PGAGetBinaryAllele");
134 PGACheckDataType("PGAGetBinaryAllele", PGA_DATATYPE_BINARY);
135
136 INDEX( windex,bix,i,WL );
137 ind = PGAGetIndividual ( ctx, p, pop );
138 chrom = (PGABinary *)ind->chrom;
139
140 PGADebugExited("PGAGetBinaryAllele");
141 return( BIT(bix, chrom[windex]) != 0 );
142 }
143
144 /*U****************************************************************************
145 PGASetBinaryInitProb - specify the probability of initializing an allele to
146 "1" when creating a PGA_DATATYPE_BINARY string. The default value is 0.5.
147
148 Category: Initialization
149
150 Inputs:
151 ctx - context variable
152 p - the binary initialization probability
153
154 Outputs:
155 None
156
157 Example:
158 Set approximately 1 percent of all binary alleles to "1" when randomly
159 initializing the population.
160
161 PGAContext *ctx;
162 :
163 PGASetBinaryInitProb(ctx, 0.01);
164
165 ****************************************************************************U*/
PGASetBinaryInitProb(PGAContext * ctx,double probability)166 void PGASetBinaryInitProb ( PGAContext *ctx, double probability )
167 {
168 PGADebugEntered("PGASetBinaryInitProb");
169 PGAFailIfSetUp("PGASetBinaryInitProb");
170 PGACheckDataType("PGASetBinaryInitProb", PGA_DATATYPE_BINARY);
171
172 if ( (probability <= 1.0) && (probability >= 0.0) )
173 ctx->init.BinaryProbability = probability;
174 else
175 PGAError( ctx, "PGASetBinaryInitProb: Invalid value of probability:",
176 PGA_FATAL, PGA_DOUBLE, (void *) &probability );
177
178 PGADebugExited("PGASetBinaryInitProb");
179 }
180
181 /*U***************************************************************************
182 PGAGetBinaryInitProb - Returns the probability that an allele will be
183 randomly initialized to "1" in a PGA_DATATYPE_BINARY string.
184
185 Category: Initialization
186
187 Inputs:
188 ctx - context variable
189
190 Outputs:
191 The probability that a bit will be randomly initialized to one
192
193 Example:
194 PGAContext *ctx;
195 double prob;
196 :
197 prob = PGAGetBinaryInitProb(ctx);
198
199 ***************************************************************************U*/
PGAGetBinaryInitProb(PGAContext * ctx)200 double PGAGetBinaryInitProb (PGAContext *ctx)
201 {
202 PGADebugEntered("PGAGetBinaryInitProb");
203 PGAFailIfNotSetUp("PGAGetBinaryInitProb");
204 PGACheckDataType("PGAGetBinaryInitProb", PGA_DATATYPE_BINARY);
205
206 PGADebugExited("PGAGetBinaryInitProb");
207 return(ctx->init.BinaryProbability);
208 }
209
210
211 /*I****************************************************************************
212 PGABinaryCreateString - Allocate a PGA_DATATYPE_BINARY string for member
213 p of population pop. If initflag is PGA_TRUE, randomly initialize all
214 alleles, otherwise clear all alleles.
215
216 Inputs:
217 ctx - context variable
218 p - string index
219 pop - symbolic constant of the population string p is in
220 initflag - a flag, if set, randomly initialize, else clear alleles
221
222 Outputs:
223 Member p in population pop is allocated and initialized.
224
225 Example:
226 Allocates and clears alleles for all strings in PGA_NEWPOP
227
228 PGAContext *ctx;
229 int p;
230 :
231 for (p=PGAGetPopSize(ctx)-1; p>=0; p--)
232 PGABinaryCreateString( ctx, p, PGA_NEWPOP, PGA_FALSE );
233
234 ****************************************************************************I*/
PGABinaryCreateString(PGAContext * ctx,int p,int pop,int initflag)235 void PGABinaryCreateString(PGAContext *ctx, int p, int pop, int initflag)
236 {
237 int i, fp;
238 PGABinary *s;
239 PGAIndividual *new = PGAGetIndividual(ctx, p, pop);
240
241 PGADebugEntered("PGABinaryCreateString");
242 PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR, "PGABinaryCreateString",
243 "initflag = ", PGA_INT, (void *) &initflag );
244
245 new->chrom = (void *)malloc(ctx->ga.tw * sizeof(PGABinary));
246 if (new->chrom == NULL)
247 PGAError(ctx, "PGABinaryCreateString: No room to allocate "
248 "new->chrom", PGA_FATAL, PGA_VOID, NULL);
249
250 s = (PGABinary *)new->chrom;
251 if (initflag)
252 if (ctx->fops.InitString) {
253 fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
254 (*ctx->fops.InitString)(&ctx, &fp, &pop);
255 } else {
256 (*ctx->cops.InitString)(ctx, p, pop);
257 }
258 else
259 for ( i=0; i<ctx->ga.tw; i++ )
260 s[i] = 0;
261
262 PGADebugExited("PGABinaryCreateString");
263 }
264
265 /*I****************************************************************************
266 PGABinaryMutation - randomly mutates a bit with a specified probability.
267 This routine is called from PGAMutation.
268
269 Inputs:
270 ctx - context variable
271 p - string index
272 pop - symbolic constant for the population string p is in
273 mr - probability of mutating (toggling) a bit
274
275 Outputs:
276 Returns the number of mutations
277
278 Example:
279 Mutates string p in population PGA_NEWPOP with a probability of 0.001
280 for each bit.
281
282 PGAContext *ctx;
283 int p;
284 :
285 PGABinaryMutation( ctx, p, PGA_NEWPOP, .001 );
286
287 ****************************************************************************I*/
PGABinaryMutation(PGAContext * ctx,int p,int pop,double mr)288 int PGABinaryMutation( PGAContext *ctx, int p, int pop, double mr )
289 {
290 int i,wi;
291 int count = 0;
292 PGABinary *c;
293
294 PGADebugEntered("PGABinaryMutation");
295
296 c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
297 for(wi=0; wi<ctx->ga.fw; wi++)
298 for(i=0; i<WL; ++i)
299 if ( PGARandomFlip(ctx, mr) )
300 {
301 TOGGLE(i,c[wi]);
302 count++;
303 }
304
305 /* clean up the partial word if eb > 0 */
306 if (ctx->ga.eb > 0 )
307 for(i=0;i<ctx->ga.eb;++i)
308 if ( PGARandomFlip(ctx, mr) )
309 {
310 TOGGLE(i,c[ctx->ga.fw]);
311 count++;
312 }
313
314 PGADebugExited("PGABinaryMutation");
315 return(count);
316
317 }
318
319 /*I****************************************************************************
320 PGABinaryOneptCrossover - performs one-point crossover on two parent strings
321 to create two children via side-effect
322
323 Inputs:
324 ctx - context variable
325 p1 - the first parent string
326 p2 - the second parent string
327 pop1 - symbolic constant of the population containing p1 and p2
328 c1 - the first child string
329 c2 - the second child string
330 pop2 - symbolic constant of the population containing c1 and c2
331
332 Outputs:
333 None.
334
335 Example:
336 Performs crossover on the two parent strings m and d, producing
337 children s and b.
338
339 PGAContext *ctx;
340 int m, d, s, b;
341 :
342 PGABinaryOneptCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );
343
344 ****************************************************************************I*/
PGABinaryOneptCrossover(PGAContext * ctx,int p1,int p2,int pop1,int c1,int c2,int pop2)345 void PGABinaryOneptCrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1,
346 int c2, int pop2)
347 {
348 PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
349 PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
350 PGABinary *child1 = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
351 PGABinary *child2 = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;
352
353 /*
354 If the bits are numbered from 0 as follows:
355
356 b b b b b b b b b b
357 0 1 2 3 4 5 6 7 30 31
358
359 Then if the cross site is bit 5 (which is the sixth bit by our
360 numbering scheme) we would get
361
362 o o o o o n n n n n
363 0 1 2 3 4 5 6 7 30 31
364
365 where o indicates the original bit and n is a new bit from the crossover
366 operator.
367 */
368
369 PGABinary mask;
370 int windex; /* index of the word the crossover bit position is in */
371 int bix; /* bit position to perform crossover (mod WL) */
372 int i;
373 int xsite;
374
375 PGADebugEntered("PGABinaryOneptCrossover");
376
377 xsite = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
378
379 INDEX(windex,bix,xsite,WL);
380
381 for(i=0;i<windex;i++) {
382 child1[i] = parent1[i];
383 child2[i] = parent2[i];
384 }
385
386 mask = ~0;
387 mask = mask >> bix;
388
389 child1[windex] = (~mask & parent1[windex])|(mask & parent2[windex]);
390 child2[windex] = (~mask & parent2[windex])|(mask & parent1[windex]);
391
392 for(i=windex+1;i<ctx->ga.tw;i++) {
393 child1[i] = parent2[i];
394 child2[i] = parent1[i];
395 }
396
397 PGADebugExited("PGABinaryOneptCrossover");
398 }
399
400
401 /*I****************************************************************************
402 PGABinaryTwoptCrossover - performs two-point crossover on two parent strings
403 producing two children via side-effect
404
405 Inputs:
406 ctx - context variable
407 p1 - the first parent string
408 p2 - the second parent string
409 pop1 - symbolic constant of the population containing string p1 and p2
410 c1 - the first child string
411 c2 - the second child string
412 pop2 - symbolic constant of the population to contain string c1 and c2
413
414 Outputs:
415 None.
416
417 Example:
418 Performs crossover on the two parent strings m and d, producing
419 children s and b.
420
421 PGAContext *ctx;
422 int m, d, s, b;
423 :
424 PGABinaryTwoptCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );
425
426 ****************************************************************************I*/
PGABinaryTwoptCrossover(PGAContext * ctx,int p1,int p2,int pop1,int c1,int c2,int pop2)427 void PGABinaryTwoptCrossover(PGAContext *ctx, int p1, int p2, int pop1, int c1,
428 int c2, int pop2)
429 {
430 PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
431 PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
432 PGABinary *child1 = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
433 PGABinary *child2 = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;
434
435 PGABinary mask, mask1, mask2;
436 int windex1, windex2;
437 int bix1, bix2;
438 int i;
439 int xsite1, xsite2;
440 int temp;
441
442 PGADebugEntered("PGABinaryTwoptCrossover");
443
444 /* pick two cross sites such that xsite2 > xsite1 */
445 xsite1 = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
446 xsite2 = xsite1;
447 while ( xsite2 == xsite1 )
448 xsite2 = PGARandomInterval(ctx, 1,ctx->ga.StringLen-1);
449 if ( xsite1 > xsite2 ) {
450 temp = xsite1;
451 xsite1 = xsite2;
452 xsite2 = temp;
453 }
454
455 INDEX(windex1,bix1,xsite1,WL);
456 INDEX(windex2,bix2,xsite2,WL);
457
458 if ( windex1 == windex2 ) { /* both cross sites in the same word */
459
460 for(i=0;i<windex1;i++) {
461 child1[i] = parent1[i];
462 child2[i] = parent2[i];
463 }
464
465 mask1 = ~0;
466 if (bix1 == 0)
467 mask1 = 0;
468 else
469 mask1 = mask1 << (WL-bix1);
470 mask2 = ~0;
471 mask2 = mask2 >> bix2;
472 mask = mask1 | mask2;
473
474 child1[windex1] = (mask & parent1[windex1])|(~mask & parent2[windex1]);
475 child2[windex1] = (mask & parent2[windex1])|(~mask & parent1[windex1]);
476
477 for(i=windex1+1;i<ctx->ga.tw;i++) {
478 child1[i] = parent1[i];
479 child2[i] = parent2[i];
480 }
481 }
482 else { /* cross sites in different words */
483
484 for(i=0;i<windex1;i++) {
485 child1[i] = parent1[i];
486 child2[i] = parent2[i];
487 }
488
489 mask = ~0;
490 mask = mask >> bix1;
491
492 child1[windex1] = (~mask & parent1[windex1])|(mask & parent2[windex1]);
493 child2[windex1] = (~mask & parent2[windex1])|(mask & parent1[windex1]);
494
495 for(i=windex1+1; i<windex2; i++) {
496 child1[i] = parent2[i];
497 child2[i] = parent1[i];
498 }
499
500 mask = ~0;
501 mask = mask >> bix2;
502
503 child1[windex2] = (mask & parent1[windex2])|(~mask & parent2[windex2]);
504 child2[windex2] = (mask & parent2[windex2])|(~mask & parent1[windex2]);
505
506 for(i=windex2+1; i<ctx->ga.tw; i++) {
507 child1[i] = parent1[i];
508 child2[i] = parent2[i];
509 }
510 }
511
512 PGADebugExited("PGABinaryTwoptCrossover");
513 }
514
515
516 /*I****************************************************************************
517 PGABinaryUniformCrossover - performs uniform crossover on two parent strings
518 producing two children via side-effect
519
520 Inputs:
521 ctx - context variable
522 p1 - the first parent string
523 p2 - the second parent string
524 pop1 - symbolic constant of the population containing string p1 and p2
525 c1 - the first child string
526 c2 - the second child string
527 pop2 - symbolic constant of the population to contain string c1 and c2
528
529 Outputs:
530 None.
531
532 Example:
533 Performs crossover on the two parent strings m and d, producing
534 children s and b.
535
536 PGAContext *ctx;
537 int m, d, s, b;
538 :
539 PGABinaryUniformCrossover( ctx, m, d, PGA_OLDPOP, s, b, PGA_NEWPOP );
540
541 ****************************************************************************I*/
PGABinaryUniformCrossover(PGAContext * ctx,int p1,int p2,int pop1,int c1,int c2,int pop2)542 void PGABinaryUniformCrossover(PGAContext *ctx, int p1, int p2, int pop1,
543 int c1, int c2, int pop2)
544 {
545 PGABinary *parent1 = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
546 PGABinary *parent2 = (PGABinary *)PGAGetIndividual(ctx, p2, pop1)->chrom;
547 PGABinary *child1 = (PGABinary *)PGAGetIndividual(ctx, c1, pop2)->chrom;
548 PGABinary *child2 = (PGABinary *)PGAGetIndividual(ctx, c2, pop2)->chrom;
549 PGABinary mask;
550 int j,wi;
551
552 PGADebugEntered("PGABinaryUniformCrossover");
553
554 for(wi=0;wi<ctx->ga.tw;wi++) {
555 if ( parent1[wi] == parent2[wi] ) {
556 child1[wi] = parent1[wi];
557 child2[wi] = parent2[wi];
558 }
559 else {
560 mask = 0;
561 for (j=0;j<WL;j++)
562 if(PGARandomFlip(ctx, ctx->ga.UniformCrossProb))
563 SET(j,mask);
564 child1[wi] = (mask & parent1[wi])|(~mask & parent2[wi]);
565 child2[wi] = (mask & parent2[wi])|(~mask & parent1[wi]);
566 }
567 }
568
569 PGADebugExited("PGABinaryUniformCrossover");
570 }
571
572 /*I****************************************************************************
573 PGABinaryPrintString - writes a bit string to a file.
574
575 Inputs:
576 ctx - context variable
577 fp - file pointer to file to write bit string to
578 p - index of the string to write out
579 pop - symbolic constant of the population string p is in
580
581 Outputs:
582 None.
583
584 Example:
585 Write string s to stdout.
586
587 PGAContext *ctx;
588 int s;
589 :
590 PGABinaryPrintString( ctx, stdout, s, PGA_NEWPOP );
591
592 ****************************************************************************I*/
PGABinaryPrintString(PGAContext * ctx,FILE * fp,int p,int pop)593 void PGABinaryPrintString( PGAContext *ctx, FILE *fp, int p, int pop )
594 {
595 PGABinary *c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
596 int i;
597
598 PGADebugEntered("PGABinaryPrintString");
599
600 for( i=0; i<ctx->ga.fw; i++ ) {
601 fprintf(fp,"[ ");
602 PGABinaryPrint( ctx, fp, (c+i), WL );
603 fprintf(fp," ]\n");
604 }
605 if ( ctx->ga.eb > 0 ) {
606 fprintf(fp,"[ ");
607 PGABinaryPrint( ctx, fp, (c+ctx->ga.fw), ctx->ga.eb );
608 fprintf(fp," ]");
609 }
610
611 PGADebugExited("PGABinaryPrintString");
612 }
613
614 /*I****************************************************************************
615 PGABinaryCopyString - Copy one bit string to another
616
617 Inputs:
618 ctx - context variable
619 p1 - string to copy
620 pop1 - symbolic constant of population containing string p1
621 p2 - string to copy p1 to
622 pop2 - symbolic constant of population containing string p2
623
624 Outputs:
625 None.
626
627 Example:
628 Copy bit string x to y (both are implicitly assumed to have the same
629 length).
630
631 PGAContext *ctx;
632 int x, y
633 :
634 PGABinaryCopyString ( ctx, x, PGA_OLDPOP, y, PGA_NEWPOP );
635
636 ****************************************************************************I*/
PGABinaryCopyString(PGAContext * ctx,int p1,int pop1,int p2,int pop2)637 void PGABinaryCopyString (PGAContext *ctx, int p1, int pop1, int p2, int pop2)
638 {
639 PGABinary *source = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
640 PGABinary *dest = (PGABinary *)PGAGetIndividual(ctx, p2, pop2)->chrom;
641 int i;
642
643 PGADebugEntered("PGABinaryCopyString");
644
645 for (i = ctx->ga.tw-1; i>=0; i--)
646 dest[i] = source[i];
647
648 PGADebugExited("PGABinaryCopyString");
649 }
650
651 /*I****************************************************************************
652 PGABinaryDuplicate - Returns true if bit string a is a duplicate of bit
653 string b, else returns false.
654
655 Inputs:
656 ctx - context variable
657 p1 - string index of the first string to compare
658 pop1 - symbolic constant of the population string p1 is in
659 p2 - string index of the second string to compare
660 pop2 - symbolic constant of the population string p2 is in
661
662 Outputs:
663 Returns true/false if strings are duplicates
664
665 Example:
666 Compare bit string x with y and print a message if they are the same.
667
668 PGAContext *ctx;
669 int x, y;
670 :
671 if ( PGABinaryDuplicate( ctx, x, PGA_NEWPOP, y, PGA_NEWPOP ) )
672 printf("strings are duplicates\n");
673
674 ****************************************************************************I*/
PGABinaryDuplicate(PGAContext * ctx,int p1,int pop1,int p2,int pop2)675 int PGABinaryDuplicate( PGAContext *ctx, int p1, int pop1, int p2, int pop2)
676 {
677 PGABinary *a = (PGABinary *)PGAGetIndividual(ctx, p1, pop1)->chrom;
678 PGABinary *b = (PGABinary *)PGAGetIndividual(ctx, p2, pop2)->chrom;
679 int wi;
680
681 PGADebugEntered("PGABinaryDuplicate");
682
683 wi = ctx->ga.tw-1;
684 if (a[0] == b[0])
685 for (; (wi>0) && (a[wi] == b[wi]); wi--);
686
687 PGADebugExited("PGABinaryDuplicate");
688
689 return((wi==0) ? PGA_TRUE : PGA_FALSE);
690 }
691
692 /*I****************************************************************************
693 PGABinaryInitString - randomly initialize a string of type PGABinary
694
695 Inputs:
696 ctx - context variable
697 p - index of string to randomly initialize
698 pop - symbolic constant of the population string p is in
699
700 Outputs:
701
702 Example:
703 PGAContext *ctx;
704 int p;
705 :
706 PGABinaryInitString ( ctx, p, PGA_NEWPOP );
707
708 ****************************************************************************I*/
PGABinaryInitString(PGAContext * ctx,int p,int pop)709 void PGABinaryInitString(PGAContext *ctx, int p, int pop)
710 {
711 PGABinary *c = (PGABinary *)PGAGetIndividual(ctx, p, pop)->chrom;
712 int i;
713 int windex; /* index of the computer word allele i is in */
714 int bix; /* binary position in word chrom[windex] of allele i */
715
716 PGADebugEntered("PGABinaryInitString");
717
718 for (i = 0; i < ctx->ga.tw; i++)
719 c[i] = 0;
720 for (i = 0; i < ctx->ga.StringLen; i++)
721 {
722 INDEX(windex,bix,i,WL);
723 if ( PGARandomFlip(ctx, ctx->init.BinaryProbability) )
724 SET ( bix, c[windex] );
725 }
726
727 PGADebugExited("PGABinaryInitString");
728 }
729
730
731 /*I****************************************************************************
732 PGABinaryBuildDatatype - Build an MPI_Datatype for a binary string
733 datatype.
734
735 Inputs:
736 ctx - context variable
737 p - index of the string to build a datatype from
738 pop - symbolic constant of the population string p is in
739
740 Outputs:
741 MPI_Datatype.
742
743 Example:
744 Called only by MPI routines. Not for user consumption.
745
746 ****************************************************************************I*/
PGABinaryBuildDatatype(PGAContext * ctx,int p,int pop)747 MPI_Datatype PGABinaryBuildDatatype(PGAContext *ctx, int p, int pop)
748 {
749
750 int counts[4]; /* Number of elements in each
751 block (array of integer) */
752 MPI_Aint displs[4]; /* byte displacement of each
753 block (array of integer) */
754 MPI_Datatype types[4]; /* type of elements in each block (array
755 of handles to datatype objects) */
756 MPI_Datatype individualtype; /* new datatype (handle) */
757 PGAIndividual *traveller; /* address of individual in question */
758
759 PGADebugEntered("PGABinaryBuildDatatype");
760
761 traveller = PGAGetIndividual(ctx, p, pop);
762 MPI_Address(&traveller->evalfunc, &displs[0]);
763 counts[0] = 1;
764 types[0] = MPI_DOUBLE;
765
766 MPI_Address(&traveller->fitness, &displs[1]);
767 counts[1] = 1;
768 types[1] = MPI_DOUBLE;
769
770 MPI_Address(&traveller->evaluptodate, &displs[2]);
771 counts[2] = 1;
772 types[2] = MPI_INT;
773
774 MPI_Address(traveller->chrom, &displs[3]);
775 counts[3] = ctx->ga.tw;
776 types[3] = MPI_UNSIGNED_LONG;
777
778 MPI_Type_struct(4, counts, displs, types, &individualtype);
779 MPI_Type_commit(&individualtype);
780
781 PGADebugExited("PGABinaryBuildDatatype");
782
783 return (individualtype);
784 }
785
786
787 /*I****************************************************************************
788 PGABinaryHammingDistance - Returns the Hamming distance between two strings
789
790 Inputs:
791 ctx - context variable
792 s1 - the first string to compare
793 s2 - the second string to compare
794
795 Outputs:
796 The Hamming distance between two strings
797
798 Example:
799 Returns the Hamming distance between bit strings x and y.
800
801 PGAContext *ctx;
802 PGABinary *x, *y;
803 int d;
804 :
805 d = PGABinaryHammingDistance( ctx, x, y );
806
807 ****************************************************************************I*/
PGABinaryHammingDistance(PGAContext * ctx,PGABinary * s1,PGABinary * s2)808 int PGABinaryHammingDistance ( PGAContext *ctx, PGABinary *s1, PGABinary *s2 )
809 {
810 int j, wi, distance;
811 PGABinary t1, t2, mask;
812
813 PGADebugEntered("PGABinaryHammingDistance");
814
815 distance = 0;
816 for(wi=0; wi<ctx->ga.tw; wi++) /* step through each word in the string */
817 if ( s1[wi] != s2[wi] ) { /* if equal, no bits are different */
818 /*fprintf(stdout,"s1[wi] = %x, s2[wi] = %x\n",s1[wi],s2[wi]);*/
819 mask = 1;
820 for(j=0;j<WL;++j) { /* not equal, compare all bits */
821 /* Build bit mask in position j. Mask bit from each */
822 /* string into t1 and t2 and test if bits are the same */
823 t1 = s1[wi] & mask;
824 t2 = s2[wi] & mask;
825 /*fprintf(stdout,"mask = %u, t1 = %u, t2 = %u, j = %d, wi = %d\n",mask,t1,t2,j,wi);*/
826 if ( t1 != t2 )
827 distance++;
828 mask <<= 1; /* shift mask 1 position */
829 }
830 }
831
832 PGADebugExited("PGABinaryHammingDistance");
833
834 return(distance);
835 }
836
837 /*I****************************************************************************
838 PGABinaryPrint - writes a bit string to a file. Puts the binary
839 representation of the bit string pointed to by chrom into a character
840 string and writes that out. Assumes the maximum length of string to
841 print is WL, and that all bits are in the same word.
842
843 Inputs:
844 ctx - context variable
845 fp - file to write the bit string to
846 chrom - pointer to the bit string to write
847 nb - number of bits to write out
848
849 Outputs:
850
851 Example:
852 Internal function. Use PGABinaryPrintString to print a binary string.
853
854 ****************************************************************************I*/
PGABinaryPrint(PGAContext * ctx,FILE * fp,PGABinary * chrom,int nb)855 void PGABinaryPrint( PGAContext *ctx, FILE *fp, PGABinary *chrom, int nb )
856 {
857 char *s, string[WL+1];
858 PGABinary mask;
859 int i;
860
861 PGADebugEntered("PGABinaryPrint");
862
863 mask = ((PGABinary)1)<<(WL-1);
864 s = string;
865 for(i=0; i<nb; mask>>=1,i++) /* mask each bit and set the */
866 *s++ = (mask&(*chrom)?'1':'0'); /* appropriate character */
867 *s=0; /* string terminator */
868 fprintf(fp, "%s", string); /* print out character string */
869
870 PGADebugExited("PGABinaryPrint");
871 }
872
873
874