cuddgenetic.c

主要进行大规模的电路综合

/**Function********************************************************************

  Synopsis    [Moves one variable up.]

  Description [Takes a variable from position x and sifts it up to
  position x_low;  x_low should be less than x. Returns 1 if successful;
  0 otherwise]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
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 */


/**Function********************************************************************

  Synopsis [Builds a DD from a given order.]

  Description [Builds a DD from a given order.  This procedure also
  sifts the final order and inserts into the array the size in nodes
  of the result. Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
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(computed,(char *)&STOREDD(num,0),(char **)&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 */


/**Function********************************************************************

  Synopsis    [Finds the largest DD in the population.]

  Description [Finds the largest DD in the population. If an order is
  repeated, it avoids choosing the copy that is in the computed table
  (it has repeat[i] > 1).]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
largest(
   )
{
    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 */


/**Function********************************************************************

  Synopsis    [Generates a random number between 0 and the integer a.]

  Description []

  SideEffects [None]

  SeeAlso     []

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

} /* end of rand_int */


/**Function********************************************************************

  Synopsis    [Hash function for the computed table.]

  Description [Hash function for the computed table. Returns the bucket
  number.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
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 */


/**Function********************************************************************

  Synopsis    [Comparison function for the computed table.]

  Description [Comparison function for the computed table. Returns 0 if
  the two arrays are equal; 1 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
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 */


/**Function********************************************************************

  Synopsis    [Returns the index of the fittest individual.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
find_best(
   )
{
    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 */


/**Function********************************************************************

  Synopsis    [Returns the average fitness of the population.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static double
find_average_fitness(
   )
{
    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 */


/**Function********************************************************************

  Synopsis [Performs the crossover between two parents.]

  Description [Performs the crossover between two randomly chosen
  parents, and creates two children, x1 and x2. Uses the Partially
  Matched Crossover operator.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
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 */


/**Function********************************************************************

  Synopsis    [Selects two parents with the roulette wheel method.]

  Description [Selects two distinct parents with the roulette wheel method.]

  SideEffects [The indices of the selected parents are returned as side
  effects.]

  SeeAlso     []

******************************************************************************/
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 */