利用改進的HBDE算法求解MAX－k－SAT問題

宋建民，茍海燕

（1.石家莊經濟學院 數理學院，河北 石家莊 050031；2.石家莊經濟學院 華信學院，河北 新樂 050700）

近年來，利用進化算法（Evolutionary Algorithms，EAs）求解NP完全問題（NP Complete Problems，NPC）已成為智能計算領域的一個研究熱點問題［1］，例如利用遺傳算法（Genetic algorithm，GA）［2］和蟻群算法（Ant Colony Optimization，ACO）［3］求解旅行商問題（Traveling Salesman Problem，TSP）、利用二進制差分演化算法 （Binary Differential Evolution Algo－rithm with Hybrid Encoding，HBDE）［4］求解0－1背包問題（0－1Knapsack Problem，0－1KP）以及利用二進制粒子群優(yōu)化算法（Binary Particle Swarm Optimization，BPSO）求解可滿足問題（Satisfiability Problem，SAT）和集合覆蓋問題（Set Covering Problem，SCP）［5，6］等，得到了許多滿意的結果。本文研究利用HBDE求解在計算機科學中具有重要地位的最大k－可滿足問題（MAX－k－SAT，k≥3）［7］，通過將 HBDE與改進的動態(tài)變鄰域搜索（Dynamic Variable Neighborhood Search，DVNS）相結合，提出了一種求解MAX－k－SAT的改進二進制差分演化算法（Improved Binary Differential Evolution，IBDE）。對于一系列隨機生成的大規(guī)模MAX－k－SAT實例，通過與GA［2］和Johnson算法［8］的求解比較表明，本文方法是一種求解該問題的可行且有效的新方法。

本文其余內容組織如下：在第1節(jié)中首先介紹HBDE算法，然后提出MAX－k－SAT的最優(yōu)化形式表示；在第2節(jié)中，首先給出一種動態(tài)變鄰域搜索（DVNS），然后基于 HBDE與DVNS相結合提出一種求解MAX－k－SAT的IBDE算法；接著在第3節(jié)中，利用一系列隨機生成的大規(guī)模MAX－k－SAT實例，分別利用IDBE算法、Johnson算法和GA進行求解與比較；最后總結全文，并提出今后的研究思路。

1 背景知識

1.1 HBDE算法

差分演化（Differential Evolution，DE）［9，10］是由 Rainer Storn和 Kenneth Price提出的一種EAs，在求解數值優(yōu)化問題中表現突出，受到了廣泛的關注。賀毅朝等人利用混合編碼方法提出了一種二進制差分演化算法（HBDE）［4］，使得DE能夠用于求解各種以二進制向量為可行解的組合優(yōu)化問題（如0－1KP，SAT和SCP等）。下面我們僅給出HBDE的算法偽代碼描述，詳細內容請參考文獻［4］。

設 HBDE的種群規(guī)模為N，n為解空間A＝｛0，1｝n與輔助搜索空間S＝［－5.0，5.0］n的維數。記第t代種群中第i個個體的混合編碼為（Xi（t），Bi（t）），其中Xi（t）＝［xi1（t），xi2（t），…，xin（t）］∈S，Bi（t）＝［bi1（t），bi2（t），…，bin（t）］∈A；記第t＋1代中間種群中第i個中間個體的混合編碼為（Vi（t＋1），Ei（t＋1）），其中Vi（t＋1）＝［vi1（t＋1），vi2（t＋1），…，vin（t＋1）］∈B，Ei（t＋1）＝［ei1（t＋1），ei2（t＋1），…，ein（t＋1）］∈A，1≤i≤N。令（Xbest（t），Bbest（t）為第t代中的最好個體，ITE為HBDE的最大迭代次數，則求解最大優(yōu)化問題maxf（X）的HBDE的算法偽代碼描述如下：

算法1.HBDE Algorithm

在 HBDE中，p1≠p2≠p3≠i并且1≤p1，p2，p3，i≤N。參數α和CR定義見文獻［4，9］；sig（x）＝1/（1＋e－x）是一個單調函數。顯然，Step4－Step11為 HBDE的一次進化迭代，因此算法1的時間復雜度為O（ITE＊N＊n）。此外，算法1是采用DE/r/1/bin模式的，對于DE的其它各模式，只要修改Step6即可得到相應模式的HBDE算法。

1.2 MAX－k－SAT問題

最大k－可滿足問題（MAX－k－SAT，k≥3）［8，11］是計算機科學中一個具有重要理論意義的NP完全問題（NPC），是著名的可滿足性問題（SAT）［5，11］的一種推廣形式，在人工智能、機器學習、VLSI集成電路設計與檢測和數據庫檢索等方面有著重要應用。由于MAX－k－SAT是NPC問題，不存在多項式時間確定算法，目前主要是利用進化算法［2，5］和近似算法［8］對其進行求解，其中最著名的有GA和Johnson算法。下面先給出MAX－k－SAT的邏輯語言定義，然后提出它的一種最優(yōu)化形式表示方法。

令P＝｛p1，p2，…，pn｝是由n個不同的命題變元構成的集合，P中變元的一個指派t＝（t1，t2，…，tn）是一個函數t：P→ ｛0，1｝。顯然在P上存在2n個不同的指派。對于僅含有P中變元的命題公式C，如果t（C）＝1，則稱C在指派t下是可滿足的。一般地，我們將形如C＝pi1∨pi2∨ …∨pi r∨﹁pi，r＋1∨﹁pi，r＋2∨ …∨﹁pi k的命題公式稱為P上的子句，其中pij∈P，k稱為子句C的長度；公式A＝C1∧C2∧…∧Ci∧…∧Cm稱為P上的一個合式范式（Conjunctive Normal Form，CNF），其中Ci（1≤i≤m）為P上的子句。

基于上述邏輯定義，我們提出MAX－k－SAT（k≥3）問題的一種最優(yōu)化表示形式。

2017年9月11日，肇慶中院作出“（2017）粵12刑初32號”刑事判決：被告人鄧強犯受賄罪，判處有期徒刑4年6個月，并處罰金人民幣50萬元；鄧強退出的贓款人民幣260萬元，依法予以沒收，并由扣押機關上繳國庫。

例如：MAX－3－SAT問題CNFA＝ （﹁p1∨p2∨p3）∧ （p1∨﹁p2∨p3）∧ （p1∨p2∨﹁p3），它的8個指派依次為：t0＝ （0，0，0），t1＝ （0，0，1），t2＝ （0，1，0），t3＝ （0，1，1），t4＝ （1，0，0），t5＝ （1，0，1），t6＝ （1，1，0），t7＝ （1，1，1），其中t0，t3，t5，t6和t7使得A中所有子句均滿足，從而max∑3i＝1tj（Cj）＝3，（其中j＝0，3，5，6，7）。MAX－3－SAT實例CNFA可以等價轉換為求解定義在｛0，1｝3上的多項式函數f（X）＝ ［（1－x1）⊕x2⊕x3］＋［x1⊕ （1－x2）⊕x3］＋［x1⊕x2⊕（1－x3）］的最值的最優(yōu)化問題。

對于含有n個不同命題變元的MAX－k－SAT問題，利用強力搜索法求解需要分別計算2n個指派滿足的子句個數，計算時間復雜性為O（2n），顯然是不可取的，因此我們在下面將介紹一種基于HBDE求解MAX－k－SAT問題的有效方法。

2 求解MAX－k－SAT問題的IBDE算法

為了改善HBDE在求解MAX－k－SAT問題時的搜索效果，下面首先給出一種局部優(yōu)化方法：動態(tài)變鄰域搜索算法（Dynamic Variable Neighborhood Search，DVNS），在此基礎上，將HBDE與DVNS相結合提出一種求解MAX－k－SAT問題的有效方法。

變鄰域搜索（Variable Neighborhood Search，VNS）是 Hansen等［12］提出的一種 Meta－Heuristic算法，已被廣泛應用于求解各種NPC問題。與傳統(tǒng)的單一鄰域結構所不同的是：VNS首先預定義一系列的鄰域結構，并且在搜索中先由某個鄰域開始，按照一定的次序系統(tǒng)性地不斷變化鄰域的搜索范圍，直到有更好的解產生為止。

在VNS中，最主要的問題是確定鄰域的結構、數量以及各鄰域在搜索中應用的次序與在搜索失敗時鄰域的改變策略，特別是鄰域搜索范圍的改變策略，其優(yōu)劣程度直接決定著其應用的成敗。借鑒VNS的思想，為避免HBDE陷入局部最優(yōu)的情況發(fā)生，下面對于解為二進制向量的最大優(yōu)化問題maxf（X），給出一種基于局部隨機鄰域變化搜索的動態(tài)變鄰域搜索算法（DVNS）。令L1與L2為隨機產生的1到n之間的兩個隨機整數，并且滿足1≤L2－L1≤n/4，于是DVNS的算法偽代碼描述如下：

算法2.DVNS（X，n）Algorithm

在算法2中，rand［1，n］表示隨機產生一個1到n之間的隨機整數；X＝［x1，x2，…，xn］為輸入向量，Y＝［y1，y2，…，yn］為輸出向量。顯然，算法2的時間復雜性為O（n）。

進化算法的全局搜索能力雖然較強，但其局部搜索能力往往不足［2］。為此，下面將DVNS與HBDE相結合提出一種用于求解MAX－k－SAT問題的改進二進制差分演化算法（Improved Binary Differential Evolution，IBDE），以加強差分演化的局部搜索能力。為了有效地將HBDE與DVNS結合，不必對HBDE的每一個個體均利用DVNS進行局部優(yōu)化，而是根據種群的規(guī)模隨機地選擇一定數量（通?！躈/3，其中N為種群規(guī)模）的個體進行優(yōu)化，這樣既提高了算法的局部搜索，同時又兼顧了算法的效率。下面即給出HBDE與DVNS結合求解MAX－k－SAT問題的算法IBDE的偽代碼描述。

算法3.IBDEAlgorithm

在算法3中，rand（0，1）表示隨機產生的一個0與1之間的隨機數。由于在算法3中只利用DVNS對不超過1/3的個體隨機進行了局部優(yōu)化，因此算法3的時間復雜性為O（ITE＊（N＊n＋N＊n/3））＋O（N＊n/3）＝O（ITE＊N＊n）?？梢?，雖然IBDE是由 HBDE與DVNS相結合而得到的，但其時間復雜性仍然與HBDE相同。

3 仿真計算結果與比較

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

由于每一個 MAX－k－SAT（k≥3）問題都可以等值轉化為一個 MAX－3－SAT問題［13］，因此將利用隨機生成的大規(guī)模MAX－3－SAT實例進行仿真計算。由于IBDE、Johnson和GA均為隨機近似算法，對于每一個MAX－3－SAT實例，取各算法10次計算結果的平均值進行比較。記n為MAX－3－SAT實例中命題變元的個數，m為其中的子句個數，于是利用各算法計算一系列隨機生成的大規(guī)模MAX－3－SAT實例的結果如下：

圖1 n＝200時各算法對實例1－5的平均計算結果比較

圖2 n＝400時各算法對實例1－5的平均計算結果比較

圖3 n＝700時各算法對實例1－5的平均計算結果比較

在圖1中，實例1－5的n＝200，m依次為400，500，600，700，800；在圖2中，實例1－5的n＝400，m依次為900，1000，1100，1200，1300；在圖3中，實例1－5的n＝700，m依次為1600，1700，1800，1900，2000。

從圖1－圖3中三個算法所得到的平均最優(yōu)值可以看出：無論是n和m如何變化，IBDE求得的平均最優(yōu)值均優(yōu)于GA和Johnson算法，并且與n和m之間的比值無關；GA的計算結果也明顯優(yōu)于Johnson算法，而且也與n和m之間的比值無關；Johnson算法的求解效果明顯是三者中最差的，而且當m/n接近3時求解效果是最差的。

上述計算結果的比較表明：對于隨機大規(guī)模 MAX－k－SAT（k≥3）問題的求解，IBDE是一種比GA和Johnson算法更有效的新方法；此外，從IBDE和GA的平均求解結果均明顯優(yōu)于Johnson算法還可以看出，利用進化算法求解MAX－k－SAT（k≥3）問題是一種比Johnson算法更行之效的方法。

4 結束語

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

［1］徐宗本.計算智能—模擬進化計算［M］.北京：高等教育出版社，2005.

［2］陳國良，王熙法，莊鎮(zhèn)泉，等.遺傳算法及其應用［M］.北京：人民郵電出版社，2003.

［3］M.Dorigo，G.Caro.The Ant Colony Optimization meta－h(huán)euristic.In D.Corne，M.Dorigo，F.Glover，New Ideas in Optimization.London：McGraw Hill，1999，11－32.

［4］賀毅朝，王熙照，寇應展.一種具有混合編碼的二進制差分演化算法［J］.計算機研究與發(fā)展.2007，44（9）：1476－1484。

［5］賀毅朝，王彥祺，寇應展.一種求解3－SAT問題新方法.計算機工程與應用［J］.2006，42（16）：70－72.

［6］Frans Van den Bergh.An analysis of particle swarm optimizers［PhD］.Pretoria：University of Pretoria，2001.

［7］Ding－Zhu Du，Ker－I Ko，Xiaodu Hu.Design and Analysis of Approximation Algorithms.Springer Science Business Media，LLC，2012.

［8］Dorit S.Hochbaum（Edited）.NP難解問題的近似算法.北京：世界圖書出版公司，1995.

［9］Storn R，Price K.Differential Evolution—A simple and efficient heuristic for global optimization over continuous spaces.Journal of Global Optimization，1997，11：341－359.

［10］賀毅朝，王熙照，王彥祺，等.差分演化的收斂性分析與算法改進研究.軟件學報.2010，21（5）：875－885。

［11］堵丁柱，葛可一，王潔.計算復雜性導引［M］.北京：高等教育出版社，2002.

［12］U.K.Chakraborty，S.Das and A.Konar，Differential Evolution with Local Neighborhood［J］.in Proc.of Congress on Evolutionary Computation（CEC 2006），Vancouver，BC，Canada.IEEE Press，2006.

［13］張健.邏輯公式的可滿足性判定―方法、工具及應用.北京：科學出版社，2000.