王勛,宋建民,賀毅朝

（1.石家莊經(jīng)濟學院信息工程學院,河北石家莊050031；2.石家莊經(jīng)濟學院數(shù)理學院,河北石家莊050031）

基于遺傳算法求解NPC的研究

王勛1,宋建民2,賀毅朝1

（1.石家莊經(jīng)濟學院信息工程學院,河北石家莊050031；2.石家莊經(jīng)濟學院數(shù)理學院,河北石家莊050031）

首先建立了0-1KP和3-SAT的數(shù)學模型；然后分別基于遺傳算法（GA）與貪心策略相結(jié)合給出了一種求解0-1KP的有效算法,基于GA與局部搜索相結(jié)合給出了一種求解3-SAT的可行算法；最后通過對0-1KP實例和3-SAT實例的仿真計算,驗證了算法的可行性與有效性.

NP完全問題；遺傳算法；0-1背包問題；可滿足問題

NP完全問題（NP-Complete problem,NPC）[1-2]是理論計算機科學中非常重要的一類難解問題,對于計算復雜性的研究起著關(guān)鍵的作用.0-1背包問題（0-1Knapsack problem,0-1KP）[2-6]和SAT（Satisfiability problem,SAT）[2,7-10]均為NPC中非常經(jīng)典的問題,同時也是組合優(yōu)化問題[11-12],其中KP在預算控制和貨物裝載等領(lǐng)域有廣泛的應用,而SAT在邏輯推理和人工智能等領(lǐng)域有廣泛的應用.本文利用遺傳算法與某些策略相結(jié)合求解0-1KP和SAT,并且通過具體的實例計算驗證了其可行性和有效性.

1 遺傳算法簡介

遺傳算法（Genetic algorithm,GA）[13-14]是1975年由美國密西根大學的Holland D J教授借鑒生物進化機制提出來的一種仿生算法.在GA中,將待求解問題的每一個可行解看作是群體中的一個染色體個體,利用二進制（或十進制）編碼表示,其優(yōu)劣由適應度來衡量（適應度不一定是目標函數(shù)值）.在GA的進化中,利用交叉算子和變異算子作用于當前群體中的個體而產(chǎn)生新的個體,根據(jù)新個體的適應度由選擇算子選擇來構(gòu)成新一代種群,如此反復迭代進化,直到獲得滿意的結(jié)果為止.GA的算法流程一般描述如下.

算法1 GA算法

（1）初始化：設(shè)置迭代次數(shù)N,隨機生成M個個體構(gòu)成初始種群P（0）,令進化代數(shù)t=0；

（2）計算適應度：計算種群P（t）中每個個體的適應度,確定當前最優(yōu)個體B；

（3）選擇操作：根據(jù)種群個體的適應度的值,利用選擇算子從第t代群體P（t）中選出M個優(yōu)良個體（可能出現(xiàn)某個體被選擇多次的情況）遺傳到下一代群體P1中；

（4）交叉操作：對群體P1中M個個體以交叉概率（crossover rate）Pc進行交叉操作,生成群體P2；

（5）變異操作：對群體P2中每個個體以變異概率（mutation rate）Pm進行變異操作,產(chǎn)生第t+1代群體P（t+1）,并令t=t+1；

（6）終止條件判斷：判斷是否滿足終止條件,若滿足則輸出B和f（B）并結(jié)束,否則轉(zhuǎn)至（2）繼續(xù)迭代進化.

由于選擇操作、交叉操作、變異操作和適應度計算等的時間復雜度均是關(guān)于問題維數(shù)的多項式,而遺傳算法的迭代次數(shù)通常也是關(guān)于問題維數(shù)的多項式,因此GA是一個復雜度為多項式時間的隨機算法.

2 0-1KP和SAT的數(shù)學模型

2.1 0-1KP的數(shù)學模型

0-1KP[2-3]是一種典型的KP,其本質(zhì)是在資源有限的條件下追求最大收益的資源有效分配問題,它的一般描述如下：令wi和pi分別表示n個給定物品中的第i（1≤i≤n）個物品的質(zhì)量和價值,C表示背包的容量,其中wi、pi和C都是正整數(shù),如何從這n個物品中選擇物品裝入背包使在不超過背包容量C的前提下其價值之和達到最大？

0-1KP存在許多數(shù)學模型,其中最常實用的模型為

xi為0-1決策變量,當xi=1時表示將物品i裝入背包中,當xi=0時則表示不將其裝入背包中.顯然0-1KP是一個約束最優(yōu)化問題,式（2）為其約束條件.

2.2 3-SAT的數(shù)學模型

SAT問題是Cook證明的第一個NPC[2].目前,求解SAT已經(jīng)有多種算法,如DP算法、局部搜索算法、模擬退火算法和近似算法等[2,7].由于3-SAT是一類特殊的SAT,因此SAT的數(shù)學模型對于3-SAT也是適用的.

令Pi是變元集合{q1,q2,…,qm}中變元qi（1≤i≤m）的正文字或負文字,則形如C=P1∨P2∨…∨Ps（1≤s≤m）的命題形式稱為子句,公式A=C1∧C2∧…∧Cn稱為合取范式.所謂SAT是指：給定命題變元集M上的一個合取范式A,稱判斷A是否為可滿足的問題為SAT,即判斷是否存在一個指派t=（t1,t2,...tm）使得t（A）=1.

下面,將SAT的數(shù)學模型建立為{0,1}m上判定多項式f（x1,x2,…xm）是否存在最小值0的數(shù)值優(yōu)化問題[7,9].注意到{0,1}m上的多項式fj（xj1,xj2,…xjs）=（1-xj1）（1-xj2）…（1-xjk）xj（k+1）xj（k+2）…xjs在X=（t1,t2,...tm）∈{0,1}m時的值為0,當且僅當子句在指派t=（t1,t2,...tm）下的值為1,其中1≤s≤m, 1≤j≤n,因此合取范式A=C1∧C2∧…∧Cn是可滿足的當且僅當多項式函數(shù)（3）在{0,1}m上存在最小值0.由此,即建立了SAT的數(shù)學模型.

由于任意SAT等值于一個3-SAT,因此下面將主要討論3-SAT的求解.

3 利用GA求解0-1KP和SAT

本節(jié)將分別基于GA與貪心策略相結(jié)合、與局部搜索算法相結(jié)合給出求解0-1KP和3-SAT的改進算法GA1和GA2.

3.1 利用GA求解0-1KP

在利用GA求解0-1KP時,產(chǎn)生的新個體有可能不滿足約束條件（2）,稱這種個體為非正常個體.非正常個體的存在將大大降低算法的收斂性,為了避免這種現(xiàn)象,將利用算法2給出的貪心策略[3]對非正常個體進行處理,使之成為滿足約束條件（2）的個體.為了區(qū)別于基本GA,下面將結(jié)合了算法2的GA記為GA1.

令數(shù)組W[1…n]存放n個物品的質(zhì)量,數(shù)組P[1…n]存放n個物品的價值,背包容量記為C,設(shè)個體X=（x1,x2,…xn）∈{0,1}n對應的f（X）＞C,即個體X是一個非正常個體,則修正個體X的貪心策略由算法2給出.

算法2 Greedy（X）

（1）按照P[i]/W[i]（1≤i≤n）由大到小的順序?qū)ξ锲放判?并按所排順序?qū)⑽锲废聵舜嫒霐?shù)組H[1...n]；

（2）令sum=0；i=1；

（3）當（sum＜C且i≤n）時重復執(zhí)行（4）至（6）；

（4）如果XH[i]=1且sum+W[H[i]]≤C則sum=sum+W[H[i]]且i=i+1；

（5）如果XH[i]=0則i=i+1；

（6）如果XH[i]=1且sum+W[H[i]]＞C則令XH[i]=0且i=i+1；

（7）當i≤n時重復執(zhí)行（8）至（9）；

（8）如果sum+W[H[i]]≤C則sum=sum+W[H[i]]且令XH[i]=1,i=i+1；

（9）如果sum+W[H[i]]＞C則令XH[i]=0,i=i+1；

（10）輸出X,算法結(jié)束.

在算法2中,對n個物品按照價值容量比進行排序所耗費的時間最多,因此算法Greedy（X）的時間復雜度為O（nlogn）.在GA中利用Greedy（X）對不滿足約束條件的個體進行處理,使得滿足約束條件的個體在處理后能夠放入背包中,不再需要重新產(chǎn)生新的個體,這樣既提高了算法的全局尋優(yōu)能力,又加快了算法的收斂速度.

下面將GA與Greedy（X）結(jié)合給出算法GA1.令Xbes（t）表示種群P（t）中最優(yōu)個體,Xworst（t）表示種群P（t）中最差個體,f（Xbes（t））和f（Xworst（t））分別為它們的適應度,算法的最大迭代次數(shù)為T,則GA1的算法描述如下.

算法3 GA1算法

（1）輸入0-1KP實例；

（2）隨機生成初始種群P（0）={Xi（0）∈{0,1}n|1≤i≤M}；

（3）計算f（Xi（0））（1≤i≤M）,當f（Xi（0））＞C時調(diào)用Greedy（Xi（0））；

（4）確定Xbes（0）和Xworst（0）,并令t=0；

（5）如果t＞T,則轉(zhuǎn)至（10）執(zhí)行；

（6）對種群P（t）進行交叉、變異、選擇操作,產(chǎn)生新種群P（t+1）；

（7）計算f（Xi（t+1））（1≤i≤M）,當f（Xi（t+1））＞C時調(diào)用Greedy（Xi（t+1））；

（8）確定Xbes（t+1）和Xworst（t+1）,若f（Xworst（t））＞f（Xbes（t+1））則Xworst（t+1）=Xbes（t）；

（9）置t=t+1,并轉(zhuǎn)（5）執(zhí)行；

（10）輸出Xbes（t）和f（Xbes（t））,算法結(jié)束.

由于Greedy（X）的時間復雜度是多項式時間的,在GA1中調(diào)用Greedy（X）的次數(shù)不超過算法迭代次數(shù)的M倍,而算法3迭代次數(shù)是關(guān)于n的多項式,因此GA1仍是具有多項式時間復雜度的隨機算法.

3.2 利用GA求解3-SAT

在利用GA求解3-SAT時,為了克服GA易于陷入局部最優(yōu)的缺點,在GA中引入局部搜索算法（local search algorithm,LSA）[7,9,10,12].

首先給出LSA的算法描述.記個體X=（x1,x2,...xm）∈{0,1}m,這里m為合取范式A中的變元個數(shù).又令g（X）表示以X=（x1,x2,...xm）為指派時A中可滿足子句的個數(shù).g（～X）表示以X=（x1,x2,...xm）為指派,且取反某個基因座之后A中可滿足子句的個數(shù).K[1...m/3]用于存儲不滿足子句個數(shù)的減少值,Kmax表示該數(shù)組中的最大值.則LSA的算法偽代碼描述如下.

算法4 LSA（X）

（1）for j=m/3 to（m/3）*2 do

（2）xj=1-xj；

（3）K[j]=g（～X）-g（X）；

（4）xj=1-xj；

（5）endfor；

（6）確定K[m/3…（m/3）*2]中的最大值Kmax及其對應的基因座k；

（7）將X中基因座k的值取反；

（8）輸出X,算法結(jié)束.

在LSA中,算法通過嘗試改變某基因座的值以使個體不滿足3-SAT的子句的個數(shù)減少,找到使得子句個數(shù)減少最多的基因座并將其值取反,所得新個體必是局部最優(yōu)的.LSA使得個體在改變最少的情況下得到最佳的優(yōu)化結(jié)果,其時間復雜度是O（m）.

將LSA與GA相結(jié)合,給出求解3-SAT的混合遺傳算法GA2.令Xbes（t）表示種群P（t）中最優(yōu)個體, Xworst（t）表示種群P（t）中最差個體,f（Xbes（t））和f（Xworst（t））分別為它們的適應度,算法的最大迭代次數(shù)為T,則GA2的算法描述如下.

算法5 GA2算法

（1）輸入3-SAT實例；

（2）隨機生成初始種群P（0）={Xi（0）∈{0,1}n|1≤i≤M}；

（3）調(diào)用LSA（Xi（0））（1≤i≤M）,并令t=0；

（4）計算f（Xi（t））（1≤i≤M）,并確定Xbes（t）和Xworst（t）；

（5）如果t＞T,則轉(zhuǎn)至（11）執(zhí)行；

（6）對種群P（t）進行交叉、變異、選擇操作,產(chǎn)生新種群P（t+1）；

（7）調(diào)用LSA（Xi（t+1））（1≤i≤M）；

（8）計算f（Xi（t+1））（1≤i≤M）,并確定Xbes（t+1）和Xworst（t+1）；

（9）若f（Xbes（t+1））＜f（Xworst（t））則Xworst（t+1）=Xbes（t）；

（10）置t=t+1,并轉(zhuǎn)（5）執(zhí)行；

（11）輸出Xbes（t）和f（Xbes（t））,算法結(jié)束.

由于LSA的時間復雜度是O（m）,因此易知算法GA2是求解3-SAT的具有多項式時間復雜度的隨機算法.

4 仿真實驗與分析

為了驗證GA1和GA2求解0-1KP與3-SAT的可行性和有效性,分別利用GA1與GA2求解0-1KP實例和3-SAT實例,并將計算結(jié)果與相關(guān)算法分析比較,從而驗證GA1與GA2的性能.計算所使用的微型機的配置如下：CPU為Intel（R）Core（TM）i3,主頻2.53 GHz,內(nèi)存為4 G,操作系統(tǒng)為Microsoft Windows 7.所有算法均利用VC 6.0編程實現(xiàn).

4.1 基于GA1求解0-1KP實例的結(jié)果與分析

首先給出2個較大規(guī)模的0-1KP的實例[6].

0-1KP實例1給定50個物品,物品價值集為{3,13,10,13,5,6,6,3,11,3,9,2,7,9,7,4,6,3,9,4,9,5,8,9,10,14, 7,8,7,9,5,5,11,7,5,11,6,9,8,9,11,8,5,10,10,9,10,8,10,12},物品質(zhì)量集為{2,5,1,9,3,6,4,9,3,2,8,9,6,2,5,2,5,9, 4,2,3,4,8,5,4,3,1,2,1,1,3,3,6,3,1,2,1,4,1,1,4,5,3,5,5,2,6,1,5,3},背包容量為80.

0-1KP實例2給定200個物品,物品價值集為{98,42,27,4,41,85,38,52,26,12,44,87,92,45,95,23,44,48, 75,20,57,25,66,62,90,31,9,97,81,83,54,74,92,54,88,81,70,96,44,84,36,74,50,38,27,58,82,50,40,2,25,71,65,21, 14,50,59,34,60,38,42,17,69,80,76,38,91,58,85,38,75,91,27,39,80,90,72,32,59,80,49,66,54,20,88,33,68,21,98, 58,86,38,43,61,13,88,27,41,44,68,18,59,32,17,5,86,23,47,95,46,22,35,54,11,9,40,61,41,11,8,34,2,4,100,2 8, 54,16,58,44,45,67,23,10,44,84,22,61,13,54,14,52,81,91,40,63,73,76,67,89,19,61,40,3,15,51,69,89,36,42,4 6, 9,55,57,69,98,63,41,46,2,5,89,16,64,49,77,53,76,70,95,87,82,26,19,33,92,83,78,83,92,3,63,59,89,82,45,5,46, 1,33,54},物品質(zhì)量集{8,20,18,8,8,10,20,13,15,18,8,12,18,3,18,3,18,7,12,11,15,2,4,6,4,18,9,7,18,19,15,1,3,11, 20,17,20,4,6,7,3,13,17,17,4,2,1,1,4,7,20,10,1,19,20,5,11,12,1,7,3,10,6,20,11,13,2,20,1,4,18,18,20,6,12,12,1, 12,19,15,16,58,6,2,2,1,6,6,15,8,11,12,14,3,16,6,15,19,20,9,4,16,3,14,5,3,17,19,15,10,2,9,7,13,13,3,9,1,6,2 0, 8,15,8,17,19,6,20,17,1,20,11,12,4,10,15,2,7,17,10,6,12,4,4,12,2,20,6,5,13,12,5,5,19,4,19,17,2,17,12,16,18,2, 18,14,12,1,10,6,10,2,18,20,18,7,1,14,7,5,17,5,13,9,3,11,19,10,7,9,1,15,17,11,15,19,7,4,4},背包容量為1 000.

算法GA1和GA的參數(shù)設(shè)置為：迭代次數(shù)置為200,群體規(guī)模為40,交叉概率為0.8,變異概率0.085.統(tǒng)計出3種算法求解實例1和實例2的最好結(jié)果（Best）和平均結(jié)果（Mean）,其中Mean取自10次實驗數(shù)據(jù)的平均結(jié)果.這些數(shù)據(jù)與基本GA以及改進的BFO算法[6]的數(shù)據(jù)進行比較,計算結(jié)果如表1所示.

表1 GA1、改進BFO和GA求解0-1KP實例的結(jié)果比較Tab.1 The comparison of results of GA1,Improved BFO and GA for 0-1KP instances

由表1可知,對于0-1KP實例1,GA1求得的最好值比GA和改進BFO更優(yōu),其平均值與改進BFO相差不大,但明顯優(yōu)于GA.對于0-1KP實例2,GA1求得的最好值和平均值明顯比GA和改進BFO要優(yōu)很多.以上對比表明,對于0-1KP的求解GA1效果相比GA和改進BFO均優(yōu),特別是當實例規(guī)模增大時, GA1求解效果的優(yōu)越性更加明顯,因此GA1是一種求解0-1KP可行且有效的算法.

4.2 基于GA2求解3-SAT實例的結(jié)果與分析

為了驗證GA2求解3-SAT問題的可行性與有效性,分別利用GA2和GA求解一系列隨機生成的3-SAT實例,實例的規(guī)模由（m,n）表示,其中m為變元個數(shù),n為子句個數(shù).計算結(jié)果見表2中.

在GA2和GA中,參數(shù)設(shè)置為：種群規(guī)模為10,最大迭代次數(shù)為200,交叉概率為0.6,變異概率為0.1.在表2中,分別給出了2種算法得到可滿足解的比率（Suc）和實驗次數(shù)（Test）,以及GA2相比GA得到可滿足解的成功率的增值（Imp）.

表2 GA2和GA求解3-SAT實例的結(jié)果比較Tab.2 The comparison of results of GA2 and GA for 3-SAT instances%

由表2可知,在實驗次數(shù)、變元數(shù)和子句數(shù)相同情況下,GA2比GA的求解性能更高,GA2得到可滿足解的成功率比GA平均提高了近3.2%,可見基于LSA對GA的改進是非常成功的,即GA2是一種適于求解3-SAT問題的有效算法.

5 小結(jié)

本文首先分別介紹了0-1KP和3-SAT的數(shù)學模型,給出了基本遺傳算法的實現(xiàn)流程；然后分別基于GA與貪心策略相結(jié)合、與局部搜索相結(jié)合求解0-1KP和3-SAT,給出了相應的改進算法GA1和GA2.仿真計算結(jié)果表明,改進遺傳算法是求解0-1KP和3-SAT行之有效的方法.

[1]鄭宇軍,薛錦云,凌海風.組合優(yōu)化問題簡約與算法推演[J].軟件學報,2011,22（9）：1985-1993.

[2]Alsuwaiyel M H.算法設(shè)計技巧與分析[M].吳偉昶,方世昌,譯.北京：電子工業(yè)出版社,2004.

[3]賀毅朝,劉坤起,張翠軍,等.求解背包問題的貪心算法及其應用[J].計算機工程與設(shè)計,2007,28（11）：55-57.

[4]曾國清.0-1背包問題的遺傳算法求解[J].高校理科研究,2006（3）：242-243.

[5]王秋芬,梁道雷.一種求解0-1背包問題的算法[J].計算機技術(shù)與發(fā)展,2013,23（1）：123-127.

[6]杜明煜,雷秀娟.改進的細菌覓食優(yōu)化算法求解0-1背包問題[J].計算機技術(shù)與發(fā)展,2014,24（5）：44-47.

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

[8]田奕,劉濤,李國杰.求解可滿足問題的一種高效遺傳算法[J].模式識別與人工智能,1996,9（3）：209-212.

[9]曹國生,賀毅朝,李敏,等.基于改進的遺傳算法求解可滿足性問題[J].現(xiàn)代計算機,2008,28（4）：16-19.

[10]Zbigniew M,David B F.如何求解問題——現(xiàn)代啟發(fā)式方法[M].曹宏慶,李艷,董紅斌,等譯.北京：中國水利水電出版社, 2003.

[11]耿素云,屈婉玲,王捍貧.離散數(shù)學教程[M].北京：北京大學出版社,2002.

[12]張宏斌.組合優(yōu)化問題的啟發(fā)式搜索[J].計算機科學,1998,25（2）：13-16..

[13]周明,孫樹棟.遺傳算法原理及應用[M].北京：國防工業(yè)出版社,1999.

[14]岳琪,宋文龍.遺傳算法與組合優(yōu)化問題研究[J].信息技術(shù),2004,28（1）：53-54.

（責任編輯：盧奇）

Solving NP-Complete problems by genetic algorithms

Wang Xun1,Song Jianmin2,He Yichao1
（1.College of Information Engineering,Shijiazhuang University of Economics,Shijiazhuang 050031, China；2.Mathematics and Sciences,Shijiazhuang University of Economics,Shijiazhuang 050031, China）

Two NP-Complete problems：the 0-1 knapsack problem and 3-SAT problem were introduced firstly in this paper.An efficient algorithm for solving 0-1KP was given based on genetic algorithm combining with greedy strategy,and an efficient algorithm for solving 3-SAT problem was presented based on genetic algorithm combining with local search strategy.At last,the feasible and effective of the algorithm were verified by 0-1KP instances and 3-SAT instances of simulation.

NP-complete problem；genetic algorithm；0-1 knapsack problem；satisfiability problem

TP301.6

A

1008-7516（2014）06-0040-06

10.3969/j.issn.1008-7516.2014.06.009

2014-09-25

河北省教育廳自然科學基金（Z2013110）

王勛（1992—）,男,湖北鐘祥人.主要從事算法設(shè)計與分析研究.

賀毅朝（1969—）,男,河北晉州人,碩士,教授,CCF高級會員.主要從事進化算法、隨機算法與近似算法、計算復雜性理論研究.