1 /**CFile***********************************************************************
2
3 FileName [cuddGenetic.c]
4
5 PackageName [cudd]
6
7 Synopsis [Genetic algorithm for variable reordering.]
8
9 Description [Internal procedures included in this file:
10 <ul>
11 <li> cuddGa()
12 </ul>
13 Static procedures included in this module:
14 <ul>
15 <li> make_random()
16 <li> sift_up()
17 <li> build_dd()
18 <li> largest()
19 <li> rand_int()
20 <li> array_hash()
21 <li> array_compare()
22 <li> find_best()
23 <li> find_average_fitness()
24 <li> PMX()
25 <li> roulette()
26 </ul>
27
28 The genetic algorithm implemented here is as follows. We start with
29 the current DD order. We sift this order and use this as the
30 reference DD. We only keep 1 DD around for the entire process and
31 simply rearrange the order of this DD, storing the various orders
32 and their corresponding DD sizes. We generate more random orders to
33 build an initial population. This initial population is 3 times the
34 number of variables, with a maximum of 120. Each random order is
35 built (from the reference DD) and its size stored. Each random
36 order is also sifted to keep the DD sizes fairly small. Then a
37 crossover is performed between two orders (picked randomly) and the
38 two resulting DDs are built and sifted. For each new order, if its
39 size is smaller than any DD in the population, it is inserted into
40 the population and the DD with the largest number of nodes is thrown
41 out. The crossover process happens up to 50 times, and at this point
42 the DD in the population with the smallest size is chosen as the
43 result. This DD must then be built from the reference DD.]
44
45 SeeAlso []
46
47 Author [Curt Musfeldt, Alan Shuler, Fabio Somenzi]
48
49 Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado
50
51 All rights reserved.
52
53 Redistribution and use in source and binary forms, with or without
54 modification, are permitted provided that the following conditions
55 are met:
56
57 Redistributions of source code must retain the above copyright
58 notice, this list of conditions and the following disclaimer.
59
60 Redistributions in binary form must reproduce the above copyright
61 notice, this list of conditions and the following disclaimer in the
62 documentation and/or other materials provided with the distribution.
63
64 Neither the name of the University of Colorado nor the names of its
65 contributors may be used to endorse or promote products derived from
66 this software without specific prior written permission.
67
68 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
69 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
70 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
71 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
72 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
73 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
74 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
75 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
76 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
77 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
78 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
79 POSSIBILITY OF SUCH DAMAGE.]
80
81 ******************************************************************************/
82
83 #include "misc/util/util_hack.h"
84 #include "cuddInt.h"
85
86 ABC_NAMESPACE_IMPL_START
87
88
89
90 /*---------------------------------------------------------------------------*/
91 /* Constant declarations */
92 /*---------------------------------------------------------------------------*/
93
94 /*---------------------------------------------------------------------------*/
95 /* Stucture declarations */
96 /*---------------------------------------------------------------------------*/
97
98 /*---------------------------------------------------------------------------*/
99 /* Type declarations */
100 /*---------------------------------------------------------------------------*/
101
102 /*---------------------------------------------------------------------------*/
103 /* Variable declarations */
104 /*---------------------------------------------------------------------------*/
105
106 #ifndef lint
107 static char rcsid[] DD_UNUSED = "$Id: cuddGenetic.c,v 1.28 2004/08/13 18:04:48 fabio Exp $";
108 #endif
109
110 static int popsize; /* the size of the population */
111 static int numvars; /* the number of input variables in the ckt. */
112 /* storedd stores the population orders and sizes. This table has two
113 ** extra rows and one extras column. The two extra rows are used for the
114 ** offspring produced by a crossover. Each row stores one order and its
115 ** size. The order is stored by storing the indices of variables in the
116 ** order in which they appear in the order. The table is in reality a
117 ** one-dimensional array which is accessed via a macro to give the illusion
118 ** it is a two-dimensional structure.
119 */
120 static int *storedd;
121 static st__table *computed; /* hash table to identify existing orders */
122 static int *repeat; /* how many times an order is present */
123 static int large; /* stores the index of the population with
124 ** the largest number of nodes in the DD */
125 static int result;
126 static int cross; /* the number of crossovers to perform */
127
128 /*---------------------------------------------------------------------------*/
129 /* Macro declarations */
130 /*---------------------------------------------------------------------------*/
131
132 /* macro used to access the population table as if it were a
133 ** two-dimensional structure.
134 */
135 #define STOREDD(i,j) storedd[(i)*(numvars+1)+(j)]
136
137 /**AutomaticStart*************************************************************/
138
139 /*---------------------------------------------------------------------------*/
140 /* Static function prototypes */
141 /*---------------------------------------------------------------------------*/
142
143 static int make_random (DdManager *table, int lower);
144 static int sift_up (DdManager *table, int x, int x_low);
145 static int build_dd (DdManager *table, int num, int lower, int upper);
146 static int largest (void);
147 static int rand_int (int a);
148 static int array_hash (const char *array, int modulus);
149 static int array_compare (const char *array1, const char *array2);
150 static int find_best (void);
151 #ifdef DD_STATS
152 static double find_average_fitness (void);
153 #endif
154 static int PMX (int maxvar);
155 static int roulette (int *p1, int *p2);
156
157 /**AutomaticEnd***************************************************************/
158
159 /*---------------------------------------------------------------------------*/
160 /* Definition of exported functions */
161 /*---------------------------------------------------------------------------*/
162
163 /*---------------------------------------------------------------------------*/
164 /* Definition of internal functions */
165 /*---------------------------------------------------------------------------*/
166
167
168 /**Function********************************************************************
169
170 Synopsis [Genetic algorithm for DD reordering.]
171
172 Description [Genetic algorithm for DD reordering.
173 The two children of a crossover will be stored in
174 storedd[popsize] and storedd[popsize+1] --- the last two slots in the
175 storedd array. (This will make comparisons and replacement easy.)
176 Returns 1 in case of success; 0 otherwise.]
177
178 SideEffects [None]
179
180 SeeAlso []
181
182 ******************************************************************************/
183 int
cuddGa(DdManager * table,int lower,int upper)184 cuddGa(
185 DdManager * table /* manager */,
186 int lower /* lowest level to be reordered */,
187 int upper /* highest level to be reorderded */)
188 {
189 int i,n,m; /* dummy/loop vars */
190 int index;
191 #ifdef DD_STATS
192 double average_fitness;
193 #endif
194 int small; /* index of smallest DD in population */
195
196 /* Do an initial sifting to produce at least one reasonable individual. */
197 if (!cuddSifting(table,lower,upper)) return(0);
198
199 /* Get the initial values. */
200 numvars = upper - lower + 1; /* number of variables to be reordered */
201 if (table->populationSize == 0) {
202 popsize = 3 * numvars; /* population size is 3 times # of vars */
203 if (popsize > 120) {
204 popsize = 120; /* Maximum population size is 120 */
205 }
206 } else {
207 popsize = table->populationSize; /* user specified value */
208 }
209 if (popsize < 4) popsize = 4; /* enforce minimum population size */
210
211 /* Allocate population table. */
212 storedd = ABC_ALLOC(int,(popsize+2)*(numvars+1));
213 if (storedd == NULL) {
214 table->errorCode = CUDD_MEMORY_OUT;
215 return(0);
216 }
217
218 /* Initialize the computed table. This table is made up of two data
219 ** structures: A hash table with the key given by the order, which says
220 ** if a given order is present in the population; and the repeat
221 ** vector, which says how many copies of a given order are stored in
222 ** the population table. If there are multiple copies of an order, only
223 ** one has a repeat count greater than 1. This copy is the one pointed
224 ** by the computed table.
225 */
226 repeat = ABC_ALLOC(int,popsize);
227 if (repeat == NULL) {
228 table->errorCode = CUDD_MEMORY_OUT;
229 ABC_FREE(storedd);
230 return(0);
231 }
232 for (i = 0; i < popsize; i++) {
233 repeat[i] = 0;
234 }
235 computed = st__init_table(array_compare,array_hash);
236 if (computed == NULL) {
237 table->errorCode = CUDD_MEMORY_OUT;
238 ABC_FREE(storedd);
239 ABC_FREE(repeat);
240 return(0);
241 }
242
243 /* Copy the current DD and its size to the population table. */
244 for (i = 0; i < numvars; i++) {
245 STOREDD(0,i) = table->invperm[i+lower]; /* order of initial DD */
246 }
247 STOREDD(0,numvars) = table->keys - table->isolated; /* size of initial DD */
248
249 /* Store the initial order in the computed table. */
250 if ( st__insert(computed,(char *)storedd,(char *) 0) == st__OUT_OF_MEM) {
251 ABC_FREE(storedd);
252 ABC_FREE(repeat);
253 st__free_table(computed);
254 return(0);
255 }
256 repeat[0]++;
257
258 /* Insert the reverse order as second element of the population. */
259 for (i = 0; i < numvars; i++) {
260 STOREDD(1,numvars-1-i) = table->invperm[i+lower]; /* reverse order */
261 }
262
263 /* Now create the random orders. make_random fills the population
264 ** table with random permutations. The successive loop builds and sifts
265 ** the DDs for the reverse order and each random permutation, and stores
266 ** the results in the computed table.
267 */
268 if (!make_random(table,lower)) {
269 table->errorCode = CUDD_MEMORY_OUT;
270 ABC_FREE(storedd);
271 ABC_FREE(repeat);
272 st__free_table(computed);
273 return(0);
274 }
275 for (i = 1; i < popsize; i++) {
276 result = build_dd(table,i,lower,upper); /* build and sift order */
277 if (!result) {
278 ABC_FREE(storedd);
279 ABC_FREE(repeat);
280 st__free_table(computed);
281 return(0);
282 }
283 if ( st__lookup_int(computed,(char *)&STOREDD(i,0),&index)) {
284 repeat[index]++;
285 } else {
286 if ( st__insert(computed,(char *)&STOREDD(i,0),(char *)(long)i) ==
287 st__OUT_OF_MEM) {
288 ABC_FREE(storedd);
289 ABC_FREE(repeat);
290 st__free_table(computed);
291 return(0);
292 }
293 repeat[i]++;
294 }
295 }
296
297 #if 0
298 #ifdef DD_STATS
299 /* Print the initial population. */
300 (void) fprintf(table->out,"Initial population after sifting\n");
301 for (m = 0; m < popsize; m++) {
302 for (i = 0; i < numvars; i++) {
303 (void) fprintf(table->out," %2d",STOREDD(m,i));
304 }
305 (void) fprintf(table->out," : %3d (%d)\n",
306 STOREDD(m,numvars),repeat[m]);
307 }
308 #endif
309 #endif
310
311 small = find_best();
312 #ifdef DD_STATS
313 average_fitness = find_average_fitness();
314 (void) fprintf(table->out,"\nInitial population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
315 #endif
316
317 /* Decide how many crossovers should be tried. */
318 if (table->numberXovers == 0) {
319 cross = 3*numvars;
320 if (cross > 60) { /* do a maximum of 50 crossovers */
321 cross = 60;
322 }
323 } else {
324 cross = table->numberXovers; /* use user specified value */
325 }
326
327 /* Perform the crossovers to get the best order. */
328 for (m = 0; m < cross; m++) {
329 if (!PMX(table->size)) { /* perform one crossover */
330 table->errorCode = CUDD_MEMORY_OUT;
331 ABC_FREE(storedd);
332 ABC_FREE(repeat);
333 st__free_table(computed);
334 return(0);
335 }
336 /* The offsprings are left in the last two entries of the
337 ** population table. These are now considered in turn.
338 */
339 for (i = popsize; i <= popsize+1; i++) {
340 result = build_dd(table,i,lower,upper); /* build and sift child */
341 if (!result) {
342 ABC_FREE(storedd);
343 ABC_FREE(repeat);
344 st__free_table(computed);
345 return(0);
346 }
347 large = largest(); /* find the largest DD in population */
348
349 /* If the new child is smaller than the largest DD in the current
350 ** population, enter it into the population in place of the
351 ** largest DD.
352 */
353 if (STOREDD(i,numvars) < STOREDD(large,numvars)) {
354 /* Look up the largest DD in the computed table.
355 ** Decrease its repetition count. If the repetition count
356 ** goes to 0, remove the largest DD from the computed table.
357 */
358 result = st__lookup_int(computed,(char *)&STOREDD(large,0),
359 &index);
360 if (!result) {
361 ABC_FREE(storedd);
362 ABC_FREE(repeat);
363 st__free_table(computed);
364 return(0);
365 }
366 repeat[index]--;
367 if (repeat[index] == 0) {
368 int *pointer = &STOREDD(index,0);
369 result = st__delete(computed, (const char **)&pointer, NULL);
370 if (!result) {
371 ABC_FREE(storedd);
372 ABC_FREE(repeat);
373 st__free_table(computed);
374 return(0);
375 }
376 }
377 /* Copy the new individual to the entry of the
378 ** population table just made available and update the
379 ** computed table.
380 */
381 for (n = 0; n <= numvars; n++) {
382 STOREDD(large,n) = STOREDD(i,n);
383 }
384 if ( st__lookup_int(computed,(char *)&STOREDD(large,0),
385 &index)) {
386 repeat[index]++;
387 } else {
388 if ( st__insert(computed,(char *)&STOREDD(large,0),
389 (char *)(long)large) == st__OUT_OF_MEM) {
390 ABC_FREE(storedd);
391 ABC_FREE(repeat);
392 st__free_table(computed);
393 return(0);
394 }
395 repeat[large]++;
396 }
397 }
398 }
399 }
400
401 /* Find the smallest DD in the population and build it;
402 ** that will be the result.
403 */
404 small = find_best();
405
406 /* Print stats on the final population. */
407 #ifdef DD_STATS
408 average_fitness = find_average_fitness();
409 (void) fprintf(table->out,"\nFinal population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
410 #endif
411
412 /* Clean up, build the result DD, and return. */
413 st__free_table(computed);
414 computed = NULL;
415 result = build_dd(table,small,lower,upper);
416 ABC_FREE(storedd);
417 ABC_FREE(repeat);
418 return(result);
419
420 } /* end of cuddGa */
421
422
423 /*---------------------------------------------------------------------------*/
424 /* Definition of static functions */
425 /*---------------------------------------------------------------------------*/
426
427 /**Function********************************************************************
428
429 Synopsis [Generates the random sequences for the initial population.]
430
431 Description [Generates the random sequences for the initial population.
432 The sequences are permutations of the indices between lower and
433 upper in the current order.]
434
435 SideEffects [None]
436
437 SeeAlso []
438
439 ******************************************************************************/
440 static int
make_random(DdManager * table,int lower)441 make_random(
442 DdManager * table,
443 int lower)
444 {
445 int i,j; /* loop variables */
446 int *used; /* is a number already in a permutation */
447 int next; /* next random number without repetitions */
448
449 used = ABC_ALLOC(int,numvars);
450 if (used == NULL) {
451 table->errorCode = CUDD_MEMORY_OUT;
452 return(0);
453 }
454 #if 0
455 #ifdef DD_STATS
456 (void) fprintf(table->out,"Initial population before sifting\n");
457 for (i = 0; i < 2; i++) {
458 for (j = 0; j < numvars; j++) {
459 (void) fprintf(table->out," %2d",STOREDD(i,j));
460 }
461 (void) fprintf(table->out,"\n");
462 }
463 #endif
464 #endif
465 for (i = 2; i < popsize; i++) {
466 for (j = 0; j < numvars; j++) {
467 used[j] = 0;
468 }
469 /* Generate a permutation of {0...numvars-1} and use it to
470 ** permute the variables in the layesr from lower to upper.
471 */
472 for (j = 0; j < numvars; j++) {
473 do {
474 next = rand_int(numvars-1);
475 } while (used[next] != 0);
476 used[next] = 1;
477 STOREDD(i,j) = table->invperm[next+lower];
478 }
479 #if 0
480 #ifdef DD_STATS
481 /* Print the order just generated. */
482 for (j = 0; j < numvars; j++) {
483 (void) fprintf(table->out," %2d",STOREDD(i,j));
484 }
485 (void) fprintf(table->out,"\n");
486 #endif
487 #endif
488 }
489 ABC_FREE(used);
490 return(1);
491
492 } /* end of make_random */
493
494
495 /**Function********************************************************************
496
497 Synopsis [Moves one variable up.]
498
499 Description [Takes a variable from position x and sifts it up to
500 position x_low; x_low should be less than x. Returns 1 if successful;
501 0 otherwise]
502
503 SideEffects [None]
504
505 SeeAlso []
506
507 ******************************************************************************/
508 static int
sift_up(DdManager * table,int x,int x_low)509 sift_up(
510 DdManager * table,
511 int x,
512 int x_low)
513 {
514 int y;
515 int size;
516
517 y = cuddNextLow(table,x);
518 while (y >= x_low) {
519 size = cuddSwapInPlace(table,y,x);
520 if (size == 0) {
521 return(0);
522 }
523 x = y;
524 y = cuddNextLow(table,x);
525 }
526 return(1);
527
528 } /* end of sift_up */
529
530
531 /**Function********************************************************************
532
533 Synopsis [Builds a DD from a given order.]
534
535 Description [Builds a DD from a given order. This procedure also
536 sifts the final order and inserts into the array the size in nodes
537 of the result. Returns 1 if successful; 0 otherwise.]
538
539 SideEffects [None]
540
541 SeeAlso []
542
543 ******************************************************************************/
544 static int
build_dd(DdManager * table,int num,int lower,int upper)545 build_dd(
546 DdManager * table,
547 int num /* the index of the individual to be built */,
548 int lower,
549 int upper)
550 {
551 int i,j; /* loop vars */
552 int position;
553 int index;
554 int limit; /* how large the DD for this order can grow */
555 int size;
556
557 /* Check the computed table. If the order already exists, it
558 ** suffices to copy the size from the existing entry.
559 */
560 if (computed && st__lookup_int(computed,(char *)&STOREDD(num,0),&index)) {
561 STOREDD(num,numvars) = STOREDD(index,numvars);
562 #ifdef DD_STATS
563 (void) fprintf(table->out,"\nCache hit for index %d", index);
564 #endif
565 return(1);
566 }
567
568 /* Stop if the DD grows 20 times larges than the reference size. */
569 limit = 20 * STOREDD(0,numvars);
570
571 /* Sift up the variables so as to build the desired permutation.
572 ** First the variable that has to be on top is sifted to the top.
573 ** Then the variable that has to occupy the secon position is sifted
574 ** up to the second position, and so on.
575 */
576 for (j = 0; j < numvars; j++) {
577 i = STOREDD(num,j);
578 position = table->perm[i];
579 result = sift_up(table,position,j+lower);
580 if (!result) return(0);
581 size = table->keys - table->isolated;
582 if (size > limit) break;
583 }
584
585 /* Sift the DD just built. */
586 #ifdef DD_STATS
587 (void) fprintf(table->out,"\n");
588 #endif
589 result = cuddSifting(table,lower,upper);
590 if (!result) return(0);
591
592 /* Copy order and size to table. */
593 for (j = 0; j < numvars; j++) {
594 STOREDD(num,j) = table->invperm[lower+j];
595 }
596 STOREDD(num,numvars) = table->keys - table->isolated; /* size of new DD */
597 return(1);
598
599 } /* end of build_dd */
600
601
602 /**Function********************************************************************
603
604 Synopsis [Finds the largest DD in the population.]
605
606 Description [Finds the largest DD in the population. If an order is
607 repeated, it avoids choosing the copy that is in the computed table
608 (it has repeat[i] > 1).]
609
610 SideEffects [None]
611
612 SeeAlso []
613
614 ******************************************************************************/
615 static int
largest(void)616 largest(void)
617 {
618 int i; /* loop var */
619 int big; /* temporary holder to return result */
620
621 big = 0;
622 while (repeat[big] > 1) big++;
623 for (i = big + 1; i < popsize; i++) {
624 if (STOREDD(i,numvars) >= STOREDD(big,numvars) && repeat[i] <= 1) {
625 big = i;
626 }
627 }
628 return(big);
629
630 } /* end of largest */
631
632
633 /**Function********************************************************************
634
635 Synopsis [Generates a random number between 0 and the integer a.]
636
637 Description []
638
639 SideEffects [None]
640
641 SeeAlso []
642
643 ******************************************************************************/
644 static int
rand_int(int a)645 rand_int(
646 int a)
647 {
648 return(Cudd_Random() % (a+1));
649
650 } /* end of rand_int */
651
652
653 /**Function********************************************************************
654
655 Synopsis [Hash function for the computed table.]
656
657 Description [Hash function for the computed table. Returns the bucket
658 number.]
659
660 SideEffects [None]
661
662 SeeAlso []
663
664 ******************************************************************************/
665 static int
array_hash(const char * array,int modulus)666 array_hash(
667 const char * array,
668 int modulus)
669 {
670 int val = 0;
671 int i;
672 int *intarray;
673
674 intarray = (int *) array;
675
676 for (i = 0; i < numvars; i++) {
677 val = val * 997 + intarray[i];
678 }
679
680 return ((val < 0) ? -val : val) % modulus;
681
682 } /* end of array_hash */
683
684
685 /**Function********************************************************************
686
687 Synopsis [Comparison function for the computed table.]
688
689 Description [Comparison function for the computed table. Returns 0 if
690 the two arrays are equal; 1 otherwise.]
691
692 SideEffects [None]
693
694 SeeAlso []
695
696 ******************************************************************************/
697 static int
array_compare(const char * array1,const char * array2)698 array_compare(
699 const char * array1,
700 const char * array2)
701 {
702 int i;
703 int *intarray1, *intarray2;
704
705 intarray1 = (int *) array1;
706 intarray2 = (int *) array2;
707
708 for (i = 0; i < numvars; i++) {
709 if (intarray1[i] != intarray2[i]) return(1);
710 }
711 return(0);
712
713 } /* end of array_compare */
714
715
716 /**Function********************************************************************
717
718 Synopsis [Returns the index of the fittest individual.]
719
720 Description []
721
722 SideEffects [None]
723
724 SeeAlso []
725
726 ******************************************************************************/
727 static int
find_best(void)728 find_best(void)
729 {
730 int i,small;
731
732 small = 0;
733 for (i = 1; i < popsize; i++) {
734 if (STOREDD(i,numvars) < STOREDD(small,numvars)) {
735 small = i;
736 }
737 }
738 return(small);
739
740 } /* end of find_best */
741
742
743 /**Function********************************************************************
744
745 Synopsis [Returns the average fitness of the population.]
746
747 Description []
748
749 SideEffects [None]
750
751 SeeAlso []
752
753 ******************************************************************************/
754 #ifdef DD_STATS
755 static double
find_average_fitness(void)756 find_average_fitness(void)
757 {
758 int i;
759 int total_fitness = 0;
760 double average_fitness;
761
762 for (i = 0; i < popsize; i++) {
763 total_fitness += STOREDD(i,numvars);
764 }
765 average_fitness = (double) total_fitness / (double) popsize;
766 return(average_fitness);
767
768 } /* end of find_average_fitness */
769 #endif
770
771
772 /**Function********************************************************************
773
774 Synopsis [Performs the crossover between two parents.]
775
776 Description [Performs the crossover between two randomly chosen
777 parents, and creates two children, x1 and x2. Uses the Partially
778 Matched Crossover operator.]
779
780 SideEffects [None]
781
782 SeeAlso []
783
784 ******************************************************************************/
785 static int
PMX(int maxvar)786 PMX(
787 int maxvar)
788 {
789 int cut1,cut2; /* the two cut positions (random) */
790 int mom,dad; /* the two randomly chosen parents */
791 int *inv1; /* inverse permutations for repair algo */
792 int *inv2;
793 int i; /* loop vars */
794 int u,v; /* aux vars */
795
796 inv1 = ABC_ALLOC(int,maxvar);
797 if (inv1 == NULL) {
798 return(0);
799 }
800 inv2 = ABC_ALLOC(int,maxvar);
801 if (inv2 == NULL) {
802 ABC_FREE(inv1);
803 return(0);
804 }
805
806 /* Choose two orders from the population using roulette wheel. */
807 if (!roulette(&mom,&dad)) {
808 ABC_FREE(inv1);
809 ABC_FREE(inv2);
810 return(0);
811 }
812
813 /* Choose two random cut positions. A cut in position i means that
814 ** the cut immediately precedes position i. If cut1 < cut2, we
815 ** exchange the middle of the two orderings; otherwise, we
816 ** exchange the beginnings and the ends.
817 */
818 cut1 = rand_int(numvars-1);
819 do {
820 cut2 = rand_int(numvars-1);
821 } while (cut1 == cut2);
822
823 #if 0
824 /* Print out the parents. */
825 (void) fprintf(table->out,
826 "Crossover of %d (mom) and %d (dad) between %d and %d\n",
827 mom,dad,cut1,cut2);
828 for (i = 0; i < numvars; i++) {
829 if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
830 (void) fprintf(table->out,"%2d ",STOREDD(mom,i));
831 }
832 (void) fprintf(table->out,"\n");
833 for (i = 0; i < numvars; i++) {
834 if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
835 (void) fprintf(table->out,"%2d ",STOREDD(dad,i));
836 }
837 (void) fprintf(table->out,"\n");
838 #endif
839
840 /* Initialize the inverse permutations: -1 means yet undetermined. */
841 for (i = 0; i < maxvar; i++) {
842 inv1[i] = -1;
843 inv2[i] = -1;
844 }
845
846 /* Copy the portions whithin the cuts. */
847 for (i = cut1; i != cut2; i = (i == numvars-1) ? 0 : i+1) {
848 STOREDD(popsize,i) = STOREDD(dad,i);
849 inv1[STOREDD(popsize,i)] = i;
850 STOREDD(popsize+1,i) = STOREDD(mom,i);
851 inv2[STOREDD(popsize+1,i)] = i;
852 }
853
854 /* Now apply the repair algorithm outside the cuts. */
855 for (i = cut2; i != cut1; i = (i == numvars-1 ) ? 0 : i+1) {
856 v = i;
857 do {
858 u = STOREDD(mom,v);
859 v = inv1[u];
860 } while (v != -1);
861 STOREDD(popsize,i) = u;
862 inv1[u] = i;
863 v = i;
864 do {
865 u = STOREDD(dad,v);
866 v = inv2[u];
867 } while (v != -1);
868 STOREDD(popsize+1,i) = u;
869 inv2[u] = i;
870 }
871
872 #if 0
873 /* Print the results of crossover. */
874 for (i = 0; i < numvars; i++) {
875 if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
876 (void) fprintf(table->out,"%2d ",STOREDD(popsize,i));
877 }
878 (void) fprintf(table->out,"\n");
879 for (i = 0; i < numvars; i++) {
880 if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
881 (void) fprintf(table->out,"%2d ",STOREDD(popsize+1,i));
882 }
883 (void) fprintf(table->out,"\n");
884 #endif
885
886 ABC_FREE(inv1);
887 ABC_FREE(inv2);
888 return(1);
889
890 } /* end of PMX */
891
892
893 /**Function********************************************************************
894
895 Synopsis [Selects two parents with the roulette wheel method.]
896
897 Description [Selects two distinct parents with the roulette wheel method.]
898
899 SideEffects [The indices of the selected parents are returned as side
900 effects.]
901
902 SeeAlso []
903
904 ******************************************************************************/
905 static int
roulette(int * p1,int * p2)906 roulette(
907 int * p1,
908 int * p2)
909 {
910 double *wheel;
911 double spin;
912 int i;
913
914 wheel = ABC_ALLOC(double,popsize);
915 if (wheel == NULL) {
916 return(0);
917 }
918
919 /* The fitness of an individual is the reciprocal of its size. */
920 wheel[0] = 1.0 / (double) STOREDD(0,numvars);
921
922 for (i = 1; i < popsize; i++) {
923 wheel[i] = wheel[i-1] + 1.0 / (double) STOREDD(i,numvars);
924 }
925
926 /* Get a random number between 0 and wheel[popsize-1] (that is,
927 ** the sum of all fitness values. 2147483561 is the largest number
928 ** returned by Cudd_Random.
929 */
930 spin = wheel[numvars-1] * (double) Cudd_Random() / 2147483561.0;
931
932 /* Find the lucky element by scanning the wheel. */
933 for (i = 0; i < popsize; i++) {
934 if (spin <= wheel[i]) break;
935 }
936 *p1 = i;
937
938 /* Repeat the process for the second parent, making sure it is
939 ** distinct from the first.
940 */
941 do {
942 spin = wheel[popsize-1] * (double) Cudd_Random() / 2147483561.0;
943 for (i = 0; i < popsize; i++) {
944 if (spin <= wheel[i]) break;
945 }
946 } while (i == *p1);
947 *p2 = i;
948
949 ABC_FREE(wheel);
950 return(1);
951
952 } /* end of roulette */
953
954
955 ABC_NAMESPACE_IMPL_END
956
957
958