變尺度背包問題研究

喬世成++姜靜清

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

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

一、0-1 背包問題

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

（1）

（2）

二、變尺度背包問題算法

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

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

假定，粗尺度變異算子個數(shù)為 ，其初始化的結(jié)果為：

（3）

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

（4）

參數(shù)說明：

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

——當前迭代次數(shù)；

——可以決定震蕩頻率。

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

假定，粗尺度變異算子個數(shù)為 ，其初始化的結(jié)果為：

（5）

（6）

參數(shù)說明：

——可以實現(xiàn)控制變異算子速度調(diào)節(jié)，可以實現(xiàn)精度的變化；

——當前迭代次數(shù)；

——在y的范圍內(nèi)進行選擇。

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

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

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

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

四、結(jié)論

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

參考文獻：

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

[2]嚴太山.用基于貪婪算法的混合遺傳算法求解0/1背包問題[J].岳陽：現(xiàn)代計算機，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]系統(tǒng)仿真學報，2013， 25（1）：12-17

作者簡介：

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

基金項目：

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