關(guān)于0－1背包問題的研究＊

王 雯，武 燕

（太原工業(yè)學(xué)院，山西 太原 030008）

0 引言

背包問題是一種組合優(yōu)化問題，具有較強(qiáng)的實(shí)際意義，從現(xiàn)實(shí)應(yīng)用角度來看，貨物的裝箱問題、物資的分配和存儲(chǔ)問題等都可以用背包問題來解決。隨著現(xiàn)代網(wǎng)絡(luò)的日益發(fā)展，在電子商務(wù)領(lǐng)域中，背包公鑰密碼的應(yīng)用也越來越廣泛。但是當(dāng)求解問題的數(shù)量較多時(shí)，最優(yōu)解的求解還是比較困難，所以，對(duì)0－1背包問題進(jìn)行算法研究或改進(jìn)是一件很有必要的工作。

傳統(tǒng)求解背包問題的方法有近似算法和精確算法，其中，近似算法包括貪婪法、粒子群算法［1］、遺傳算法、蟻群算法［2］等；精確算法包括回溯法、動(dòng)態(tài)規(guī)劃法等。精確算法存在空間及時(shí)間復(fù)雜性的問題，為克服此缺點(diǎn)，用近似算法求解背包問題已經(jīng)越來越受到人們的關(guān)注。除了上述這幾種常見的算法以外，還出現(xiàn)了二進(jìn)制差異演化算法［3］、知識(shí)進(jìn)化算法［4］等新的算法。還有粗糙集也可以用于解決背包問題，將粗糙集理論引入遺傳算法來解決背包問題，目的在于提高單純遺傳算法的搜索效率，同時(shí)也可以改善解的質(zhì)量。

1 0－1背包問題［5］

背包問題可以這樣理解：假設(shè)一位商人有一個(gè)容量為C公斤的背包，現(xiàn)在有n個(gè)重量和價(jià)值分別為ci＞0和pi＞0（i＝1，2，…，n）的物件，選擇哪幾個(gè)物件放入背包，能使所裝物件的價(jià)值最大，并且不超過背包的容量限制。

0－1背包問題是指每類物件都有一件放入或者不放入。設(shè)變量為xi，當(dāng)物件i被放入時(shí)，則xi＝1；不放入時(shí)，xi＝0。其數(shù)學(xué)表達(dá)式為：

2 常規(guī)算法在求解0－1背包問題中的應(yīng)用

2.1 近似算法

2.1.1 貪婪法

貪婪法屬于一種啟發(fā)式算法，貪婪算法會(huì)以當(dāng)前狀況為基礎(chǔ)作最優(yōu)選擇，容易忽略整體，但它可以在較短的時(shí)間內(nèi)求到解，在很多情況下可以達(dá)到預(yù)期的目的，缺點(diǎn)是該啟發(fā)式算法不一定能夠獲得最優(yōu)解。

貪婪策略對(duì)貪婪法求取最優(yōu)解至關(guān)重要，常用的貪婪策略有質(zhì)量貪婪準(zhǔn)則和價(jià)值密度貪婪準(zhǔn)則、價(jià)值貪婪準(zhǔn)則。這3種貪婪策略對(duì)背包的裝入都是采用多步過程來完成的。貪婪法可以與其他算法相結(jié)合來解決背包問題，例如有楊婷婷、趙新超的更貪心粒子群算法，對(duì)于大規(guī)模背包問題的求解非常有幫助；此外還有馬杰良和劉茜提出的混合遺傳算法［6］，貪婪算法可以為遺傳進(jìn)化過程打下良好的基礎(chǔ)，最終結(jié)果表明在求解質(zhì)量及速度方面該算法都卓有成效。

2.1.2 遺傳算法

遺傳算法具有高效性、全局最優(yōu)性和并行性的優(yōu)點(diǎn)，廣泛應(yīng)用于函數(shù)的優(yōu)化過程中，它把問題中每個(gè)可能性的解當(dāng)成群體的一個(gè)染色體，再對(duì)染色體進(jìn)行編碼，依據(jù)目標(biāo)函數(shù)進(jìn)行個(gè)體評(píng)價(jià)，得出適應(yīng)值，并依據(jù)適應(yīng)值開始尋優(yōu)，其尋優(yōu)過程由選擇和雜交、變異步驟實(shí)現(xiàn)［7］。在此過程中，選擇算子及雜交算子影響尋優(yōu)過程的搜索能力，變異算子則決定了尋優(yōu)過程中空間的每個(gè)點(diǎn)都能被搜索到，因此該算法具有能夠搜索全局最優(yōu)解的優(yōu)點(diǎn)。

采用傳統(tǒng)的遺傳算法解決背包問題時(shí)，得到最優(yōu)解或近似最優(yōu)解的前提是背包問題的規(guī)模較小，當(dāng)背包問題的規(guī)模較大時(shí)，會(huì)出現(xiàn)早熟的情況，不會(huì)得出理想的結(jié)果，需要進(jìn)一步改進(jìn)。改進(jìn)的方法可以用罰函數(shù)法來對(duì)目標(biāo)函數(shù)進(jìn)行改造；還可以把貪心算法和遺傳算法相結(jié)合，貪心算法可以對(duì)染色體的解碼過程進(jìn)行改造，即為混合遺傳算法。

除此以外，文獻(xiàn)［8］把禁忌搜索算法和遺傳算法相結(jié)合，為背包問題的解決提供了新的思路，該算法在父代種群的選擇、雜交和變異操作基礎(chǔ)上，對(duì)產(chǎn)生的子代單獨(dú)個(gè)體進(jìn)行禁忌搜索，搜索完成后，該個(gè)體將會(huì)被鄰域的最優(yōu)解取代。當(dāng)禁忌搜索完所有子代個(gè)體后，就完成了新種群的衍生過程。其實(shí)驗(yàn)結(jié)果說明，該算法在搜索效率及收斂速度上卓有成效。

另外文獻(xiàn)［9］指出了主動(dòng)進(jìn)化遺傳算法的思想，這種算法在對(duì)種子個(gè)體進(jìn)行編碼時(shí)采用概率編碼方法，用定向變異方式代替了交叉操作，可以使遺傳算法的尋優(yōu)過程更為有效和確定，避免了傳統(tǒng)遺傳算法中由于是不定向變異而產(chǎn)生的盲目性。

2.1.3 蟻群算法

蟻群算法具有較強(qiáng)的魯棒性和全局優(yōu)化性，并且該算法容易與其他優(yōu)化算法相結(jié)合，在車輛路徑系統(tǒng)與通信系統(tǒng)等方面應(yīng)用較為完善。在利用蟻群算法解決0－1背包問題時(shí)，關(guān)鍵點(diǎn)在于某一物件聚集的信息素越多，該物件就越有可能被選中。對(duì)應(yīng)于0－1背包問題的物件取值0，1，利用蟻群算法時(shí)將一個(gè)變量設(shè)為兩只螞蟻，并定義目標(biāo)函數(shù)f為［10］：

其中：M為一充分大的正數(shù)。

蟻群算法應(yīng)用于背包問題的具體過程可概括為首先要對(duì)迭代次數(shù)進(jìn)行設(shè)置，之后把各螞蟻放在對(duì)應(yīng)變量的0或1位置點(diǎn)，然后依據(jù)轉(zhuǎn)移概率對(duì)各螞蟻進(jìn)行移動(dòng)，依據(jù)強(qiáng)度更新方程對(duì)信息素的軌跡進(jìn)行更新，最后對(duì)當(dāng)前最佳螞蟻的位置點(diǎn)進(jìn)行記錄，往復(fù)循環(huán)此過程直至達(dá)到退出條件。

一般情況下蟻群算法的收斂速度較快，但當(dāng)數(shù)據(jù)的數(shù)量增多時(shí)，蟻群算法的收斂速度隨數(shù)據(jù)規(guī)模的增大而降低。很多學(xué)者對(duì)該算法的缺點(diǎn)進(jìn)行了改進(jìn)，在減少算法時(shí)間和降低尋優(yōu)計(jì)算量方面做出了一定貢獻(xiàn)。文獻(xiàn)［11］提出了一種新的混合算法，該方法使用蟻群算法得到優(yōu)化解，為擴(kuò)大解的搜索空間使用了抗體克隆選擇算法，這種混合算法可以提高收斂的速度，同時(shí)也在一定程度上增強(qiáng)了尋優(yōu)的能力。文獻(xiàn)［12］中把交換策略引入到蟻群算法中，對(duì)不屬于禁忌表的有向線段序號(hào)及屬于禁忌表的有向線段序號(hào)進(jìn)行交換，該局部?jī)?yōu)化方法可改善每一代構(gòu)造的解，因此解的質(zhì)量可以得到很好的改善，使收斂速度明顯加快。文獻(xiàn)［13］提出一種新的基于解的相異度的蟻群算法，這種算法把信息量放在物件上，而非傳統(tǒng)蟻群算法將信息量放在路徑上，同時(shí)該算法增加了信息量的局部更新機(jī)制，如果一個(gè)物件被選中，其信息量會(huì)馬上減少，從而降低其他螞蟻選擇該物件的可能性，變異操作可以依據(jù)相異度適當(dāng)?shù)貙?duì)變異概率進(jìn)行調(diào)整。這種算法中解的變異概率是由解的相異程度決定的，因此可以克服解的早熟現(xiàn)象，無論是解的全局性還是解的多樣性都得到了很大的改善，特別適用于求解數(shù)量多、規(guī)模大的背包問題。

2.2 精確算法

2.2.1 動(dòng)態(tài)規(guī)劃法

在20世紀(jì)50年代，Richard Bell man提出了動(dòng)態(tài)規(guī)劃法，這種方法可以將多階段決策問題轉(zhuǎn)換成一些相互關(guān)聯(lián)的單階段問題，再對(duì)這些單階段問題逐個(gè)解決。此方法可以較好地解決離散性問題，其整體思路可概括為在把原問題分解成許多子問題的基礎(chǔ)上，通過每個(gè)子問題的求解最終得出原問題的解。

在所有背包問題的求解算法中，動(dòng)態(tài)規(guī)劃算法被公認(rèn)為是一種經(jīng)典算法，該算法具有便于實(shí)現(xiàn)及思路簡(jiǎn)單的優(yōu)點(diǎn)，但也有不足之處，如果背包問題的數(shù)量較多、規(guī)模較大時(shí)此方法就有很大的局限，維數(shù)過高，復(fù)雜度大大增加，存在維數(shù)障礙，不易實(shí)現(xiàn)。

2.2.2 回溯法

回溯法中采用了深度優(yōu)先的策略，在整個(gè)解空間樹中，根結(jié)點(diǎn)作為始發(fā)點(diǎn)，從這開始搜索整個(gè)解空間樹，結(jié)束時(shí)必須使根結(jié)點(diǎn)的每個(gè)子樹都被搜索完成。在求解0－1背包問題時(shí)，回溯法一定程度上可以得到最優(yōu)解，但當(dāng)問題的數(shù)量較多時(shí)實(shí)現(xiàn)起來會(huì)比較困難。

可見，當(dāng)背包問題的規(guī)模較小時(shí)，精確算法具有較強(qiáng)的實(shí)用性，但當(dāng)背包問題的規(guī)模不斷增大時(shí)，其計(jì)算復(fù)雜，往往得不到最優(yōu)解。

2.3 各種算法的分析與比較

通過上面的研究可知，各算法都有優(yōu)、缺點(diǎn)：①貪婪法速度較快，但不足之處是不一定能獲得最優(yōu)解；②遺傳算法能夠獲得近似最優(yōu)解，但可能會(huì)產(chǎn)生早熟的情況；③蟻群算法能夠獲得近似最優(yōu)解，但問題的規(guī)模較大時(shí)，收斂速度不理想；④動(dòng)態(tài)規(guī)劃法能夠獲得最優(yōu)解，但求解過程速度較慢，并且如果背包問題的數(shù)量較多時(shí)不宜實(shí)現(xiàn)；⑤回溯法能夠獲得最優(yōu)解，但時(shí)間的復(fù)雜度比較高，背包問題的規(guī)模較大時(shí)實(shí)現(xiàn)比較困難。

因此，上述各種算法的不足之處可以概括為兩種：即最優(yōu)解容易陷入局部最優(yōu)；不能在較短的時(shí)間內(nèi)求出全局最優(yōu)解。

3 解決背包問題算法的發(fā)展方向

關(guān)于背包問題算法的發(fā)展過程，從最早解決背包問題的精確算法，到之后又產(chǎn)生的近似算法，以及一些混合算法，這些方法都卓有成效，但依然有很多不足。未來背包問題算法的發(fā)展方向之一是將知識(shí)發(fā)現(xiàn)算法引入到傳統(tǒng)的算法當(dāng)中，用知識(shí)發(fā)現(xiàn)算法挖掘背包問題中的主要信息。

在知識(shí)發(fā)現(xiàn)算法中，粗糙集理論常用來解決一些不精確的問題，適用于知識(shí)的分類及獲取，同時(shí)可以利用粗糙集理論的知識(shí)化簡(jiǎn)能力對(duì)知識(shí)系統(tǒng)進(jìn)行化簡(jiǎn)，減少屬性及屬性值，降低屬性項(xiàng)目復(fù)雜的計(jì)算程度。

用粗糙集理論來解決0－1背包問題的可能性是存在的，可以使用粗糙集理論發(fā)現(xiàn)0－1背包問題中的主要物件，在此基礎(chǔ)上再利用遺傳算法對(duì)它進(jìn)行迭代運(yùn)算。遺傳算法在解決0－1背包問題時(shí)會(huì)產(chǎn)生大量數(shù)據(jù)，使用粗糙集理論對(duì)數(shù)據(jù)進(jìn)行化簡(jiǎn)、篩選和分析，這樣可以降低數(shù)據(jù)的復(fù)雜程度和維數(shù)，使用提煉及概括后的數(shù)據(jù)會(huì)較容易發(fā)現(xiàn)遺傳算法中的重要基因位，可以避免遺傳算法陷入局部最優(yōu)解，并在一定程度上改善遺傳算法的搜索效率。

本文提出將知識(shí)發(fā)現(xiàn)算法和遺傳算法相結(jié)合，使用粗糙集理論的屬性化簡(jiǎn)能力對(duì)遺傳算法進(jìn)化信息數(shù)據(jù)表進(jìn)行約簡(jiǎn)，進(jìn)而可以更有效地解決0－1背包問題。

［1］ 馬慧民，葉春明，張爽.二進(jìn)制改進(jìn)粒子群算法在背包問題中的應(yīng)用［J］.上海理工大學(xué)學(xué)報(bào)，2006，28（1）：31－34.

［2］ 劉華鎣，林玉娥，劉金月.基于蟻群算法求解0／1背包問題［J］.大慶石油學(xué)院學(xué)報(bào)，2005，29（3）：59－63.

［3］ 蔡鴻英，郝志峰，王志剛，等.解0－1背包問題的二進(jìn)制差異演化算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（7）：1716－1721.

［4］ 馬慧民，葉春明，張爽，等.背包問題的知識(shí)進(jìn)化算法［J］.計(jì)算機(jī)工程，2009，35（6）：208－212.

［5］ Silvano Martello，David Pisinger，Paolo Toth.New trends in exact algorithms for the 0－1 knapsack problem［J］.European Journal of Operational Research，2000，123：325－332.

［6］ 劉茜，馬杰良.對(duì)求解0－1背包問題的混合遺傳算法的改進(jìn)［J］.重慶科技學(xué)院學(xué)報(bào)，2006，8（4）：84－87.

［7］ 王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2006.

［8］ 王樂.對(duì)解決背包問題的遺傳禁忌搜索算法的研究［D］.鄭州：鄭州大學(xué)，2006：29－35.

［9］ 史亮，董槐林，王備戰(zhàn)，等.求解大規(guī)模0－1背包問題的主動(dòng)進(jìn)化遺傳算法［J］.計(jì)算機(jī)工程，2007，33（13）：31－33.

［10］ 馬良，王龍德.背包問題的螞蟻優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2001，21（8）：4－5.

［11］ 趙朝卿，胡小兵.一種新的求解0－1背包問題的混合算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44（18）：61－63.

［12］ 潘夏福，倪子偉.基于交換策略的蟻群算法求解多維0－1背包問題［J］.計(jì)算機(jī)與現(xiàn)代化，2008（3）：83－85.

［13］ 秦玲，白云.解0－1背包問題的蟻群算法［J］.計(jì)算機(jī)工程，2006，32（6）：212－214.