Minimizing the number of one-paths in BDDs by an evolutionary algorithm

Ordered binary decision diagrams (BDDs) are used in VLSI CAD, especially for the canonical representation of Boolean functions. In the last decade, the method of choice for optimizing this data structure was minimizing the number of nodes in the associated graph. However, recent works have shown that the number of paths is also important. In this work, minimizing the number of one-paths of BDDs is accomplished by an evolutionary algorithm (EA) acting on the permutation of variables. The optimal operator weights for the EA were determined by a parameter study. Experimental results demonstrate the efficiency of our approach.