source: vis_dev/glu-2.3/src/cuBdd/cuddGenetic.c @ 100

Last change on this file since 100 was 13, checked in by cecile, 13 years ago

library glu 2.3

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