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

Macros
#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. More...

static int	make_random (DdManager table, int lower, GeneticInfo_t info)
	Generates the random sequences for the initial population. More...

static int	sift_up (DdManager *table, int x, int x_low)
	Moves one variable up. More...

static int	build_dd (DdManager table, int num, int lower, int upper, GeneticInfo_t info)
	Builds a DD from a given order. More...

static int	largest (GeneticInfo_t *info)
	Finds the largest DD in the population. More...

static int	rand_int (DdManager *dd, int a)
	Generates a random number between 0 and the integer a. More...

static int	array_hash (void const array, int modulus, void const arg)
	Hash function for the computed table. More...

static int	array_compare (void const array1, void const array2, void const *arg)
	Comparison function for the computed table. More...

static int	find_best (GeneticInfo_t *info)
	Returns the index of the fittest individual. More...

static int	PMX (DdManager dd, int maxvar, GeneticInfo_t info)
	Returns the average fitness of the population. More...

static int	roulette (DdManager dd, int p1, int p2, GeneticInfo_t info)
	Selects two distinct parents with the roulette wheel method. More...

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

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

◆ array_compare()

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

◆ array_hash()

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

◆ build_dd()

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

◆ cuddGa()

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

◆ find_best()

static int find_best ( GeneticInfo_t * info )

static

Returns the index of the fittest individual.

Side effects None

◆ largest()

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

◆ make_random()

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

◆ PMX()

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

◆ rand_int()

static int rand_int	(	DdManager *	dd,
		int	a
	)

static

Generates a random number between 0 and the integer a.

Side effects None

◆ roulette()

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.

◆ sift_up()

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

Data Structures

Macros

Typedefs

Functions

Detailed Description

Function Documentation

◆ array_compare()

◆ array_hash()

◆ build_dd()

◆ cuddGa()

◆ find_best()

◆ largest()

◆ make_random()

◆ PMX()

◆ rand_int()

◆ roulette()

◆ sift_up()