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

Binary Decision Diagram variable ordering based on catastrophe genetic algorithm

作　　者：王镇道[1] 陈义[1] 

机构地区：[1]湖南大学物理与微电子科学学院,长沙410082

出　　处：《计算机工程与应用》2015年第3期55-60,共6页Computer Engineering and Applications

基　　金：湖南省科技计划资助项目(No.2014FJ3155)

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

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

分 类 号：TP11[自动化与计算机技术—控制理论与控制工程]