cuddGenetic.c

Go to the documentation of this file.

#include "CUDD/util.h"
#include "CUDD/cuddInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef lint
static char rcsid[] DD_UNUSED = "$Id: cuddGenetic.c,v 1.30 2012/02/05 01:07:18 fabio Exp $";
#endif

static int popsize;     /* the size of the population */
static int numvars;     /* the number of input variables in the ckt. */
/* storedd stores the population orders and sizes. This table has two
** extra rows and one extras column. The two extra rows are used for the
** offspring produced by a crossover. Each row stores one order and its
** size. The order is stored by storing the indices of variables in the
** order in which they appear in the order. The table is in reality a
** one-dimensional array which is accessed via a macro to give the illusion
** it is a two-dimensional structure.
*/
static int *storedd;
static st_table *computed;  /* hash table to identify existing orders */
static int *repeat;     /* how many times an order is present */
static int large;       /* stores the index of the population with
                ** the largest number of nodes in the DD */
static int result;
static int cross;       /* the number of crossovers to perform */

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/* macro used to access the population table as if it were a
** two-dimensional structure.
*/
#define STOREDD(i,j)    storedd[(i)*(numvars+1)+(j)]

#ifdef __cplusplus
extern "C" {
#endif

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static int make_random (DdManager *table, int lower);
static int sift_up (DdManager *table, int x, int x_low);
static int build_dd (DdManager *table, int num, int lower, int upper);
static int largest (void);
static int rand_int (int a);
static int array_hash (char *array, int modulus);
static int array_compare (const char *array1, const char *array2);
static int find_best (void);
#ifdef DD_STATS
static double find_average_fitness (void);
#endif
static int PMX (int maxvar);
static int roulette (int *p1, int *p2);

#ifdef __cplusplus
}
#endif

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


int
cuddGa(
  DdManager * table /* manager */,
  int  lower /* lowest level to be reordered */,
  int  upper /* highest level to be reorderded */)
{
    int     i,n,m;      /* dummy/loop vars */
    int     index;
#ifdef DD_STATS
    double  average_fitness;
#endif
    int     small;      /* index of smallest DD in population */

    /* Do an initial sifting to produce at least one reasonable individual. */
    if (!cuddSifting(table,lower,upper)) return(0);

    /* Get the initial values. */
    numvars = upper - lower + 1; /* number of variables to be reordered */
    if (table->populationSize == 0) {
    popsize = 3 * numvars;  /* population size is 3 times # of vars */
    if (popsize > 120) {
        popsize = 120;  /* Maximum population size is 120 */
    }
    } else {
    popsize = table->populationSize;  /* user specified value */
    }
    if (popsize < 4) popsize = 4;   /* enforce minimum population size */

    /* Allocate population table. */
    storedd = ALLOC(int,(popsize+2)*(numvars+1));
    if (storedd == NULL) {
    table->errorCode = CUDD_MEMORY_OUT;
    return(0);
    }

    /* Initialize the computed table. This table is made up of two data
    ** structures: A hash table with the key given by the order, which says
    ** if a given order is present in the population; and the repeat
    ** vector, which says how many copies of a given order are stored in
    ** the population table. If there are multiple copies of an order, only
    ** one has a repeat count greater than 1. This copy is the one pointed
    ** by the computed table.
    */
    repeat = ALLOC(int,popsize);
    if (repeat == NULL) {
    table->errorCode = CUDD_MEMORY_OUT;
    FREE(storedd);
    return(0);
    }
    for (i = 0; i < popsize; i++) {
    repeat[i] = 0;
    }
    computed = st_init_table(array_compare,array_hash);
    if (computed == NULL) {
    table->errorCode = CUDD_MEMORY_OUT;
    FREE(storedd);
    FREE(repeat);
    return(0);
    }

    /* Copy the current DD and its size to the population table. */
    for (i = 0; i < numvars; i++) {
    STOREDD(0,i) = table->invperm[i+lower]; /* order of initial DD */
    }
    STOREDD(0,numvars) = table->keys - table->isolated; /* size of initial DD */

    /* Store the initial order in the computed table. */
    if (st_insert(computed,(char *)storedd,(char *) 0) == ST_OUT_OF_MEM) {
    FREE(storedd);
    FREE(repeat);
    st_free_table(computed);
    return(0);
    }
    repeat[0]++;

    /* Insert the reverse order as second element of the population. */
    for (i = 0; i < numvars; i++) {
    STOREDD(1,numvars-1-i) = table->invperm[i+lower]; /* reverse order */
    }

    /* Now create the random orders. make_random fills the population
    ** table with random permutations. The successive loop builds and sifts
    ** the DDs for the reverse order and each random permutation, and stores
    ** the results in the computed table.
    */
    if (!make_random(table,lower)) {
    table->errorCode = CUDD_MEMORY_OUT;
    FREE(storedd);
    FREE(repeat);
    st_free_table(computed);
    return(0);
    }
    for (i = 1; i < popsize; i++) {
    result = build_dd(table,i,lower,upper); /* build and sift order */
    if (!result) {
        FREE(storedd);
        FREE(repeat);
        st_free_table(computed);
        return(0);
    }
    if (st_lookup_int(computed,(char *)&STOREDD(i,0),&index)) {
        repeat[index]++;
    } else {
        if (st_insert(computed,(char *)&STOREDD(i,0),(char *)(long)i) ==
        ST_OUT_OF_MEM) {
        FREE(storedd);
        FREE(repeat);
        st_free_table(computed);
        return(0);
        }
        repeat[i]++;
    }
    }

#if 0
#ifdef DD_STATS
    /* Print the initial population. */
    (void) fprintf(table->out,"Initial population after sifting\n");
    for (m = 0; m < popsize; m++) {
    for (i = 0; i < numvars; i++) {
        (void) fprintf(table->out," %2d",STOREDD(m,i));
    }
    (void) fprintf(table->out," : %3d (%d)\n",
               STOREDD(m,numvars),repeat[m]);
    }
#endif
#endif

    small = find_best();
#ifdef DD_STATS
    average_fitness = find_average_fitness();
    (void) fprintf(table->out,"\nInitial population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
#endif

    /* Decide how many crossovers should be tried. */
    if (table->numberXovers == 0) {
    cross = 3*numvars;
    if (cross > 60) {   /* do a maximum of 50 crossovers */
        cross = 60;
    }
    } else {
    cross = table->numberXovers;      /* use user specified value */
    }
    if (cross >= popsize) {
    cross = popsize;
    }

    /* Perform the crossovers to get the best order. */
    for (m = 0; m < cross; m++) {
    if (!PMX(table->size)) {    /* perform one crossover */
        table->errorCode = CUDD_MEMORY_OUT;
        FREE(storedd);
        FREE(repeat);
        st_free_table(computed);
        return(0);
    }
    /* The offsprings are left in the last two entries of the
    ** population table. These are now considered in turn.
    */
    for (i = popsize; i <= popsize+1; i++) {
        result = build_dd(table,i,lower,upper); /* build and sift child */
        if (!result) {
        FREE(storedd);
        FREE(repeat);
        st_free_table(computed);
        return(0);
        }
        large = largest();  /* find the largest DD in population */

        /* If the new child is smaller than the largest DD in the current
        ** population, enter it into the population in place of the
        ** largest DD.
        */
        if (STOREDD(i,numvars) < STOREDD(large,numvars)) {
        /* Look up the largest DD in the computed table.
        ** Decrease its repetition count. If the repetition count
        ** goes to 0, remove the largest DD from the computed table.
        */
        result = st_lookup_int(computed,(char *)&STOREDD(large,0),
                       &index);
        if (!result) {
            FREE(storedd);
            FREE(repeat);
            st_free_table(computed);
            return(0);
        }
        repeat[index]--;
        if (repeat[index] == 0) {
            int *pointer = &STOREDD(index,0);
            result = st_delete(computed, &pointer, NULL);
            if (!result) {
            FREE(storedd);
            FREE(repeat);
            st_free_table(computed);
            return(0);
            }
        }
        /* Copy the new individual to the entry of the
        ** population table just made available and update the
        ** computed table.
        */
        for (n = 0; n <= numvars; n++) {
            STOREDD(large,n) = STOREDD(i,n);
        }
        if (st_lookup_int(computed,(char *)&STOREDD(large,0),
                  &index)) {
            repeat[index]++;
        } else {
            if (st_insert(computed,(char *)&STOREDD(large,0),
            (char *)(long)large) == ST_OUT_OF_MEM) {
            FREE(storedd);
            FREE(repeat);
            st_free_table(computed);
            return(0);
            }
            repeat[large]++;
        }
        }
    }
    }

    /* Find the smallest DD in the population and build it;
    ** that will be the result.
    */
    small = find_best();

    /* Print stats on the final population. */
#ifdef DD_STATS
    average_fitness = find_average_fitness();
    (void) fprintf(table->out,"\nFinal population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
#endif

    /* Clean up, build the result DD, and return. */
    st_free_table(computed);
    computed = NULL;
    result = build_dd(table,small,lower,upper);
    FREE(storedd);
    FREE(repeat);
    return(result);

} /* end of cuddGa */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

static int
make_random(
  DdManager * table,
  int  lower)
{
    int i,j;        /* loop variables */
    int *used;      /* is a number already in a permutation */
    int next;       /* next random number without repetitions */

    used = ALLOC(int,numvars);
    if (used == NULL) {
    table->errorCode = CUDD_MEMORY_OUT;
    return(0);
    }
#if 0
#ifdef DD_STATS
    (void) fprintf(table->out,"Initial population before sifting\n");
    for (i = 0; i < 2; i++) {
    for (j = 0; j < numvars; j++) {
        (void) fprintf(table->out," %2d",STOREDD(i,j));
    }
    (void) fprintf(table->out,"\n");
    }
#endif
#endif
    for (i = 2; i < popsize; i++) {
        for (j = 0; j < numvars; j++) {
        used[j] = 0;
    }
    /* Generate a permutation of {0...numvars-1} and use it to
    ** permute the variables in the layesr from lower to upper.
    */
        for (j = 0; j < numvars; j++) {
        do {
        next = rand_int(numvars-1);
        } while (used[next] != 0);
        used[next] = 1;
        STOREDD(i,j) = table->invperm[next+lower];
        }
#if 0
#ifdef DD_STATS
    /* Print the order just generated. */
    for (j = 0; j < numvars; j++) {
        (void) fprintf(table->out," %2d",STOREDD(i,j));
    }
    (void) fprintf(table->out,"\n");
#endif
#endif
    }
    FREE(used);
    return(1);

} /* end of make_random */


static int
sift_up(
  DdManager * table,
  int  x,
  int  x_low)
{
    int        y;
    int        size;

    y = cuddNextLow(table,x);
    while (y >= x_low) {
    size = cuddSwapInPlace(table,y,x);
    if (size == 0) {
        return(0);
    }
    x = y;
    y = cuddNextLow(table,x);
    }
    return(1);

} /* end of sift_up */


static int
build_dd(
  DdManager * table,
  int  num /* the index of the individual to be built */,
  int  lower,
  int  upper)
{
    int     i,j;        /* loop vars */
    int     position;
    int     index;
    int     limit;      /* how large the DD for this order can grow */
    int     size;

    /* Check the computed table. If the order already exists, it
    ** suffices to copy the size from the existing entry.
    */
    if (computed && st_lookup_int(computed,(char *)&STOREDD(num,0),&index)) {
    STOREDD(num,numvars) = STOREDD(index,numvars);
#ifdef DD_STATS
    (void) fprintf(table->out,"\nCache hit for index %d", index);
#endif
    return(1);
    }

    /* Stop if the DD grows 20 times larges than the reference size. */
    limit = 20 * STOREDD(0,numvars);

    /* Sift up the variables so as to build the desired permutation.
    ** First the variable that has to be on top is sifted to the top.
    ** Then the variable that has to occupy the secon position is sifted
    ** up to the second position, and so on.
    */
    for (j = 0; j < numvars; j++) {
    i = STOREDD(num,j);
    position = table->perm[i];
    result = sift_up(table,position,j+lower);
    if (!result) return(0);
    size = table->keys - table->isolated;
    if (size > limit) break;
    }

    /* Sift the DD just built. */
#ifdef DD_STATS
    (void) fprintf(table->out,"\n");
#endif
    result = cuddSifting(table,lower,upper);
    if (!result) return(0);

    /* Copy order and size to table. */
    for (j = 0; j < numvars; j++) {
    STOREDD(num,j) = table->invperm[lower+j];
    }
    STOREDD(num,numvars) = table->keys - table->isolated; /* size of new DD */
    return(1);

} /* end of build_dd */


static int
largest(void)
{
    int i;  /* loop var */
    int big;    /* temporary holder to return result */

    big = 0;
    while (repeat[big] > 1) big++;
    for (i = big + 1; i < popsize; i++) {
    if (STOREDD(i,numvars) >= STOREDD(big,numvars) && repeat[i] <= 1) {
        big = i;
    }
    }
    return(big);

} /* end of largest */


static int
rand_int(
  int  a)
{
    return(Cudd_Random() % (a+1));

} /* end of rand_int */


static int
array_hash(
  char * array,
  int  modulus)
{
    int val = 0;
    int i;
    int *intarray;

    intarray = (int *) array;

    for (i = 0; i < numvars; i++) {
    val = val * 997 + intarray[i];
    }

    return ((val < 0) ? -val : val) % modulus;

} /* end of array_hash */


static int
array_compare(
  const char * array1,
  const char * array2)
{
    int i;
    int *intarray1, *intarray2;

    intarray1 = (int *) array1;
    intarray2 = (int *) array2;

    for (i = 0; i < numvars; i++) {
    if (intarray1[i] != intarray2[i]) return(1);
    }
    return(0);

} /* end of array_compare */


static int
find_best(void)
{
    int i,small;

    small = 0;
    for (i = 1; i < popsize; i++) {
    if (STOREDD(i,numvars) < STOREDD(small,numvars)) {
        small = i;
    }
    }
    return(small);

} /* end of find_best */


#ifdef DD_STATS
static double
find_average_fitness(void)
{
    int i;
    int total_fitness = 0;
    double average_fitness;

    for (i = 0; i < popsize; i++) {
    total_fitness += STOREDD(i,numvars);
    }
    average_fitness = (double) total_fitness / (double) popsize;
    return(average_fitness);

} /* end of find_average_fitness */
#endif


static int
PMX(
  int  maxvar)
{
    int     cut1,cut2;  /* the two cut positions (random) */
    int     mom,dad;    /* the two randomly chosen parents */
    int     *inv1;      /* inverse permutations for repair algo */
    int     *inv2;
    int     i;      /* loop vars */
    int     u,v;        /* aux vars */

    inv1 = ALLOC(int,maxvar);
    if (inv1 == NULL) {
    return(0);
    }
    inv2 = ALLOC(int,maxvar);
    if (inv2 == NULL) {
    FREE(inv1);
    return(0);
    }

    /* Choose two orders from the population using roulette wheel. */
    if (!roulette(&mom,&dad)) {
    FREE(inv1);
    FREE(inv2);
    return(0);
    }

    /* Choose two random cut positions. A cut in position i means that
    ** the cut immediately precedes position i.  If cut1 < cut2, we
    ** exchange the middle of the two orderings; otherwise, we
    ** exchange the beginnings and the ends.
    */
    cut1 = rand_int(numvars-1);
    do {
    cut2 = rand_int(numvars-1);
    } while (cut1 == cut2);

#if 0
    /* Print out the parents. */
    (void) fprintf(table->out,
           "Crossover of %d (mom) and %d (dad) between %d and %d\n",
           mom,dad,cut1,cut2);
    for (i = 0; i < numvars; i++) {
    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
    (void) fprintf(table->out,"%2d ",STOREDD(mom,i));
    }
    (void) fprintf(table->out,"\n");
    for (i = 0; i < numvars; i++) {
    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
    (void) fprintf(table->out,"%2d ",STOREDD(dad,i));
    }
    (void) fprintf(table->out,"\n");
#endif

    /* Initialize the inverse permutations: -1 means yet undetermined. */
    for (i = 0; i < maxvar; i++) {
    inv1[i] = -1;
    inv2[i] = -1;
    }

    /* Copy the portions whithin the cuts. */
    for (i = cut1; i != cut2; i = (i == numvars-1) ? 0 : i+1) {
    STOREDD(popsize,i) = STOREDD(dad,i);
    inv1[STOREDD(popsize,i)] = i;
    STOREDD(popsize+1,i) = STOREDD(mom,i);
    inv2[STOREDD(popsize+1,i)] = i;
    }

    /* Now apply the repair algorithm outside the cuts. */
    for (i = cut2; i != cut1; i = (i == numvars-1 ) ? 0 : i+1) {
    v = i;
    do {
        u = STOREDD(mom,v);
        v = inv1[u];
    } while (v != -1);
    STOREDD(popsize,i) = u;
    inv1[u] = i;
    v = i;
    do {
        u = STOREDD(dad,v);
        v = inv2[u];
    } while (v != -1);
    STOREDD(popsize+1,i) = u;
    inv2[u] = i;
    }

#if 0
    /* Print the results of crossover. */
    for (i = 0; i < numvars; i++) {
    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
    (void) fprintf(table->out,"%2d ",STOREDD(popsize,i));
    }
    (void) fprintf(table->out,"\n");
    for (i = 0; i < numvars; i++) {
    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
    (void) fprintf(table->out,"%2d ",STOREDD(popsize+1,i));
    }
    (void) fprintf(table->out,"\n");
#endif

    FREE(inv1);
    FREE(inv2);
    return(1);

} /* end of PMX */


static int
roulette(
  int * p1,
  int * p2)
{
    double *wheel;
    double spin;
    int i;

    wheel = ALLOC(double,popsize);
    if (wheel == NULL) {
    return(0);
    }

    /* The fitness of an individual is the reciprocal of its size. */
    wheel[0] = 1.0 / (double) STOREDD(0,numvars);

    for (i = 1; i < popsize; i++) {
    wheel[i] = wheel[i-1] + 1.0 / (double) STOREDD(i,numvars);
    }

    /* Get a random number between 0 and wheel[popsize-1] (that is,
    ** the sum of all fitness values. 2147483561 is the largest number
    ** returned by Cudd_Random.
    */
    spin = wheel[numvars-1] * (double) Cudd_Random() / 2147483561.0;

    /* Find the lucky element by scanning the wheel. */
    for (i = 0; i < popsize; i++) {
    if (spin <= wheel[i]) break;
    }
    *p1 = i;

    /* Repeat the process for the second parent, making sure it is
    ** distinct from the first.
    */
    do {
    spin = wheel[popsize-1] * (double) Cudd_Random() / 2147483561.0;
    for (i = 0; i < popsize; i++) {
        if (spin <= wheel[i]) break;
    }
    } while (i == *p1);
    *p2 = i;

    FREE(wheel);
    return(1);

} /* end of roulette */