TY - JOUR
T1 - Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm
AU - Chen, Shan Tai
AU - Lin, Shun Shii
AU - Huang, Li Te
AU - Wei, Chun Jen
N1 - Funding Information:
We thank all reviewers for their valuable comments and suggestions. This research was supported in part by a grant NSC 92-2213-E-003-006 from National Science Council, R.O.C. Our gratitude also goes to the Academic Paper Editing Clinic, National Taiwan Normal University.
PY - 2004/5
Y1 - 2004/5
N2 - Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.
AB - Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.
KW - Binary Decision Diagram
KW - DEBEA
KW - EBEA
KW - Evolutionary algorithm
KW - Heuristic algorithm
KW - Paralleled algorithm
UR - https://www.scopus.com/pages/publications/3543069406
UR - https://www.scopus.com/pages/publications/3543069406#tab=citedBy
U2 - 10.1023/B:HEUR.0000026899.63797.f9
DO - 10.1023/B:HEUR.0000026899.63797.f9
M3 - Article
AN - SCOPUS:3543069406
SN - 1381-1231
VL - 10
SP - 337
EP - 355
JO - Journal of Heuristics
JF - Journal of Heuristics
IS - 3
ER -