布爾滿足性判定算法研究.pdf

1、布爾滿足性判定問題是多個不同學(xué)科的交叉問題，它是一類著名的NP-完全問題。但是，隨著布爾滿足性判定算法性能的不斷提升，它已經(jīng)被大量的應(yīng)用于實際問題的求解，如組合電路等價性檢測、自動測試模板生成、軟件模式檢測、滿足模塊定理證明、計算生物學(xué)和自動規(guī)劃等。大量具有不同特性的布爾滿足性判定算法被設(shè)計和優(yōu)化，以實現(xiàn)對實際問題的快速求解。但是，部分問題求解的時間復(fù)雜度和空間復(fù)雜度還有待進一步降低，很多難實例問題仍然在有限的時間內(nèi)無法求解。針對特定問

2、題類的高效布爾滿足性判定算法一直是計算機及人工智能領(lǐng)域的熱點研究問題之一。
　　本文在深入研究布爾滿足性判定算法的基礎(chǔ)上，針對不同的問題進行了建模和算法設(shè)計，其主要研究內(nèi)容分為四部分。
　　1、針對Model RB模型的特性，通過集合和圖的方式對問題進行了形式化建模和描述，融合完全布爾滿足性判定算法和隨機布爾滿足性判定算法的不同優(yōu)勢，實現(xiàn)了高效的完全布爾滿足性判定算法。基于完全布爾滿足性判定算法的基本搜索流程，提出了基于互斥

3、集和關(guān)聯(lián)集的搜索判定算法。在搜索過程中，根據(jù)動態(tài)生成的子句集構(gòu)造搜索樹、選擇決策變量并確定回退機制。為實現(xiàn)搜索過程中的快速沖突回退，使用隨機算法獲得圖中的最大團，并利用最大團中的節(jié)點構(gòu)造初始搜索樹。實驗結(jié)果顯示，算法在Model RB模型和圖著色問題實例中具有較好的性能。
　　2、隨著人們對基因認(rèn)識的不斷深入和基因序列提取能力的不斷增強，計算生物學(xué)對基因的研究已經(jīng)從單基因的性質(zhì)研究逐漸轉(zhuǎn)向?qū)蛘{(diào)控網(wǎng)絡(luò)的動態(tài)特性研究。在基因調(diào)控網(wǎng)

4、絡(luò)研究中的一個重要問題是吸引子的求解問題，吸引子代表基因網(wǎng)絡(luò)的穩(wěn)定狀態(tài)，一個吸引子表示一種細胞類型?；谕讲紶柧W(wǎng)絡(luò)建模的方式，將基因調(diào)控網(wǎng)絡(luò)的動態(tài)調(diào)控過程轉(zhuǎn)化成了同步布爾網(wǎng)絡(luò)的狀態(tài)轉(zhuǎn)換圖。為降低狀態(tài)轉(zhuǎn)換圖中吸引子的求解復(fù)雜度，以布爾網(wǎng)絡(luò)中的強連通分支為單位將布爾網(wǎng)絡(luò)劃分成了多個塊，各個塊之間形成有向無環(huán)的依賴關(guān)系。算法通過計算每一個塊的局部吸引子來獲得整個網(wǎng)絡(luò)的吸引子。在計算局部吸引子時，算法通過展開布爾網(wǎng)絡(luò)轉(zhuǎn)換函數(shù)的方式將吸引子求解

5、問題轉(zhuǎn)換成布爾滿足性判定問題進行求解。實驗結(jié)果表明，基于分塊的吸引子求解算法針對復(fù)雜的基因調(diào)控網(wǎng)絡(luò)具有顯著的優(yōu)勢。
　　3、為充分利用計算機多核的處理能力，實現(xiàn)高效的問題求解，并行計算已經(jīng)成為一種必然的軟件設(shè)計趨勢。在深入研究并行布爾滿足性判定算法的基礎(chǔ)上，結(jié)合基于分塊的算法特性，設(shè)計并實現(xiàn)了兩種并行的吸引子求解算法：基于塊的并行算法和基于局部吸引子的并行算法?；趬K的并行算法使用空間劃分的方式實現(xiàn)并行布爾滿足性判定求解，而基于局

6、部吸引子的并行算法在空間劃分的基礎(chǔ)上實現(xiàn)了負(fù)載均衡?；趬K的并行算法在計算完第一個節(jié)點塊的所有局部吸引子后，將局部吸引子平均分配給所有CPU的核進行后續(xù)的節(jié)點塊計算?；诰植课拥牟⑿兴惴ㄓ嬎阃暌粋€局部吸引子就會產(chǎn)生一個消息，通知空閑CPU核進行后續(xù)的計算。實驗結(jié)果表明，并行吸引子求解的性能優(yōu)于串行求解的性能，基于局部吸引子的并行算法優(yōu)于基于塊的并行算法。特別是當(dāng)CPU的核數(shù)較多時，基于局部吸引子的并行算法優(yōu)勢更加突出。
　　4