基于遗传禁忌混合策略的二叉判定图最小化算法研究
Binary Decision Diagram Minimization Algorithm Based on Genetic Tabu Hybrid Strategy
摘要
提出了一种新的动态启发式二叉判定图(BDD)最小化算法.该算法将遗传算法的全局搜索能力和禁忌搜索的邻域搜索策略相结合来寻找BDD的最优变量排序,以实现BDD结点规模最小化.实验结果表明该算法性能优于其它启发式算法.*
A new dynamic heuristic binary decision diagram(BDD) minimization algorithm is proposed. The algorithm combines the global search ability of genetic algorithm with the neighborhood search strategy of tabu search to find the optimal BDD variable ordering with which BDD can achieve size minimization. Experimental results show that this algorithm is of better performance than other heuristic methods.
出处
《信息与控制》
CSCD
北大核心
2005年第2期142-146,共5页
Information and Control
关键词
二叉判定图
最小化
变量排序
遗传算法
禁忌搜索
binary decision diagram(BDD)
minimization
variable ordering
genetic algorithm
tabu search
参考文献10
-
1Bryant R E. Graph-based algorithms for boolean function manipulation [J]. IEEE Transactions on Computers, 1986, 35(8) :677～691.
-
2Meinel C, Theobald T. Algorithm and Data Structures in VLSI Design OBDD - Foundations and Applications [ M ]. Heidelberg,Berlin :Springer-Verlag, 1998.
-
3Friedman S J, Supowit K J. Finding the optimal variable ordering for binary decision diagrams [ J ]. IEEE Transactions on Computers, 1990, 39(5) :710 ～713.
-
4Drechsler R, Becker B, Gockel N. Genetic algorithm for variable ordering of OBDDs [J]. IEE Proceedings of Computers and Digital Techniques, 1996, 143 (6) :364 ～ 368.
-
5Bollig B, Wegener I. Improving the variable ordering of OBDDs is NP-complete [ J]. IEEE Transactions on Computers, 1996, 45(9) :993 ～ 1002.
-
6Rudell R. Dynamic variable ordering for ordered binary decision diagrams [ A]. Proceedings of the 1993 IEEE/ACM International Conference on Computer-aided Design [ C ]. Los Alamitos, CA,USA: IEEE Computer Society Press, 1993. 42～47.
-
7Bollig B, Lobbing M, Wegener I. Simulated annealing to improve variable orderings for OBDDs [ A ]. Proceedings of the IEEE/ACM Workshop on Logic Synthesis [ C ]. Los Alamitos, CA,USA: IEEE Computer Society Press, 1995. 5b:5.1 ～5.10.
-
8Panda S, Somenzi F, Plessier B F. Symmetry detection and dy namic variable ordering of decision diagrams [ A]. Proceedings of the 1994 IEEE/ACM International Conference on Computer-aided Design [C]. Los Alamitos, CA, USA: IEEE Computer Society Press, 1994. 628～631.
-
9Panda S, Somenzi F. Who are the variables in your neighborhood [A]. Proceedings of the 1995 IEEE/ACM International Conference on Computer-aided Design [ C ]. Washington, DC, USA: IEEE Computer Society Press, 1995.74 ～77.
-
10Somenzi F. CUDD: CU Decision Diagram Package Release 2.3.1 [ CP/DK]. ftp ://vlsi. colorado. edu/pub/, 2001.
-
1自动化技术、计算机技术[J].中国无线电电子学文摘,2005,0(6):113-137.
-
2王镇道,陈义.基于灾变遗传算法的二叉判定图最小化算法[J].计算机工程与应用,2015,51(3):55-60. 被引量：3
-
3胡东华,张旭.A^＊算法在BDD变量最优排序方法中的应用[J].计算机技术与发展,2007,17(7):70-72.
-
4苏开乐,吕关锋,宋炯.一个高效BDD的简洁实现[J].计算机学报,2014,37(9):2021-2026. 被引量：2
-
5季莉,朱娜.一种基于二叉判定图的包过滤规则设计方法[J].计算机工程,2006,32(6):183-185.
-
6李绍荣,徐玉婷.基于BDD的组合电路等价性检验[J].计算机科学,2007,34(3):293-294.
-
7郭建,杜惠敏,韩俊刚,郝克刚.基于时态逻辑的硬件设计形式化验证技术——模型检验[J].小型微型计算机系统,2001,22(5):521-524. 被引量：5
-
8智慧来.同一变量排序下的多OBDD合并算法[J].计算机工程与应用,2014,50(17):20-23.
-
9周从华,刘志锋.具有过去时态算子的计算树逻辑模型检测[J].计算机工程,2007,33(22):98-100. 被引量：2
-
10王明全,于海斌,王宏.二叉判定图最优化算法研究综述[J].信息与控制,2004,33(5):567-572. 被引量：5
