王 雯，武 燕

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

0 引言

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

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

1 0－1背包問題［5］

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

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

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

2.1 近似算法

2.1.1 貪婪法

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

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

2.1.2 遺傳算法

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

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

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

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

2.1.3 蟻群算法

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

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

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

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

2.2 精確算法

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

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

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

2.2.2 回溯法

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

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

2.3 各種算法的分析與比較

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

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

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

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

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

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

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

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

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

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

［4］ 馬慧民，葉春明，張爽，等.背包問題的知識進化算法［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］ 劉茜，馬杰良.對求解0－1背包問題的混合遺傳算法的改進［J］.重慶科技學(xué)院學(xué)報，2006，8（4）：84－87.

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

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

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

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

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

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

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