楊 洋，潘大志，賀毅朝

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

0 引言

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

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

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

定義1：記D{0-1}KP的規(guī)模為項(xiàng)的個(gè)數(shù)3n，則規(guī)模為3n的D{0-1}KP實(shí)例由價(jià)值系數(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)表示項(xiàng)j是否被裝入背包中。顯然，任意的0-1向量X=[x0,x1,…,x3n-1]∈{0,1}3n僅僅表示D{0-1}KP的一個(gè)潛在解，只有當(dāng)它同時(shí)滿足了約束條件(2)和(3)時(shí)才是一個(gè)可行解[3]。

2 核算法

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

首先，對(duì)任意{0-1}KP的“精準(zhǔn)核”C可以表述為：

(5)

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

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

算法1 Core

輸入：價(jià)值密度排序后價(jià)值向量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)是一種借鑒“適者生存”這一理念的演化算法，通過(guò)模擬生物種群增殖過(guò)程中的遺傳變異過(guò)程，進(jìn)行問(wèn)題求解，在生產(chǎn)調(diào)度、圖像處理等領(lǐng)域[12]應(yīng)用廣泛。對(duì)于傳統(tǒng)遺傳算法中三類算子具體內(nèi)容可參考文獻(xiàn)[9,13]，對(duì)于利用EGA求解D{0-1}KP相關(guān)內(nèi)容，具體可參考文獻(xiàn)[4]，本文限于篇幅，不再贅述。

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

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

算法2 CEGA.

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

輸出：近似最優(yōu)解B(t)及近似背包價(jià)值量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)))；

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

4 實(shí)例計(jì)算與比較

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

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

4.1 計(jì)算結(jié)果

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

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

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

4.2 計(jì)算收斂速度比較

運(yùn)用核算法，能夠加速算法的收斂，而FirEGA算法容易存在收斂緩慢的問(wèn)題，因而在FirEGA基礎(chǔ)上改進(jìn)得到的CEGA算法在收斂速度上，應(yīng)優(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實(shí)例UDKP1-10的結(jié)果比較

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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}背包問(wèn)題的研究[J].計(jì)算機(jī)學(xué)報(bào)，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] 陳國(guó)良,王熙法,莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[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] 周 明,孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(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.