最大可滿(mǎn)足性問(wèn)題的博弈算法研究.pdf

1、最大可滿(mǎn)足性問(wèn)題(MaxSAT)是人工智能領(lǐng)域研究的核心問(wèn)題之一，很多復(fù)雜的實(shí)際問(wèn)題都可以通過(guò)MaxSAT建模并求解，對(duì)于MaxSAT問(wèn)題的研究具有理論和實(shí)際的雙重意義。近些年，隨著科學(xué)研究的進(jìn)步和工業(yè)技術(shù)的發(fā)展，MaxSAT問(wèn)題的規(guī)模成倍增長(zhǎng)。為滿(mǎn)足新的MaxSAT問(wèn)題求解的需求，本文基于布爾博弈模型提出兩個(gè)適用于不同規(guī)模MaxSAT實(shí)例求解的博弈算法，包括用于求解一般規(guī)模MaxSAT實(shí)例的基本博弈算法bgmaxsat和用于求解大規(guī)模

2、MaxSAT實(shí)例的分組博弈算法bgmaxsat_m。
　　本文的主要工作總結(jié)為以下四點(diǎn)。(1)我們提出一種將MaxSAT實(shí)例映射為布爾博弈模型的建模方法，通過(guò)博弈參與者的策略選擇過(guò)程來(lái)模擬MaxSAT實(shí)例中的變量賦值過(guò)程。博弈參與者的策略基于重新定義的目標(biāo)函數(shù)和收益計(jì)算函數(shù)進(jìn)行選擇，并依據(jù)其他參與者的策略不斷更新。(2)針對(duì)MaxSAT問(wèn)題的特征，我們對(duì)經(jīng)典布爾博弈模型進(jìn)行改進(jìn)，提出基于動(dòng)態(tài)收益矩陣的動(dòng)態(tài)博弈模型。在動(dòng)態(tài)博弈模型中

3、，參與者的收益矩陣在博弈過(guò)程中實(shí)時(shí)變化，使得所有參與者都能夠按照自身的目標(biāo)函數(shù)快速收斂?；趧?dòng)態(tài)博弈模型，我們提出求解一般規(guī)模MaxSAT實(shí)例的基本博弈算法bgmaxsat。(3)針對(duì)大規(guī)模MaxSAT實(shí)例產(chǎn)生大量博弈參與者的問(wèn)題，我們提出一種新的博弈參與者聯(lián)盟構(gòu)建方法。我們基于無(wú)向圖重建博弈參與者間的關(guān)系，將相互間無(wú)關(guān)系的參與者劃分為一組來(lái)構(gòu)建聯(lián)盟，從而有效降低博弈規(guī)模。(4)基于博弈參與者聯(lián)盟，我們提出求解大規(guī)模MaxSAT實(shí)例的分

4、組博弈算法bgmaxsat_m在bgmaxsat_m算法中，我們將博弈的基本單位設(shè)定為參與者聯(lián)盟，并將信息共享通道僅設(shè)定在聯(lián)盟之間。
　　在實(shí)驗(yàn)部分，我們基于4個(gè)測(cè)試數(shù)據(jù)集進(jìn)行了多組對(duì)比實(shí)驗(yàn)。首先，我們?cè)?46個(gè)一般規(guī)模MaxSAT實(shí)例上評(píng)估bgmaxsat算法，并與CCLS2016、Swcca-ms、ahmaxsat155三個(gè)最新算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，在求解一般規(guī)模的MaxSAT實(shí)例時(shí)，bgmaxsat算法的性能與CCLS

5、2016算法相近，其分別在不同分類(lèi)的實(shí)例上各占優(yōu)勢(shì)，同時(shí)優(yōu)于Swcca-ms算法和ahmaxsat155算法。其次，我們?cè)?00個(gè)變量規(guī)模超過(guò)105的大規(guī)模MaxSAT實(shí)例上評(píng)估bgmaxsat_m算法，并與CCLS2016、wbo、Open-wbo、pwbo、CnC-LS五個(gè)最新算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，在求解大規(guī)模MaxSAT實(shí)例時(shí)，bmgaxsat_m算法的性能在所有分類(lèi)的實(shí)例上均明顯優(yōu)于CCLS2016算法、wbo算法和pwb