變尺度背包問題研究

喬世成++姜靜清

摘 要：在使用傳統的算法來對背包問題進行解決時，有收斂問題和精度不高問題的情況出現，所以本文提出了一種使用粗尺度與細尺度相結合的變尺度方式來對背包問題進行解決的方案，從而提高算法的搜索性能。

關鍵詞：背包問題 變尺度 算法 收斂

一、0-1 背包問題

它可以作如下闡述：假定有一個背包，還有 種物品，這些物品都是有相應的價值和重量的，那么，此時在不超過背包重量極限的情況下，達到價值的最大值。它所對應的數學模型是：

（1）

（2）

二、變尺度背包問題算法

本文提出的便尺度背包問題涉及到兩種變異算子，一種是粗尺度變異算子，當然，它的很多的性能都是由震蕩周期來決定的，周期不同，它的搜索的性能是不同的，當然，這里指的是大范圍的搜索能力，通過粗尺度變異算子可以在進行全局的搜索過程中有較好的性能，使搜索的廣度增大。另一種是細尺度變異算子，它是針對于小范圍的搜索，并且隨著搜索的進行，它的值也是在變動的，越往下執行它的精確度越高，提高其收斂的性能，這樣可以搜索的精度得到提高，具體說明如下：

在進行算法的進化開始時，系統里面的最優粒子和全局最優解的距離是無從得知的，有這樣的情況出現，即兩者之間的距離是無規律的，距離大小是隨機變動，所以，就得使用粗尺度變異算子來完成大面積的搜索功能，在具體使用的過程中，使用周期性的震蕩函數來計算出變異算子，通過這樣的方式來完成粒子的多變性，當然所選擇的函數可以根據實際情況而定：

假定，粗尺度變異算子個數為 ，其初始化的結果為：

（3）

當然，具體計算時，它的選取是隨機的，在實際的迭代過程中，其會使用一下的方式來進行變動：

（4）

參數說明：

——空間寬度，本文所選擇空間寬度B=8；

——當前迭代次數；

——可以決定震蕩頻率。

所以，通過使用上述的算法進行計算完畢后，已經把全局最優解控制在一定的范圍了，所以在這種情況下，就要使用細尺度變異算子來實現最優解的精確搜索和確定，在本文具體實現的過程中使用遞減的指數函數來實現細尺度變異算子的篩選，從而使其搜索的能力更強。當然，在具體實現時，其速度也是可以根據實際情況來把控的：

假定，粗尺度變異算子個數為 ，其初始化的結果為：

（5）

（6）

參數說明：

——可以實現控制變異算子速度調節，可以實現精度的變化；

——當前迭代次數；

——在y的范圍內進行選擇。

在具體計算的過程中，假設經過了 次迭代過程，在經過計算后，此時刻的最優解的速度定義為 ，當然 是在 之中進行選擇的，那么，就可以對速度進行變尺度了，如果要是保證速度的多變性，從而使搜索更有效，如果 ，如果速度增加，則將其減小，如果 減小，則將其增大，其變化多少由高斯標準差來決定。

本文的便尺度算法可以實現速度取值空間的覆蓋，其實現原理類似游標卡尺的工作原理，在這里，粗尺度變異算子相當于主尺，可以實現大概的長度的測量，而細尺度變異算子相當于游尺，可以進一步實現長度的精確測量。使用變尺度算法中的粗尺度，就可以迅速的逃逸出局部極小值，從而使定位最優解區域的能力更優；使用變尺度算法中的細尺度，可以對一個區間范圍內的數據進行精確的搜索，從而找到最優解。

三、變尺度背包問題解決方案

在解決背包問題時，一個很關鍵的步驟是選擇初始群體，它的選擇能夠使最終的結果更加明顯，那么選擇怎樣的初始群體才算是一個好的初始群體，首先，保證分布性良好，能夠正確的反映出空間覆蓋情況，這樣做的目的是避免所使用的算法計算的局限性太強；其次，群體里面的個體的質量良好，從而在具體計算過程中，能夠使算法計算過程有效，從而減小盲目搜索的概率。所以，在本文初始化粒子位置的過程中，把各個物品先求解價值重量比值，然后按照此值進行相關排序操作，此時就是初始位置，其他粒子則不進行相應計算，而是隨機產生。其部分實現過程描述如下：1、選擇參數，確定粒子位置；2、選擇全局最優粒子；3、計算粗尺度變異算子和細尺度變異算子；4、根據算法對粒子狀態進行相應更新操作；5、根據上述操作確定最優解。

四、結論

本文提出了一種使用粗尺度與細尺度相結合的變尺度方式來對背包問題進行解決的方案，從而提高算法的搜索性能，一是因為變尺度使得在計算量減小的情況下使得粒子的多樣性增加，另外，使用貪心測量提高了收斂速度。為了更好闡明本文的變尺度算法，說明其用于解決背包問題的優勢，本文對其進行了實驗驗證，并與一些經典算法進行了比較，如更貪心粒子群算法、病毒協同進化粒子群算法、模擬退火思想改進的粒子群算法等進行了相關的比較和分析。綜合數據分析，本文設計的算法更加優異。

參考文獻：

[1]張曉琴，黃玉清.基于禁忌搜索的啟發式求解背包問題算法[J].成都：電子科技大學學報，2005， 3（34）： 359-362

[2]嚴太山.用基于貪婪算法的混合遺傳算法求解0/1背包問題[J].岳陽：現代計算機，2007， 26（5）： 247-249

[3]賀毅朝，劉沖起，張翠軍，等.求解背包問題的貪心遺傳算法及其應用[J].計算機工程與設計，2007，28（11）：2655-2657

[4]宋海生等.求解多限制 0-1背包問題的混合遺傳算法[D].計算機工程 2009， 35（13） 4-7

[5]秦玲等.解0-1 背包問題的蟻群算法[J]. 計算機工程，2006， 3（26）： 212-214

[6]杜海峰等. 解0-1 背包問題的人工免疫抗體修正克隆算法[J]. 控制理論與應用，2005， 3（22）： 436-439

[7]陶新民等.變尺度變異離散粒子群算法求解背包問題[J]系統仿真學報，2013， 25（1）：12-17

作者簡介：

喬世成（1984.09-）男，漢族，內蒙古通遼市庫倫旗人，講師，工學碩士，研究方向：計算機網絡；姜靜清（1968.05-）女，漢族，內蒙古通遼市人，教授，工學博士，碩士研究生導師，研究生方向：數據挖掘、機器學習。

基金項目：

內蒙古民族大學科學研究基金資助項目（項目編號：NMDYB15081）endprint