distr/cudd/cuddGenetic.c

   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
 103 static char rcsid[] DD_UNUSED = "$Id: cuddGenetic.c,v 1.28 2004/08/13 18:04:48 fabio Exp $";
 104 #endif
 105
 106 static int popsize;             /* the size of the population */
 107 static 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 */
 116 static int *storedd;
 117 static st_table *computed;      /* hash table to identify existing orders */
 118 static int *repeat;             /* how many times an order is present */
 119 static int large;               /* stores the index of the population with
 120                                 ** the largest number of nodes in the DD */
 121 static int result;
 122 static 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
 134 extern "C" {
 135 #endif
 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 (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 #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 ******************************************************************************/
 187 int
 188 cuddGa(
 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 ******************************************************************************/
 444 static int
 445 make_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 ******************************************************************************/
 512 static int
 513 sift_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 ******************************************************************************/
 548 static int
 549 build_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 ******************************************************************************/
 619 static int
 620 largest(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 ******************************************************************************/
 648 static int
 649 rand_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 ******************************************************************************/
 669 static int
 670 array_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 ******************************************************************************/
 701 static int
 702 array_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 ******************************************************************************/
 731 static int
 732 find_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
 759 static double
 760 find_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 ******************************************************************************/
 789 static int
 790 PMX(
 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 ******************************************************************************/
 909 static int
 910 roulette(
 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