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