基于災(zāi)變自適應(yīng)遺傳算法的二叉判定圖最小化算法.pdf

1、二叉判定圖(BDD)是描述布爾函數(shù)或組合邏輯電路的一種數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于形式驗證領(lǐng)域，包括組合邏輯電路、時序邏輯電路，以及等價性檢驗、模型檢驗等，被許多用于電路設(shè)計的CAD系統(tǒng)作為底層數(shù)據(jù)結(jié)構(gòu)。不過，在實際應(yīng)用中，能否使用二叉判定圖進(jìn)行求解，很大程度上取決于使用BDD表示問題時所需的存儲空間大小，即，BDD的節(jié)點(diǎn)規(guī)模，而這是嚴(yán)重依賴于變量序列的。對BDD變量排序相關(guān)的研究，能夠大幅降低BDD節(jié)點(diǎn)規(guī)模，進(jìn)而緩解模型檢驗態(tài)空間爆炸問題，具

2、有十分重要的意義。
　　文章簡要介紹了BDD相關(guān)基礎(chǔ)理論和變量排序相關(guān)情況，并在傳統(tǒng)遺傳算法的BDD變量排序算法基礎(chǔ)上，基于災(zāi)變的概念，提出了災(zāi)變自適應(yīng)遺傳算法，用以求解BDD變量最小化問題。該算法能夠根據(jù)需要動態(tài)調(diào)整算法交叉和變異概率，降低對初始參數(shù)的依賴，減少算法運(yùn)行負(fù)擔(dān)，并能在不擴(kuò)大種群規(guī)模的情況下，極大地增加了個體多樣性，改善遺傳算法的早熟收斂問題。而且，由于算法本身并不關(guān)心發(fā)生災(zāi)變之前種群的進(jìn)化方式與進(jìn)化方向，因而極易與

3、其它改進(jìn)策略結(jié)合起來，特別是一些局部搜索效率較高的算法，能夠在原有特性的基礎(chǔ)上引入全局優(yōu)勢，進(jìn)一步減小節(jié)點(diǎn)規(guī)模，擴(kuò)展余地十分充足。
　　論文使用Uniform Random-3-SAT測試集的基準(zhǔn)樣本進(jìn)行測試。試驗結(jié)果表明:災(zāi)變算法的全局特性顯著優(yōu)于傳統(tǒng)遺傳算法，能夠在基本遺傳算法的基礎(chǔ)上進(jìn)一步減小節(jié)點(diǎn)規(guī)模，平均改善程度約為11％，最高改善程度可達(dá)25％。而引入自適應(yīng)策略以后，平均改善程度得以進(jìn)一步提高，達(dá)到12.82％，最高改善