宋建民,弓小影

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

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

1 MAX-k-SAT問題

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

2 IBDE算法設計

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

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

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

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

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

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

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

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

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

4 小結(jié)

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

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

[2]賀毅朝,王彥祺,寇應展.一種求解3-SAT問題新方法[J].計算機工程與應用,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]堵丁柱,葛可一,王潔.計算復雜性導引[M].北京：高等教育出版社,2002.

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

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

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