一種求解MAX-k-SAT問題的新方法

宋建民,弓小影

（石家莊經(jīng)濟(jì)學(xué)院數(shù)理學(xué)院,河北石家莊 050031）

近年來,利用二進(jìn)制差分演化算法求解0-1背包問題、利用二進(jìn)制粒子群優(yōu)化算法求解可滿足問題和集合覆蓋問題等,得到了許多滿意的結(jié)果[1-3].本文研究利用二進(jìn)制差分演化算法求解在計(jì)算機(jī)科學(xué)中具有重要地位的最大k-可滿足問題[4].通過將二進(jìn)制差分演化算法與改進(jìn)的動(dòng)態(tài)變鄰域搜索相結(jié)合,提出了一種改進(jìn)二進(jìn)制差分演化算法,并應(yīng)用于一系列隨機(jī)生成的大規(guī)模MAX-k-SAT實(shí)例.實(shí)驗(yàn)結(jié)果證明該方法是一種求解該問題的可行新方法.

1 MAX-k-SAT問題

基于MAX-k-SAT（k≥3）的邏輯定義,提出MAX-k-SAT（k≥3）問題的一種最優(yōu)化表示形式.

2 IBDE算法設(shè)計(jì)

對(duì)于含有n個(gè)不同命題變?cè)腗AX-k-SAT問題,利用強(qiáng)力搜索法求解需要分別計(jì)算2n個(gè)指派滿足的子句個(gè)數(shù),計(jì)算時(shí)間復(fù)雜性為O（2n）,顯然是不可取的,因此我們?cè)谙旅鎸⒔榻B一種基于HBDE求解MAX-k-SAT問題的有效方法.

變鄰域搜索（VNS）是Hansen等提出的一種meta-Heuristic算法,已被廣泛應(yīng)用于求解各種NPC問題[7].與傳統(tǒng)的單一鄰域結(jié)構(gòu)所不同的是：VNS首先預(yù)定義一系列的鄰域結(jié)構(gòu),并且在搜索中先由某個(gè)鄰域開始,按照一定的次序系統(tǒng)性地不斷變化鄰域的搜索范圍,直到有更好的解產(chǎn)生為止.借鑒VNS的思想,為避免HBDE陷入局部最優(yōu)的情況發(fā)生,下面對(duì)于解為二進(jìn)制向量的最大優(yōu)化問題maxf（X）,給出一種基于局部隨機(jī)鄰域變化搜索的動(dòng)態(tài)變鄰域搜索算法（DVNS）.令L1與L2為隨機(jī)產(chǎn)生的1到n之間的兩個(gè)隨機(jī)整數(shù),并且滿足1≤L2-L1≤n/4,于是DVNS的算法偽代碼描述如下.

進(jìn)化算法的全局搜索能力雖然較強(qiáng),但其局部搜索能力往往不足[8].為此,下面將DVNS與HBDE相結(jié)合提出一種用于求解MAX-k-SAT問題的改進(jìn)二進(jìn)制差分演化算法（Improved Binary Differential Evolution,IBDE）,以加強(qiáng)差分演化的局部搜索能力.為了有效地將HBDE與DVNS結(jié)合,不必對(duì)HBDE的每一個(gè)個(gè)體均利用DVNS進(jìn)行局部?jī)?yōu)化,而是根據(jù)種群的規(guī)模隨機(jī)地選擇一定數(shù)量（通常≤N/3,其中N為種群規(guī)模）的個(gè)體進(jìn)行優(yōu)化,這樣既提高了算法的局部搜索,同時(shí)又兼顧了算法的效率.下面即給出HBDE與DVNS結(jié)合求解MAX-k-SAT問題的算法IBDE的偽代碼描述.

在算法IBDE中,rand（0,1）表示隨機(jī)產(chǎn)生的一個(gè)0與1之間的隨機(jī)數(shù).由于在算法IBDE中只利用DVNS對(duì)不超過1/3的個(gè)體隨機(jī)進(jìn)行了局部?jī)?yōu)化,因此算法IBDE的時(shí)間復(fù)雜性為O（ITE*（N*n+N*n/3））+O（N*n/3）=O（ITE*N*n）.可見,雖然 IBDE 是由 HBDE 與 DVNS 相結(jié)合而得到的,但其時(shí)間復(fù)雜性仍然與HBDE相同.

3 仿真計(jì)算結(jié)果與比較

為了驗(yàn)證IBDE求解MAX-k-SAT問題的可行性與有效性,利用隨機(jī)產(chǎn)生的一系列大規(guī)模MAX-k-SAT實(shí)例進(jìn)行仿真計(jì)算,并與Johnson算法和GA進(jìn)行比較.為了比較的公平性,在利用GA求解時(shí),同樣按照上文算法的方法將DVNS用于對(duì)其個(gè)體進(jìn)行局部?jī)?yōu)化.仿真計(jì)算使用lenovo X201i筆記本,硬件環(huán)境為Intel（R）Pentium（R）CPU：U5400-1.20 GHz,2.00GB內(nèi)存,操作系統(tǒng)為Windows 7,并利用VC++6.0進(jìn)行編程實(shí)現(xiàn).

由于每一個(gè)MAX-k-SAT（k≥3）問題都可以等值轉(zhuǎn)化為一個(gè)MAX-3-SAT問題[9],因此將利用隨機(jī)生成的大規(guī)模MAX-3-SAT實(shí)例進(jìn)行仿真計(jì)算.由于IBDE、Johnson和GA均為隨機(jī)近似算法,對(duì)于每一個(gè)MAX-3-SAT實(shí)例,取各算法10次計(jì)算結(jié)果的平均值進(jìn)行比較.記n為MAX-3-SAT實(shí)例中命題變?cè)膫€(gè)數(shù),m為其中的子句個(gè)數(shù),于是利用各算法計(jì)算一系列隨機(jī)生成的大規(guī)模MAX-3-SAT實(shí)例的結(jié)果見圖1.

圖1 n=200時(shí)各算法對(duì)實(shí)例1-5的平均計(jì)算結(jié)果比較Fig.1 The resultcomparison of each algorithm on average1-5when n=200

在圖1中,實(shí)例1-5的n=200,m依次為400、500、600、700、800,從3個(gè)算法所得到的平均最優(yōu)值可以看出,無論m如何變化,IBDE求得的平均最優(yōu)值均優(yōu)于GA和Johnson算法,并且與n和m之間的比值無關(guān).計(jì)算結(jié)果比較表明,對(duì)于隨機(jī)大規(guī)模MAX-k-SAT（k≥3）問題的求解,IBDE是一種比GA和Johnson算法更有效的新方法.

4 小結(jié)

本文基于動(dòng)態(tài)變鄰域搜索改進(jìn)二進(jìn)制差分演化算法的局部搜索能力,給出了一種求解MAX-k-SAT問題的改進(jìn)差分演化算法IBDE.通過利用一系列隨機(jī)生成的大規(guī)模MAX-k-SAT實(shí)例與GA和Johnson算法的仿真計(jì)算進(jìn)行比較,結(jié)果表明：對(duì)于大規(guī)模的隨機(jī)MAX-k-SAT問題,IBDE算法不僅是可行的,而且是高效的.由于HBDE是一種適于求解可行解能夠表示為二進(jìn)制編碼的（動(dòng)態(tài)）組合優(yōu)化問題的算法,今后將進(jìn)一步探討如何將其與DVNS有效結(jié)合以求解其他組合優(yōu)化問題.

[1]賀毅朝,王熙照,寇應(yīng)展.一種具有混合編碼的二進(jìn)制差分演化算法[J].計(jì)算機(jī)研究與發(fā)展,2007,44（9）：1476-1484.

[2]賀毅朝,王彥祺,寇應(yīng)展.一種求解3-SAT問題新方法[J].計(jì)算機(jī)工程與應(yīng)用,2006,42（16）：70-72.

[3]Frans V B.An analysis of particle swarm optimizers[D].Pretoria：University of Pretoria,2001.

[4]Du D Z,Ko K I,Hu XD.Design and analysis of approximation algorithms[M].Springer Science BusinessMedia,LLC,2012.

[5]DoritS,Hochbaum E.NP難解問題的近似算法[M].北京：世界圖書出版公司,1995.

[6]堵丁柱,葛可一,王潔.計(jì)算復(fù)雜性導(dǎo)引[M].北京：高等教育出版社,2002.

[7]Chakraborty U K,Das S,Konar A.Differentialevolution with localneighborhood[J].IEEECongress on Evolutionary Computation,2006（7）：2042-2049.

[8]陳國(guó)良,王熙法,莊鎮(zhèn)泉,等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社,2003.

[9]張健.邏輯公式的可滿足性判定-方法、工具及應(yīng)用[M].北京：科學(xué)出版社,2000.