Genetic algorithm for variable reordering. More...
#include "util.h"
#include "cuddInt.h"
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. |
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.
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.
static int array_compare | ( | void const * | array1, | |
void const * | array2, | |||
void const * | arg | |||
) | [static] |
Comparison function for the computed table.
static int array_hash | ( | void const * | array, | |
int | modulus, | |||
void const * | arg | |||
) | [static] |
Hash function for the computed table.
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.
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.)
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.
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).]
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.
static int PMX | ( | DdManager * | dd, | |
int | maxvar, | |||
GeneticInfo_t * | info | |||
) | [static] |
Returns the average fitness of the population.
Performs the crossover between two randomly chosen parents, and creates two children, x1 and x2. Uses the Partially Matched Crossover operator.
static int rand_int | ( | DdManager * | dd, | |
int | a | |||
) | [static] |
Generates a random number between 0 and the integer a.
static int roulette | ( | DdManager * | dd, | |
int * | p1, | |||
int * | p2, | |||
GeneticInfo_t * | info | |||
) | [static] |
Selects two distinct parents with the roulette wheel method.
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.