王 雯，武 燕

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

0 引言

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

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

1 0－1背包問題［5］

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

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

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

2.1 近似算法

2.1.1 貪婪法

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

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

2.1.2 遺傳算法

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

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

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

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

2.1.3 蟻群算法

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

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

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

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

2.2 精確算法

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

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

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

2.2.2 回溯法

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

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

2.3 各種算法的分析與比較

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

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

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

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

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

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

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

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

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

［3］ 蔡鴻英，郝志峰，王志剛，等.解0－1背包問題的二進制差異演化算法［J］.計算機工程與設計，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］.重慶科技學院學報，2006，8（4）：84－87.

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

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

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

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

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

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

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