貪心核加速動(dòng)態(tài)規(guī)劃算法精確求解適用范圍

王茂萍 潘大志 馮世強(qiáng)

摘 要：針對(duì)背包容量折扣系數(shù)在0.8～0.9時(shí)，貪心核加速動(dòng)態(tài)規(guī)劃算法（GCADP）無法求得逆向強(qiáng)相關(guān)折扣{0-1}背包問題實(shí)例（IDKP）精確解的問題，為求得D{0-1}KP實(shí)例的精確解，在對(duì)IDKP實(shí)例參數(shù)進(jìn)行分析的基礎(chǔ)上，給出GCADP算法能精確求解D{0-1}KP實(shí)例的限定條件：任意項(xiàng)集的價(jià)值系數(shù)滿足價(jià)值最小項(xiàng)大于價(jià)值次大項(xiàng)的0.99倍。將該條件應(yīng)用到4類D{0-1}KP實(shí)例的參數(shù)設(shè)置中，生成新的大規(guī)模D{0-1}KP實(shí)例。對(duì)4類D{0-1}KP實(shí)例運(yùn)用GCADP和動(dòng)態(tài)規(guī)劃（DP）進(jìn)行計(jì)算，計(jì)算結(jié)果表明，新的4類D{0-1}KP實(shí)例均得到精確解，并且GCADP隨著數(shù)據(jù)規(guī)模的變大，求解時(shí)長增長平緩。

關(guān)鍵詞：折扣{0-1}背包問題;貪心核加速動(dòng)態(tài)規(guī)劃算法;動(dòng)態(tài)規(guī)劃;價(jià)值密度;貪心策略

DOI：10. 11907/rjdk. 192600 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）008-0054-06

Abstract：The greedy core acceleration dynamic programming algorithm（GCADP） cant find the exact solution of the instance when solving the inverse strongly correlated instances of D{0-1}KP（IDKP） with the knapsack capacity discounted coefficient of 0.8-0.9. In order to obtain the exact solution of the D{0-1}KP instance， based on the analysis of the IDKP instance parameters， the GCADP algorithm can accurately solve the D{0-1}KP instance with limited condition that the value coefficient of any item set satisfies the smallest value item and is greater than 0.99 times the second largest value item. This condition is applied to the parameter settings of the four types of D{0-1}KP instances to create a new large scale four-class D{0-1}KP instance. The four types of D{0-1}KP instances use GCADP and dynamic programming（DP） calculations. Instances calculation results show that the new four types of D{0-1}KP instances are all accurately solved， and the data size increases， the solve time of GCADP grows slowly.

Key Words：discount {0-1} knapsack problem; greedy core acceleration dynamic programming algorithm; dynamic programming; value density; greedy strategy

0 引言

折扣{0-1}背包問題（Discounted{0-1} Knapsack Problem， D{0-1}KP）是基于經(jīng)典{0-1}背包問題（{0-1} Knapsack Problem， {0-1}KP）提出的一種拓展形式，也是典型的組合優(yōu)化問題[1-2]。在實(shí)際生活中，某一商場有大量商品A和商品B，為避免出現(xiàn)商品滯銷，商場推出商業(yè)打折活動(dòng)，將商品A和商品B以一定折扣系數(shù)捆綁在一起進(jìn)行銷售，由其刻畫的數(shù)學(xué)模型便是D{0-1}KP，其折扣捆綁銷售的特點(diǎn)可實(shí)現(xiàn)商業(yè)價(jià)值最大化，因此該模型在生活中得到了廣泛應(yīng)用[3]。

多個(gè)目標(biāo)的D{0-1}KP問題是由Guldan[3-5]提出的，并給出了它的啟發(fā)式和確定性算法，通過動(dòng)態(tài)規(guī)劃達(dá)到求解目的。Rong等將傳統(tǒng)背包問題中的核問題與D{0-1}KP相結(jié)合，求解基于核問題的動(dòng)態(tài)規(guī)劃改進(jìn)方法，但確定性算法的求解時(shí)間較長，缺乏實(shí)用性。目前，求解D{0-1}KP的進(jìn)化算法已有很多可參考的成果，如馮艷紅等[6]運(yùn)用差分進(jìn)化帝王蝶優(yōu)化算法求解D{0-1}KP，均得到近似解，且近似比為1;劉雪靜等[7]提出自適應(yīng)細(xì)菌覓食算法求解D{0-1}KP，均獲得最優(yōu)解;賀毅朝等[8]利用遺傳算法求解D{0-1}KP的第二數(shù)學(xué)模型和第三數(shù)學(xué)模型;楊洋等[9]在動(dòng)態(tài)規(guī)劃思想基礎(chǔ)上，結(jié)合核算法和新型貪心修復(fù)優(yōu)化算法（New Greedy Repaired Optimization Algorithm， NGROA），通過縮小D{0-1}KP規(guī)模實(shí)現(xiàn)加速求解問題的目的，并提出貪心核加速動(dòng)態(tài)規(guī)劃算法（Greedy Core Acceleration Dynamic Programming Algorithm， GCADP）。但從文獻(xiàn)[9]的實(shí)例計(jì)算與結(jié)果對(duì)比中發(fā)現(xiàn)，僅有逆向強(qiáng)相關(guān)實(shí)例（Inverse Strongly Correlated Instances of D{0-1}KP， IDKP）通過GCADP求解可得到精確解，其它3類實(shí)例均有誤差率。因此，本文探討如何確定GCADP的精確求解適用范圍。

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

定義1[10-16]：給定[n]個(gè)均含有3個(gè)項(xiàng)（或物品）的項(xiàng)集，項(xiàng)集[i]（[0in-1]）中含有的3個(gè)項(xiàng)分別記為[3i]、[3i+1]、[3i+2]，其中前兩項(xiàng)[3i]、[3i+1]具有的價(jià)值系數(shù)分別為[p3i]和[p3i+1]，重量系數(shù)分別為[w3i]和[w3i+1]。前兩項(xiàng)合并在一起構(gòu)成第3項(xiàng)[3i+2]，其具有的價(jià)值系數(shù)為[p3i+2=p3i+p3i+1]，折扣重量系數(shù)為[w3i+2]，滿足[w3i+2

顯然，運(yùn)用DP求解D{0-1}KP是一個(gè)填充零矩陣[V]的過程，[V]中元素均為當(dāng)前物品組合的最大值，所以該矩陣最后一位元素為該問題的精確解。當(dāng)物品規(guī)模較大時(shí)，利用DP求解D{0-1}KP耗時(shí)較長，因此實(shí)用性較差，可考慮縮小問題規(guī)模，從而達(dá)到快速求解的目的。

2.3 GCADP求解D{0-1}KP

GCADP首先通過模糊核區(qū)間（Fuzzy Core Interval， FCI）算法確定模糊核區(qū)間的上界和下界，再處理模糊核區(qū)間內(nèi)的數(shù)據(jù)，使其數(shù)據(jù)所在項(xiàng)集均不被選中，最后對(duì)模糊核區(qū)間內(nèi)的物品運(yùn)用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解，從而得到最終解。

FCI算法中的貪心策略選擇與傳統(tǒng)方法不同，傳統(tǒng)GROA是選擇價(jià)值密度最大的，而NGROA是選擇價(jià)值最大的。通過核算法的貪心選擇確定模糊核區(qū)間的核中心和核半徑，經(jīng)過數(shù)據(jù)處理后，按價(jià)值密度從大到小進(jìn)行排列，從初始物品到模糊核區(qū)間下界之前的物品均被選中。因此，只需確認(rèn)模糊核區(qū)間內(nèi)的物品選擇情況即可，從而縮小問題規(guī)模，再利用DP對(duì)模糊核區(qū)間內(nèi)的物品進(jìn)行求解，實(shí)現(xiàn)縮短整體時(shí)長的目的。通過實(shí)例計(jì)算結(jié)果進(jìn)行對(duì)比，發(fā)現(xiàn)GCADP對(duì)IDKP實(shí)例能得到精確解，其它3類實(shí)例可得到較好的近似解。

3 IDKP背包容量

傳統(tǒng)實(shí)例背包容量為[C=αi=0n-1w3i+2，] [α]為[0.45，0.75]上的一個(gè)隨機(jī)數(shù)。GCADP對(duì)傳統(tǒng)IDKP均能得到精確解，若將IDKP背包容量中的[α]擴(kuò)大為[0.8，0.95]上的隨機(jī)數(shù)，在GCADP的求解模糊核區(qū)間FCI算法中進(jìn)行貪心求解時(shí)，隨著背包容量的擴(kuò)大，被選中的項(xiàng)集數(shù)目也隨之增多。此時(shí)，未在GCADP精確求解適用范圍內(nèi)的項(xiàng)集被選入背包內(nèi)，因此GACDP不再對(duì)IDKP作精確求解。本文選取折扣系數(shù)[α]分別為0.8、0.85、0.9和0.95，運(yùn)用GCADP和DP對(duì)IDKP的求解結(jié)果與求解時(shí)間如表1所示。

本文使用的工作站為HP Z8 G4（Z3Z16AV-SC001），操作系統(tǒng)為Windows 10 專業(yè)版，硬件配置為Intel（R） Xeon（R） Silver 4114 CPU @ 2.20GHz 2.19GHz，32.00GB ，利用MATLAB18a對(duì)問題進(jìn)行繪圖求解。記DP的結(jié)果為[Opt1]，計(jì)算時(shí)長為[T1];GCADP的結(jié)果為[Opt2]，計(jì)算時(shí)長為[T2]（[T1，T2]單位為秒）。設(shè)置誤差率（Error Rate， ER）計(jì)算方式為：[ER=1-Opt2Opt1]。

由表1可知，當(dāng)更改背包容量[C]后，僅有IDKP1均達(dá)到精確解，IDKP2～I(xiàn)DKP10隨著折扣系數(shù)的增大，誤差也隨之增大，此時(shí)GCADP對(duì)ID KP不再達(dá)到精確解。說明IDKP的原始數(shù)據(jù)特性滿足GCADP精確求解適用范圍的部分，當(dāng)背包容量[C]擴(kuò)大時(shí)，不再精確求解。因此，考慮IDKP的參數(shù)特性，得到GCADP的精確求解適用范圍。

4 IDKP參數(shù)設(shè)置

在文獻(xiàn)[9]中，GCADP僅對(duì)4類D{0-1}KP原始實(shí)例中的IDKP有正確的貪心選擇策略，使其達(dá)到精確解。但通過擴(kuò)大折扣系數(shù)將背包容量擴(kuò)大后，IDKP實(shí)例也達(dá)不到精確解。因此，本節(jié)通過探究IDKP與其它3類實(shí)例參數(shù)設(shè)置之間的差異性，發(fā)現(xiàn)IDKP的參數(shù)特性，從而找到GCADP精確求解的適用范圍。

4.1 IDKP參數(shù)特性

基于參考文獻(xiàn)[8]中4類D{0-1}KP實(shí)例的參數(shù)設(shè)置，給出IDKP實(shí)例的參數(shù)設(shè)置：[p3i∈R2，1000，][p3i+1∈][R2，1000，][p3i

因此，當(dāng)實(shí)例參數(shù)設(shè)置均滿足[e3i

5 四類D{0-1}KP實(shí)例計(jì)算與結(jié)果分析

5.1 四類實(shí)例

通過以上證明發(fā)現(xiàn)，[e3i

5.2 求解結(jié)果與對(duì)比

通過GCADP與DP對(duì)4類實(shí)例進(jìn)行求解，得到表2、表3的結(jié)果，為了更清晰地看出GCADP與DP的求解速率，將表2、表3的時(shí)長繪制為圖1。

從表2、表3中可以看出：在更改參數(shù)設(shè)置后的UDKP等4類實(shí)例計(jì)算中，將背包容量的折扣系數(shù)[α]擴(kuò)大為0.8、0.85、0.9、0.95，GCADP與DP的求解結(jié)果相同。由于電腦運(yùn)行內(nèi)存有限，當(dāng)UDKP5、WDKP5、SDKP5和IDKP5的數(shù)據(jù)規(guī)模與背包容量較大時(shí)，DP不能構(gòu)造出零矩陣，因而不能對(duì)其進(jìn)行動(dòng)態(tài)規(guī)劃求解。因此，在表2、表3中針對(duì)該部分實(shí)例的運(yùn)算結(jié)果用“—”表示，同時(shí)對(duì)該部分實(shí)例采用CPLEX運(yùn)算，其結(jié)果與GCADP的求解結(jié)果一致，說明GCADP對(duì)4類實(shí)例均能實(shí)現(xiàn)精確求解。因此，該限定條件：第[i]個(gè)項(xiàng)集的價(jià)值系數(shù)滿足[99100p3i+1

6 結(jié)語

本文通過分析IDKP這類實(shí)例的通用參數(shù)設(shè)置，發(fā)現(xiàn)當(dāng)?shù)赱i]個(gè)項(xiàng)集的價(jià)值系數(shù)滿足[99100p3i+1

參考文獻(xiàn)：

[1] GUDER J. Discounted knapsack problems for pairs of items [D]. ?Erlangen： Friedrich-Alexander-Universit t Erlangen-Nürnberg，2005.

[2] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Erlangen：Friedrich-Alexander-Universit t Erlangen-Nürnberg， 2007.

[3] BAO L，CAO J，LI J，et al.Boosted near-miss under-sampling on SVM ensembles for concept detection in large-scale imbalanced datasets[J]. Neurocomputing，2016，172：198-206.

[4] LOYOLA-GONZALEZ O，MARTINEZ-TRINIDAD J F，CARRASCO-OCHOA J A，et al.Effect of class imbalance on qualitymeasures for contrast patterns：an experimental study[J]. Information Sciences，2016（374）：179-192.

[5] GONG J，KIM H.RHSBoost：improving classification performance in imbalance data[J]. Computational Statistics &Data Analysis，2017（111）：1-13.

[6] 馮艷紅，楊娟，賀毅朝，等. 差分進(jìn)化帝王蝶優(yōu)化算法求解折扣{0-1}背包問題[J]. 電子學(xué)報(bào)，2018，46（6）：1343-1350.

[7] 劉雪靜，賀毅朝，吳聰聰，等. 基于細(xì)菌覓食算法求解折扣{0-1}背包問題的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2018，54（2）：155-162.

[8] 賀毅朝，王熙照，李文斌，等. ?基于遺傳算法求解折扣{0-1}背包問題的研究[J]. 計(jì)算機(jī)學(xué)報(bào)， 2016， 39（12）： 2614-2630.

[9] 史文旭，楊洋，鮑勝利. 貪心核加速動(dòng)態(tài)規(guī)劃算法求解折扣{0-1}背包問題[J]. 計(jì)算機(jī)應(yīng)用，2019（7）：1912-1917.

[10] 楊洋，潘大志，劉益，等. 折扣{0-1}背包問題的簡化新模型及遺傳算法求解[J]. 計(jì)算機(jī)應(yīng)用， 2019， 39（3）：656-662.

[11] 楊洋，潘大志，賀毅朝. 改進(jìn)修復(fù)策略遺傳算法求解折扣{0-1}背包問題[J]. ?計(jì)算機(jī)工程與應(yīng)用， 2018， 54（21）： 37-42.

[12] FENG Y H，WANG G G，LI W， et al. Multi-strategy monarch butterfly optimization algorithm for discounted {0-1} knapsack problem [J]. ?Neural Computing & Applications， 2018（30）： 3019-3016.

[13] 楊洋，潘大志，賀毅朝. ?核加速遺傳算法求解折扣{0-1}背包問題[J]. 西華師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，39（2）：165-172.

[14] RONG A Y，F(xiàn)IGUEIRA 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.

[15] YICHAO H， XINLU Z， JIANMIN S. Design method of the iterative algorithm based on dynamic programming [J]. ?Mathematics In Practice and understanding， 2016， 46（6）： 173-180.

[16] KELLERER H， PFERSCHY U， PISINGER D. Knapsack problems[M]. ?Springer Berlin Heidelberg， 2004.

[17] BELLMAN R. Dynamic programming[J]. Science，1966，153： 34-37.

[18] MARTELLO S， PISINGER D， TOTH P. Dynamic programming and strong bounds for the 0-1 Knapsack problem[J]. ?Management Science， 1999， 45（3）：414-424.

[19] KATHRIN K，WIECEK M M. Dynamic programming approaches to the multiple criteria knapsack problem[J]. Naval Research Logistics， 2015， 47（1）：57-76.

[20] BALEV S，YANEV N， FREVILLE A， et al. A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem[J]. ?European Journal of Operational Research， 2008， 186（1）： 63-76.

（責(zé)任編輯：黃 ?。?/p>