IDGBDD: The novel use of ID3 to improve Genetic algorithm in BDD reordering

ID3 is a classical decision algorithm that has been widely used in decision making problem. Ordered Binary Decision Diagram (OBDD) is a data structure for switching functions that has been used in many areas of Boolean function manipulation. The major problem with BDD-based calculations is the variable ordering which addresses the question of finding an ordering of the input variables which minimizes the size of the BDD-representation. We used ID3 as a heuristic method to improve the genetic algorithm method that has used for reordering BDD (IDGBDD) [1]. In this approach, we used ID3 as a best preorder predictor. Then we applied this order set as a first order level in BDDs. At the end, we used the genetic algorithm as a process stage to perform the final reordering to reduce the number of nodes. The result of using ID3 algorithm was reduction the number of nodes in 57% of the benchmark experiment examples. however, in 9.5% of the benchmark experiment examples, we have encountered increase in the number of nodes. It also decreased the number of iteration in 71% of the examples, but we also have encountered increase of the iteration in 4.7% of ran examples. The average improvement amount that obtained in decreased node number was equal 11.183%. Also the average improvement amount that obtained in decreased iteration was equal 25.79%.