貪心核加速動態規劃算法精確求解適用范圍

王茂萍 潘大志 馮世強

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

關鍵詞：折扣{0-1}背包問題;貪心核加速動態規劃算法;動態規劃;價值密度;貪心策略

DOI：10. 11907/rjdk. 192600 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：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）是基于經典{0-1}背包問題（{0-1} Knapsack Problem， {0-1}KP）提出的一種拓展形式，也是典型的組合優化問題[1-2]。在實際生活中，某一商場有大量商品A和商品B，為避免出現商品滯銷，商場推出商業打折活動，將商品A和商品B以一定折扣系數捆綁在一起進行銷售，由其刻畫的數學模型便是D{0-1}KP，其折扣捆綁銷售的特點可實現商業價值最大化，因此該模型在生活中得到了廣泛應用[3]。

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

1 D{0-1}KP定義及數學模型

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

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

2.3 GCADP求解D{0-1}KP

GCADP首先通過模糊核區間（Fuzzy Core Interval， FCI）算法確定模糊核區間的上界和下界，再處理模糊核區間內的數據，使其數據所在項集均不被選中，最后對模糊核區間內的物品運用動態規劃算法進行求解，從而得到最終解。

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

3 IDKP背包容量

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

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

由表1可知，當更改背包容量[C]后，僅有IDKP1均達到精確解，IDKP2～IDKP10隨著折扣系數的增大，誤差也隨之增大，此時GCADP對ID KP不再達到精確解。說明IDKP的原始數據特性滿足GCADP精確求解適用范圍的部分，當背包容量[C]擴大時，不再精確求解。因此，考慮IDKP的參數特性，得到GCADP的精確求解適用范圍。

4 IDKP參數設置

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

4.1 IDKP參數特性

基于參考文獻[8]中4類D{0-1}KP實例的參數設置，給出IDKP實例的參數設置：[p3i∈R2，1000，][p3i+1∈][R2，1000，][p3i

因此，當實例參數設置均滿足[e3i

5 四類D{0-1}KP實例計算與結果分析

5.1 四類實例

通過以上證明發現，[e3i

5.2 求解結果與對比

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

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

6 結語

本文通過分析IDKP這類實例的通用參數設置，發現當第[i]個項集的價值系數滿足[99100p3i+1

參考文獻：

[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] 馮艷紅，楊娟，賀毅朝，等. 差分進化帝王蝶優化算法求解折扣{0-1}背包問題[J]. 電子學報，2018，46（6）：1343-1350.

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

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

[9] 史文旭，楊洋，鮑勝利. 貪心核加速動態規劃算法求解折扣{0-1}背包問題[J]. 計算機應用，2019（7）：1912-1917.

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

[11] 楊洋，潘大志，賀毅朝. 改進修復策略遺傳算法求解折扣{0-1}背包問題[J]. ?計算機工程與應用， 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]. 西華師范大學學報（自然科學版），2018，39（2）：165-172.

[14] 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.

[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.

（責任編輯：黃 健）