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

王勛,宋建民,賀毅朝

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

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

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

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

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

NP完全問(wèn)題；遺傳算法；0-1背包問(wèn)題；可滿足問(wèn)題

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

1 遺傳算法簡(jiǎn)介

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

算法1 GA算法

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

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

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

（4）交叉操作：對(duì)群體P1中M個(gè)個(gè)體以交叉概率（crossover rate）Pc進(jìn)行交叉操作,生成群體P2；

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

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

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

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

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

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

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

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

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

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

令Pi是變?cè)蟵q1,q2,…,qm}中變?cè)猶i（1≤i≤m）的正文字或負(fù)文字,則形如C=P1∨P2∨…∨Ps（1≤s≤m）的命題形式稱為子句,公式A=C1∧C2∧…∧Cn稱為合取范式.所謂SAT是指：給定命題變?cè)疢上的一個(gè)合取范式A,稱判斷A是否為可滿足的問(wèn)題為SAT,即判斷是否存在一個(gè)指派t=（t1,t2,...tm）使得t（A）=1.

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

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

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

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

3.1 利用GA求解0-1KP

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

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

算法2 Greedy（X）

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

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

（3）當(dāng)（sum＜C且i≤n）時(shí)重復(fù)執(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）當(dāng)i≤n時(shí)重復(fù)執(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中,對(duì)n個(gè)物品按照價(jià)值容量比進(jìn)行排序所耗費(fèi)的時(shí)間最多,因此算法Greedy（X）的時(shí)間復(fù)雜度為O（nlogn）.在GA中利用Greedy（X）對(duì)不滿足約束條件的個(gè)體進(jìn)行處理,使得滿足約束條件的個(gè)體在處理后能夠放入背包中,不再需要重新產(chǎn)生新的個(gè)體,這樣既提高了算法的全局尋優(yōu)能力,又加快了算法的收斂速度.

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

算法3 GA1算法

（1）輸入0-1KP實(shí)例；

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

（3）計(jì)算f（Xi（0））（1≤i≤M）,當(dāng)f（Xi（0））＞C時(shí)調(diào)用Greedy（Xi（0））；

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

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

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

（7）計(jì)算f（Xi（t+1））（1≤i≤M）,當(dāng)f（Xi（t+1））＞C時(shí)調(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）的時(shí)間復(fù)雜度是多項(xiàng)式時(shí)間的,在GA1中調(diào)用Greedy（X）的次數(shù)不超過(guò)算法迭代次數(shù)的M倍,而算法3迭代次數(shù)是關(guān)于n的多項(xiàng)式,因此GA1仍是具有多項(xiàng)式時(shí)間復(fù)雜度的隨機(jī)算法.

3.2 利用GA求解3-SAT

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

首先給出LSA的算法描述.記個(gè)體X=（x1,x2,...xm）∈{0,1}m,這里m為合取范式A中的變?cè)獋€(gè)數(shù).又令g（X）表示以X=（x1,x2,...xm）為指派時(shí)A中可滿足子句的個(gè)數(shù).g（～X）表示以X=（x1,x2,...xm）為指派,且取反某個(gè)基因座之后A中可滿足子句的個(gè)數(shù).K[1...m/3]用于存儲(chǔ)不滿足子句個(gè)數(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及其對(duì)應(yīng)的基因座k；

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

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

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

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

算法5 GA2算法

（1）輸入3-SAT實(shí)例；

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

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

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

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

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

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

（8）計(jì)算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的時(shí)間復(fù)雜度是O（m）,因此易知算法GA2是求解3-SAT的具有多項(xiàng)式時(shí)間復(fù)雜度的隨機(jī)算法.

4 仿真實(shí)驗(yàn)與分析

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

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

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

0-1KP實(shí)例1給定50個(gè)物品,物品價(jià)值集為{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實(shí)例2給定200個(gè)物品,物品價(jià)值集為{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)計(jì)出3種算法求解實(shí)例1和實(shí)例2的最好結(jié)果（Best）和平均結(jié)果（Mean）,其中Mean取自10次實(shí)驗(yàn)數(shù)據(jù)的平均結(jié)果.這些數(shù)據(jù)與基本GA以及改進(jìn)的BFO算法[6]的數(shù)據(jù)進(jìn)行比較,計(jì)算結(jié)果如表1所示.

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

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

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

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

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

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

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

5 小結(jié)

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

[1]鄭宇軍,薛錦云,凌海風(fēng).組合優(yōu)化問(wèn)題簡(jiǎn)約與算法推演[J].軟件學(xué)報(bào),2011,22（9）：1985-1993.

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

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

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

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

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

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

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

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

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

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

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

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

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

（責(zé)任編輯：盧奇）

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

河北省教育廳自然科學(xué)基金（Z2013110）

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

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