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

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

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

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

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

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

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