基于灾变遗传算法的二叉判定图最小化算法

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (3): 55-60.

基于灾变遗传算法的二叉判定图最小化算法

王镇道，陈义

湖南大学物理与微电子科学学院，长沙 410082

出版日期:2015-02-01 发布日期:2015-01-28

Binary Decision Diagram variable ordering based on catastrophe genetic algorithm

WANG Zhendao, CHEN Yi

School of Physics and Microelectronics Sciences, Hunan University, Changsha 410082, China

Online:2015-02-01 Published:2015-01-28

摘要/Abstract

摘要： 二叉判定图广泛应用于形式验证，但相关算法存在节点规模过大的问题。提出了一种基于灾变遗传算法的二叉判定图最小化算法，它能在不扩大种群规模的情况下增加个体多样性，改善遗传算法局部收敛的问题。试验结果表明该算法的全局特性显著优于传统遗传算法，能够进一步减小节点规模，改善程度最高可达25%。而且，由于使用何种进化策略并不影响灾变的发生，因此，算法可扩展性好，极易与其他改进策略结合起来，在原有特性的基础上引入全局优势，以进一步减小节点规模。

关键词: 二叉判定图, 遗传算法, 灾变, 最小化, 变量排序

Abstract: The Binary Decision Diagrams is widely used in formal verification, but a problem about the great node size, while using the correlation algorithm, is unsolved. It presents a new catastrophe genetic algorithm for minimizing the Binary Decision Diagrams, inspired by the basic genetic algorithm. It can increase the diversity of individuals without expanding the population size, which can improve the local convergence. The experimental evaluation uses some benchmarks and proves better results than the basic genetic algorithm on global optimization and this algorithm reduces the node size additionally by 25% mostly. Moreover, the algorithm has good extensibility. It is easy to combine with other improvement strategies together, to improve the global advantage, because the evolutionary strategy does not affect the occurrence of catastrophe.

Key words: Binary Decision Diagram（BDD）, genetic algorithm, catastrophe, minimization, variable ordering

王镇道，陈义. 基于灾变遗传算法的二叉判定图最小化算法[J]. 计算机工程与应用, 2015, 51(3): 55-60.

WANG Zhendao, CHEN Yi. Binary Decision Diagram variable ordering based on catastrophe genetic algorithm[J]. Computer Engineering and Applications, 2015, 51(3): 55-60.

[1]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[2]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[3]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[4]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[5]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[6]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[7]	马成齐，李学华，张兰杰，向维. 抗遮挡的单目深度估计算法[J]. 计算机工程与应用, 2021, 57(2): 217-222.
[8]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[9]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[10]	冯晓东，黄世荣，戴冠鸥，杨伟家，罗尧治. 天牛须遗传杂交算法的研究与应用[J]. 计算机工程与应用, 2021, 57(15): 90-100.
[11]	苏庆，林华智，黄剑锋，林志毅. 结合CNN和Catboost算法的恶意安卓应用检测模型[J]. 计算机工程与应用, 2021, 57(15): 140-146.
[12]	姜良重，雷航，李贞昊，钱伟中，施甘图. 采用自适应优化权重的出库货位优化方法研究[J]. 计算机工程与应用, 2021, 57(15): 271-278.
[13]	贺娇，谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15): 279-285.
[14]	王秀丽，周鹏，侯静楠，王仕俊，林霞. 面向变电站机器人巡检路径规划中的算法研究[J]. 计算机工程与应用, 2021, 57(14): 245-250.
[15]	陈元文. MapReduce技术在物资调运与配载问题中的应用[J]. 计算机工程与应用, 2021, 57(12): 273-278.