遗传算法在OBDD变量排序中的应用

摘要

编序的二元判决图（ＯＢＤＤ）在电路测试和逻辑验证等方面具有广泛的应用。如何选取一个电路的变量顺序，使得所构造的 ＯＢＤＤ最小，是等同于 ＮＰＣ的问题［１］。目前有多种寻找电路变量顺序的方法，但都具有一定程度的局限性，不能找到近似的最优解。本文从遗传算法入手，利用几种启发式变量排序方法的结果作为最初的染色体群体，并适当加入随机变量顺序，然后按照遗传算法的方法进行运算，经过多代循环找到近似最优解。在运算过程中采用了快速衡量变量顺序好坏的方法，使得运算时间大大缩短。实验结果表明，该方法比已有的启发式方法更有效，能够在全局范围内搜索最优解，所找到的ＩＳＣＡＳ’８５电路的变量顺序是目前所有文献报道中最好的。