GENETIC ALGORITHM FOR BINARY AND FUNCTIONAL DECISION DIAGRAMS OPTIMIZATION

Suzana Stojković, Darko Veličković, Claudio Moraga

DOI Number
10.2298/FUEE1802169S
First page
169
Last page
187

Abstract


Decision diagrams (DD) are a widely used data structure for discrete functions representation. The major problem in DD-based applicationsis the DD size minimization (reduction of the number of nodes), because their size is dependent on the variables order. Genetic algorithms are often used in different optimization problems including the DD size optimization. In this paper, we apply the genetic algorithm to minimize the size of both Binary Decision Diagrams (BDDs) and Functional Decision Diagrams (FDDs). In both cases, in the proposed algorithm, a Bottom-Up Partially Matched Crossover (BU-PMX) is used as the crossover operator. In the case of BDDs, mutation is done in the standard way by variables exchanging. In the case of FDDs, the mutation by changing the polarity of variables is additionally used. Experimental results of optimization of the BDDs and FDDs of the set of benchmark functions are also presented.

Keywords

Binary Decision Diagrams, Functional Decision Diagrams, Decision Diagrams oprimization, Genetic algorithm.

Full Text:

PDF

References


R. E. Bryant, ”Graph-based Algorithms for Boolean Function Manipulation”, IEEE Transactions on Computers, Vol. C-35, No. 8, pp. 677-691, August 1986.

S. J. Friedman and K. J. Supowit, ”Finding the Optimal Variable Ordering Methods for Binary Decision Diagrams”, IEEE Transactions on Computers, Vol. 39, No. 5, pp. 710-713, May 1990.

R. Rudell, ”Dynamic Variable Ordering for Ordered Binary Decision Diagrams”, Proceedings of International Conference on CAD, 1993, pp. 42-47.

R. Drechsler, B. Becker and N. Go¨ckel . ”A Genetic Algorithm for Variable Ordering of OB-DDs”, IEE Proceedings Computers and Digital Techniques, Vol 143, No 6, November 1996, pp. 363368.

R. Drechsler and N. Go¨ckel, ”Minimization of BDDs by Evolutionary Algorithms”, International Workshop on Logic Synthesis (IWLS), Lake Tahoe, 1997.

R. Drechsler, B. Becker and N. Go¨ckel, ”Learning Heuristics for OBDD Minimization by Evolutionary Algorithms”, Proceedings Parallel Problem Solving from Nature (PPSN), Lecture Notes in Computer Science 1141, 1996, pp. 730-739.

W. Lenders, C. Baier, ”Genetic Algorithms for the Variable Ordering Problem of Binary Decision Diagrams”, Lecture Notes in Computer Science, Vol. 3469, pp. 1-20, 2005.

I. Furdu and B. Patrut, ”Genetic Algorithm for Ordered Decision Diagrams Optimization”, Proceedings of ICMI 45, September 2006, pp. 437-444.

I. Furdu and T. Socaciu, ”Genetic Algorithm for Variable Ordering of Ordered Binary Decision Diagrams”, Proceedings of CNMI 2007, Novenber 2007, pp. 67-78.

R. Kaur and M. Bansal, ”BDD Ordering and Minimization Using VariousCrossover Operators in Genetic Algorithm”, Inernational Journal of Innovative Research in Electrical, Electronics, Instrumentation and Control Engineering, Vol. 2, Issue 3, pp. 12471250, March 2014.

S. Jindal, M. Bansal, ”A Novel and Efficient Variable Ordering and Minimization Algorithm based on Evolutionary Computation”, Indian Journal of Science and Technology, Vol. 9(48), pp. 1-10, December 2016.

M. Hilgemeier, N. Drechsler and R.Drechsler, ”Minimizing the Number of One-Paths in BDDs by an Evolutionary Algorithm”, Proceedings of The 2003 Congress on Evolutionary Algorithm, December 2003.

S. Shirinzadeh, M. Soeken and R. Drechsler, ”Multi-Objective BDD Optimization with Evolutionary Algorithms”, Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, July 2015, pp. 751-758.

S. Stojkovic, M. Stankovic, C. Moraga, ”Complexity reducton of Toffoli networks besed on FDD”, Facta Universitatis, Ser. Electronics and Energetics, Vol. 28, No. 2, 251-262, 2015.

S. Stojkovic, M. Stankovic, C. Moraga, R. Stankovic, ”Procedure for FDD-based reversible synthesis by levels”, Proceedings of 12th International Workshop on Boolean Problems, September 22-23. 2016, Freiberg, German, pp. 1-6.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626