王 勛，宋建民，賀毅朝

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

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

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

遺傳算法（Genetic algorithm，GA）［4］是1975年由美國(guó)密西根大學(xué)的D.J.Holland借鑒生物進(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問(wèn)題的數(shù)學(xué)模型

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

0－1背包問(wèn)題（0－1Knapsack Problem，0－1KP）［2，7］是一種典型的 KP問(wèn)題，其本質(zhì)是在資源有限的條件下追求最大收益的資源有效分配問(wèn)題，它的一般描述如下：

令wi和pi分別表示n個(gè)給定物品中的第i（1≤i≤n）個(gè)物品的重量和價(jià)值，C表示背包的容量，其中wi，pi和C都是正整數(shù)，如何從這n個(gè)物品中選擇物品裝入背包使在不超過(guò)背包容量C的前提下其價(jià)值之和達(dá)到最大？

0－1KP問(wèn)題存在許多數(shù)學(xué)模型，其中最常實(shí)用的模型如下：

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

2.2 3－SAT問(wèn)題的數(shù)學(xué)模型

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

令Pi是變?cè)希鹮1，q2，…，qm｝中變?cè)猶i（1≤i≤m）的正文字或負(fù)文字，則形如C＝P1∨P2∨…∨Ps（1≤s≤m）的命題形式稱為子句，公式A＝C1∧C2∧…∧Cn稱為合取范式。所謂SAT問(wèn)題是指：給定命題變?cè)疢上的一個(gè)合取范式A，稱判斷A是否為可滿足的問(wèn)題為SAT問(wèn)題，即判斷是否存在一個(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)題［3］。注意到｛0，1｝m上的多項(xiàng)式f（x1，x2，…，xs）＝（1－x1）（1－x2）…

jjjjjj（1－xjk）xj（k＋1）xj（k＋2）…xjs在 X＝（t1，t2，…，tm）∈｛0，1｝m時(shí)的值為0當(dāng)且僅當(dāng)子句 Cj＝在指派t＝（t1，t2，…，tm）下的值為1，其中1≤s≤m，1≤j≤n，因此合取范式A＝C1∧C2∧…∧Cn是可滿足的當(dāng)且僅當(dāng)多項(xiàng)式函數(shù)

在｛0，1｝m上存在最小值0。由此，即建立了SAT的數(shù)學(xué)模型。

由于任意SAT問(wèn)題等值于一個(gè)3－SAT問(wèn)題，因此下面將主要討論3－SAT問(wèn)題的求解。

3 利用GA求解0－1KP和SAT問(wèn)題

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

3.1 利用GA求解0－1KP問(wèn)題

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

令數(shù)組W［1…n］存放n個(gè)物品的重量，數(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(mén)，則GA1的算法描述如下。

算法3 GA1算法

（1）輸入0－1KP問(wèn)題實(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問(wèn)題

在利用GA求解3－SAT問(wèn)題時(shí)，為了克服GA易于陷入局部最優(yōu)的缺點(diǎn)，在GA中引入局部搜索算法（local search algorithm，LSA）［9，11，13］以避免其陷入局部最優(yōu)的缺點(diǎn)。

下面首先給出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）＊2do

（2） xj＝1－xj；

（3） K［j］＝g（～X）－g（X）；

（4） xj＝1－xj；

（5）end for；

（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問(wèn)題的混合遺傳算法GA2。令Xbes（t）表示種群P（t）中最優(yōu)個(gè)體，Xworst（t）表示種群P（t）中最差個(gè)體，f（Xbes（t））和f（Xworst（t））分別為它們的適應(yīng)度，算法的最大迭代次數(shù)為T(mén)，則GA2的算法描述如下。

算法5 GA2算法

（1）輸入3－SAT問(wèn)題實(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問(wèn)題的具有多項(xiàng)式時(shí)間復(fù)雜度的隨機(jī)算法。

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

為了驗(yàn)證GA1和GA2求解0－1KP問(wèn)題與3－SAT問(wèn)題的可行性和有效性，下面分別利用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.53GHz，內(nèi)存為4G，操作系統(tǒng)為Microsoft Windows 7。所有算法均利用VC 6.0編程實(shí)現(xiàn)。

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

下面首先給出兩個(gè)較大規(guī)模的0－1KP的實(shí)例［14］。

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｝，物品重量集為｛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，28，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，46，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｝，物品重量集為｛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，20，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｝，背包容量為1000。

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

表1 GA1、改進(jìn)BFO和GA求解0－1KP實(shí)例的結(jié)果比較

通過(guò)比較發(fā)現(xiàn)：對(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問(wèn)題GA1的求解效果相比GA和改進(jìn)BFO均優(yōu)，特別是當(dāng)實(shí)例規(guī)模增大時(shí)，GA1求解效果的優(yōu)越性更加明顯，因此GA1是一種求解0－1KP問(wèn)題可行且有效的算法。

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中，分別給出了兩種算法得到可滿足解的比率（Suc）和實(shí)驗(yàn)次數(shù)（Test），以及GA2相比GA得到可滿足解的成功率的增值（Imp）。

表2 GA2和GA求解3－SAT實(shí)例的結(jié)果比較

由表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é)束語(yǔ)

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

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

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

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

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

［5］ M.H.Alsuwaiyel（著），吳偉昶，方世昌（譯）.算法設(shè)計(jì)技巧與分析［M］.北京：電子工業(yè)出版社，2004.8.

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

［7］ 曾國(guó)清.0－1背包問(wèn)題的遺傳算法求解［J］.高校理科研究，2006，3：242－243.

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

［9］ Zbigniew Michalewicz（著），曹宏慶（譯）.如何求解問(wèn)題——現(xiàn)代啟發(fā)式方法［M］.北京：中國(guó)水利水電出版社.

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

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

［12］ 耿素云，屈婉玲，王捍貧.離散數(shù)學(xué)教程［M］.北京：北京大學(xué)出版社，2002.

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

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