OBDDs变量序的遗传算法求解策略

发布时间：2021-03-16 08:53

　　有序二叉判定图（OBDDs）是一种表示布尔函数的高效数据结构,在形式化验证领域内有着广泛应用。它为符号模型检测算法提供实现框架,使得模型检测中的状态空间爆炸问题得以缓解。OBDDs的规模严重地依赖于变量序,在最坏情况下其规模是呈指数级增长的。研究高效的变量排序算法,缩小其结点规模,对于提高符号模型检测效率具有至关重要的意义。OBDDs变量序问题已被证明是一个NP完全问题。现有的变量序求解算法,如:精确变量排序、启发式变量排序等,都是根据给定的函数结构对变量进行排序,对初始函数依赖性较强。因此具有一定的局限性,不能较好的解决这一问题。目前,遗传算法在求解该问题上效果较好。该算法以动态方式搜索最优解,摆脱了对给定函数的依赖性。但算法仍存在搜索效率低、局部优化能力弱、收敛速度慢等问题。为提升遗传算法求解OBDDs变量序问题的搜索效率,文章在原遗传算法基础上引入了自适应策略,并对其自适应模型进行改进。改进的算法根据种群进化程度动态调整交叉概率和变异概率,确保种群进化朝着正确方向进行,从而提升算法收敛速度和局部优化能力。算法通过调用软件包Buddy中部分内置函数测试样本获得实验数据。实验结果表明... 

【文章来源】：辽宁师范大学辽宁省

【文章页数】：48 页

【学位级别】：硕士

【部分图文】：

真值表及其对应二叉判定树

二叉判定树简化过程

无序的BDDsFig.2.3TheunorderedBDDs

【参考文献】：
期刊论文
[1]基于灾变遗传算法的二叉判定图最小化算法[J]. 王镇道,陈义.  计算机工程与应用. 2015(03)
[2]改进的乘幂适应度函数在遗传算法中的应用[J]. 杨水清,杨加明,孙超.  计算机工程与应用. 2014(17)
[3]基于适应度函数及交叉操作改进的自适应遗传算法[J]. 窦明鑫,刘晓霞.  合作经济与科技. 2012(13)
[4]模拟退火算法在BDD变量最优排序中的应用[J]. 胡东华,张旭.  科技信息(科学教研). 2007(34)
[5]自适应遗传算法的改进及在系统辨识中应用研究[J]. 任子武,伞冶.  系统仿真学报. 2006(01)
[6]二叉判定图最优化算法研究综述[J]. 王明全,于海斌,王宏.  信息与控制. 2004(05)



本文编号：3085771