文档介绍：UlI Y2605884 Binary Decision Diagram Minimization Based on Catastrophe Adaptive ic Algorithm by CHEN Yi .(HunanUniversity)2009 Athesissubmitted inpartial satisfaction ofthe requirements forthedegree of Master ofScience in MicroElectronics and solid state Electronics inthe Graduate school of Hunan Un iversity Supervisor Professor WANG Zhendao May,2014 湖南大学学位论文原创性声明本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名:瑜、义日期:砂垆年f月多日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于 I、保密口,在年解密后适用本授权书。 2、不保密囹。(请在以上相应方框内打“√”) 日期:?纠乒年∥月岁日日期:匆笋年6月歹日童义班一露斟参基于灾变自适应遗传算法的二叉判定图最小化算法摘要二叉判定图(BDD)是描述布尔函数或组合逻辑电路的一种数据结构,广泛应用于形式验证领域,包括组合逻辑电路、时序逻辑电路,以及等价性检验、模型检验等,被许多用于电路设计的CAD系统作为底层数据结构。不过,在实际应用中,能否使用二叉判定图进行求解,很大程度上取决于使用BDD表示问题时所需的存储空间大小,即,BDD的节点规模,而这是严重依赖于变量序列的。对 BDD变量排序相关的研究,能够大幅降低BDD节点规模,进而缓解模型检验态空间爆炸问题,具有十分重要的意义。文章简要介绍了BDD相关基础理论和变量排序相关情况,并在传统遗传算法的BDD变量排序算法基础上,基于灾变的概念,提出了灾变自适应遗传算法, 用以求解BDD变量最小化问题。该算法能够根据需要动态调整算法交叉和变异概率,降低对初始参数的依赖,减少算法运行负担,并能在不扩大种群规模的情况下,极大地增加了个体多样性,改善遗传算法的早熟收敛问题。而且,由于算法本身并不关心发生灾变之前种群的进化方式与进化方向,因而极易与其它改进策略结合起来,特别是一些局部搜索效率较高的算法,能够在原有特性的基础上引入全局优势,进一步减小节点规模,扩展余地十分充足。论文使用Uniform 。试验结果表明:灾变算法的全局特性显著优于传统遗传算法,能够在基本遗传算法的基础上进一步减小节点规模,平均改善程度约为11%,最高改善程度可达25%。而引入自适应策略以后,平均改善程度得以进一步提高,%,%。关键词:二叉判定图;形式验证;遗传算法:自适应;灾变算法;变量排序硕士学位论文 Abstract The Binary Decision Diagrams is a description ofdata structure forBoolean function binational logic circuit,which iswidely used informal verification, such binational logic circuits,sequential logic circuit,as well as equivalence checking,model isalso used as the underlying data structure by many CAD system in circuit ,in practice,it isheavily depended on the required storage space,named BDD node size,while using thecorrelation algorithm. And theresearchers found that,the BDD node sizesheavi