cudd/cuddGenetic.c File Reference

Genetic algorithm for variable reordering. More...

#include "util.h"
#include "cuddInt.h"
Include dependency graph for cuddGenetic.c:

Data Structures

struct  GeneticInfo
 Miscellaneous information. More...

Defines

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

Typedefs

typedef struct GeneticInfo GeneticInfo_t

Functions

int cuddGa (DdManager *table, int lower, int upper)
 Genetic algorithm for DD reordering.
static int make_random (DdManager *table, int lower, GeneticInfo_t *info)
 Generates the random sequences for the initial population.
static int sift_up (DdManager *table, int x, int x_low)
 Moves one variable up.
static int build_dd (DdManager *table, int num, int lower, int upper, GeneticInfo_t *info)
 Builds a DD from a given order.
static int largest (GeneticInfo_t *info)
 Finds the largest DD in the population.
static int rand_int (DdManager *dd, int a)
 Generates a random number between 0 and the integer a.
static int array_hash (void const *array, int modulus, void const *arg)
 Hash function for the computed table.
static int array_compare (void const *array1, void const *array2, void const *arg)
 Comparison function for the computed table.
static int find_best (GeneticInfo_t *info)
 Returns the index of the fittest individual.
static int PMX (DdManager *dd, int maxvar, GeneticInfo_t *info)
 Returns the average fitness of the population.
static int roulette (DdManager *dd, int *p1, int *p2, GeneticInfo_t *info)
 Selects two distinct parents with the roulette wheel method.

Detailed Description

Genetic algorithm for variable reordering.

The genetic algorithm implemented here is as follows. We start with the current DD order. We sift this order and use this as the reference DD. We only keep 1 DD around for the entire process and simply rearrange the order of this DD, storing the various orders and their corresponding DD sizes. We generate more random orders to build an initial population. This initial population is 3 times the number of variables, with a maximum of 120. Each random order is built (from the reference DD) and its size stored. Each random order is also sifted to keep the DD sizes fairly small. Then a crossover is performed between two orders (picked randomly) and the two resulting DDs are built and sifted. For each new order, if its size is smaller than any DD in the population, it is inserted into the population and the DD with the largest number of nodes is thrown out. The crossover process happens up to 50 times, and at this point the DD in the population with the smallest size is chosen as the result. This DD must then be built from the reference DD.

Author:
Curt Musfeldt, Alan Shuler, Fabio Somenzi

Copyright (c) 1995-2015, Regents of the University of Colorado

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


Function Documentation

static int array_compare ( void const *  array1,
void const *  array2,
void const *  arg 
) [static]

Comparison function for the computed table.

Returns:
0 if the two arrays are equal; 1 otherwise.
Side effects
None
static int array_hash ( void const *  array,
int  modulus,
void const *  arg 
) [static]

Hash function for the computed table.

Returns:
the bucket number.
Side effects
None
static int build_dd ( DdManager table,
int  num,
int  lower,
int  upper,
GeneticInfo_t info 
) [static]

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.
Side effects
None
int cuddGa ( DdManager table,
int  lower,
int  upper 
)

Genetic algorithm for DD reordering.

The two children of a crossover will be stored in storedd[popsize] and storedd[popsize+1] --- the last two slots in the storedd array. (This will make comparisons and replacement easy.)

Returns:
1 in case of success; 0 otherwise.
Side effects
None
Parameters:
table manager
lower lowest level to be reordered
upper highest level to be reorderded
static int find_best ( GeneticInfo_t info  )  [static]

Returns the index of the fittest individual.

Side effects
None
static int largest ( GeneticInfo_t info  )  [static]

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).]

Side effects
None
static int make_random ( DdManager table,
int  lower,
GeneticInfo_t info 
) [static]

Generates the random sequences for the initial population.

The sequences are permutations of the indices between lower and upper in the current order.

Side effects
None
static int PMX ( DdManager dd,
int  maxvar,
GeneticInfo_t info 
) [static]

Returns the average fitness of the population.

Side effects
None Performs the crossover between two parents.

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

Side effects
None
static int rand_int ( DdManager dd,
int  a 
) [static]

Generates a random number between 0 and the integer a.

Side effects
None
static int roulette ( DdManager dd,
int *  p1,
int *  p2,
GeneticInfo_t info 
) [static]

Selects two distinct parents with the roulette wheel method.

Side effects
The indices of the selected parents are returned as side effects.
static int sift_up ( DdManager table,
int  x,
int  x_low 
) [static]

Moves one variable up.

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
Side effects
None
 All Data Structures Files Functions Variables Typedefs Enumerations Defines

Generated on 31 Dec 2015 for cudd by  doxygen 1.6.1