计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2015年
3期
55-60
,共6页
二叉判定图%遗传算法%灾变%最小化%变量排序
二扠判定圖%遺傳算法%災變%最小化%變量排序
이차판정도%유전산법%재변%최소화%변량배서
Binary Decision Diagram(BDD)%genetic algorithm%catastrophe%minimization%variable ordering
二叉判定图广泛应用于形式验证,但相关算法存在节点规模过大的问题。提出了一种基于灾变遗传算法的二叉判定图最小化算法,它能在不扩大种群规模的情况下增加个体多样性,改善遗传算法局部收敛的问题。试验结果表明该算法的全局特性显著优于传统遗传算法,能够进一步减小节点规模,改善程度最高可达25%。而且,由于使用何种进化策略并不影响灾变的发生,因此,算法可扩展性好,极易与其他改进策略结合起来,在原有特性的基础上引入全局优势,以进一步减小节点规模。
二扠判定圖廣汎應用于形式驗證,但相關算法存在節點規模過大的問題。提齣瞭一種基于災變遺傳算法的二扠判定圖最小化算法,它能在不擴大種群規模的情況下增加箇體多樣性,改善遺傳算法跼部收斂的問題。試驗結果錶明該算法的全跼特性顯著優于傳統遺傳算法,能夠進一步減小節點規模,改善程度最高可達25%。而且,由于使用何種進化策略併不影響災變的髮生,因此,算法可擴展性好,極易與其他改進策略結閤起來,在原有特性的基礎上引入全跼優勢,以進一步減小節點規模。
이차판정도엄범응용우형식험증,단상관산법존재절점규모과대적문제。제출료일충기우재변유전산법적이차판정도최소화산법,타능재불확대충군규모적정황하증가개체다양성,개선유전산법국부수렴적문제。시험결과표명해산법적전국특성현저우우전통유전산법,능구진일보감소절점규모,개선정도최고가체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 addition-ally 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.