核加速遺傳算法求解折扣{0-1}背包問題

楊 洋，潘大志，賀毅朝

(1.西華師范大學 數(shù)學與信息學院，四川 南充 637009；2.河北地質(zhì)大學 信息工程學院，河北 石家莊 050031)

0 引言

折扣{0-1}背包問題(D{0-1}KP)是經(jīng)典0-1背包問題的一個擴展形式[1-5]，其思想源于商業(yè)領(lǐng)域的打折，在項目決策、投資和預算控制等方面具有廣闊的應用背景[3]。Guder和Guldan首先提出了單目標及多目標的D{0-1}KP，并實現(xiàn)問題求解[1-2]。后面大部分文獻針對D{0-1}KP都是在精確算法或進化算法的基礎(chǔ)，提出改進算法實現(xiàn)求解[3-5,10-11]。

文獻[3]和文獻[4]在利用遺傳算法求解的過程中，交叉和變算子讓本來已經(jīng)選擇且應該選擇的物品被舍棄，使得D{0-1}KP較難得到最優(yōu)解。而對于核算法，尤其是對于大規(guī)模實例時，求解速度比較緩慢。針對遺傳算法和核算法單獨處理D{0-1}KP時均較難快速取得較優(yōu)解甚至最優(yōu)解的問題，本文在現(xiàn)有GROA修復算法的基礎(chǔ)上[4]，將核算法[3]融合到遺傳算法，得到核加速遺傳算法(CEGA)。該算法通過計算得到精準核，將遺傳算法的交叉和變異操作限定在核內(nèi)進行操作，再用GROA對編碼進行修復，以達到加速問題求解、提高求解質(zhì)量的目的。

1 D{0-1}KP定義及數(shù)學模型

定義1：記D{0-1}KP的規(guī)模為項的個數(shù)3n，則規(guī)模為3n的D{0-1}KP實例由價值系數(shù)P={{p3i,p3i+1,p3i+2}|0in-1}、重量系數(shù)W={{w3i,w3i+1,w3i+2}|0in-1}和背包載重C構(gòu)成，其中p3i+2=p3i+p3i+1，w3i+2

(1)

s.t.x3i+x3i+1+x3i+21,i=0,1,…，n-1

(2)

(3)

x3i,x3i+1,x3i+2∈{0,1}，i=0,1,…,n-1

(4)

其中，二元變量xj(0j3n-1)表示項j是否被裝入背包中。顯然，任意的0-1向量X=[x0,x1,…,x3n-1]∈{0,1}3n僅僅表示D{0-1}KP的一個潛在解，只有當它同時滿足了約束條件(2)和(3)時才是一個可行解[3]。

2 核算法

核算法求解背包問題，是Balas和Zemel[14]為縮小求解問題規(guī)模于1980年提出的一種方法。該方法首先找出問題所有物品集的一個子集，作為問題對映的“核”，然后對核內(nèi)物品進行取舍的搜索，達到加速求解問題的效果。實踐證明，利用核算法能夠有效加速小規(guī)模問題的求解[15]。但理論上求解背包問題的核對應的時間復雜度與求解該問題本身的時間復雜度相當，而D{0-1}KP是一個NP-hard問題，因此，對于大規(guī)模D{0-1}KP，利用核算法求解其時間復雜度也很大，問題仍然較難快速求解。

首先，對任意{0-1}KP的“精準核”C可以表述為：

(5)

其中布爾集合X={x1,x2,…,xn}表示為該背包問題的最優(yōu)解，xi=0表示第i個物品不選取，xi=1表示第i個物品選??；N是將物品按照價值密度進行排序后的集合。

對于D{0-1}KP，其核的求解與(5)式相同。但因D{0-1}KP每個項集中僅能選取一個項，則對于任意D{0-1}KP的布爾項集集合X，需滿足條件(2)和(3)，求解核的算法描述如算法1。

算法1 Core

輸入：價值密度排序后價值向量P和質(zhì)量向量W,背包容量C，參數(shù)N

輸出：C=[s,t]

1.FORi←1TO3n

2.IFk+wSi

3.k←k+wSi；

4.X(i)←1；

5.END IF

6.END FOR

7.FORi←1TO3n

8.IFX(i)～=0

9.s←i；

10.BREAK；

11.END IF

12.END FOR

13.FORi←1TO3nDO

14.IFX(3n+1-i)=0

15.t←i；

16.BREAK；

17.END IF

18.END FOR

3 核加速遺傳算法

遺傳算法[8-11](Genetic Algorithms，GA)是一種借鑒“適者生存”這一理念的演化算法，通過模擬生物種群增殖過程中的遺傳變異過程，進行問題求解，在生產(chǎn)調(diào)度、圖像處理等領(lǐng)域[12]應用廣泛。對于傳統(tǒng)遺傳算法中三類算子具體內(nèi)容可參考文獻[9,13]，對于利用EGA求解D{0-1}KP相關(guān)內(nèi)容，具體可參考文獻[4]，本文限于篇幅，不再贅述。

為方便算法描述，設(shè)“S[0,1,…,3n-1]←Density({pj/wj|pj∈P,wj∈W,0j3n-1})”表示對所有的項(設(shè)有3n個項)按照價值密度即pj/wj(0j3n-1)的比值大小，從大到小進行排序并存入數(shù)組S中。

利用核算法的特點，得到精準核后，主要是將遺傳算法的交叉算子、變異算子和選擇算子的操作范圍限定在精準核進行問題處理，從而減少無效操作并加速算法收斂。這里將融合核算法的遺傳算法記為核加速遺傳算法(CEGA)，其算法步驟如算法2。

算法2 CEGA.

輸入：價值向量P和質(zhì)量向量W,背包容量C，參數(shù)N，遺傳交叉變異算子Pc和Pm，最大迭代次數(shù)MaxIt

輸出：近似最優(yōu)解B(t)及近似背包價值量f(B(t))

1.S[0,1,…,3n-1]←Density({pj/wj|pj∈P,wj∈W,0j3n-1})；

2.Randomly generate populationP(0)={Xi(0)|1iN}；

3.FORi←1TON

4.(Xi(0),f(Xi(0)))←GROA(Xi(0),S)；

5.END FOR

6.DetermineB(0)byf(Xi(0))(1iN)inP(0)；t←0；

7.WHILE(tMaxIt)

8.P1(t)←CRO(Core(P(t)),pc)；

9.P2(t)←MUO(Core(P1(t)),pm)；

10.FORi←1TONDO

11.(Zi(t),f(Zi(t)))←GROA(Zi(t),S)；

12.END FOR

13.DetermineB(t+1)byf(Zi(t))inP2(t)∪{B(t)}；

14.P(t+1)←SEO(P2(t))；

15.t←t+1；

16.END WHILE

17.RETURN(B(t),f(B(t)))；

與文獻[4]中的FirEGA算法比較，CEGA算法在CRO算子和MUO算子過程中引入Core算法，交叉變異的算子只在核內(nèi)進行，達到提升交叉變異效率。同時，易得CEGA的時間復雜度是O(n3)。

4 實例計算與比較

沿用文獻[4]中所提出的四類D{0-1}KP實例數(shù)據(jù)，每類數(shù)據(jù)均包含規(guī)模依次等量遞增的數(shù)據(jù)10種，關(guān)于數(shù)據(jù)的具體闡述可參考文獻[4]。本文所提出新算法CEGA與文獻[4]中FirEGA算法框架基本一致，且相應計算過程并無變化，因而相關(guān)參數(shù)與文獻[4]設(shè)定一致：pc=0.8，pm=0.01，種群規(guī)模為50。

本文使用計算器為聯(lián)想Y470型筆記本，CPU配置為Intel(R) Core(TM) i3-2350M CPU@2.3GHz。采用MATLAB 7.0進行問題進行建模求解，并將結(jié)果繪制成圖，利用SPSS 21.0對所得結(jié)果進行檢驗。

4.1 計算結(jié)果

CEGA算法對D{0-1}KP四類實例求解的結(jié)果見表1—表4。其中Opt為通過動態(tài)規(guī)劃法(記為DPDKP)求解得到的實際最優(yōu)解值，也即問題的理想最優(yōu)解。Best、Worst和Mean分別為FirEGA和CEGA兩類算法在30次獨立計算中所得最優(yōu)解、最差解、及結(jié)果的數(shù)學期望。Time1、Time2則分別表示FirEGA和CEGA兩類算法在30次獨立計算中算法收斂的平均迭代次數(shù)(單位：次)。為體現(xiàn)兩種算法在求解精度方面的差異，這里通過計算近似比差異率來作為分析數(shù)據(jù)結(jié)果主要參數(shù)。其中，Best/Opt-1、Mean/Opt-1、Worst/Opt-1為最優(yōu)解近似差異率、期望值近似差率和最差解近似差異率。

由表1—表4中的數(shù)據(jù)可知：CEGA求解UDKP實例的最優(yōu)值近似比差異率在0.97%至2.07%范圍內(nèi)，平均值和最差值的近似比差異率在1.31%至3.01%范圍內(nèi)，而FirEGA求解結(jié)果對應的差異率范圍為7.04%～12.61%、8.09%～13.58%。表明CEGA與FirEGA在求解UDKP實例中的結(jié)果差異明顯，CEGA得到問題解得質(zhì)量有顯著性提升。CEGA算法求解WDKP實例對應的近似比差異率除WDKP10稍微差一點之外，其他9種實例計算結(jié)果均好于FirEGA。CEGA算法求解SDKP實例的最優(yōu)值近似比差異率在0.47%至1.33%范圍內(nèi)，平均值和最差值的近似比差異率在0.68%至1.61%范圍內(nèi)，均優(yōu)于FirEGA求解結(jié)果。CEGA算法求解IDKP實例的最優(yōu)值近似比差異率在0.00%至0.15%范圍內(nèi)，平均值和最差值的近似比差異率在0.04%至0.78%范圍內(nèi)，與FirEGA算法相比，解得質(zhì)量得到較大改善。

為更好的體現(xiàn)CEGA算法和FirEGA算法求解四類實例的效果，通過圖1—圖8分別給出它們兩種算法求解四類實例的1-Best/Opt和Mean/Opt-1曲線對比圖。

4.2 計算收斂速度比較

運用核算法，能夠加速算法的收斂，而FirEGA算法容易存在收斂緩慢的問題，因而在FirEGA基礎(chǔ)上改進得到的CEGA算法在收斂速度上，應優(yōu)于FirEGA。由表1—表4可知，CEGA算法收斂速度明顯優(yōu)于FirEGA算法。為更加直觀展示各算法收斂速度，將各自收斂代數(shù)數(shù)據(jù)Time1和Time2生成圖9—圖12。從圖中不難發(fā)現(xiàn)，在收斂速度上CEGA算法比FirEGA有明顯的提升。

表1 FirEGA和CEGA求解D{0-1}KP實例UDKP1-10的結(jié)果比較

表2 FirEGA和CEGA求解D{0-1}KP實例WDKP1-10的結(jié)果比較

表3 FirEGA和CEGA求解D{0-1}KP實例SDKP1-10的結(jié)果比較

表4 FirEGA和CEGA求解D{0-1}KP實例IDKP1-10的結(jié)果比較

5 結(jié)語

為改善FirEGA算法求解D{0-1}KP問題易陷于局部最優(yōu)解、收斂緩慢的問題，將核加速算法與遺傳算法進行融合得到求解D{0-1}KP問題的核加速遺傳算法CEGA。為驗證算法的有效性，將CEGA用于求解文獻[4]中給出的四類D{0-1}KP實例，由計算結(jié)果可知，無論是在解的質(zhì)量還是收斂速度上，CEGA均優(yōu)于FirEGA，表明CEGA算法在求解D{0-1}KP問題上是有效、可行的。

參考文獻：

[1] GUDER.Discounted Knapsack Problems for pairs of items[D].Nuremberg：University of Erlangen-Nurnberg,2005.

[2] GULDAN B.Heuristic and exact algorithms for discounted knapsack prob1ems[D].Nuremberg: University of Erlangen-Nuremberg,2007.

[3] RONG A Y.FIGUEIRA J R.KLAMROTH K.Dynamic programming based algorithms for the discounted {0-1} knapsack problem[J].Applied Mathematics and Computation.2012,218(12):6921-6933.

[4] 賀毅朝，王熙照，李文斌，等.基于遺傳算法求解折扣{0-1}背包問題的研究[J].計算機學報，2016,39(12):2614-2630.

[5] HE Y C,WANG X Z,HE Y L,et al.Exact and approximate algorithms for discounted {0-1} knapsack problem[J].Information Sciences,2016,369(10):634-647.

[6] GOLDBERG D E.Genetic Algorithms in Search,Optimization and Machine Learning[M].Boston:Addison-Welsley,1989.

[7] JONG K A D.Analysis of the behavior of a class of genetic adaptive systems[D].Ann Arbor:Wiuersity of Michigan,1975.

[8] 陳國良,王熙法,莊鎮(zhèn)泉，等.遺傳算法及其應用[M].北京：人民郵電出版社,2003.

[9] RUDOLPH G,JONG K D.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks,1994,5(1):96-101.

[10] JONG K D,Learning with genetic algorithms:An overview[J].Machine Learning,1988,3(3):121-138.

[11] 周 明,孫樹棟.遺傳算法原理及應用[M].北京：國防工業(yè)出版社,1999.

[12] SCHMITT I M.Theory of genetic algorithms[J].Theoretical Computer Science,2001,259(1/2):1-61.

[13] BALAS E,ZEMEL E.An Algorithm for Large Zero-One Knapsack Problems[J].Operations Research,1980,28(5):1130-1154.

[14] PISINGER D.Core problems in Knapsack Algorithms[J].Operations Research,1999,47(4):570-575.

[15] PISINGER D.An expanding-core algorithm for the exact 0-1 knapsack problem[J].European Journal of Operational Research,1995,87(1):175-187.